python - 从 Graph 类中提取度数、平均度数

Question

有人尝试过实现一个软件来从 NetworkX 的图类中提取度数、平均度数吗？我并不是要求在 networkX 中实现稳定的方法。我在这里要求从头开始实现。

这是我到目前为止所尝试过的(不确定这是否正确)？

for i in range(3, 9):
    G = nx.gnp_random_graph(i, 0.2) #Returns a G_{n,p} random graph, also known as an Erdős-Rényi graph or a binomial graph.
    #print(len(G))
    #print(len(G.nodes()))
    from collections import *
    import collections

    class OrderedCounter(Counter, OrderedDict):
        pass

    m=[list (i) for i in G.edges()]

    flat_list = [item for sublist in m for item in sublist]
    counterlist = OrderedCounter(flat_list)
    degree_sequence=sorted(sorted(counterlist.values(), reverse=True))
    degreeCount=collections.Counter(degree_sequence)
    print("degreeCount:", degreeCount)

    #deg, cnt = zip(*degreeCount.items()) #Returns the average degree of the neighborhood of each node.
    #print(deg, cnt)

    nodes = len(G) 
    count_Triangle = 0 #Initialize result 
    # Consider every possible triplet of edges in graph 
    for i in range(nodes): 
        for j in range(nodes): 
            for k in range(nodes): 
                # check the triplet if it satisfies the condition 
                if( i!=j and i !=k and j !=k and
                        G[i][j] and G[j][k] and G[k][i]): 
                    count_Triangle += 1
                    print(count_Triangle)

当我以这种方式计算三角形时，我不断收到关键错误，这是因为我知道我传递的索引不正确。我认为 G 是一个 dict 对象。想不通。

此外，如果我尝试提取上面的 deg, cnt ，我认为从中提取平均度数的解决方案，当字典为空时，我会不断收到错误。

Answer 1

用于三角形计数

• 类似字典的访问G[u][v]对图G中的边数据进行操作，因此字典G[中的键u](一般来说)不是图中的所有其他节点；尽管字典 G 中的键确实包含图中的所有节点。

• 如果您想采用这种形式的索引，您可能最好生成一个邻接矩阵，该矩阵对于 n 节点图具有 n x n 个元素。那么在 [0, n] 范围内对 i 的所有查询 A[i][j] 都将有效；如果没有边，则返回值为0。

• 另请参阅 itertools，这将使您的代码更加简洁。

for i,j,k in itertools.combinations(xrange(n), 3):
    # a generator of all unique combinations of [0,1,2,3,4]
    # this already excludes the cases where i==j, i==k j==k
    print(i,j,k)

但是要小心，因为这个包中有很多非常相似的功能。

这里有一些代码可以让您在此处获取三角形计数

import networkx as nx
import matplotlib.pyplot as plt
import itertools

T1 = []
T2 = []

n = 7
p = 0.2
reps = 1000
for r in xrange(reps):
    G = nx.gnp_random_graph(n, p)

    A = nx.adj_matrix(G);

    t = 0;
    for (i,j,k) in itertools.combinations(xrange(n), 3):
        # a generator of all unique 3-combinations of [0,1,2,...,n]
        if i==k or i==j or j==k:
            print ("Found a duplicate node!", i,j,k)
            continue # just skip it -- shouldn't happen
        if A[i,j] and A[j,k] and A[i,k]:
            t += 1
    T1.append(t);

    # let's check we agree with networkx built-in
    tr = nx.triangles(G)
    T2.append(sum(tr.values()))    

T2 = [t /3.0 for t in T2]; # divide all through by 3, since this is a count of the nodes of each triangle and not the number of triangles.

plt.figure(1); plt.clf()
plt.hist([T1, T2], 20)

在这里您可以看到三角形计数是相同的(我在 y 轴上放置了对数刻度，因为较高三角形计数的频率相当低)。

用于度数计算

看来您需要更清楚地了解要计算的程度: - 这是一个无向图，这意味着如果 u 和 v 之间存在边，那么这两个节点的度数至少应为 1。您的计算仅对边进行一次计数。

其次，您生成的图形没有很多边，特别是对于较小的图形。当 p=0.2 时，完全没有任何边的 3 节点图的比例为 51%，甚至 5 节点图也有 11% 的时间没有边。因此空列表并不表示失败。

平均度数很容易检查，可以使用图形属性:

2*G.number_of_edges() / float(G.number_of_nodes())

或内置的每节点度数计算器。

sum([d for (n, d) in nx.degree(G)]) / float(G.number_of_nodes())