吉林大学学报(工学版) ›› 2013, Vol. 43 ›› Issue (01): 98-105.

Previous Articles     Next Articles

Community mining from complex networks based on loop tightness

LIU Da-you1,2, YANG Jian-ning1,2, YANG Bo1,2, ZHAO Xue-hua1,2, Jin Di3   

  1. 1. College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    2. Key Laboratory of Symbolic Computation and Knowledge Engineering of Ministry of Education, Jilin University, Changchun, 130012, China;
    3. School of Computer Science and Engineering, Tianjin University, Tianjin 300072, China
  • Received:2012-05-06 Online:2013-01-01 Published:2013-01-01

PDF (PC)

574

Abstract: In this paper, a Loop Tightness Algorithm (LTA) is proposed. First, it finds the network loops and calculates it tightness value quickly. Then, it obtains the communities of the networks based on the tightness values. Finally, it reveals the relationship between the network loops and the community structure. The LTA is tested and validated by means of synthetic networks and real networks.

Key words: artificial infelligence, data mining, complex networks, community mining, loop tightness algorithm(LTA)

CLC Number: 

  • TP18
[1] 杨博,刘大有,Liu Ji-ming,等.复杂网络聚类方法[J].软件学报, 2009,20(1):54-66. Yang Bo, Liu Da-you, Liu Ji-ming, et al. Complex network clustering algorithms[J]. Journal of Software,2009,20(1):54-66.

[2] Kleinberg J M. Authoritative sources in a hyperlinked environment[J]. Journal of the ACM (JACM),1999,46:604-632.

[3] Girvan M, Newman M E J. Community structure in social and biological networks[J]. Proceedings of the National Academy of Sciences,2002,99:7821.

[4] Radicchi F, Castellano C, Cecconi F, et al. Defining and identifying communities in networks[J]. Proceedings of the National Academy of Sciences of the United States of America,2004,101:2658.

[5] Tyler J R, Wilkinson D M, Huberman B A. Email as spectroscopy:Automated discovery of community structure within organizations[J]. The Information Society,2005,21(2):143-153.

[6] Wu F, Huberman B A. Finding communities in linear time: a physics approach[J]. The European Physical Journal B-Condensed Matter and Complex Systems,2004,38:331-338.

[7] Yang B, Cheung W K, Liu J. Community mining from signed social networks[J].IEEE Transactions on. Knowledge and Data Engineering, 2007,19:1333-1348.

[8] Pothen A, Simon H D, Liou K P. Partitioning sparse matrices with eigenvectors of graphs[J]. Siam J Matrix Anal Applic,1990,11:430-452.

[9] Fiedler M. Algebraic connectivity of graphs[J]. Czechoslovak Mathematical Journal,1973,23:298-305.

[10] Kernighan B W, Lin S. An efficient heuristic procedure for partitioning graphs[J]. Bell System Technical Journal,1970,49:291-307.

[11] Newman MEJ. Fast algorithm for detecting community structure in networks[J]. Physical Review E,2004,69:066133.

[12] Guimera R, Amaral L A N. Functional cartography of complex metabolic networks[J]. Nature 2005,433:895-900.

[13] Xing E P, Jordan M I, Russell S. A Generalized Mean Field Algorithm for Variational Inference in Exponential Families. Uncertinty in AI 2003.

[14] Fu W, Song L, Xing E P. Dynamic mixed membership blockmodel for evolving networks//In Proceedings of the 26th Annual International Conference on Machine learning,2009:329-336.

[15] Airoldi E M, Blei D M, Fienberg S E, et al. Mixed membership stochastic blockmodels[J]. The Journal of Machine Learning Research,2008,9:1981-2014.

[16] Wang Y J, Wong G Y. Stochastic blockmodels for directed graphs[J]. Journal of the American Statistical Association,1987:8-19.

[17] Flake G W, Lawrence S, Giles C L, et al. Self-organization and identification of web communities[J]. Computer,2002;35:66-70.

[18] Hofman J M, Wiggins C H. Bayesian approach to network modularity[J]. Physical Review Letters,2008,100:258701.

[19] Holland P W, Leinhardt S. Local structure in social networks[J]. Sociological methodology 1976,7:1-45.

[20] Newman M E J, Girvan M. Finding and evaluating community structure in networks[J]. Physical Review E,2004,69(2):026113.

[21] Guimera R, Sales-Pardo M, Amaral L A N. Modularity from fluctuations in random graphs and complex networks[J]. Physical Review E,2004,70:025101.

[22] Lancichinetti A, Fortunato S. Benchmarks for testing community detection algorithms on directed and weighted graphs with overlapping communities[J]. Physical Review E,2009,80:016118.

[23] 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:396-405.

[24] Zachary W W. An information flow model for conflict and fission in small groups[J]. Journal of Anthropological Research,1977:452-473.
[1] DENG Jian-xun, XIONG Zhong-yang, DENG Xin. Improved DNALA algorithm based on spectral clustering matrix [J]. 吉林大学学报(工学版), 2018, 48(3): 903-908.
[2] GUO Yu-quan, LI Xiong-fei. Fractal clustering method for uncovering community of complex network [J]. 吉林大学学报(工学版), 2016, 46(5): 1633-1638.
[3] REN Wei-wu, HU Liang, ZHAO Kuo. Intrusion alert correlation model based on data mining and ontology [J]. 吉林大学学报(工学版), 2015, 45(3): 899-906.
[4] WANG Liang, HU Kun-yuan, KU Tao, WU Jun-wei. Discovering spatiotemporal hot spot region and mining patterns fro moving trajectory random sampling [J]. 吉林大学学报(工学版), 2015, 45(3): 913-920.
[5] LIU Shu-fen, MENG Dong-xue, WANG Xiao-yan. DBSCAN algorithm based on grid cell [J]. 吉林大学学报(工学版), 2014, 44(4): 1135-1139.
[6] LIU Zhao-jun, ZHAO Hao-yu, WANG Jing, LI Xiong-fei, LI Wei. Clustering XML documents by layer information [J]. 吉林大学学报(工学版), 2014, 44(01): 124-128.
[7] ZHANG Jun-wei, YANG Jing, ZHANG Jian-pei, ZHANG Le-jun. Sensitive association rule hiding based on sliding window [J]. 吉林大学学报(工学版), 2013, 43(01): 172-178.
[8] BAI Tian, JI Jin-chao, HE Jia-liang, ZHOU Chun-guang. New clustering method of mixed-attribute data [J]. 吉林大学学报(工学版), 2013, 43(01): 130-134.
[9] WANG Jian-lin, YANG Yin-sheng, WANG Xue-ling. Evaluation of land use in Yellow river delta based on extension data mining [J]. 吉林大学学报(工学版), 2012, 42(增刊1): 479-483.
[10] PAN Wei-tao, XIE Yuan-bin, HAO Yue, SHI Jiang-yi. Frequent subcircuits extraction algorithm based on heuristic chain search [J]. 吉林大学学报(工学版), 2011, 41(6): 1748-1753.
[11] NI Ping,LIAO Jian-xin,ZHU Xiao-min,WAN Li,. Incremental multi-dimension scaling visualization mining method for data stream [J]. 吉林大学学报(工学版), 2011, 41(03): 817-821.
[12] TIAN Ye, LIU Da-You. Improved clustering algorithm in peertopeer environments [J]. 吉林大学学报(工学版), 2010, 40(06): 1639-1643.
[13] WANG Li-min,ZANG Xue-bai,CAO Chun-hong. Data mining model of decision forest based on generalized informaion theory [J]. 吉林大学学报(工学版), 2010, 40(01): 155-0158.
[14] Zhou Chun-guang,Qu Peng-cheng,Wang Xi,Wang Jian-yu,Wang Zhe . DSNE:a new dynamic social network analysis algorithm [J]. 吉林大学学报(工学版), 2008, 38(02): 408-0413.
[15] Li Chuan-chuan,Liu Yan-heng,Tian Da-xin . Network intrusion detection system based on sequential patterns [J]. 吉林大学学报(工学版), 2007, 37(01): 121-125.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd