igraph或其他库文库重叠社区检测

2018-06-24 09:30:18

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

我查看了许多由igraph提供的社区检测算法，但我认为它们都不处理重叠的社区。

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

我之前使用igraph的Python接口实现了Ahn等人的层次链接聚类算法; 在这里看到它的源代码。

另外，使用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"])

如果你不介意使用另一种编程语言，你有CFinder（Java），它基于团体渗透（它基本上寻找紧密连接的团队），优化统计度量的OSLOM（C ++），当然还有其他的。

否则，如果你想坚持python，你也可以应用Evans＆Lambiotte'09的方法：1）将你的图转换成线图，2）在其上应用常规的社区检测方法，例如使用igraph，以及3）获得重叠社区。将您的图转换为折线图看起来不太复杂，并且应该很快，只要您的原始图形不太大。在任何情况下，它都比执行社区检测本身要快。

请注意，Evans和Lambiotte有替代方法来从常规（互斥社区）方法中获得重叠社区，例如Bennet等人的方法。 '12或Wang等人。 09。但是，实施它们似乎不那么直截了当。

根据这个博客，networkx现在可以计算重叠社区。

下面的代码是用于派克渗透方法，可在Networkx 11.6中找到。 Github在这里

import networkx as nx
from itertools import combinations

def get_percolated_cliques(G, k):
perc_graph = nx.Graph()
cliques = list(frozenset(c) for c in nx.find_cliques(G) if len(c) >= k)
perc_graph.add_nodes_from(cliques)

# Add an edge in the clique graph for each pair of cliques that percolate
for c1, c2 in combinations(cliques, 2):
    if len(c1.intersection(c2)) >= (k - 1):
        perc_graph.add_edge(c1, c2)

for component in nx.connected_components(perc_graph):
    yield(frozenset.union(*component))

链接地址: http://www.djcxy.com/p/68345.html

上一篇: Overlapping community detection with igraph or other libaries

下一篇: Questions every good Java/Java EE Developer should be able to answer?