›› 2012, Vol. 27 ›› Issue (6): 1261-1268.doi: 10.1007/s11390-012-1302-4

• Artificial Intelligence and Pattern Recognition • Previous Articles     Next Articles

Local Community Detection Using Link Similarity

Ying-Jun Wu1 (吴英骏), Han Huang1,2,* (黄翰), Member, CCF, ACM, IEEE, Zhi-Feng Hao3 (郝志峰), and Feng Chen4 (陈丰)   

  1. 1. State Key Lab of Network and Switching Technology, Beijing University of Posts and Telecommunications Beijing 100876, China;
    2. School of Information and Communication Engineering, Beijing University of Posts and Telecommunications Beijing 100876, China
  • Received:2011-09-09 Revised:2012-03-09 Online:2012-11-05 Published:2012-11-05
  • Supported by:

    This work was supported by the National Natural Science Foundation of China under Grant No. 61170193, the Doctoral Program of the Ministry of Education of China under Grant No. 20090172120035, the Natural Science Foundation of Guangdong Province of China under Grant No. S2012010010613, the Fundamental Research Funds for the Central Universities of South China University of Technology of China under Grant No. 2012ZM0087, the Pearl River Science & Technology Start Project of China under Grant No. 2012J2200007.

Exploring local community structure is an appealing problem that has drawn much recent attention in the area of social network analysis. As the complete information of network is often difficult to obtain, such as networks of web pages, research papers and Facebook users, people can only detect community structure from a certain source vertex with limited knowledge of the entire graph. The existing approaches do well in measuring the community quality, but they are largely dependent on source vertex and putting too strict policy in agglomerating new vertices. Moreover, they have predefined parameters which are difficult to obtain. This paper proposes a method to find local community structure by analyzing link similarity between the community and the vertex. Inspired by the fact that elements in the same community are more likely to share common links, we explore community structure heuristically by giving priority to vertices which have a high link similarity with the community. A three-phase process is also used for the sake of improving quality of community structure. Experimental results prove that our method performs effectively not only in computer-generated graphs but also in real-world graphs.

CLC Number: 

  • null
[1] Parthasarathy S, Ruan Y, Satuluri V. Community discov-ery in social networks: Applications, methods and emergingtrends. In Social Network Data Analytics, Aggarwal C (ed.),2011, pp.79-113.

[2] Tang W, Zhuang H, Tang J. Learning to infer social ties inlarge networks. In Proc. the 2011 European Conf. MachineLearning and Knowledge Discovery in Databases, Sept. 2011,Part 3, pp.381-397.

[3] Kumar R, Raghavan P, Rajagopalan S, Sivakumar D, Tomp-kins A, Upfal E. The web as a graph. In Proc. the 19thACM SIGMOD-SIGACT-SIGART Symposium on Principlesof Database Systems, May 2000, pp.1-10.

[4] Tang J, Zhang J, Yao L, Li J, Zhang L, Su Z. Arnetminer: Ex-traction and mining of academic social networks. In Proc. the14th ACM SIGKDD International Conference on KnowledgeDiscovery and Data Mining, Aug. 2008, pp.990-998.

[5] Clauset A, Newman M, Moore C. Finding community struc-ture in very large networks. Physical review E, 2004, 70(6):066111.

[6] Rattigan M, Maier M, Jensen D. Graph clustering with net-work structure indices. In Proc. the 24th International Con-ference on Machine Learning, June 2007, pp.783-790.

[7] Von Luxburg U. A tutorial on spectral clustering. Statisticsand Computing, 2007, 17(4): 395-416.

[8] Pan J J, Yang Q. Co-localization from labeled and unlabeleddata using graph laplacian. In Proc. the 20th Int. JointConf. Artificial Intelligence, Jan. 2007, pp.2166-2171.

[9] Fortunato S. Community detection in graphs. Physics Re-ports, 2010, 486(3/5): 75-174.

[10] Su Z, Yang Q, Zhang H, Xu X, Hu Y. Correlation-based doc-ument clustering using web logs. In Proc. the 34th AnnualHawaii Int. Conf. System Sciences, 2001, Vol.5,, p.5022.

[11] Kriegel H, Kröger P, Zimek A. Clustering high-dimensionaldata: A survey on subspace clustering, pattern-based cluster-ing, and correlation clustering. ACM Transactions on Knowl-edge Discovery from Data, 2009, 3(1), Article No.1.

[12] Liu N, Yang Q. Eigenrank: A ranking-oriented approach tocollaborative filtering. In Proc. the 31st Int. Conf. Researchand Develop. Inform. Retrieval, July 2008, pp.83-90.

[13] Hotho A, Jäschke R, Schmitz C, Stumme G. Information re-trieval in folksonomies: Search and ranking. In Proc. the 3rdEuropean Conf. The Semantic Web: Research and Applica-tions, June 2006, pp.411-426.

[14] Newman M. Detecting community structure in networks. TheEuropean Physical Journal B-Condensed Matter and Com-plex Systems, 2004, 38(2): 321-330.

[15] Bagrow J, Bollt E. Local method for detecting communities.Physical Review E, 2005, 72(4): 046108.

[16] Clauset A. Finding local community structure in networks.Physical Review E, 2005, 72(2): 026132.

[17] Luo F, Wang J, Promislow E. Exploring local communitystructures in large networks. Web Intelligence and Agent Sys-tems, 2008, 6(4): 387-400.

[18] Bagrow J. Evaluating local community methods in networks.Journal of Statistical Mechanics: Theory and Experiment,2008, 2008: P05001.

[19] Chen J, Zaane O, Goebel R. Local community identificationin social networks. In Proc. the 2009 Int. Conf. Advances inSocial Network Analysis and Mining, July 2009, pp.237-242.

[20] Zhang X, Wang L, Li Y, Liang W. Extracting local com-munity structure from local cores. In Proc. the 16th Int.Conf. Database Systems for Advanced Applications, April2011, pp.287-298.

[21] Rosvall M, Bergstrom C. Maps of random walks on complexnetworks reveal community structure. Proc. the NationalAcademy of Sciences of the United States of America, 2008,105(4): 1118-1123.

[22] Radicchi F, Castellano C, Cecconi F, Loreto V, Parisi D.Defining and identifying communities in networks. Proc. theNational Academy of Sciences of the United States of Amer-ica, 2004, 101(9): 2658-2663.

[23] Andersen R. A local algorithm for finding dense subgraphs.ACM Transactions on Algorithms, 2010, 6(4), Article No. 60.

[24] Andersen R, Lang K. An algorithm for improving graph par-titions. In Proc. the 19th Annual ACM-SIAM Symposiumon Discrete Algorithms, Jan. 2008, pp.651-660.

[25] Andersen R, Lang K. Communities from seed sets. In Proc.the 15th International Conference on World Wide Web, May2006, pp.223-232.

[26] Riedy J, Bader D, Jiang K, Pande P, Sharma R. Detectingcommunities from given seeds in social networks. TechnicalReport GT-CSE-11-01, Georgia Institute of Technology, Feb.2011.

[27] Flake G, Lawrence S, Giles C. Efficient identification of Webcommunities. In Proc. the 6th Int. Conf. Knowledge Dis-covery and Data Mining, Aug. 2000, pp.150-160.

[28] Girvan M, Newman M. Community structure in social andbiological networks. Proc. the National Academy of Sciencesof the United States of America, 2002, 99(12): 7821-7826.

[29] Xu X, Yuruk N, Feng Z, Schweiger T. Scan: A structural clus-tering algorithm for networks. In Proc. the 13th Int. Conf.Knowledge Discovery and Data Mining, Aug. 2007, pp.824-833.

[30] McCallum A, Nigam K, Rennie J, Seymore K. Automatingthe construction of internet portals with machine learning.Information Retrieval, 2000, 3(2): 127-163.

[31] Lu Y, Zhang L, Liu J, Tian Q. Constructing concept lexicawith small semantic gaps. IEEE Transactions on Multimedia,2010, 12(4): 288-299.

[32] Yang J, Cai R, Wang Y, Zhu J, Zhang L, Ma W. Incorporat-ing site-level knowledge to extract structured data from webforums. In Proc. the 18th International Conference on WorldWide Web, April 2009, pp.181-190.

[33] Li X, Wang Y, Acero A. Learning query intent from reg-ularized click graphs. In Proc. the 31st Int. Conf. Re-search and Development in Information Retrieval, July 2008,pp.339-346.
[1] Hui-Feng Sun, Jun-Liang Chen, Gang Yu, Chuan-Chang Liu, Yong Peng, Guang Chen, and Bo Cheng. JacUOD: A New Similarity Measurement for Collaborative Filtering [J]. , 2012, 27(6): 1252-1260.
[2] Punam BediMember, ACM, Senior Member, IEEE, Anjali Thukral, Hema Banati, Abhishek Behl, and Varun Mendiratta. A Multi-Threaded Semantic Focused Crawler [J]. , 2012, 27(6): 1233-1242.
Full text



[1] Li Renwei;. Soundness and Completeness of Kung s Reasoning Procedure[J]. , 1988, 3(1): 7 -15 .
[2] Pong Man-Chi; Zhang Yongguang; Xu Hong; Ding Jie;. OOMMS:A Module Management System Based on an Object-Oriented Model[J]. , 1993, 8(2): 76 -85 .
[3] Wu Xindong;. Inductive Learning[J]. , 1993, 8(2): 22 -36 .
[4] Tang Weiqing; Wen Sili; Liu Shenquan;. An Object-Oriented Model ofUser Interface Generation Tool[J]. , 1994, 9(3): 275 -284 .
[5] Schubert Foo; Siu Cheung Hui;. System Architectural Design for DeliveringVideo Mail over the World-Wide-Web[J]. , 1997, 12(4): 372 -385 .
[6] SUN Yongqiang; LIN Kai; LU Chaojun;. Partial Completion of Equational Theories[J]. , 2000, 15(6): 552 -559 .
[7] Heng Li, Jin-Song Liu, Zhao Xu et al.. Test Data Sets and Evaluation of Gene Prediction Programs on the Rice Genome[J]. , 2005, 20(4): 446 -453 .
[8] Hua Li, Shui-Cheng Yan, and Li-Zhong Peng[1]. Robust Non-Frontal Face Alignment with Edge Based Texture[J]. , 2005, 20(6): 849 -854 .
[9] Byounghyun Yoo and Soonhung Han. Representation of Urban Buildings Using Modified Relief Mapping[J]. , 2006, 21(2): 204 -208 .
[10] Hong Mei, Dong-Gang Cao, and Fu-Qing Yang. Development of Software Engineering: A Research Perspective[J]. , 2006, 21(5): 682 -696 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
E-mail: jcst@ict.ac.cn
  Copyright ©2015 JCST, All Rights Reserved