背景
本人毕设题目为《基于社区发现的最大化影响力分析》,在导师和师兄的指导下,阅读了本论文的第一部分——社交网络图的压缩(即该论文的算法1)
对于一个庞大的社交网络关系图,如果直接在原图上运行算法,虽然结果可能会最为精确,但是可能会导致非常高的时间与空间复杂度,本篇论文中提出社交网络图压缩算法,在尽可能保证原图社区结构的基础上,压缩网络图,使算法的时间与空间复杂度进一步降低,为后面的算法做了铺垫。
论文原文
Graph compression
伪代码
压缩示例
代码实现
import networkx as nx
import matplotlib.pyplot as plt
def compress_graph(G):
# 初始化度为1和度为2的顶点集合D1,D2
d_1 = [node for node in G.nodes if G.degree(node) == 1]
d_2 = [node for node in G.nodes if G.degree(node) == 2]
# 重复合并度为1和度为2的步骤,直到两个集合为空
while True:
if not d_1 and not d_2:
break
# 合并度为1的节点到他的邻居节点
if d_1:
for node in d_1:
neighbor = list(G.neighbors(node))[0]
nx.contracted_nodes(G, neighbor, node, self_loops=False, copy=False)
# 压缩节点后,会使邻居节点的度--,因此要重新判断邻居的度并把它放到对应集合
if G.degree(neighbor) == 1:
if neighbor in d_2:
d_2.remove(neighbor)
d_1.append(neighbor)
elif G.degree(neighbor) == 2:
d_2.append(neighbor)
d_1.remove(node)
# 合并度为2的节点到他的邻居节点
if d_2:
for node in d_2:
neighbors = list(G.neighbors(node))
neighbor_1, neighbor_2 = neighbors[0], neighbors[1]
# 判断是否为桥节点
if G.has_edge(neighbor_1, neighbor_2):
# 不是桥节点则更新权值,并进行合并
G[neighbor_1][neighbor_2]['weight'] += G[node][neighbor_1]['weight'] * G[node][neighbor_2][
'weight'] / 2
# 哪个邻居节点的度大,那么该节点就压缩进哪个节点
if G.degree(neighbor_1) >= G.degree(neighbor_2):
nx.contracted_nodes(G, neighbor_1, node, self_loops=False, copy=False)
else:
nx.contracted_nodes(G, neighbor_2, node, self_loops=False, copy=False)
# 压缩节点后,会使邻居节点的度--,因此要重新判断邻居的度并把它放到对应集合
if G.degree(neighbor_1) == 1:
if neighbor_1 in d_2:
d_2.remove(neighbor_1)
d_1.append(neighbor_1)
elif G.degree(neighbor_1) == 2:
d_2.append(neighbor_1)
if G.degree(neighbor_2) == 1:
if neighbor_2 in d_2:
d_2.remove(neighbor_2)
d_1.append(neighbor_2)
elif G.degree(neighbor_2) == 2:
d_2.append(neighbor_2)
# 桥节点或者已经处理完的非桥节点都应该从集合删除
d_2.remove(node)
return G
# 读入数据集
# 读.gml文件,主键为id
# g = nx.read_gml("DataSet/karate.gml", label='id')
# 设置所有边权值为1
# nx.set_edge_attributes(g, 1, 'weight')
# 读.txt文件
g = nx.read_weighted_edgelist("DataSet/email.txt")
# 读.net文件
# g = nx.Graph(nx.read_pajek("DataSet/PGPgiantcompo.net"))
# 删除无向图的自环
g.remove_edges_from(nx.selfloop_edges(g))
# 压缩网络图
cg = compress_graph(g)
# 绘制网络对比图
fig, (ax1, ax2) = plt.subplots(ncols=2, figsize=(20, 10))
nx.draw(g, with_labels=True, ax=ax1)
ax1.set_title('Original Graph')
nx.draw(cg, with_labels=True, ax=ax2)
ax2.set_title('Compressed Graph')
plt.show()
# 打印网络图详细信息
print(nx.info(g))
print(nx.info(cg))
运行结果
email数据集
PGPgiantcompo数据集
可以看出压缩效果是非常不错的!!!
数据集下载
下载 “email数据集”
email.txt – 已下载284次 – 156.18 KB