Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Overlapping community detection with igraph or other libaries

I would like to detect overlapping communities in small networks/graphs. By overlapping, I mean that a node can be included within more than one communities/clusters in the output of the detection algorithm.

I have looked at various community detection algorithms curretly provided by igraph, but I think none of them handles overlapping communities.

Ideally, I would like to be able to programmatically utilize some implementation of such algorithm(s) in Python. However, implementation in other languages is OK too.

like image 858
skyork Avatar asked Dec 01 '22 17:12

skyork


1 Answers

I have implemented the hierarchical link clustering algorithm of Ahn et al a while ago using the Python interface of igraph; see its source code here.

Also, implementing CFinder in Python using igraph is fairly easy; this is what I came up with:

#!/usr/bin/env python
from itertools import combinations

import igraph
import optparse

parser = optparse.OptionParser(usage="%prog [options] infile")
parser.add_option("-k", metavar="K", default=3, type=int,
        help="use a clique size of K")

options, args = parser.parse_args()

if not args:
    parser.error("Required input file as first argument")

k = options.k
g = igraph.load(args[0], format="ncol", directed=False)
cls = map(set, g.maximal_cliques(min=k))

edgelist = []
for i, j in combinations(range(len(cls)), 2):
    if len(cls[i].intersection(cls[j])) >= k-1:
        edgelist.append((i, j))

cg = igraph.Graph(edgelist, directed=False)
clusters = cg.clusters()
for cluster in clusters:
    members = set()
    for i in cluster:
        members.update(cls[i])
    print "\t".join(g.vs[members]["name"])
like image 159
Tamás Avatar answered Dec 15 '22 13:12

Tamás