Partitioning Weighted Undirected Graph

Question

I have an array of edges and weights:

[['a', 'b', 4],
 ['a', 'c', 3],
 ['c', 'a', 2], 
 ...]

I have about 100,000 edges and weights are between 1 and 700, most around 100.

I am thinking of using Markov Cluster Algorithm however wanted to reach out to see if this is the best to use. What about Affinity Propagation? In either case, what is the workflow? Do you typically have a way to measure how well clustered the results. Is there an equivalent to a silhouette score? Is there a way to visualize the clusters?

Answer 1

So what you need is Modularity score. Speaking as a Graph Clustering guy (my master thesis topic, PhD research and my main research direction during last 2.5 years) I recommend you to go through what physicists did in Complex Networks field under the name of Community Detection. If you search Prof. Mark Newman who first proposed Modularity score you'll find a bunch of interesting papers in this field. Infomap algorithm by Martin Rosvall, Louvain algorithm by Vincent Blondel and CNM algorithm by Aaron Clauset are some of the most known algorithms.

The most commonly used algorithm for graph clustering nowadays is the one by Vincent Blondel which has implementations for both NetworkX and igraph (if you are a python guy!). This algorithm is originally for weighted graphs and probably answers your question.

Hope it helps, Good luck!

Answer 2

Even a simple Internet search reveals numerous papers on graph clustering approaches and algorithms. This paper is most likely the best starting point, as it presents a rather comprehensive overview of the topic in terms of the problem as well as approaches, methods and algorithms for solutions. The rest you can find easily via online search. In regard to graph clustering visualization, I recommend you to check my relevant answer - I'm pretty sure that the tools I reference there are able to visualize graph clusters as well.

Answer 3

If you are using python, and have created a weighted graph using NetworkX, then you can use python-louvain for clustering. Where G is a weighted graph:

import community 
partition = community.best_partition(G, weight='weight')