《A community detection algorithm based on graph compression for large-scale social networks》论文笔记

背景

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

文章标题:《A community detection algorithm based on graph compression for large-scale social networks》论文笔记
文章作者:世间难得逍遥
文章链接:https://www.abyss.website/classify/%e8%ae%ba%e6%96%87%e7%ac%94%e8%ae%b0/%e3%80%8aa-community-detection-algorithm-based-on-graph-compression-for-large-scale-social-networks%e3%80%8b%e8%ae%ba%e6%96%87%e7%ac%94%e8%ae%b0/

许可协议: CC BY 4.0 转载请保留原文链接及作者。


暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇