48
$\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?

$\endgroup$

8 Answers 8

23
$\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.

$\endgroup$
2
  • 2
    $\begingroup$ many thanks for pointing this out to me, I had completely missed the reference to the weights in the documentation. $\endgroup$ Sep 22, 2010 at 17:42
  • $\begingroup$ @Petr: Can you please take a look at this question? stackoverflow.com/questions/64870651/… can this be done with weighted node? $\endgroup$
    – stats_noob
    Nov 17, 2020 at 14:38
11
$\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.

$\endgroup$
2
  • 1
    $\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, 2011 at 18:24
  • 1
    $\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, 2011 at 19:11
8
$\begingroup$

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

cheers

$\endgroup$
1
  • $\begingroup$ @Seb any implementations in R you know of? $\endgroup$
    – John Colby
    Nov 14, 2011 at 20:21
5
$\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.

$\endgroup$
1
  • 1
    $\begingroup$ Louvain modularity algorithm is fast and steady, i wonder if there is a map reduce version of it. $\endgroup$
    – Page
    Sep 12, 2012 at 9:44
4
$\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')
$\endgroup$
2
  • $\begingroup$ 'Bad graph type, use only non directed graph' $\endgroup$
    – GRquanti
    Mar 25, 2021 at 2:24
  • $\begingroup$ @kingledion, if you have node properties ... can these be taken into account? Or is this just a structural partitioning? $\endgroup$
    – sAguinaga
    Feb 4, 2022 at 12:09
2
$\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.

$\endgroup$
2
$\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

$\endgroup$
2
$\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,

$\endgroup$

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