基于社区节点重要性的社会网络压缩方法

北京大学学报（自然科学版）

基于社区节点重要性的社会网络压缩方法

李泓波¹,张健沛¹,杨静¹,白劲波^2,3,初妍¹,张乐君¹

1. 哈尔滨工程大学计算机科学与技术学院, 哈尔滨 150001; 2. 哈尔滨工程大学经济管理学院, 哈尔滨 150001; 3. 黑龙江工程学院计算机科学与技术学院, 哈尔滨 150050;

收稿日期:2012-05-31 出版日期:2013-01-20 发布日期:2013-01-20

Social Network Compression Based on the Importance of the Community Nodes

LI Hongbo¹, ZHANG Jianpei¹, YANG Jing¹, BAI Jinbo^2,3, CHU Yan¹, ZHANG Lejun¹

1. College of Computer Science and Technology, Harbin Engineering University, Harbin 150001; 2. School of Economics and Management, Harbin Engineering University, Harbin 150001; 3. School of Computer Science and Technology, Heilongjiang Institute of Technology, Harbin 150050;

Received:2012-05-31 Online:2013-01-20 Published:2013-01-20

摘要/Abstract

摘要： 针对目前图压缩方法中存在的时间复杂度较高、依赖先验知识设定参数、需要调节的参数过多、压缩有损、忽视网络社区结构等问题, 提出基于社区节点重要性的社会网络压缩方法。该方法由基于贪婪策略的社区发现算法(GS)和社会网络压缩算法(SNC)两部分组成。GS算法采用拓扑势理论, 不但可以实现社区发现, 而且可挖掘出社区中的重要节点。SNC算法以网络社区为压缩对象, 在保持社区间的关联关系的前提下实现了无损压缩, 并可在必要时保留社区中的重要节点或基本结构。通过实验, 对方法的可行性和有效性进行了验证。

关键词: 社会网络挖掘, 拓扑势, 节点重要性, 无损压缩, 贪婪策略

Abstract: In response to the inadequacies of current graph compression methods, such as higher time complexity, dependence on experiences to set parameters, too many parameters to adjust, compression loss, ignoring the community structure of network, a social network compression method is proposed based on the importance of the community nodes. The method include community discovery algorithm (GS) based on greedy strategy and social network compression algorithm (SNC). Adopting topological potential theory GS algorithm is not only capable of discovering communities but also capable of mining important nodes in the communities. SNC algorithm takes communities as targets, achieves lossless compression while maintaining the connections between communities, and keeps important nodes in communities or basic community structure if necessary. The feasibility and effectiveness of the method are verified in experiments.

Key words: social network mining, topology potential, importance of nodes, lossless compression, greedy strategy

中图分类号:

TP391

李泓波,张健沛,杨静,白劲波,初妍,张乐君. 基于社区节点重要性的社会网络压缩方法[J]. 北京大学学报（自然科学版）.

LI Hongbo,ZHANG Jianpei,YANG Jing,BAI Jinbo,CHU Yan,ZHANG Lejun. Social Network Compression Based on the Importance of the Community Nodes[J]. Acta Scientiarum Naturalium Universitatis Pekinensis.

[1]	刘秋慧, 张坤丽, 许鸿飞, 俞士汶, 昝红英. 助词“的”用法自动识别研究[J]. 北京大学学报（自然科学版）, 2018, 54(3): 466-474.
[2]	柯永红, 朱永福, 穗志方, 俞士汶. 基于多特征的语义角色标注一致性计算方法研究[J]. 北京大学学报（自然科学版）, 2018, 54(3): 475-480.
[3]	杨萌, 李培峰, 朱巧明. 一种基于Tree-LSTM的句子相似度计算方法[J]. 北京大学学报（自然科学版）, 2018, 54(3): 481-486.
[4]	张雨, 曾立, 邹磊. 大规模图数据的正则路径查询[J]. 北京大学学报（自然科学版）, 2018, 54(2): 236-242.
[5]	魏星, 王玮, 陈静萍, 解焱陆, 张劲松. 基于发音特征的汉语发音偏误自动标注[J]. 北京大学学报（自然科学版）, 2018, 54(2): 243-248.
[6]	林心宜, 严睿, 赵东岩. 融合词、句层级信息的抽取式摘要优化框架[J]. 北京大学学报（自然科学版）, 2018, 54(2): 229-235.
[7]	周楠, 赵悦, 李要嫱, 徐晓娜, 才旺拉姆, 吴立成. 基于瓶颈特征的藏语拉萨话连续语音识别研究[J]. 北京大学学报（自然科学版）, 2018, 54(2): 249-254.
[8]	谭亦鸣, 王明文, 李茂西. 基于翻译质量估计的神经网络译文自动后编辑[J]. 北京大学学报（自然科学版）, 2018, 54(2): 255-261.
[9]	吴焕钦, 张红阳, 李静梅, 朱俊国, 杨沐昀, 李生. 基于伪数据的机器翻译质量估计模型的训练[J]. 北京大学学报（自然科学版）, 2018, 54(2): 279-285.
[10]	吕书宁, 董志安. 利用URL-Key领域术语识别方法[J]. 北京大学学报（自然科学版）, 2018, 54(2): 262-270.
[11]	王文超, 吕学强, 张凯, 周建设. 足球赛事战报的自动写作研究[J]. 北京大学学报（自然科学版）, 2018, 54(2): 271-278.
[12]	陈玉敬, 吕学强, 周建设, 李宁. NBA赛事新闻的自动写作研究[J]. 北京大学学报自然科学版, 2017, 53(2): 211-218.
[13]	余传明, 冯博琳, 左宇恒, 陈百云, 安璐. 基于个人-群体-商户关系模型的虚假评论识别研究[J]. 北京大学学报自然科学版, 2017, 53(2): 262-272.
[14]	王博立, 史晓东, 苏劲松. 一种基于循环神经网络的古文断句方法[J]. 北京大学学报自然科学版, 2017, 53(2): 255-261.
[15]	姜杰, 夏睿. 机器学习与语义规则融合的微博情感分类方法[J]. 北京大学学报自然科学版, 2017, 53(2): 247-254.