Take the 2-minute tour ×
Cross Validated is a question and answer site for people interested in statistics, machine learning, data analysis, data mining, and data visualization. It's 100% free, no registration required.

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?

Many thanks for any advice ~l

share|improve this question
add comment

7 Answers

up vote 11 down vote accepted

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.

share|improve this answer
    
many thanks for pointing this out to me, I had completely missed the reference to the weights in the documentation. –  laramichaels Sep 22 '10 at 17:42
add comment

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.

share|improve this answer
    
(My pleasure chl - thank you :) ) –  Tal Galili Oct 16 '10 at 8:47
    
Hello there, Just to let you know that Gephi cannot handle weighted undirected graph to identify community through modularity. thanks. -Gautam –  Gautam Thakur Feb 4 '11 at 18:24
    
@Gautam Good to know, thanks. I am not really familiar with Gephi, but I thought it was in active development. –  chl Feb 4 '11 at 19:11
add comment

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

cheers

share|improve this answer
    
@Seb Thanks for that additional information! –  chl Oct 16 '10 at 13:31
    
@Seb any implementations in R you know of? –  John Colby Nov 14 '11 at 20:21
add comment

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.

share|improve this answer
add comment

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. Email me ( rabbanyk- at - ualberta - dot - ca ) if it could help.

Cheers,

share|improve this answer
add comment

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.

share|improve this answer
    
Louvain modularity algorithm is fast and steady, i wonder if there is a map reduce version of it. –  Page Sep 12 '12 at 9:44
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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