Re: [igraph] Question on igraph_community_fastgreedy

[Richard Geddes]

Another question regarding the output of igraph_community_fastgreedy:

The first element in the vector, modularity, is the initial Q for the
graph, before any merges are performed.. is this correct?

The first row element in the matrix, merges, contains the two components
(communities) to be joined.

So, to display the Q after the merge in an n node graph, I would have to
display:

initial Q:   modularity[0]

component0       component1       resulting Q
--------------------       ---------------------       ---------------------
merges[0, 0]       merges[0, 1]       modularity[1]
merges[1, 0]       merges[1, 1]       modularity[2]
    :                            :                            :
    :                            :                            :
merges[n-2, 0]    merges[n-2, 1]   modularity[n-1]


Does this look correct?

Thanks
R

Tamas Nepusz wrote:
>> 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.
>