基于网络加权机制的动态迭代聚类算法

计算机科学 ›› 2019, Vol. 46 ›› Issue (11A): 167-171.

基于网络加权机制的动态迭代聚类算法

汪自洁¹, 周雅静², 李慧嘉²

(中国政法大学司法文明协同创新中心北京100080)¹;
(中央财经大学管理科学与工程学院北京100081)²

出版日期:2019-11-10 发布日期:2019-11-20
作者简介:汪自洁(1987-),女,博士生,主要研究方向为司法文明、复杂网络和大数据分析等;李慧嘉(1985-),男,博士,副教授,CCF会员,主要研究方向为数据挖掘、商务智能、人工智能等,E-mail:Hjli@amss.ac.cn。
基金资助:
本文受国家自然科学基金项目(71871233,71401194),北京市自然科学基金(9182015)资助。

Dynamical Network Clustering Algorithm Based on Weighting Strategy

WANG Zi-jie¹, ZHOU Ya-jing², LI Hui-jia²

(Collaborative Innovation Center of Judicial Civilization,China University of Political Science and Law,Beijing 100080,China)¹;
(Central University of Finance and Economics,School of Management Science and Engineering,Beijing 100081,China)²

Online:2019-11-10 Published:2019-11-20

摘要/Abstract

摘要： 动态网络在分析功能属性与拓扑结构的相关性方面具有重要作用。文中提出了一个新的动态迭代聚类算法,通过引入包含拓扑信息的权重W和紧密度T来调整边权和节点紧密度,以提高网络聚类结构检测的速度与准确度。值得一提的是,为了估计最优的迭代停止时间,文中利用以时间t为分辨率参数的稳定性指标(stability)作为测度指标,可以自然地找到使聚类划分达到最优的时刻t。该算法非常高效,而且不需要预先指定聚类的数目,因此可以方便地应用于各种模糊网络。最后在包括法律案例关联网络等数据上的实验结果表明,该算法能快速而准确地探测各种人工和现实网络的聚类结构。

关键词: 动态循环算法, 法律案例关联网络, 加权机制, 紧密度, 网络聚类检测

Abstract: Network dynamic plays an important role in analyzing the correlation between the function properties and the topological structure.This paper proposed a novel dynamical iteration algorithm incorporating the iterative process of membership vector with weighting scheme,i.e.weighting W and tightness T.These new elements can be used to adjust the link strength and the node compactness for improving the speed and accuracy of community structure detection.To estimate the optimal stop time of iteration,this paper utilized stability function defined as the Markov random walk auto-covariance.The algorithm is very efficient,and doesn’t need to specify the number of communities in advance,so it naturally supports overlapping communities by associating each node with a membership vector describing node’s involvement in each community.Theoretical analysis and experiments show that the algorithm can uncover communities effectively and efficiently.

Key words: Dynamical iteration algorithm, Judicial case network, Network clustering, Tightness, Weighting strategy

中图分类号:

TP393

汪自洁, 周雅静, 李慧嘉. 基于网络加权机制的动态迭代聚类算法[J]. 计算机科学, 2019, 46(11A): 167-171. https://doi.org/

WANG Zi-jie, ZHOU Ya-jing, LI Hui-jia. Dynamical Network Clustering Algorithm Based on Weighting Strategy[J]. Computer Science, 2019, 46(11A): 167-171. https://doi.org/

参考文献

[1]ALBERT R, Albert-LÁszlÓB I.Statistical mechanics of complex networks [J].Reviews of Modern Physics,2002,74(1):47.
[2]ROMUALDO P S,VÁZQUEZ A,VESPIGNANI A.Dynamical and correlation properties of the Internet [J].Physical review letters,2001,87(25):258701.
[3]PODANI J,OLTVAI Z N,JEONG H,et al.Comparable system-level organization of Archaea and Eukaryotes [J].Nature Gene-tics,2001,29(1):54-56.
[4]LEON D,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,11:P11010.
[5]FORTUNATO S.Community detection in graphs[J].Physics Reports,2010,486(3):75-174.
[6]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.
[7]SANTO F,BARTHÉLEMY M.Resolution limit in community detection [J].Proceedings of the National Academy of Sciences,2007,104(1):36-41.
[8]ALIREZA K,AJDARIRAD A,HASLER M.Network community-detection enhancement by proper weighting [J].Physical Review E,2011,83(4):046104.
[9]NEWMAN M E J.Fast Algorithm for Detecting CommunityStructure in Networks[J].Physical Review E,2004,69:066133.
[10]ZHOU H J.Distance,dissimilarity index,and network community structure [J].Physical Review E,2003,67(6):061901.
[11]ROSVALL M,BERGSTROM C T.Maps of Random Walks on Complex Networks Reveal Community Structure[J].Procee-dings of the National Academy of Sciences,2008,105(4):1118-1123.
[12]DELVENNE J C,YALIRAKI S N,BARAHONA M.Stability of graph communities across time scales,eprint [J].arXiv:0812.1811.
[13]RENAUD L,DELVENNE J C,BARAHONA M.Laplacian dynamics and multiscale modular structure in networks [J].arXiv,2008,0812.1770.
[14]李慧嘉,李爱华,李慧颖.社团结构迭代快速探测算法[J].计算机学报,2017,40(4):970-984.
[15]李慧嘉,严冠,刘志东,等.基于动态系统的网络社团线性探测算法[J].中国科学:数学,2017,47:241-256.
[16]REICHARDT J,BORNHOLDT S.Detecting fuzzy community structures in complex networks with a Potts model [J].Physical Review Letters,2004,93(21):218701.
[17]VINCENT D,et al.Fast unfolding of communities in large networks [J].Journal of Statistical Mechanics:Theory and Experiment,2008,2008(10):P10008.
[18]GUIMERA R O,NUNES A L A.Functional cartography ofcomplex metabolic networks [J].Nature,2005,433(7028):895-900.
[19]LANCICHINETTI A,FORTUNATO S.Community detectionalgorithms:a comparative analysis [J].Physical Review E,2009,80(5):056117.
[20]ZACHARY W W.An information flow model for conflict and fission in small groups [J].Journal of Anthropological Research,1977:452-473.
[21]李慧嘉,李慧颖,李爱华.多尺度的社团结构稳定性分析[J].计算机学报,2015,38(2):301-312.
[22]LI H J,ZHANG X S.Analysis of Stability of Community Structure Across Multiple Hierarchical Levels [J].Europhysics Letters,2013,103:58002.
[23]AARON C,NEWMAN M E J,MOORE C.Finding community structure in very large networks [J].Physical Review E,2004,70(6):066111.

Metrics

Viewed

Full text

Abstract

Cited

Shared

Discussed