skyork - 11 months ago 147

Python Question

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`

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.

Answer Source

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"])
```