How to do community detection in a weighted social network/graph? 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?
 A: Gephi implements the Louvain Modularity method: http://wiki.gephi.org/index.php/Modularity
cheers
A: 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.
A: 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')

A: 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.
A: 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.
A: 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,
A: 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
A: 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.
