0

I had to shift from using community_fastgreedy() to community_edge_betweenness() due to the inability of community_fastgreedy() to handle directed graphs (directed unweighted graph).

My understanding is that community_fastgreedy() is bottom-up approach while community_edge_betweenness() is top-down and both work on the principle of finding communities that maximize modularity, one by merging communities and the other by removing edges.

In the original paper by M.Girvan and M.E.J.Newman "Community structure in social and biological networks", there is no mention of it being able to handle directed graph. This is being used for community_edge_betweenness().

I referred here and Link documentation to get more information on the algorithm for directed networks.

My questions are -

  1. Is my understanding of, community_fastgreedy() and community_edge_betweenness() implementation in python-igraph depend on maximizing modularity, correct.

  2. Can you please point me to the documentation of how community_edge_betweenness is implemented to handle directed network in python-igraph or to a newer version of the paper by Girvan and Newman.

Since i am new to community detection any pointers are useful. I am aware of better methods (Louvain, Infomap) but still need to use CNM or GN for comparision purposes.

Thanks.

Improve this question

1 Answer 1

Reset to default
4

  1. community_edge_betweenness() does not try to maximize modularity. Modularity is only used as a rule of thumb to decide where to "cut" the dendrogram generated by the algorithm if the user insists on a "flat" community structure instead of a flat dendrogram.

  2. community_edge_betweenness() "handles" directed graphs simply by looking for directed paths instead of undirected ones when it calculates the edge betweenness scores for the edges (which are then used in turn to decide which edge to remove at a particular step). As far as I know, no research has been made on whether this approach is scientifically sound and correct or not.

The reason why most community detection methods (especially the ones that are maximizing modularity) do not cater for directed graphs is because the concept of a "community" is not well-defined for directed graphs - most of the algorithms look for parts in the graph that are "denser than expected by chance", but this vague definition does not say anything about how the directions of edges should be used. Also, there are multiple (conflicting) extensions of the modularity score for directed graphs.

As far as I know, the only method in igraph that has a "formal" treatment to the problem of communities in directed networks is the InfoMap algorithm. InfoMap defines communities based on minimal encodings of random walks within graphs so it is able to take the edge directions into account accurately - roughly speaking, communities found by the InfoMap algorithm are groups of nodes for which a random walker has a small probability of "escaping" from the group. (The InfoMap homepage has a nice visual explanation). So, if you really need to find communities in a directed graph, I would suggest using the InfoMap method.

Improve this answer
Sign up to request clarification or add additional context in comments.

1 Comment

Thanks for the clear explanation. Has been very helpful.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.