3
$\begingroup$

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:

enter image description here

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

To partition graph you can use divisive or agglomerative methods.

In short when using divisive methods you observe the pair of nodes and count how many shortest path among all other nodes include the edge between the observed nodes. Intiutively: If you have two clusters, the shortest path among all nodes from the left and nodes from the right on the picture go through 7-8. For more details check Girvan–Newman Method.

When using agglomerative methods you pick a set of nodes and calculate the ratio (edges of all nodes from the set)/(edges of all nodes from the set between nodes from the set) and by picking/removing nodes from the set you try to find the minimum.

When dealing with large networks you will have to use heuristic methods and I would like to give you a suggestion that will drastically reduce the computing time: use graph database.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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