测量图中节点的“远程性”
测量图中节点的“远程性”
提问于 2019-04-28 17:36:49
在古老的论坛游戏“TradeWars 2002”中，我画出了一张图的所有边。有1000个节点。该图是正式的有向图，尽管节点之间的大多数边都是无向的。图是强连通的。
我在networkx中对宇宙进行建模。我想使用networkx方法来识别网络中“最远”的节点。不过，我不知道如何用图论术语来表达“最遥远”。但我的想法是，当有人在其他两个任意节点之间传输时，很少会碰到节点。在连接良好的节点的边缘，可能有一串节点沿着一条终止的路径向外延伸。
我想象的是节点733。与其他连接更好的节点相比，不太可能有人意外地发现了这个节点。
我可以使用networkx库中的什么来量化一些“远程”度量？
这是整个宇宙：
回答 1
Stack Overflow用户
发布于 2019-04-29 06:09:51
对于这类问题，networkx有一套算法：centrality。例如，您可以使用最简单的函数：closeness_centrality
# Create a random graph
G = nx.gnp_random_graph(50, 0.1)nx.closeness_centrality(G)
{0: 0.3888888888888889,
1: 0.45794392523364486,
2: 0.35507246376811596,
3: 0.4375,
4: 0.4083333333333333,
5: 0.3684210526315789,
...# Draw the graph
labels = {n: n for n in G.nodes}
nx.draw(G, with_labels=True, labels=labels)
通过返回closeness_centrality最小的节点(注意节点ID和上图中蓝色圆圈中的节点)，可以列出最远(不太中心)的节点：
c = nx.closeness_centrality(G)
sorted(c.items(), key=lambda x: x[1])[:5]
[(48, 0.28823529411764703),
(7, 0.33793103448275863),
(11, 0.35251798561151076),
(2, 0.35507246376811596),
(46, 0.362962962962963)]页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55888924
复制相关文章
相似问题
腾讯云开发者
