与 igraph 或其他库重叠社区检测 [英] Overlapping community detection with igraph or other libaries
问题描述
我想检测小型网络/图中的重叠社区.通过重叠,我的意思是一个节点可以包含在检测算法的输出中的多个社区/集群中.
我查看了 igraph
当前提供的各种社区检测算法,但我认为它们都没有处理重叠社区.p>
理想情况下,我希望能够以编程方式利用 Python 中此类算法的某些实现.但是,其他语言的实现也可以.
我已经实现了分层链接聚类算法不久前,Ahn 等人使用 igraph 的 Python 接口;在此处查看其源代码.
此外,使用 igraph 在 Python 中实现 CFinder 相当容易;这就是我想出的:
#!/usr/bin/env python从 itertools 导入组合导入 igraph导入 optparseparser = optparse.OptionParser(usage="%prog [options] infile")parser.add_option("-k", metavar="K", default=3, type=int,帮助 =使用 K 的集团规模")选项,args = parser.parse_args()如果不是参数:parser.error("需要输入文件作为第一个参数")k = 选项.kg = igraph.load(args[0], format="ncol",directed=False)cls = map(set, g.maximal_cliques(min=k))边列表 = []对于 i, j 组合(范围(len(cls)),2):如果 len(cls[i].intersection(cls[j])) >= k-1:edgelist.append((i, j))cg = igraph.Graph(edgelist,directed=False)集群 = cg.clusters()对于集群中的集群:成员 = 集()对于集群中的 i:members.update(cls[i])打印 " ".join(g.vs[members]["name"])
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.
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 " ".join(g.vs[members]["name"])
这篇关于与 igraph 或其他库重叠社区检测的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!