python - 计算图中每个节点的聚类
问题描述
谁能帮助我如何在不使用 python 库的情况下计算图中每个节点的聚类?一般公式是2.0 * E / (V *(V - 1))
。代码(无法正常工作):
def clustering():
clust = []
print(vertexDegree)
E = len(list1)
for i in vertexDegree:
if i <= 1:
clust.append(0)
else:
clust.append(2.0 * E / (i *(i - 1)))
vertex = 1
for i in clust:
print("Vertex ", vertex, "have clustering: ", i)
vertex += 1
print(clust)
list1是连接节点的列表 -[[1, 2], [3, 5], [2, 4]]
E是所有连接(边)的数量
V是邻居(节点)之间可能的连接(边)的数量。
图形由字典 - 表示{1: [2], 2: [1, 4], 3: [5], 4: [2], 5: [3]}
,计算vertexDegree并保存在列表中 -[1, 2, 1, 1, 1]
解决方案
将 networkx 的代码转换为使用基于字典的图形
Networkx 代码:如何使用 Networkx 在 Python 中计算图中每个节点的聚类系数
代码
def clustering(data, undirected = True):
"""
Computes clustering coefficient for each
node in graph g
"""
def has_edge(n1, n2):
""" Helper function
True if n1 has edge to n2 or n2 has edge to n1
"""
# n1 neighbors
neighbours = g.get(n1, [])
if n2 in neighbours:
return True
# n2 neighbors
neighbours = g.get(n2, [])
if n2 in neighbours:
return True
return False
def edges_to_dic(edges, undirected = True):
" Generates graph dictionary from edges "
res = {}
for v1, v2 in edges:
res.setdefault(v1, set())
res[v1].add(v2)
if undirected:
res.setdefault(v2, set())
res[v2].add(v1)
return res
if isinstance(data, list):
# list of edges
g = edges_to_dic(data, undirected)
else:
g = data
result = {}
for node in g:
# Iterate over nodes of g
neighbours = g[node]
n_neighbors = len(neighbours)
n_links = 0
if n_neighbors > 1:
for node1 in neighbours:
for node2 in neighbours:
if has_edge(node1,node2):
n_links += 1
n_links /= 2 #because n_links is calculated twice
result[node] = 2*n_links/(n_neighbors*(n_neighbors-1))
else:
result[node] = 0
return result
用法
与字典一起使用
g = {1: [2], 2: [1, 4], 3: [5], 4: [2], 5: [3]}
print(clustering(g))
# Output: {1: 0, 2: 0.0, 3: 0, 4: 0, 5: 0}
适用于边缘
edges = [[1, 2], [3, 5], [2, 4]]
print(clustering(edges))
# Output: {1: 0, 2: 0.0, 3: 0, 4: 0, 5: 0}
解释
所有系数都为零的原因是:
- 节点 1、3、4、5 只有一个邻居,因此它们的系数为零
- 节点 2 有邻居 [1, 4] 但这些邻居没有连接,因此系数为零。
测试 源
def show_results(edges, text):
" Show results for set of test cases "
print(text)
print('\tUndirected: ', clustering(edges))
print('\tDirected', clustering(edges, undirected = False))
tests = [
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]], # C = 1
[[1, 2], [1, 3], [1, 4], [3, 4]], # C = 1/3
[[1, 2], [1, 3], [1, 4]] # C = 0
]
texts = [
"Case C = 1",
"Case C = 1/3",
"Case C = 0"
]
for edges, text in zip(tests, texts):
show_results(edges, text)
输出
Case C = 1
Undirected: {1: 1.0, 2: 1.0, 3: 1.0, 4: 1.0}
Directed {1: 0.5, 2: 0.5, 3: 0}
Case C = 1/3
Undirected: {1: 0.3333333333333333, 2: 0, 3: 1.0, 4: 1.0}
Directed {1: 0.16666666666666666, 3: 0}
Case C = 0
Undirected: {1: 0.0, 2: 0, 3: 0, 4: 0}
Directed {1: 0.0}
测试图
推荐阅读
- batch-file - 通过网络使用批处理重命名文件
- c++ - 错误:使用类模板“blocked_range”需要模板参数
- java - Android List<> 保存与前一个对象相等的新对象
- html - CSS 仅格式化 div 宽度的一部分
- python - 使用字符串输入和列表推导初始化对象列表 - input().split() 导致值错误
- python - 项目的 Virtualenv 开始为 sklearn 报错
- react-native - 如何防止在本机反应中多次点击按钮?
- ansible - Ansible URI 在第一次运行时在 Gitlab CI 管道中不起作用
- xml - 通过 XSLT 1.0 向 XML 添加新元素,但没有 xmlns
- python - Python Apscheduler 不停止函数执行