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, Network clustering, Weighting strategy, Tightness, Judicial case network

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   
[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[2] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[3] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[4] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[5] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[6] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[7] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[8] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[9] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .
[10] WANG Zhen-chao, HOU Huan-huan and LIAN Rui. Path Optimization Scheme for Restraining Degree of Disorder in CMT[J]. Computer Science, 2018, 45(4): 122 -125 .