Research on Community Detection Method for Social Networks Based on User Interaction and Similarity

doi:10.3969/j.issn.1671-1122.2015.07.012

Abstract

Abstract:

With the development of the complex social networks, researches on algorithms about social networks community detection also develop constantly. Researches on algorithms about social networks community detection only take advantage of single dimension information of the network. This paper presents a community detection method that considers user interaction and the similarity comprehensively, detecting community structure in social network by mixing together multiple dimensions information effectively. The method summarizes multi-dimensional relations between users as interaction and similarity .using similarity modularity that is added similarity penalty factor as object function to guide the community division. Experimental results on real data sets show that the method not only can reflect the dynamic changes in the network, but also can get closely linked collection of nodes with similar attributes, proving the rationality and effectiveness of the method.

Key words: social networks, community detection, similarity modularity

CLC Number:

TP309

XU Wei, LIN Bo-gang, LIN Si-juan, YANG Yang. Research on Community Detection Method for Social Networks Based on User Interaction and Similarity[J]. Netinfo Security, 2015, 15(7): 77-83.

Figures/Tables 10

References 24

[1]	Mccallum A, Corrada-Emmanuel A, Wang X. Topic and role discovery in social networks[J]. Ijcai, 2005, 30(2):786--791.
[2]	Yin B, Yang Y, Liu W.Exploring social activeness and dynamic interest in community-based recommender system[C]//Proceedings of the companion publication of the 23rd international conference on World wide web companion. International World Wide Web Conferences Steering Committee, 2014: 771-776.
[3]	Zhang W, Wang J, Feng W.Combining latent factor model with location features for event-based group recommendation[C]//Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013: 910-918.
[4]	Lu Z, Wen Y, Cao G.Community detection in weighted networks: Algorithms and applications[C]//Pervasive Computing and Communications (PerCom), 2013 IEEE International Conference on. IEEE, 2013: 179-184.
[5]	Shakarian P, Roos P, Callahan D, et al.Mining for geographically disperse communities in social networks by leveraging distance modularity[C]//Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2013: 1402-1409.
[6]	Corneil D G, Gotlieb C C.An efficient algorithm for graph isomorphism[J]. Journal of the ACM (JACM), 1970, 17(1): 51-64.
[7]	Pothen A, Simon H D, Liou K P.Partitioning sparse matrices with eigenvectors of graphs[J]. SIAM Journal on Matrix Analysis and Applications, 1990, 11(3): 430-452.
[8]	Girvan M, Newman M E J. Community structure in social and biological networks[C]// Proceedings of the National Academy of Sciences, 2002, 99(12): 7821-7826.
[9]	Newman M E.Fast algorithm for detecting community structure in networks[J]. Physical Review E, 2004, 69(6):279-307.
[10]	Clauset A, Newman M E J, Moore C. Finding community structure in very large networks[J]. Physical Review E, 2004, 70(6):264-277.
[11]	Blondel V D, Guillaume J L, Lambiotte R, et al.Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics Theory & Experiment, 2008, 30(2):155-168.
[12]	Raghavan U N, Albert R, Kumara S.Near linear time algorithm to detect community structures in large-scale networks[J]. Physical Review E, 2007, 76(3): 1-11.
[13]	Barber M J, Clark J W.Detecting network communities by propagating labels under constraints.[J]. Physical Review E, 2009, 80(2):283-289.
[14]	赵卓翔, 王轶彤, 田家堂, 等. 社会网络中基于标签传播的社区发现新算法[J]. 计算机研究与发展, 2011 (S3): 8-15.
[15]	Gregory S.Finding overlapping communities in networks by label propagation[J]. New Journal of Physics, 2010, 12(10):2011-2024.
[16]	Nguyen N P, Dinh T N, Xuan Y, et al.Adaptive algorithms for detecting community structure in dynamic social networks[C]//INFOCOM, 2011 Proceedings IEEE. IEEE, 2011: 2282-2290.
[17]	索勃, 李战怀, 陈群,等. 基于信息流动分析的动态社区发现方法[J]. 软件学报, 2014, 25(3):547-559.
[18]	Dev H.A user interaction based community detection algorithm for online social networks[C]//Proceedings of the 2014 ACM SIGMOD international conference on Management of data. ACM, 2014: 1607-1608.
[19]	黄宇. 基于隐性语义挖掘的社区划分算法[D].成都:电子科技大学, 2013.
[20]	Zhou W, Jin H, Liu Y.Community discovery and profiling with social messages[C]//Proceedings of the 18th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2012: 388-396.
[21]	Steyvers M, Smyth P, Rosen-Zvi M, et al.Probabilistic author-topic models for information discovery[C]//Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2004: 306-315.
[22]	Mccallum A, Corrada-Emmanuel A, Wang X.Topic and role discovery in social networks[J]. Ijcai, 2005, 30(2):786-791.
[23]	张平. 基于密度模块的微博社区发现方法[D].昆明: 云南大学,2013.
[24]	Alfalahi K, Atif Y, Harous S.Community detection in social networks through similarity virtual networks[C]//Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining. ACM, 2013: 1116-1123.