时间戳

首页 > 解决方案 > 从 Graph 类中提取度数、平均度数

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

问题描述

有没有人试图实现一个软件来从 NetworkX 的 Graph Class 中提取度数、平均度数？我不是要求在 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)

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

此外，如果我尝试deg, cnt从上面提取我认为是获得平均学位的解决方案，当字典为空时，我会不断出错。

标签： pythonnetworkx

解决方案

用于三角形计数

  • 类似dict的访问G[u][v]对图中的边缘数据进行操作G，因此dictG[u]中的键不是（通常）图中的所有其他节点；尽管 dict 中的键G确实包括图中的所有节点。

  • 如果你想追求这种形式的索引，你可能最好生成一个邻接矩阵，它有 nxn 个元素用于 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())

推荐阅读