《计算机应用研究》|Application Research of Computers

基于随机聚类采样算法的复杂网络社团探测

Detecting community structure using stochastic cluster sampling algorithm

免费全文下载 (已被下载 次)  
获取PDF全文
作者 蔡君,余顺争
机构 1.广东技术师范学院 电子与信息学院,广州 510665;2.中山大学 电子与通信工程系,广州 510275
统计 摘要被查看 次,已被下载
文章编号 1001-3695(2013)12-3560-04
DOI 10.3969/j.issn.1001-3695.2013.12.010
摘要 根据网络节点的局部拓扑信息构建稀疏相似网络。基于稀疏相似网络, 提出了一种改进后的随机聚类采样算法对网络社团进行探测。在人工和真实网络上, 将算法与未改进的随机聚类采样算法以及几种典型的社团探测算法进行了准确率和时间复杂度的比较。实验结果表明, 该方法在时间复杂度上具有明显的优势, 并且具有较好的准确率。
关键词 复杂网络;社团探测;随机聚类采用;相似性
基金项目 国家自然科学基金资助项目(61202271,61272381)
国家“863”计划基金资助项目(2007AA01Z449)
国家自然科学基金—广东联合基金重点资助项目(U0735002)
广东省自然科学基金资助项目(S2013040014339)
本文URL http://www.arocmag.com/article/01-2013-12-010.html
英文标题 Detecting community structure using stochastic cluster sampling algorithm
作者英文名 CAI Jun, YU Shun-zheng
机构英文名 1. School of Electronic & Information, Guangdong Polytechnic Normal University, Guangzhou 510665, China; 2. Dept. of Electronic & Communication Engineering, Sun Yat-Sen University, Guangzhou 510275, China
英文摘要 Firstly, this paper constructed a sparse similarity network based on the node's local information. Then, proposed an algorithm of detecting community structure using the improved stochastic cluster sampling based on the sparse similarity network. In the artificial and real networks, it compared the proposed algorithm with the no improved stochastic cluster sampling and several typical algorithms detecting community structure in time complexity and accuracy. The experimental results show that the method has obvious advantages in the time complexity and it has better accuracy rate than other algorithms.
英文关键词 complex network; community detecting; stochastic cluster sampling; similarity
参考文献 查看稿件参考文献
  [1] PORTER M A, ONNELA J P, MUCHA P J. Communities in networks[J] . Notices of the AMS, 2009, 56(9):1082-1097.
[2] POTHEN A, SIMON H D, LIOU K P. Partitioning sparse matrices with eigenvectors of graphs[J] . SIAM Jounal Matrix Analysis Applications, 1990, 11(3):430-452.
[3] CAPOCCI A, SERVEDIO V D P, CALDARELLI G, et al. Detecting communities in large networks[J] . Physical A, 2005, 352(2-4):669-676.
[4] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J] . Proceedings of the National Academy of Sciences of the United States of America, 2002, 99(12):7821-7826.
[5] FORTUNATO S, LATORA V, MARCHIORI M. Method to find community structures based on information centrality[J] . Physical Review E, 2004, 70(5):0561041-05610413.
[6] NEWMAN M E J. Fast algorithm for detecting community structure in networks[J] . Physical Review E, 2004, 69(6):0661331-0661335.
[7] GUIMERA R, AMARAL L. Functional cartography of complex metabolic networks[J] . Nature, 2005, 433(7028):895-900.
[8] 戴飞飞, 唐普英. 基于PSO微粒群算法的复杂网络社区结构发现[J] . 计算机工程与应用, 2008, 44(22):56-58.
[9] SANTO F. Community detection in graphs[J] . Physics Reports, 2010, 486(3-5):75-174. [10] 杨博, 刘大有, LIU Ji-ming, 等. 复杂网络聚类方法[J] . 软件学报, 2009, 20(1):54-66.
[11] LU Lin-yuan, JIN Ci-hang, ZHOU Tao. Similarity index based on local paths for link prediction of complex network[J] . Physical Review E, 2009, 80(4):0461221-0461229.
[12] KATZ L. A new status index derived from sociometric analysis[J] . Psychometrika, 1953, 18(1):39-43.
[13] LEICHT E A, HOLME P, NEWMAN M E J. Vertex similarity in networks[J] . Physical Review E, 2006, 73(2):0261201-02612010.
[14] SALTON G, McGILL M J. Introduction to modern information retrieval[M] . New York:McGraw-Hill Inc. , 1983.
[15] ADAMIC L A, ADAR E. Friends and neighbors on the Web[J] . Social Networks, 2003, 25(3):211-230.
[16] ZHOU Tao, LU Lin-yuan, ZHANG Yi-cheng. Predicting missing links via local information[J] . The European Physical Journal B, 2009, 71(4):623-630.
[17] PAN Ying, LI De-hua, LIU Jian-guo, et al. Detecting community structure in complex networks via node similarity[J] . Physica A:Statistical Mechanics and its Applications, 2010, 389(14):2849-2857.
[18] BARBU A, ZHU Song-chun. Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities[J] . IEEE Trans on Pattern Analysis and Machine Intelligence, 2005, 27(8):1239-1253.
[19] DANON L, DíAZ-GUILERA A, DUCH J, et al. Comparing community structure identification[J] . Journal of Statistical Mechanics:Theory and Experiment, 2005, 2005(9):2-10.
[20] NEWMAN M E J, GIRVAN M. Finding and evaluating community structure in networks[J] . Physical Review E, 2004, 69(2):0261131-02611315.
[21] ZACHARY W W. An information flow model for conflict and fission in small groups[J] . Journal of Anthropological Research, 1977, 33(4):452-473.
[22] GIRVAN M, NEWMAN M E J. Community structure in social and biological networks[J] . Proceedings of National Academy of Science of the United States of America, 2002, 99(12):7812-7826.
[23] GUIMERA R, DANON L, DIAZ-GUILERA A, et al. Self-similar community structure in a network of human interactions[J] . Physical Review E, 2003, 68(6):0651031-0651034.
收稿日期
修回日期
页码 3560-3563
中图分类号 TP393
文献标志码 A