节点的平均距离按节点数的对数增加 python

Question

我想在随机图中显示节点的平均距离增加 log N，其中 N 是节点数。这里的 p 是一对节点之间有边的概率。我试过的是：

import matplotlib.pyplot as plt
import networkx as nx
%matplotlib inline

def run_experiment(ns, p=0.45, iters=30):
    """
    p: probability of having an edge between a pair of nodes
    ns: sequence of `number of nodes(n)` to try
    iters: number of times to run for each `n`
    
    """
    G = {}
    shortestPath={}
    res = []
    for n in ns:
        print(n)
        for i in range(iters):
            G[i] = nx.gnp_random_graph(n, p)
            shortestPath[i] = nx.average_shortest_path_length(G[i], weight=None, method=None)
        means = array([shortestPath[k] for k in shortestPath]).mean()
        print(means)
        res.append(means)
    return np.array(res)

我尝试了一些 n 值：

ns = [1,10, 100, 1000]
res = run_experiment(ns)

然后我绘制它以显示对数曲线，但我得到了这个：

dictionary = dict(zip(ns, res))
plt.plot(list(dictionary.keys()),list(dictionary.values()))
plt.yscale('log')
plt.xscale('log')

有什么问题？

Answer 1

看来问题出在随机图的生成上（参见）。通过建议的函数（参见下面的代码）添加随机生成的图会导致（该图实际上有一个额外的 ns-entry 用于 3000）：

这似乎证实了您的结果。这里的代码：

from itertools import combinations, groupby
import random
from numpy import array
import matplotlib.pyplot as plt
import networkx as nx
%matplotlib inline

# from 
def gnp_random_connected_graph(n, p):
    """
    Generates a random undirected graph, similarly to an Erdős-Rényi 
    graph, but enforcing that the resulting graph is conneted
    """
    edges = combinations(range(n), 2)
    G = nx.Graph()
    G.add_nodes_from(range(n))
    if p <= 0:
        return G
    if p >= 1:
        return nx.complete_graph(n, create_using=G)
    for _, node_edges in groupby(edges, key=lambda x: x[0]):
        node_edges = list(node_edges)
        random_edge = random.choice(node_edges)
        G.add_edge(*random_edge)
        for e in node_edges:
            if random.random() < p:
                G.add_edge(*e)
    return G

def run_experiment(ns, p=0.45, iters=30):
    """
    p: probability of having an edge between a pair of nodes
    ns: sequence of `number of nodes(n)` to try
    iters: number of times to run for each `n`
    
    """
    G = {}
    shortestPath={}
    res = []
    for n in ns:
        print(n)
        for i in range(iters):
            #G[i] = nx.gnp_random_graph(n, p)
            G[i] = gnp_random_connected_graph(n, p)
            shortestPath[i] = nx.average_shortest_path_length(G[i], weight=None, method=None)
        means = array([shortestPath[k] for k in shortestPath]).mean()
        print(means)
        res.append(means)
    return np.array(res)

ns = [1,10, 100, 1000]
res = run_experiment(ns)

dictionary = dict(zip(ns, res))
plt.plot(list(dictionary.keys()),list(dictionary.values()))
plt.yscale('log')
plt.xscale('log')

请注意，我刚刚更改了您代码中的一行并引用了生成函数。

节点的平均距离按节点数的对数增加 python

The mean distance of the nodes increases by log of the number of nodes python

python

graph

networkx