如何统计NetworkX二分图中的正方形（闭合4路径）数量

实现方法 #

可以直接基于NetworkX内置的nx.bipartite.square_clustering函数计算总正方形（闭合4路径）数量，无需自行实现遍历逻辑，效率有保障。

原理说明 #

• 每个正方形会被它包含的4个顶点各计数1次
• 单个节点u的正方形聚类系数公式为：C4(u) = 包含u的正方形数量 / C(deg(u), 2)，其中C(deg(u), 2)是u的邻居两两组合的总数，计算式为deg(u)*(deg(u)-1)/2
• 推导可得包含节点u的正方形数量为：C4(u) * deg(u) * (deg(u)-1) / 2
• 所有节点的该值求和后除以4，就是整张图的总正方形数（抵消每个正方形的4次重复计数）

示例代码 #

import networkx as nx

# 生成示例二分图
B = nx.bipartite.random_graph(100, 100, .05)

# 计算总正方形数
c4_dict = nx.bipartite.square_clustering(B)
total = sum(c4 * B.degree(node) * (B.degree(node)-1) / 2 for node, c4 in c4_dict.items()) / 4

print(f"闭合4路径总数量：{int(total)}")

内容的提问来源于stack exchange，提问作者user16733461