使用 networkx 计算非随机性

Question

我正在尝试计算图表的 non-randomness using networkx。

某些图表会出现此错误，但其他图表不会。

~\anaconda3\lib\site-packages\networkx\algorithms\non_randomness.py
eq. 4.5

nr_rd = (nr - ((n - 2 * k) * p + k)) / math.sqrt(2 * k * p * (1 - p))

什么图形特征导致了这个错误？

文档描述了两种可能的例外情况。这个也不是。

这是导致错误的图表示例。节点标签（a、m、d）、颜色和大小是用于对相似节点进行分组的节点属性。每个节点都有一个唯一的 ID，图中未显示。

这是创建该图并生成错误的代码。

nodes = ['a1','a2','a3','a4','m1','m2','m3','m4','d']
edges = [('a1','m1'),('a2','m2'),('a3','m3'),('a4','m4'),('m1','d'),('m2','d'),('m3','d'),('m4','d')]

my_g = nx.Graph()

for n in nodes:
    my_g.add_node(n)

for e in edges:
    my_g.add_edge(e[0],e[1])

nx.non_randomness(my_g)

Answer 1

有趣的是，我尝试了下面的可重现示例，它似乎工作正常：

import networkx as nx

G = nx.karate_club_graph()
nr, nr_rd = nx.non_randomness(G)

这是使用 networkx 的版本 2.7.1。此外，此函数未针对有向图或多重图实现，这可能有助于解释为什么它适用于测试中的某些图而不适用于其他图（但也可能是由于其他原因）。所以隔离这个原因的一种方法是确保 G 满足这个条件：

    G : NetworkX graph
        Graph must be symmetric, connected, and without self-loops.

更新: 鉴于问题中的示例图，使用默认设置的函数确实存在问题。但是，明确指定所有参数似乎可以解决问题（至少对于此示例而言）：

import networkx as nx

nodes = ["a1", "a2", "a3", "a4", "m1", "m2", "m3", "m4", "d"]
edges = [
    ("a1", "m1"),
    ("a2", "m2"),
    ("a3", "m3"),
    ("a4", "m4"),
    ("m1", "d"),
    ("m2", "d"),
    ("m3", "d"),
    ("m4", "d"),
]


G = nx.Graph()

for n in nodes:
    G.add_node(n)

for e in edges:
    G.add_edge(e[0], e[1])

print(nx.non_randomness(G, k=1, weight=None))
# (2.2360679774997902, -0.5433972933277872)

使用 networkx 计算非随机性

Calculating non-randomness with networkx

python

graph-theory

networkx