girvan_newman#

girvan_newman(G, most_valuable_edge=None)[source]#

使用Girvan-Newman方法在图中寻找社区。

Parameters:
GNetworkX图
most_valuable_edge函数

该函数接受一个图作为输入并输出一条边。该函数返回的边将在算法的每次迭代中重新计算并移除。

如果未指定，将使用具有最高 networkx.edge_betweenness_centrality() 的边。

Returns:
迭代器

返回一个迭代器，该迭代器在 G 中生成节点集的元组。每个节点集是一个社区，每个元组是算法在特定级别上的社区序列。

Notes

Girvan-Newman算法通过逐步从原始图中移除边来检测社区。该算法在每一步移除“最有价值”的边，传统上是具有最高介数中心性的边。随着图分解成多个部分，紧密的社区结构被暴露出来，结果可以表示为树状图。

Examples

要获取第一对社区:

>>> G = nx.path_graph(10)
>>> comp = nx.community.girvan_newman(G)
>>> tuple(sorted(c) for c in next(comp))
([0, 1, 2, 3, 4], [5, 6, 7, 8, 9])

要仅获取前*k*个社区元组，请使用 itertools.islice()

>>> import itertools
>>> G = nx.path_graph(8)
>>> k = 2
>>> comp = nx.community.girvan_newman(G)
>>> for communities in itertools.islice(comp, k):
...     print(tuple(sorted(c) for c in communities))
...
([0, 1, 2, 3], [4, 5, 6, 7])
([0, 1], [2, 3], [4, 5, 6, 7])

要在社区数量大于*k*时停止获取社区元组，请使用:func:itertools.takewhile

>>> import itertools
>>> G = nx.path_graph(8)
>>> k = 4
>>> comp = nx.community.girvan_newman(G)
>>> limited = itertools.takewhile(lambda c: len(c) <= k, comp)
>>> for communities in limited:
...     print(tuple(sorted(c) for c in communities))
...
([0, 1, 2, 3], [4, 5, 6, 7])
([0, 1], [2, 3], [4, 5, 6, 7])
([0, 1], [2, 3], [4, 5], [6, 7])

要根据权重选择要移除的边:

>>> from operator import itemgetter
>>> G = nx.path_graph(10)
>>> edges = G.edges()
>>> nx.set_edge_attributes(G, {(u, v): v for u, v in edges}, "weight")
>>> def heaviest(G):
...     u, v, w = max(G.edges(data="weight"), key=itemgetter(2))
...     return (u, v)
...
>>> comp = nx.community.girvan_newman(G, most_valuable_edge=heaviest)
>>> tuple(sorted(c) for c in next(comp))
([0, 1, 2, 3, 4, 5, 6, 7, 8], [9])

要在选择边时利用边权重，例如，具有最高介数中心性的边:

>>> from networkx import edge_betweenness_centrality as betweenness
>>> def most_central_edge(G):
...     centrality = betweenness(G, weight="weight")
...     return max(centrality, key=centrality.get)
...
>>> G = nx.path_graph(10)
>>> comp = nx.community.girvan_newman(G, most_valuable_edge=most_central_edge)
>>> tuple(sorted(c) for c in next(comp))
([0, 1, 2, 3, 4], [5, 6, 7, 8, 9])
要指定不同的边排序算法，请使用

most_valuable_edge 关键字参数:

>>> from networkx import edge_betweenness_centrality
>>> from random import random
>>> def most_central_edge(G):
...     centrality = edge_betweenness_centrality(G)
...     max_cent = max(centrality.values())
...     # 将中心性值缩放到0和1之间，并添加一些随机噪声。
...     centrality = {e: c / max_cent for e, c in centrality.items()}
...     # 添加一些随机噪声。
...     centrality = {e: c + random() for e, c in centrality.items()}
...     return max(centrality, key=centrality.get)
...
>>> G = nx.path_graph(10)
>>> comp = nx.community.girvan_newman(G, most_valuable_edge=most_central_edge)
On this page