# Finding communities in online social networks by removing nodes

I want to carry out Graph Clustering in a huge undirected graph with millions of edges and nodes. Graph is almost clustered with different clusters joined together only by some nodes (kind of ambiguous nodes which can relate to multiple clusters). There will be very few or almost no edges between two clusters. This problem is almost similar to finding vertex cut set of a graph, with one exception that graph needs to be partitioned into many components(their number being unknown). Please, refer to this picture:

Its almost like different strongly connected components sharing a couple of nodes between them and i am supposed to remove those nodes to separate those strongly connected components. Edges are weigthed but this problem is more like finding structures in a graph, so edge weigths won't be of relevance. (Another way to think about the problem would be to visualize Solid Spheres touching each other at some points with Spheres being those strongly connected components and touching points being those ambiguous nodes.)

I am prototyping something, so am quiet short of time to pick up Graph Clustering Algorithms by myself and to select the best possible. Plus I need a solution that would cut nodes and not edges since different clusters share nodes and not edges in my case.

Is there any research paper, blog that addresses this or somewhat related problem? Or can anyone come up with a solution to this problem howsoever dirty.

Since millions of nodes and edges are involved, I would need a MapReduce implementation of the solution. Any inputs, links for that too?

Is there any current open source implementation in MapReduce that could be directly used?

I think this problem is analogous to Finding Communities in online social networks by removing vertices.

-

The way your question is phrased (seeking to remove nodes to find/separate compact strongly connected components) suggests a naive approach where you compute node betweenness centrality, remove high-scoring nodes, and iterate this process. Iteration is necessary; in the example picture for example the rightmost solid black dot does not score high initially and will only start doing so once the second rightmost solid black dot is removed. Even bearing in mind that you could compute betweenness centrality for paths of some bounded length, this approach will still be prohibitively expensive computationally.

Out of curiosity I clustered your example network using mcl (http://micans.org/mcl), and in default settings it finds four groups, with the black nodes allocated among those four groups. With mcl it is a bit of a concern that nodes that are highly connected with distinct sets of nodes may pull those sets together. This did not happen in the example, but is something to keep in mind. The advantage of mcl is that it is threaded and scales to millions of nodes given decent (multi-processor) hardware.

Another method to try is the Louvain method (http://sites.google.com/site/findcommunities/). This optimises modularity. It is apparently exceedingly fast: the analysis of a typical network of 2 million nodes only takes 2 minutes.

-