背景

本人毕设题目为《基于社区发现的最大化影响力分析》，在导师和师兄的指导下，阅读了本论文的第一部分——社交网络图的压缩（即该论文的算法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 – 已下载18次 – 156.18 KB