计算机科学 ›› 2019, Vol. 46 ›› Issue (12): 45-55.doi: 10.11896/jsjkx.190700051
尹欣红, 赵世燕, 陈晓云
YIN Xin-hong, ZHAO Shi-yan, CHEN Xiao-yun
摘要: 复杂网络是从大量现实存在的复杂系统中抽象得到的,网络的整体功能体现在网络中节点间的相互作用上,社团结构是其关键性结构特征。社团对应于系统的功能模块,提取网络的功能模块有助于深层探究复杂网络的内部规律,从复杂网络中检测社团结构具有重要的理论研究意义和实用价值。因此,很多研究者对社团检测进行了研究,进而提出了很多社团检测算法,如基于模块度优化的社团检测算法、基于标签传播的社团检测算法、基于随机游走的社团检测算法等。在对这些算法进行充分研究的基础上,通过模拟随机游走的过程,结合信号传播过程中随着传播距离的增大,信号量会缓慢衰减的思想,提出了一种带偏置的信号传播机制的随机游走的社团检测算法。该算法从网络中选取一个节点作为信号源,随机选择与其相邻的节点作为下一跳节点,将衰减后的信号量传递到该节点,依次迭代并传递信号。考虑到信号的衰减,为每条边设置偏置,对信号传播过程进行限定。通过模拟信号的传播,将网络的每个顶点作为信号源来重复这一过程,得到传播矩阵。然后,为每个顶点添加自环,并结合邻接矩阵以及顶点间的相似性,形成具有新属性的相似性矩阵。根据新属性矩阵和传播矩阵为每个顶点构造属性。最后,使用k-means算法进行聚类,得到高质量的社团结构。为了验证该方法的性能,在10个实际网络数据集以及不同规模的人工合成网络上进行实验。实验结果充分证明,所提算法能够从网络中提取出高质量的社团结构,从而有效地为社团检测领域提供依据。
中图分类号:
[1]ZACHARY W W.An information flow model for conflict and fission in small groups [J].Journal of Anthropological Research,1977,33(4):452-473.[2]LEI X J,WANG F,WU F X,et al.Protein complex identification through markov clustering with firefly algorithm on dynamicproteinprotein interaction networks[J].Information Sciences,2016,329(6):303-316.[3]ATAY Y,KOC I,BABAOGLU I,et al.Community detection from biological and social networks:A comparative analysis of metaheuristic algorithms [J].Applied Soft Computing,2017,50:194-211.[4]FORTUNATO S,HRIC D.Community detection in networks:a user guide [J].Physics Reports,2016,659:1-44.[5]NEWMAN M E.The structure of scientific collaboration networks [J].Proceedings of the National Academy of Sciences of the United States of America,2001,98(2):404-409.[6]MARK E J N,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.[7]SINGH A,HUMPHRIES M D .Finding communities in sparse networks [J].Scientific Reports,2015,5(1):8828.[8]LEWIS A C F,JONES N S,PORTER M A,et al.The function of communities in protein interaction networks at multiple scales [J].BMC Systems Biology,2010,4(1):100.[9]BEDI P,SHARMA C.Community detection in social networks [J].Wiley Interdisciplinary Reviews:Data Mining and Know-ledge Discovery,2016,6(3):115-135.[10]GIRVAN M,NEWMAN M E J.Community structure in social and biological networks[J].Proceedings of the National Academy of Sciences,2002,99(12):7821-7826.[11]KERNIGHAN B W,LIN S.An efficient heuristic procedure for partitioning graphs [J].The Bell System Technical Journal,1970,49(2):291-307.[12]FIEDLER M.Laplacian of graphs and algebraic connectivity [J].Banach Center Publications,1989,25(1):57-70.[13]URSCHEL J C,ZIKATANOV L T.Spectral bisection of graphs and connectedness [J].Linear Algebra and its Applications,2014,449:1-16.[14]DONATH W E,HOFFMAN A J.Lower bounds for the partitioning of graphs [C]//Selected Papers of Alan J Hoffman:With Commentary.World Scientific,2003:437-442.[15]XU Y,ZHUANG Z,LI W M,et al.Effective community division based on improved spectral clustering [J].Neurocomputing,2018,279:54-62.[16]GUI C,ZHANG R S,HU R J.Guoming Huang,Jiaxuan Wei.Overlapping communities detection based on spectral analysis of line graphs [J].Physica A:Statistical Mechanics and its Applications,2018,498:50-65.[17]NEWMAN M E J.Modularity and community structure in networks [J].Proceedings of the National Academy of Sciences,2006,103(23):8577-8582.[18]DUCH J,ARENAS A.Community detection in complex net- works using extremal optimization [J].Physical Review E,2005,72(2):027104.[19]GUIMERA R,AMARAL L A N.Functional cartography of complex metabolic networks [J].Nature,2005,433(7028):895.[20]GUERRERO M,MONTOYA F G,BAÑOS R,et al.Adaptive community detection in complex networks using genetic algorithms [J].Neurocomputing,2017,266:101-113.[21]SAID A,ABBASI R A,MAQBOOL O,et al.Cc-ga:a clustering coefficient based genetic algorithm for detecting communities in social networks[J].Applied Soft Computing,2018,63:59-70.[22]DAMICD,ALOISE D,MLADENOVICN.Ascent-descent variable neighborhood decomposition search for community detection by modularity maximization [J].Annals of Operations Research,2019,272(1/2):273-287.[23]NEWMAN M E.Fast algorithm for detecting community structure in networks [J].Phys Rev E Stat Nonlin Soft Matter Phys,2004,69(6 Pt 2):066133.[24]BLONDEL V D,GUILLAUME J L,LAMBIOTTE R,et al. Fast unfolding of communities in large networks [J].Journal of Statistical Mechanics:Theory and Experiment,2008,2008(10):P10008.[25]TABRIZI S A,SHAKERY A,Asadpour M,et al.Personalized pagerank clustering:A graph clustering algorithm based on random walks [J].Physica A:Statistical Mechanics and its Applications,2013,392(22):5772-5785.[26]AKTUNC R,TOROSLU I H,OZER M,et al.A dynamic modularity based community detection algorithm for large-scale networks:Dslm [C]//2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM).IEEE,2015:1177-1183.[27]CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks [J].Physical Review E,2004,70(6):066111.[28]DANON L,DÍAZ-GUILERA A,ARENAS A.The effect of size heterogeneity on community identification in complex networks [J].Journal of Statistical Mechanics:Theory and Experiment,2006,2006(11):P11010.[29]WAKITA K,TSURUMI T.Finding community structure in mega-scale social networks[C]//Proceedings of the 16th International Conference on World Wide Web.ACM,2007:1275-1276.[30]RAGHAVAN U N,ALBERT R,KUMARA S.Near linear time algorithm to detect community structures in large-scale networks [J].Physical Review E,2007,76(3):036106.[31]DENG Z H,QIAO H H,SONG Q,et al.A complex network community detection algorithm based on label propagation and fuzzy c-means [J].Physica A:Statistical Mechanics and its Applications,2019,519:217-226.[32]BARBER M J,CLARK J W.Detecting network communities by propagating labels under constraints [J].Physical Review E,2009,80(2):026129.[33]HU X G,HE W,LI H Z,et al.Role-based label propagation algorithm for community detection [J].arXiv:1601.06307,2016.[34]GUI C,ZHANG R S,ZHAO Z L,et al.Lpa-cbd an improved label propagation algorithm based on community belonging degree for community detection[J].International Journal of Modern Physics C,2018,29(02):1850011.[35]THAKARE S B,KIWELEKAR A W.Skiplpa:an efficient label propagation algorithm for community detection in sparse network [C]//Proceedings of the 9th Annual ACM India Confe-rence.ACM,2016:97-106.[36]CHIN J H,RATNAVELU K.A semi-synchronous label propagation algorithm with constraints for community detection in complex networks [J].Scientific Reports,2017,7:45836.[37]SU Y S,WANG B J,ZHANG X Y.A seed-expanding method based on random walks for community detection in networks with ambiguous community structures [J].Scientific Reports,2017,7:41830.[38]SUN H L,CHNG E,YONG X,et al.A fast community detection method in bipartite networks by distance dynamics [J].Physica A:Statistical Mechanics and its Applications,2018,96:108-120.[39]ZHOU H J.Network landscape from a brownian particle’s perspective [J].Physical Review E,2003,67(4):041908.[40]PONS P,LATAPY M.Computing communities in large net- works using random walks [C]//International Symposium on Computer and Information Sciences.Springer,2005:284-293.[41]ROSVALL M,BERGSTROM C T.Maps of random walks on complex networks reveal community structure [J].Proceedings of the National Academy of Sciences,2008,105(4):1118-1123.[42]ROSVALL M,BERGSTROM C T.Multilevel compression of random walks on networks reveals hierarchical organization in large integrated systems [J].PloS One,2011,6(4):e18209.[43]HU Y Q,LI M H,ZHANG P,et al.Community detection by signaling on complex networks [J].Physical Review E,2008,78(1):016115.[44]ESMAILIAN P,JALILI M.Community detection in signed networks:the role of negative ties in different scales [J].Scientific Reports,2015,5(1):14339.[45]BAHADORI S,MORADI P.A local random walk method for identifying communities in social networks [C]//Artificial Intelligence and Robotics(IRANOPEN).IEEE,2017:177-181.[46]HARTIGAN J A,WONG M A.Algorithm as 136:A k-means clustering algorithm [J].Journal of the Royal Statistical Society.Series C (Applied Statistics),1979,28(1):100-108.[47]FORTUNATO S,BARTHELEMY M.Resolution limit in community detection [J].Proceedings of the National Academy of Sciences,2007,104(1):36-41.[48]ANA L N F,JAIN A K.Robust data clustering [C]//IEEE Computer Society Conference onComputer Vision and Pattern Recognition.IEEE,2003.[49]ZACHARY W W.An information flow model for conflict and fission in small groups [J].Journal of Anthropological Research,1977,33(4):452-473.[50]LUSSEAU D,SCHNEIDER K,BOISSEAU O J,et al.The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations [J].Behavioral Ecology and Sociobiology,2003,54(4):396-405.[51]STEINHAEUSER K,CHAWLA N V.Identifying and evaluating community structure in complex networks [J].Pattern Re-cognition Letters,2010,31(5):413-421.[52]NEWMAN M E J.Scientific collaboration networks.i.network construction and fundamental results [J].Physical Review E,2001,64(1):016131.[53]KNUTH D E.The Stanford GraphBase:a platform for combinatorial computing [M].New York:ACM,1993.[54]GLEISER P M,DANON L.Community structure in jazz [J].Advances in Complex Systems,2003,6(4):565-573.[55]MILO R,SHEN-ORR S,ITZKOVITZ S,et al.Network motifs:simple building blocks of complex networks [J].Science,2002,298(5594):824-827.[56]BOGUÑÁ M,PASTOR-SATORRAS R,DÍAZ-GUILERA A, et al.Models of social networks based on social distance attachment [J].Physical Review E,2004,70(5):056122.[57]LANCICHINETTI A,FORTUNATO S,RADICCHI F.Benchmark graphs for testing community detection algorithms [J].Physical Review E,2008,78(4):046110.[58]FAGNAN J,ABNAR A,RABBANY R,et al.Modular networks for validating community detection algorithms [J].arXiv:1801.01229,2018. |
[1] | 钱梦薇, 过弋. 融合偏置深度学习的距离分解Top-N推荐算法 Biased Deep Distance Factorization Algorithm for Top-N Recommendation 计算机科学, 2021, 48(9): 103-109. https://doi.org/10.11896/jsjkx.200800129 |
[2] | 刘丹, 赵森, 颜志良, 赵静, 王会青. 基于堆叠自动编码器的miRNA-疾病关联预测方法 miRNA-disease Association Prediction Model Based on Stacked Autoencoder 计算机科学, 2021, 48(10): 114-120. https://doi.org/10.11896/jsjkx.200900169 |
[3] | 杨卓璇, 马源培, 严冠. 基于耦合强度的多项式时间社团探测算法 Polynomial Time Community Detection Algorithm Based on Coupling Strength 计算机科学, 2020, 47(6A): 102-107. https://doi.org/10.11896/JsJkx.190900170 |
[4] | 张虎, 周晶晶, 高海慧, 王鑫. 融合节点结构和内容的网络表示学习方法 Network Representation Learning Method on Fusing Node Structure and Content 计算机科学, 2020, 47(12): 119-124. https://doi.org/10.11896/jsjkx.190900027 |
[5] | 唐家琪, 吴璟莉, 廖元秀, 王金艳. 基于双加权投票的蛋白质功能预测 Prediction of Protein Functions Based on Bi-weighted Vote 计算机科学, 2019, 46(4): 222-227. https://doi.org/10.11896/j.issn.1002-137X.2019.04.035 |
[6] | 赵倩倩,吕敏,许胤龙. 基于两种子结构感知的社交网络Graphlets采样估计算法 Estimating Graphlets via Two Common Substructures Aware Sampling in Social Networks 计算机科学, 2019, 46(3): 314-320. https://doi.org/10.11896/j.issn.1002-137X.2019.03.046 |
[7] | 宾晟, 孙更新. 基于多关系社交网络的协同过滤推荐算法 Collaborative Filtering Recommendation Algorithm Based on Multi-relationship Social Network 计算机科学, 2019, 46(12): 56-62. https://doi.org/10.11896/jsjkx.181102189 |
[8] | 刘庆烽, 刘哲, 宋余庆, 朱彦. 基于约束随机游走的肿瘤图像分割方法 Tumor Image Segmentation Method Based on Random Walk with Constraint 计算机科学, 2018, 45(7): 243-247. https://doi.org/10.11896/j.issn.1002-137X.2018.07.042 |
[9] | 肖迎元,张红玉. 基于用户潜在特征的社交网络好友推荐方法 Friend Recommendation Method Based on Users’ Latent Features in Social Networks 计算机科学, 2018, 45(3): 218-222. https://doi.org/10.11896/j.issn.1002-137X.2018.03.034 |
[10] | 付立东,聂靖靖. 基于进化谱分方法的动态社团检测 Dynamic Community Detection Based on Evolutionary Spectral Method 计算机科学, 2018, 45(2): 171-174. https://doi.org/10.11896/j.issn.1002-137X.2018.02.030 |
[11] | 陆亿红,张振宁,杨雄. 一种基于节点特征向量的复杂网络社团发现算法 Community Structure Detection Algorithm Based on Nodes’ Eigenvectors 计算机科学, 2017, 44(Z6): 419-423. https://doi.org/10.11896/j.issn.1002-137X.2017.6A.094 |
[12] | 卿勇,刘梦娟,银盈,李杨曦. SMART:一种面向电商平台快速消费品的图推荐算法 SMART:A Graph-based Recommendation Algorithm for Fast Moving Consumer Goods in E-commerce Platform 计算机科学, 2017, 44(Z11): 464-469. https://doi.org/10.11896/j.issn.1002-137X.2017.11A.099 |
[13] | 李鹏,李英乐,王凯,何赞园,李星,常振超. 基于交互行为和连接分析的社交网络社团检测 Community Detection Based on User Interaction and Link Analysis in Social Networks 计算机科学, 2017, 44(7): 197-202. https://doi.org/10.11896/j.issn.1002-137X.2017.07.035 |
[14] | 刘林峰,严禹道,吴国新. 一种基于节点移动倾向检测的社会网络机会转发机制 Opportunistic Forwarding Mechanism Based on Node Movement Tendencies Detecting 计算机科学, 2017, 44(7): 74-78. https://doi.org/10.11896/j.issn.1002-137X.2017.07.013 |
[15] | 卞梦阳,杨青,张敬伟,张会兵,钱俊彦. 基于FP-Growth的图上随机游走推荐方法 Recommendation Method Based on Random Walk on Graph Integrated with FP-Growth 计算机科学, 2017, 44(6): 232-236. https://doi.org/10.11896/j.issn.1002-137X.2017.06.039 |
|