girvan_newman

girvan_newman(G, most_valuable_edge=None)

使用 Girvan–Newman 方法在图中查找社区。

参数：

GNetworkX 图

most_valuable_edge函数

接受图作为输入并输出一条边的函数。算法每次迭代时，都会重新计算并移除此函数返回的边。

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

返回：

迭代器

一个迭代器，遍历 G 中节点集合的元组。每个节点集合是一个社区，每个元组是算法在特定级别的社区序列。

说明

Girvan–Newman 算法通过逐步移除原始图中的边来检测社区。该算法在每一步移除“最有价值”的边，传统上是指具有最高边介数中心性的边。随着图分解成多个部分，紧密连接的社区结构得以显现，结果可以绘制成树状图。

示例

获取第一对社区

>>> 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 时停止获取社区元组，请使用 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())
...     # Scale the centrality values so they are between 0 and 1,
...     # and add some random noise.
...     centrality = {e: c / max_cent for e, c in centrality.items()}
...     # Add some random noise.
...     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)