We use cookies to improve your experience with our site.

Indexed in:

SCIE, EI, Scopus, INSPEC, DBLP, CSCD, etc.

Submission System
(Author / Reviewer / Editor)
Advanced Search
Volume 27 Issue 6
November  2012
Turn off MathJax
Article Contents
Abstract
References
Related Articles
Ying-Jun Wu, Han Huang, Zhi-Feng Hao, Feng Chen. Local Community Detection Using Link Similarity[J]. Journal of Computer Science and Technology, 2012, 27(6): 1261-1268. DOI: 10.1007/s11390-012-1302-4
Citation: Ying-Jun Wu, Han Huang, Zhi-Feng Hao, Feng Chen. Local Community Detection Using Link Similarity[J]. Journal of Computer Science and Technology, 2012, 27(6): 1261-1268. DOI: 10.1007/s11390-012-1302-4
shu

Local Community Detection Using Link Similarity

  • 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

Funds: 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.
More Information
  • Received Date: September 08, 2011
  • Revised Date: March 08, 2012
  • Published Date: November 04, 2012
    Abstract
  • 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.
    • FullText(HTML)
    • References (33)
  • [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.
    • Relative Articles

  • Related Articles

    [1]Hang Qie, Yong Dou, Zhen Huang, Yun-Sheng Xiong. Isolate Sets Based Parallel Louvain Method for Community Detection[J]. Journal of Computer Science and Technology, 2023, 38(2): 373-390. DOI: 10.1007/s11390-023-1599-1
    [2]Guo-Wei Wang, Jin-Dou Zhang, Jing Li. Complete Your Mobility: Linking Trajectories Across Heterogeneous Mobility Data Sources[J]. Journal of Computer Science and Technology, 2018, 33(4): 792-806. DOI: 10.1007/s11390-018-1856-x
    [3]Chong Cao, Hai-Zhou Ai. Facial similarity learning with humans in the loop[J]. Journal of Computer Science and Technology, 2015, 30(3): 499-510. DOI: 10.1007/s11390-015-1540-3
    [4]Yu-Xin Ma, Jia-Yi Xu, Di-Chao Peng, Ting Zhang, Cheng-Zhe Jin, Hua-Min Qu, Wei Chen, Qun-Sheng Peng. A Visual Analysis Approach for Community Detection of Multi-Context Mobile Social Networks[J]. Journal of Computer Science and Technology, 2013, 28(5): 797-809. DOI: 10.1007/s11390-013-1378-5
    [5]Xue Wang, Xuan Zhou, Shan Wang. Summarizing Large-Scale Database Schema Using Community Detection[J]. Journal of Computer Science and Technology, 2012, 27(3): 515-526. DOI: 10.1007/s11390-012-1240-1
    [6]Jian-Yun Liu, Yu-Hang Zhao, Zhao-Xiang Zhang, Yun-Hong Wang, Xue-Mei Yuan, Lei Hu, Zhen-Jiang Dong. Spam Short Messages Detection via Mining Social Networks[J]. Journal of Computer Science and Technology, 2012, 27(3): 506-514. DOI: 10.1007/s11390-012-1239-7
    [7]Mao-Guo Gong, Ling-Jun Zhang, Jing-Jing Ma, Li-Cheng Jiao. Community Detection in Dynamic Social Networks Based on Multiobjective Immune Algorithm[J]. Journal of Computer Science and Technology, 2012, 27(3): 455-467. DOI: 10.1007/s11390-012-1235-y
    [8]Chuan Shi, Zhen-Yu Yan, Xin Pan, Ya-Nan Cai, Bin Wu. A Posteriori Approach for Community Detection[J]. Journal of Computer Science and Technology, 2011, 26(5): 792-805. DOI: 10.1007/s11390-011-0178-z
    [9]Xin Liu, Tsuyoshi Murata. Detecting Communities in K-Partite K-Uniform (Hyper)Networks[J]. Journal of Computer Science and Technology, 2011, 26(5): 778-791. DOI: 10.1007/s11390-011-0177-0
    [10]Nan Du, Bai Wang, Bin Wu. Community Detection in Complex Networks[J]. Journal of Computer Science and Technology, 2008, 23(4): 672-683.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (27) PDF downloads (2343) Cited by()
    Related

    Copyright ©2025 JCST, All Rights Reserved     京ICP备05002829号-1

    Institute of Computing Technology, Chinese Academy of Sciences
    P.O. Box 2704, Beijing 100190, P.R. China

    Tel.: 86-10-62610746 E-mail: jcst@ict.ac.cn

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return