girvan_newman

girvan_newman(G, most_valuable_edge=None)

使用girvan–newman方法在图中查找社区。

参数

G网络X图表

most_valuable_edge功能

将图形作为输入并输出边的函数。此函数返回的边将在算法的每次迭代中重新计算和删除。

如果未指定，则使用 networkx.edge_betweenness_centrality() 将被使用。

返回

迭代器

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

笔记

Girvan–Newman算法通过逐步从原始图形中删除边来检测社区。该算法在每个步骤中删除“最有价值”的边缘，传统上是具有最高中间中心性的边缘。当图被分解成碎片时，紧密结合的群落结构被暴露出来，结果可以被描绘成树枝状图。

实例

要获取第一对社区：

>>> G = nx.path_graph(10)
>>> comp = 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 = 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 = 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 = 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 = 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 = girvan_newman(G, most_valuable_edge=most_central_edge)