Re: [igraph] Question on igraph_community_fastgreedy

[Tamas Nepusz]

> Thanks Tamas...Any estimate on how much faster based on nodes/edges?
I did not analyze the running time as a function of the number of  
nodes/edges so far, but I just did a test on my Mac with the  
"condensed matter collaboration 2003" dataset (found here: http://www-personal.umich.edu/~mejn/netdata/) 
. This network has 31163 vertices and 120029 edges. I had to extract  
the largest connected component since the original implementation  
required the graph to be connected. The igraph implementation ran to  
completion in 50.935s using the Python interface, the original one  
terminated after 81.992s (compiled with full optimization to speed,  
standard output was redirected to /dev/null).

> Also, do the input IDs have to be contiguous, e.g.,  
> 0,1,2,3,4,5,6,7,8,9 or
> can it be 0,1,2,3,4,15,16,17,28,29 with ID gaps but still be a fully
> connected component.
>
> My guess is that I would need to remap Node IDs? Thanks again.
Vertex IDs in igraph are always continuous, starting from 0. If you  
import an edge list that's not continuous, you'll have some isolated  
vertices in the network. However, that's not a problem for the fast  
greedy community detection, it is perfectly happy even if the network  
has multiple components. (However, you shouldn't compare the  
modularity score obtained this way with the modularity achieved on the  
graph where you did not have those isolated vertices). Another  
possibility is to load the network, attach an "ID" attribute to all  
the vertices that refer to the ID of the original network and then  
delete the isolated vertices. The ID attributes are kept by igraph and  
can be used afterwards to relate the vertices back to the original  
network.

--
T.