Re: [igraph] Qualifying individual communities

[Tamás Nepusz]

> What confused me was the description of the membership function, namely for 
> hierarchical algorithms like infomap:

infomap is not hierarchical as far as I know; edge.betweenness.community, 
fastgreedy.community and walktrap.community are hierarchical for sure. Infomap 
gives you a single partition only.

> "membership gives the division of the vertices, into communities. It returns 
> a numeric vector, one value for each vertex, the id of its community. 
> Community ids start from one. Note that some algorithms calculate the 
> complete (or incomplete) hierarchical structure of the communities, and not 
> just a single partitioning. For these algorithms typically the membership for 
> the highest modularity value is returned, but see also the manual pages of 
> the individual algorithms."
>  
> This implies there are multiple modularity values used not only to nest the 
> clusters but to measure their individual modularity to construct a dendrogram.
Hierarchical algorithms give you a full dendrogram which is either built from 
the bottom up (i.e. the algorithm merges nodes or communities progressively 
until it is left with a single community only) or from the top down (i.e. the 
algorithm splits communities progressively until each node is separated into 
its own community). Either way, the dendrogram is essentially a sequence of 
merges or splits that one can perform on the nodes of the graph in order to 
derive communities. In this case, igraph has to find a way to determine where 
to “cut” the dendrogram (i.e. stop the splitting or merging), and it uses the 
modularity measure to decide that; basically it calculates the modularity of 
the current partition, then performs the next merge from the dendrogram, 
calculates the modularity again, and so on. Then it selects the partitioning 
that yielded the highest possible modularity.

T.