A Graph Compression Based Overlapping Communities Detection Algorithm

doi:10.12068/j.issn.1005-3026.2015.11.006

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

CLC Number:

TP311

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.

References

[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]	GENG Rong， ZHANG Zhao， NIU Tian-shui， WANG Yu-fei. Research and Simulation of Space-based Resource Scheduling Based on Improved Ant Colony Algorithm [J]. Journal of Northeastern University(Natural Science), 2023, 44(2): 168-176.
[2]	MA Shu-hua， YOU Hai-rong， TANG Liang， HE Ping. An Adaptive Density Peak Clustering Algorithm [J]. Journal of Northeastern University(Natural Science), 2022, 43(6): 761-768.
[3]	LIU Jun， DAI Fu-cheng， XIN Ning. Virtual Machine Placement Strategy Based on Multi-objective Optimization [J]. Journal of Northeastern University(Natural Science), 2022, 43(5): 609-617.
[4]	LI Jian-hua， ZHU Ze-yang， XU Li-sheng， SUN Guo-zhe. Interpolation of Missing Physiological Data of ICU Patients Based on Deep Embedded Clustering [J]. Journal of Northeastern University(Natural Science), 2022, 43(5): 639-645.
[5]	ZHENG Yan， JIANG Yuan-xiang. Speaker Clustering Algorithm Based on Feature Fusion [J]. Journal of Northeastern University(Natural Science), 2021, 42(7): 952-959.
[6]	MAO Ya-chun， FU Yu-wen， CAO Wang， ZHAO Zhan-guo. Extraction Method of Open Pit Mine Car Based on UAV Point Cloud Data [J]. Journal of Northeastern University(Natural Science), 2021, 42(6): 842-849.
[7]	HAN Dong-hong， ZHANG Hong-liang， ZHU Shuai-wei， QI Xiao-long. Sentiment Community Detection Algorithm for Sina Weibo [J]. Journal of Northeastern University(Natural Science), 2021, 42(1): 21-31.
[8]	WANG Shu-hong， ZHU Bao-qiang， WANG Peng-yu. Application of Simulated Annealing Clustering Algorithm in Grouping of Discontinuity Orientation [J]. Journal of Northeastern University Natural Science, 2020, 41(9): 1328-1333.
[9]	WANG Xin， WANG Jing， LI Jin-feng. Risk Assessment of Social Networking Recruitment Based on Bayesian Network [J]. Journal of Northeastern University Natural Science, 2020, 41(9): 1356-1362.
[10]	SI Fang-yuan， HAN Ying-hua， ZHAO Qiang， WANG Jin-kuan. Verification of Distribution Network Connectivity Based on AP-LOF Outlier Group Detection [J]. Journal of Northeastern University Natural Science, 2020, 41(8): 1070-1074.
[11]	LIU Xin， ZHANG Wei-jun， SHI Quan， ZHOU Le. Operation Parameters Optimization of Blast Furnaces Based on Data Mining and Cleaning [J]. Journal of Northeastern University Natural Science, 2020, 41(8): 1153-1160.
[12]	GUO Jia-teng， ZHANG Zi-rui， MAO Ya-chun， LIU Shan-jun. Automatic Discontinuity Classification and Parameter Calculation from Rock Mass 3D Point Cloud [J]. Journal of Northeastern University Natural Science, 2020, 41(8): 1161-1166.
[13]	LI Chen， ZHANG Jia-wei， ZHANG Hao， WANG Qian. Generative Adversarial Networks Based Pathological Images Classification of Poorly Differentiated Cervical Cancer [J]. Journal of Northeastern University Natural Science, 2020, 41(7): 1054-1061.
[14]	YU Zhen-liang， SUN Zhi-li， ZHANG Yi-bo， WANG Jian. A Structural Reliability Analysis Method Based on Adaptive PC-Kriging Model [J]. Journal of Northeastern University Natural Science, 2020, 41(5): 667-672.
[15]	CHEN Dong-ming， YUAN Ze-zhi， HUANG Xin-yu， WANG Dong-qi. Node Similarity Measurement and Link Prediction Algorithm in Temporal Networks [J]. Journal of Northeastern University Natural Science, 2020, 41(1): 29-35.