Re: [igraph] Qualifying individual communities

[A. Gerow]

Ok, thanks again. I was thinking igraph's infomap algorithm was the multi-level one described here: http://arxiv.org/abs/1010.0431. I'm guessing igraph implements the original, two-mode version.

Correct me if my intuitions are wrong here, but I think there are four, perhaps naive, options to qualify communities:

1) Compute the ratio of within community links to between community links. (Something like the http://igraph.wikidot.com/community-detection-in-r#toc5)

2) Compute the modularity of a single-cut partition that results in the community at hand, and the rest of the graph.

3) Use an influence based model like C-score (http://arxiv.org/abs/0907.3708).

4) Compute some type of centrality on a new network of communities-as-nodes.

This may, however, be more of an empirical question I can answer experimentally. In any case, thanks for the help!

    - A

On 5 February 2014 03:44, Tamás Nepusz <address@hidden> wrote:

> 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.

--

A. Gerow

Knowledge Lab | Computation Institute

University of Chicago
5735 South Ellis Avenue
Chicago, IL 60637 - USA