我希望能够检测小型网络/图中的重叠社区。所谓重叠是指在检测算法的输出中,一个节点可以包含在多个社区/簇中。
我已经查看了
理想情况下,我希望能够以编程方式利用一些此类算法的Python实现。但使用其他语言也可以。
我已经查看了
igraph
目前提供的各种社区检测算法,但我认为它们都不能处理重叠的社区。理想情况下,我希望能够以编程方式利用一些此类算法的Python实现。但使用其他语言也可以。
#!/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"])
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))
>>> G = nx.complete_graph(5)
>>> K5 = nx.convert_node_labels_to_integers(G,first_label=2)
>>> G.add_edges_from(K5.edges())
>>> c = list(nx.k_clique_communities(G, 4))
>>> list(c[0])
[0, 1, 2, 3, 4, 5, 6]
>>> list(nx.k_clique_communities(G, 6))
networkx
库现在具有更广泛的社区检测算法。 Carla给出的示例现在是:>>> from networkx.algorithms.community import k_clique_communities
>>> G = nx.complete_graph(5)
>>> K5 = nx.convert_node_labels_to_integers(G,first_label=2)
>>> G.add_edges_from(K5.edges())
>>> c = list(k_clique_communities(G, 4))
>>> list(c[0])
[0, 1, 2, 3, 4, 5, 6]
>>> list(k_clique_communities(G, 6))
[]