Computer Science ›› 2019, Vol. 46 ›› Issue (11A): 167-171.

• Data Science • Previous Articles     Next Articles

Dynamical Network Clustering Algorithm Based on Weighting Strategy

WANG Zi-jie1, ZHOU Ya-jing2, LI Hui-jia2   

  1. (Collaborative Innovation Center of Judicial Civilization,China University of Political Science and Law,Beijing 100080,China)1;
    (Central University of Finance and Economics,School of Management Science and Engineering,Beijing 100081,China)2
  • Online:2019-11-10 Published:2019-11-20

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

CLC Number: 

  • TP393
[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.
[1] BIAN Zhai-an, LI Hui-jia, CHEN Jun-hua, MA Yu-han and ZHAO Dan. Distributed and Heterogeneous Multi-agent System for Attributed Graph Clustering [J]. Computer Science, 2017, 44(Z6): 407-413.
[2] ZUO Jin and CHEN Ze-mao. Anomaly Detection Algorithm Based on Improved K-means Clustering [J]. Computer Science, 2016, 43(8): 258-261.
[3] ZHANG Zhong-ke and WANG Yun. Cluster-based Multipath Anonymous Routing Protocol in Wireless Ad Hoc Networks [J]. Computer Science, 2014, 41(10): 177-183.
[4] LU Jia (College of Mathematics and Computer Science, Chongqing Normal University, Chongqing 400047). [J]. Computer Science, 2007, 34(4): 204-206.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!