一种基于图压缩的重叠社区发现算法

doi:10.12068/j.issn.1005-3026.2015.11.006

东北大学学报:自然科学版 ›› 2015, Vol. 36 ›› Issue (11): 1543-1547.DOI: 10.12068/j.issn.1005-3026.2015.11.006

一种基于图压缩的重叠社区发现算法

赵宇海，印莹，王雪

(东北大学信息科学与工程学院，辽宁沈阳110819)

收稿日期:2015-03-30 修回日期:2015-03-30 出版日期:2015-11-15 发布日期:2015-11-10
通讯作者: 赵宇海
作者简介:赵宇海(1975-)，男，辽宁辽阳人，东北大学副教授.
基金资助:
国家自然科学基金资助项目(61272182); 中央高校基本科研业务费专项资金资助项目(N130504001)；国家自然科学基金重点资助项目(61332014).

A Graph Compression Based Overlapping Communities Detection Algorithm

ZHAO Yu-hai， YIN Ying， WANG Xue

School of Information Science & Engineering， Northeastern University， Shenyang 110819， China.

Received:2015-03-30 Revised:2015-03-30 Online:2015-11-15 Published:2015-11-10
Contact: ZHAO Yu-hai
About author:-
Supported by:
-

摘要/Abstract

摘要： 为提高单机处理复杂网络规模的能力，提出一种新的重叠社区发现算法.首先，通过基于图压缩的社区结构表示模型(压缩社区图)，对网络进行无损压缩；然后，在压缩社区图上基于种子迭代的思想，通过不断优化社区适应度函数将种子扩展成社区；最后，将相似度高的社区进行合并，得到最终的重叠社区结果.由于压缩后的凝聚图大大降低了待处理的网络规模，并能在一定程度上减少重复计算，该方法可以大大提高计算效率和单机处理的网络规模.

关键词: 重叠社区, 社会网络, 数据挖掘, 聚类, 图压缩

Abstract: To improve the capacity of single machine to handle complex network，overlapping communities detection algorithm was proposed. First， a graph compression based social network model， namely agglomerative graph， was introduced， which was a lossless compression to the original network. Then， inspired by the idea of iteration based on seeds， the selected seeds were expanded to the communities by optimizing the proposed community fitness function iteratively. Finally， the communities of high similarity with each other were merged to get the final results. Since the scale of the network to be dealt is significantly reduced， and some redundant computations are avoided， the proposed algorithm is of high efficiency.

Key words: overlapping community, social network, data mining, clustering, graph compression

中图分类号:

TP311

赵宇海，印莹，王雪. 一种基于图压缩的重叠社区发现算法[J]. 东北大学学报:自然科学版, 2015, 36(11): 1543-1547.

ZHAO Yu-hai， YIN Ying， WANG Xue. A Graph Compression Based Overlapping Communities Detection Algorithm[J]. Journal of Northeastern University Natural Science, 2015, 36(11): 1543-1547.

参考文献

[1]Aggarwal C C.Social network data analytics［M］.Berlin:Springer-Verlag，2011:1-30.
[2]Gergely P，Imre D，Illes F，et al.Uncovering the overlapping community structure of complex networks in nature and society［J］.Nature，2005，435:814-818.
[3]Lim S，Ryu S，Kwon S，et al.LinkSCAN:overlapping community detection using the link-space transformation［C］// IEEE 30th International Conference on Data Engineering.Chicago，2014:292-303.
[4]Cui W，Xiao Y，Wang H，et al.Online search of overlapping communities［C］// Proceedings of the ACM SIGMOD International Conference on Management of Data.New York，2013:277-288.
[5]陈东明，徐晓伟.一种基于广度优先搜索的社区发现方法［J］.东北大学学报:自然科学版，2010，31(3):346-349.(Chen Dong-ming，Xu Xiao-wei.A community discovery method based on breadth-first search［J］.Journal of Northeastern University:Natural Science，2010，31(3):346-349.)
[6]Fortunato S.Community detection in graphs［J］.Physics Reports，2010，486(3/4/5):75-174.
[7]Shen H，Cheng X，Cai K，et al.Detect overlapping and hierarchical community structure in networks［J］.Physics A:Statistical Mechanics and its Application，2009，388(8):1706-1712.
[8]Lee C，Reid F，McDaid A，et al.Detecting highly overlapping community structure by greedy clique expansion［C］// The 4th SNA-KDD Workshop on Social Network Mining and Analysis.Washington D C，2010:1-10.
[9]Evans T S，Lambiotte R.Line graphs，link partitions，and overlapping communities［J］.Physical Review E，2009，80(1):100-105.
[10]Lancichinetti A，Fortunato S，Kertesz J.Detecting the overlapping and hierarchical community structure of complex networks［J］.New Journal of Physics，2009，11(3):15-33.
[11]Leskover J.Stanford large network dataset collection［EB/OL］.(2014-06-01)［2015-08-14］.http://snap.stanford.edu/data.
[12]Lázár A，bel D，Vicsek T.Modularity measures of networks with overlapping communities［J］.Europhysics Letters，2010，90(1):18-31.(上接第1538页)
[5]Ding H，Lv J J.Comparison study of two commonly used methods for envelope fitting of empirical mode decomposition［C］//International Congress on Image and Signal Processing.Piscataway:IEEE，2012:1875-1878.
[6]Chu P C，Fan C W，Huang N.Derivative-optimized empirical mode decomposition for the Hilbert-Huang transform［J］.Journal of Computational and Applied Mathematics，2014，259:57-64.
[7]Chen Q H，Huang N，Riemenschneider S，et al.A B-spline approach for empirical mode decompositions［J］.Advances in Computational Mathematics，2006，24(1/2/3/4):173-175.
[8]Qin S R，Zhong Y M.A new envelope algorithm of Hilbert-Huang transform［J］.Mechanical Systems and Signal Processing，2006，20(8):1941-1952.
[9]Xu Z G，Huang B X，Li K W.An alternative envelope approach for empirical mode decomposition［J］.Digital Signal Processing，2010，20(1):77-84.
[10]朱伟芳，赵鹤鸣，陈小平.一种最小长度约束的EMD包络拟合方法［J］.电子学报，2012，40(9):1909-1912.(Zhu Wei-fang，Zhao He-ming，Chen Xiao-ping.A least length constrained envelope approach for EMD［J］.Acta Electronica Sinica，2012，40(9):1909-1912.)
[11]Higham D J.Monotonic piecewise cubic interpolation，with applications to ODE plotting［J］.Journal of Computational and Applied Mathematics，1992，39(3):287-294.

[1]	耿蓉，张昭，牛天水，王宇飞. 基于改进蚁群算法的天基资源调度研究与仿真[J]. 东北大学学报（自然科学版）, 2023, 44(2): 168-176.
[2]	马淑华，尤海荣，唐亮，何平. 一种自适应的密度峰值聚类算法[J]. 东北大学学报（自然科学版）, 2022, 43(6): 761-768.
[3]	刘军，代福成，辛宁. 基于多目标优化的虚拟机部署策略[J]. 东北大学学报（自然科学版）, 2022, 43(5): 609-617.
[4]	李建华，朱泽阳，徐礼胜，孙国哲. 基于深度嵌入聚类的ICU患者生理数据缺失插补[J]. 东北大学学报（自然科学版）, 2022, 43(5): 639-645.
[5]	郑艳，姜源祥. 基于特征融合的说话人聚类算法[J]. 东北大学学报（自然科学版）, 2021, 42(7): 952-959.
[6]	毛亚纯，伏雨文，曹旺，赵占国. 基于无人机点云数据的露天采场矿车提取方法[J]. 东北大学学报（自然科学版）, 2021, 42(6): 842-849.
[7]	王述红，朱宝强，王鹏宇. 模拟退火聚类算法在结构面产状分组中的应用[J]. 东北大学学报:自然科学版, 2020, 41(9): 1328-1333.
[8]	司方远，韩英华，赵强，汪晋宽. 基于AP-LOF离群组检测的配电网连接验证[J]. 东北大学学报:自然科学版, 2020, 41(8): 1070-1074.
[9]	刘馨，张卫军，石泉，周乐. 基于数据挖掘与清洗的高炉操作参数优化[J]. 东北大学学报:自然科学版, 2020, 41(8): 1153-1160.
[10]	郭甲腾，张紫瑞，毛亚纯，刘善军. 基于三维点云的岩体结构面自动分类与参数计算[J]. 东北大学学报:自然科学版, 2020, 41(8): 1161-1166.
[11]	吴超，李元辉，徐帅，戴星航. 地下工程岩体节理迹长统计下限值的确定方法[J]. 东北大学学报:自然科学版, 2020, 41(8): 1167-1173.
[12]	李晨，张家伟，张昊，汪茜. 基于生成对抗网络的低分化宫颈癌病理图像分类[J]. 东北大学学报:自然科学版, 2020, 41(7): 1054-1061.
[13]	黄川，胡平，连静. 一种基于车载信号还原机动车道3D地图的大数据方法[J]. 东北大学学报:自然科学版, 2020, 41(6): 771-777.
[14]	于震梁，孙志礼，张毅博，王健. 一种自适应PC-Kriging模型的结构可靠性分析方法[J]. 东北大学学报:自然科学版, 2020, 41(5): 667-672.
[15]	陈东明，袁泽枝，黄新宇，王冬琦. 时态网络节点相似性度量及链路预测算法[J]. 东北大学学报:自然科学版, 2020, 41(1): 29-35.

一种基于图压缩的重叠社区发现算法

A Graph Compression Based Overlapping Communities Detection Algorithm

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价