43
$\begingroup$

I'm wondering if someone could suggest what are good starting points when it comes to performing community detection/graph partitioning/clustering on a graph that has weighted, undirected edges. The graph in question has approximately 3 million edges and each edge expresses the degree of similarity between the two vertices it connects. In particular, in this dataset edges are individuals and vertices are a measure of the similarity of their observed behavior.

In the past I followed a suggestion I got here on stats.stackexchange.com and used igraph's implementation of Newman's modularity clustering and was satisfied with the results, but that was on a unweighted dataset.

Are there any specific algorithms I should be looking at?

| cite | improve this question | |
$\endgroup$
20
$\begingroup$

igraph implementation of Newman's modularity clustering (fastgreedy function) can be used with weighted edges as well. Just add weight attribute to the edges and analyse as usual. In my experience, it run even faster with weights as there are less ties.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ many thanks for pointing this out to me, I had completely missed the reference to the weights in the documentation. $\endgroup$ – laramichaels Sep 22 '10 at 17:42
9
$\begingroup$

I know that Gephi can process undirected weighted graph, but I seem to remember it has to be stored in GDF, which is pretty close to CSV, or Ucinet DL. Be aware that it's still an alpha release. Now, about clustering your graph, Gephi seems to lack clustering pipelines, except for the MCL algorithm that is now available in the latest version. There was a Google Code Project in 2009, Gephi Network Statistics (featuring e.g. Newman’s modularity metric), but I don't know if something has been released in this direction. Anyway, it seems to allow some kind of modularity/clustering computations, but see also Social Network Analysis using R and Gephi and Data preparation for Social Network Analysis using R and Gephi (Many thanks to @Tal).

If you are used to Python, it is worth trying NetworkX (Here is an example of a weighted graph with the corresponding code). Then you have many ways to carry out your analysis.

You should also look at INSNA - Social Network Analysis Software or Tim Evans's webpage about Complex Networks and Complexity.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Hello there, Just to let you know that Gephi cannot handle weighted undirected graph to identify community through modularity. thanks. -Gautam $\endgroup$ – user3038 Feb 4 '11 at 18:24
  • $\begingroup$ @Gautam Good to know, thanks. I am not really familiar with Gephi, but I thought it was in active development. $\endgroup$ – chl Feb 4 '11 at 19:11
7
$\begingroup$

Gephi implements the Louvain Modularity method: http://wiki.gephi.org/index.php/Modularity

cheers

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @Seb any implementations in R you know of? $\endgroup$ – John Colby Nov 14 '11 at 20:21
4
$\begingroup$

The Louvain modularity algorithm is available in C++: https://sites.google.com/site/findcommunities/

It deals with weighted networks of millions of nodes and edges, and has been demonstrated to be much faster than Newman algorithm.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Louvain modularity algorithm is fast and steady， i wonder if there is a map reduce version of it. $\endgroup$ – Page Sep 12 '12 at 9:44
3
$\begingroup$

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')
| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I just came across the tnet package for R. The creator seems to be researching on community discovery in weighted and bipartite (two-mode) graphs.

http://opsahl.co.uk/tnet/content/view/15/27/

I have not yet use it.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

SLPA (now called GANXiS) is a fast algorithm capable of detecting both disjoint and overlapping communities in social networks (undirected/directed and unweighted/weighted). It is shown that the algorithm produces meaningful results on real-world social and gene networks. It is one of the state-of-the-art. It is available at

https://sites.google.com/site/communitydetectionslpa/

See a nice review arxiv.org/abs/1110.5813 for more info

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

I've an java implementation for non-overlapping, weighted/unweighted network that could probably handle 3 million nodes (I've tested it for a million node dataset). However, it works like k-means, and needs the number of partitions to be detected as an input (k in kmeans). You can find more info here, and here is the code, in github

Cheers,

| cite | improve this answer | |
$\endgroup$

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