Re: [igraph] Obtaining communities and modularity index for an undirected graph

[Gábor Csárdi]

On Mon, May 21, 2012 at 1:39 PM, Giuseppe G. <address@hidden> wrote:
> Thanks again Tamás.
>
> I think I have some working code based on your recommendation now. One more
> thing. It seems like, in certain cases, the number of merges is not always
> Nodes-1 but smaller. Eg. I have a network with 101 nodes and 95 merges. I
> obtain these numbers by doing

This can happen if your original input graph is not connected, i.e. it
has multiple components. If it does not, then this is probably the
sign of an error, either in your code, or in ours.

Gabor

> nodes = igraph_vcount(&graph);
> fprintf(stdout,"Vertices: %li\n", (long int) nodes);
> number_of_merges = igraph_matrix_nrow(&merges);
> fprintf(stdout,"number of merges: %li\n", (long int) number_of_merges);
>
> Is this expected behaviour? I.e. is N-1 just an upper boundary for the
> number of potential merges? Thanks!
>
> G
>
>
> On 21/05/12 13:51, Tamás Nepusz wrote:
>>>
>>> All I've used so far is only "ready-made" implementations of the Girvan
>>> Neumann algorithm, and I don't remember having had to set the number of
>>> steps. All I remember getting was one community assignment presented to
>>> me as THE GN clustering for that undirected network.
>>
>>
>> The original publication of the Girvan-Newman algorithm (see
>> http://www.pnas.org/content/99/12/7821, preprint:
>> http://www.santafe.edu/media/workingpapers/01-12-077.pdf) does not describe
>> how to select the number of communities (i.e. how to decide where to cut the
>> dendrogram). As far as I know, most of the existing implementations use the
>> modularity score or some other internal quality criterion to decide the
>> number of communities. For instance, the SNAP library uses the maximum
>> modularity criterion.
>>
>> Cheers,
>> Tamas
>>
>>
>> _______________________________________________
>> igraph-help mailing list
>> address@hidden
>> https://lists.nongnu.org/mailman/listinfo/igraph-help
>>
>
> --
> The University of Edinburgh is a charitable body, registered in
> Scotland, with registration number SC005336.
>
>
> _______________________________________________
> igraph-help mailing list
> address@hidden
> https://lists.nongnu.org/mailman/listinfo/igraph-help



-- 
Gabor Csardi <address@hidden>     MTA KFKI RMKI