Computer Science ›› 2018, Vol. 45 ›› Issue (1): 216-222.doi: 10.11896/j.issn.1002-137X.2018.01.038

Previous Articles     Next Articles

Community Detection Method Based on Multi-layer Node Similarity

ZHANG Hu, WU Yong-ke, YANG Zhi-zhuo and LIU Quan-ming   

  • Online:2018-01-15 Published:2018-11-13

Abstract: Community detection is an important research content in complex network,and the agglomerative method based on the node similarity is a typical method of community detection.Aiming at the shortages of the existing method for calculating the node similarity,this paper proposed a novel method based on the multi-layer node similarity,which can not only calculate the similarity between nodes more efficiently,but also solve the problem of merging nodes when the node similarity is same.Furthermore,this paper constructed the community detection model based on the improved calculation method of the node similarity and the measure criteria of connection tightness between groups,and conducted the community detection experiments in real world network.Compared with the experimental results of GN algorithm,Fast Newman algorithm and the improved label propagation algorithm,the proposed model can be more accurate to find the members of each community.

Key words: Node similarity,Community detection,Complex network

[1] PORTER M A,ONNELA J P,MUCHA P J.Communities in networks[J].Notices American Mathematical Society,2009,56(9):1082-1097.
[2] HUANG F L.Studies on community detection and its application in information network[J].Complex Systems and Complexi-ty Science,2010,7(1):64-74.
[3] LUCE R D,PERRY A D.A method of matrix analysis of group structure[J].Psychometrika,1949,4(2):95-116.
[4] ALBA R D.A graph-theoretic definition of a sociometric clique[J].Journal of Mathematical Sociology,1973,3(1):113-126.
[5] LUCE R D.Connectivity and generalized cliques in sociometric group structure[J].Psychometrika,1950,15(2):169-190.
[6] MOKKEN R J.Cliques,clubs and clans[J].Quality and Quantity,1979,3(2):161-173.
[7] SEIDMAN S B,FOSTER B L.A graph-theoretic generalization of the clique concept[J].Journal of Mathematical Sociology ,1978,6(1):139-154.
[8] SEIDMAN S B.Network structure and minimum degree[J].Social networks,1983,5(3):269-287.
[9] LUCCIO F,SAMI M.On the decomposition of networks intominimally interconnected networks[J].IEEE Transactions Circuit Theory,1969,16(2):184-188.
[10] 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(9):2658-2663.
[11] GUIMERA R,SALES-PARDO M,AMARAL L A N.Modulari-ty from fluctuations in random graphs and complex networks[J].Physical Review E Statistical Nonlinear & Soft Matter Physics,2004,70(2):025101.
[12] POTHEN A,SIMON H D,LION K P.Partitioning sparse matrices with eigenvectors of graphs[J].SIAM Journal on Matrix Analysis and Applications,1990,1(3):430-452.
[13] 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.
[14] REICHARDT J,BORNHOLDT S.Detecting fuzzy community structures in complex networks with a Potts model[J].Physical Review Letters,2004,3(21):218701.
[15] REICHARDT J,BORNHOLDT S.Statistical mechanics of community detection[J].Physical Review E,2006,4(1):016110.
[16] 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(2):331-338.
[17] NEWMAN M E J.Fast algorithm for detecting communitystructure in networks[J].Physical Review E,2004,9(6):066133.
[18] BOETTCHER S,PERCUS A G.Optimization with extremaldynamics[J].complexity,2002,8(2):57-62.
[19] ZHOU T,BAI W J,CHENG L J,et al.Continuous extremal optimization for Lennard-Jones clusters[J].Physical Review E,2005,72(1):016702.
[20] SCOTT J.Social Network Analysis:A Handbook(2nd ed)[M].London:Sage Publications,2002.
[21] QIU L Q,CHEN Z Y.Community discovery algorithm based on common neighbor similarity[J].Information System Enginee-ring,2014(5):140-141.(in Chinese) 仇丽靑,陈卓艳.基于共同邻居相似度的社区发现算法[J].信息系统工程,2014(5):140-141.
[22] XU W,LIN B G,LIN S J,et al.Research on the discovery me-thod of social network based on user interaction behavior and similarity[J].Information network security,2015(7):77-83.(in Chinese) 许为,林柏钢,林思娟,等.一种基于用户交互行为和相似度的社交网络社区发现方法研究[J].信息网络安全,2015(7):77-83.
[23] WEI Q J,LI J T,WANG Y.Micro-blog network community discovery algorithm based on user density[J].Computer Applications and Software,2016,33(9):254-258.(in Chinese) 韦庆杰,李京腾,汪雨.基于用户紧密度的微博网络社区发现算法[J].计算机应用与软件,2016,33(9):254-258.
[24] CLAUSET A,NEWMAN M E J,MOORE C.Finding community structure in very large networks[J].Physical review E,2004,70(6):066111.
[25] FANG P,GUO Z B,LI Z T,et al.Online social network community structure detection algorithm based on number of shared friends[J].Journal of Frontiers of Computer Science & Technology,2012,6(5):456-464.
[26] DANON L,DIAZ-GUILERA A,DUCH J,et al.Comparingcommunity structure identification[J].Journal of Statistical Mechanics:Theory and Experiment,2005,2005(9):09008.
[27] NEWMAN M E J,GIRVAN M.Finding and evaluating community structure in networks[J].Physical Review E,2004,69(2):026113.
[28] KANG X B,JIA C Y.An improved fast community detection algorithm based on label propagation[J].Journal of Hefei University of Technology,2013,6(1):43-47.(in Chinese) 康旭彬,贾彩燕.一种改进的标签传播快速社区发现方法[J].合肥工业大学学报,2013,36(1):43-47.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!