graph - 图平均聚类系数公式

Question

一个图在一个环中包含 N 个节点。如果 n 是每个节点的位置，则每个节点都连接到位置 n-2、n-1、n+1、n+2 上的 4 个其他节点。

我找到了计算每个节点的聚类系数的公式：

在哪里

• Nv 是节点 v 的邻居之间的链接数，
• Kv 是节点 v 的邻居数

此外，该图应包括 N/2 个随机链接：

该图的平均聚类系数等于 0.47777777777777786。

我试图通过使用 NetworkX 库进行计算来理解，经过 100000 次运行后，平均聚类系数的平均值如下：

• 0.6836288481928767 对于 N=8
• 0.4970500101826404 对于 N=12
• 0.4003510099434803 对于 N=24

但是，我不知道如何使用公式来计算。

当向图中添加 N/2 个随机链接时，上述公式如何变化？

编码：

import networkx as nx 
from networkx.drawing.nx_agraph import graphviz_layout
import random

def getClusteringCoefficient(N, show_graph = False):

    G = nx.Graph()

    def next(node_from, diff):
        node_from = (node_from+diff)%N
        if(node_from==0):
            node_from = N
        return node_from

    for node_from in range(1, N+1):
        node_to_1 = next(node_from, 1)
        node_to_2 = next(node_from, 2)
        G.add_weighted_edges_from([(node_from, node_to_1, 1)])
        G.add_weighted_edges_from([(node_from, node_to_2, 1)])
    
    count=0
    random_connections = int(N/2)
    while(True):
        node_from = random.randint(1,N)
        not_neighbors = list(nx.non_neighbors(G,node_from))
        if(len(not_neighbors)==0):
            continue
        node_to_pos = random.randint(0,len(not_neighbors)-1)
        node_to = not_neighbors[node_to_pos]
        G.add_weighted_edges_from([(node_from, node_to, 1)])
        count=count+1
        if(count==random_connections):
            break;
        
    if(show_graph):
        pos=graphviz_layout(G, prog='circo')
        nx.draw(G, pos, with_labels=True)

    return nx.average_clustering(G)

total_coefficient = 0
for i in range(1,100000):
    coefficient  = getClusteringCoefficient(12)
    total_coefficient = total_coefficient+ coefficient
    
print(total_coefficient/i)

标签： graph