3
$\begingroup$

I have a large moderately dense network (50k nodes, 300k edges) and want to divide this into few (5-10) communities, based on how densely connected the nodes are.

I've been looking into the algorithms available in R's igraph-package and while they do what I want in principle, they all seem ill-suited for such large networks (e.g. igraph_community_optimal_modularity) or they provide no means of pre-specifying the number of communites. Applying those yields way too many communites (e.g., igraph_community_fastgreedy comes up with 60).

Question: How (ideally with igraph and R) can I divide the graph into a pre-specified small number of communitities, in a computationally effcient way?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Are the current statistics of your graph correct? 200k nodes with 300k edges is an extremely sparse graph by most standards. Assuming you drop nodes with no edges, this means the majority of your nodes only have one edge. $\endgroup$
    – Cliff AB
    Jan 8, 2020 at 22:48
  • $\begingroup$ You're right, this is the result of a lot of isolates which I can drop. The main network I care about is denser. I updated the numbers $\endgroup$
    – sheß
    Jan 8, 2020 at 23:43

1 Answer 1

Reset to default
2
$\begingroup$

I've succeeded in similar problems using Newman's modularity via power iteration. The algorithm is very simple: bisect the graph until you have five clusters. This consumes only five rounds of graph bisection, implying that you only need five rounds of power iteration.

Newman's paper outlines how to do it. M. E. J. Newman. "Modularity and community structure in networks." PNAS. June 6, 2006.

At the final stage you might have to make a choice about which bisections in order to optimize modularity subject to the desired number of clusters. This means you might have to commit to more bisections, which you later discard, because they offer suboptimal improvement.

If you really need to optimize it, notice that after each bisection, Newman's modularity applies a rank-1 update to our matrix. We can't leverage the Bunch-Nielsen-Sorensen result, because we don't have the full decomposition, but we can get an approximation of it. See Roy Mitz, Nir Sharon, and Yoel Shkolnisky. "Symmetric rank-one updates from partial spectrum with an application to out-of-sample extension"

Since you're using R, power iteration could be slower than using an R interface into a compiled eigenvalue solver like ARPACK. Since Newman's modularity only needs the eigenvector to the largest eigenvalue, you can request the truncated solution, which will take less time to compute.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Great, that sounds like it does what I want. Any details on how you bisected the graph? Any simple way to use built in methods of igraph? $\endgroup$
    – sheß
    Jan 9, 2020 at 1:18
  • 1
    $\begingroup$ I just wrote the code myself. It's not too involved. Newman's paper describes how to bisect graphs using power iteration. $\endgroup$
    – Sycorax ♦
    Jan 9, 2020 at 1:22

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.