Re: [igraph] test network topology

[Gabor Csardi]

On Fri, May 09, 2008 at 07:59:34PM +0200, Simone Gabbriellini wrote:
[...]
> 
> I though that there should be a statistical way to say that my network  
> is approximable by a random graph (more than a small world)... but I  
> suppose Gabor is right when he says that the only thing I can say is  
> that the density of my empiric network is approximable by a random  
> distribution...
> 
> have I undestood it correctly, Gabor?

Random distribution? I'm a bit puzzled to be honest. What i've tried to
say is that 
1) usually you want to compare your system to a "random" system. This 
   is to see how "random" your network is, or in fact rather the opposite
   how much ordered it is compared to a random graph.
2) normally this is done via a statistical test, and then you have a p-value,
   the probability that your system "is just random"
3) for graphs we don't really have established statistical tests, not even for 
   individual graph properties.
4) what we usually do is that we choose a random graph model (Gnm or 
configuration
   usually) and then say that the examined structural property is not present 
in 
   the random network, thus it is not the consequence of the density (Gnm) or 
   degree dist. (configuration) of the network.

I give you an example. The forest fire model (forest.fire.game) is known to
generate highly transitive networks. But are these transitive only because 
they have a high density? 

This question can be answered by generating random ER (Gnm) graphs with the 
same number of vertices and edges and measuring their transitivity. 

But is the transitivity only a consequence of the degree distribution of the 
network? 

This question can be answered by generating random graph with the same 
degree sequence and then measuring their transitivity.

Both ways measure whether our network is just random or not. But we can only 
do this by focusing at a given structural property at a time (transitivity 
in the example). Even in this case we don't have the statistical background 
to calculate a p-value, which is a pity.

But there might be good statistical tests for networks, i just don't know
about them, e.g. it might be worth to look at 'cugtest' in the 'sna' package.

G.

[...]

-- 
Csardi Gabor <address@hidden>    UNIL DGM