Graph Clustering for almost Clustered Graph by removing nodes(vertices)

Question

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).(Refer this picture https://docs.google.com/file/d/0B7_3zLD0XdtAd3ZwMFAwWDZuU00/edit?pli=1)

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 can i directly use?

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

So, let mi try to communicate. Your graph is "almost clustered", so you actually have a function like node.cluster returning the cluster it belongs to? And for some node, it returns 2 clusters? Or do you expect us to help you with making this function? — Boris Stitnicky
I just happen to have the graph representation i.e. either in the form of Adjacency List or Adjacency Matrix. I would need help in making this function. — Shatu
Please refer this docs.google.com/file/d/0B7_3zLD0XdtAd3ZwMFAwWDZuU00/edit?pli=1 . This should clarify what i wish to do(I just want to remove such nodes) — Shatu
the mcl cluster method should easily scale to that number of nodes and edges. It can take in an adjacency list of edges as input. Available at micans.org/mcl — micans
When you write "Plus i need a solution that would cut nodes and not edges since different clusters share nodes and not edges in my case", what do you mean? This is very unclear. If regular graph clustering algorithms do not do what you want, can you explain why? — micans

Boris Stitnicky Boris Stitnicky · Accepted Answer · 2012-05-26T09:05:52

Your problem is not so simple. I am afraid that it is related to the clique problem, which is NP complete, so unless you quantify somehow the statement "there are almost no edges between the clusters", your problem might be still very difficult. But what I would do in your shoes, would be to try one dirty, greedy approach, namely regarding the nodes as the following kind of quasi-neural net:

Each vertex I would consider to have inputs, outputs and a sigmoid activation function which convert the input value (sum of inputs) into the output value. The output value, and I consider this important, would not be cloned and sent to all the neighbors, but rather divided evenly between the neighbors. In addition to this, I would define a logarithmic decay of activity in a neuron (self-suppression, suppressive connection to itself), defined by a decay parameter global for the net.

Now, I would start simulation with all the neurons starting from activity 0.5 (activity range is 0 to 1) with very high decay parameter, which would lead to all the neuronst quickly stabilizing in 0 state. I would then gradually decrease the decay parameter until the steady state result would yield the first clique with non-zero stable activity.

The question is what to do next. One possibility is to subtract the found clique from the graph and run the same process again until we find all the cliques. This greedy approach might succeed if your graph is indeed as well behaved (really almost clustered) as you say, but might lead to unexpected results otherwise. Another possibility is to give the found clique a unique clique smell that would be repulsive (mutual suppresion) to other cliques an rerun the algorithm until the second clique is found, give it a different clique smell repulsive to all others etc., until each node has its own assigned smell.

I think this would be as many big ideas as i have about this.

The key is, that since it is probably not possible to solve this problem in the general case (likely NP complete), you need to take use of whatever special properties your graph has. That means you need to play with parameters for a while until the algorithm solves 99% of the cases that you encounter. I don't think that it is possible to give the numerically precise answer to your question without long experimentation with the actual datasets that you encounter.

Graph Clustering for almost Clustered Graph by removing nodes(vertices)

2 Answers