[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [igraph] Question on igraph_community_fastgreedy

From: Tamas Nepusz
Subject: Re: [igraph] Question on igraph_community_fastgreedy
Date: Wed, 27 Feb 2008 23:54:49 +0100

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.


reply via email to

[Prev in Thread] Current Thread [Next in Thread]