Re: [igraph] test network topology

[Simone Gabbriellini]

Hi all,

thanks for the discussion... I have done a similar work as Colin,  
using also Small World game...
see what I've found here - very rough plot:

http://www.digitaldust.it/dottorato/mmorpg/testTopology.pdf

here's my simple code:

distanzaRG<-array()
distanzaSW<-array()
transRG<-array()
transSW<-array()
empiricdist<-average.path.length(empirico)
empirictrans<-transitivity(empirico)
for (i in 1:1000){
        sw<-as.directed(watts.strogatz.game(1, 42, 37, 0.05))
        distanzaSW[i]<-average.path.length(sw)
        transSW[i]<-transitivity(sw)
    rg<-erdos.renyi.game(42, 779, type=c("gnm"), directed=TRUE)
        distanzaRG[i]<-average.path.length(rg)
        transRG[i]<-transitivity(rg)
        }

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?

btw, my results:

> summary(distanzaRG)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  1.548   1.548   1.548   1.548   1.548   1.549
> summary(distanzaSW)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
  1.059   1.081   1.087   1.087   1.093   1.115
> summary(transRG)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
 0.6707  0.6931  0.6999  0.6998  0.7059  0.7308
> summary(transSW)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max.
 0.8832  0.9064  0.9125  0.9123  0.9187  0.9401
> average.path.length(empirico)
[1] 1.530488
> transitivity(empirico)
[1] 0.7782077


thanks,
Simone

Il giorno 09/mag/08, alle ore 17:13, Gabor Csardi ha scritto:

> This question cannot really be answered in general i think,
> the answer depends on what you want to show. If you want to
> show that the structure you see is not a consequence of the
> density of the graph, then use an Erdos-Renyi random graph.
> If you want to show that it is not a consequence of the
> degree distribution then use the configuration model (i.e.
> degree.sequence.game type model). If you want to show that
> it is not the consequence of the transitivity, then you
> need random graphs conditioned on transitivity, etc.
>
> On Fri, May 09, 2008 at 04:23:21PM +0200, Tamas Nepusz wrote:
> > > I generated 1000 random graphs with similar characteristics to my
> > > empirical graph.  I then calculated the the transitivity and
> > > shortest path length for each random graph.
> > I think I would have done the same. The random graphs would have had
> > the same degree distribution as my original graph (see the rewiring
> > functionality of igraph or the degree sequence game. the latter one
> > does not prevent multiedges and loops, but the graph can be  
> > simplified
> > afterwards).
>
> Btw. degree.sequence.game is biased, it does not generate all graphs  
> with
> the same probability.
>
> G.
>
> [...]
>
> --
> Csardi Gabor <address@hidden>    UNIL DGM
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> http://lists.nongnu.org/mailman/listinfo/igraph-help