python - 将社区检测与图形或其他库重叠

Question

我想检测小型网络/图中的重叠社区。通过重叠，我的意思是一个节点可以包含在检测算法输出中的多个社区/集群中。

我查看了igraph 提供的各种社区检测算法。 ，但我认为它们都没有处理重叠的社区。

理想情况下，我希望能够以编程方式在 Python 中利用此类算法的某些实现。但是，其他语言的实现也可以。

Answer 1

我已经实现了hierarchical link clustering前段时间Ahn等人的算法使用了igraph的Python接口(interface)；查看其源代码here .

此外，使用 igraph 在 Python 中实现 CFinder 相当容易；这就是我想出的:

#!/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"])