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]Yi-Fan Zhang, Lei Sun, Qiang Cao. TLP-LDPC: Three-Level Parallel FPGA Architecture for Fast Prototyping of LDPC Decoder Using High-Level Synthesis[J]. Journal of Computer Science and Technology, 2022, 37(6): 1290-1306. DOI: 10.1007/s11390-022-1499-9
    [2]Ji-Liang Zhang, Wei-Zheng Wang, Xing-Wei Wang, Zhi-Hua Xia. Enhancing Security of FPGA-Based Embedded Systems with Combinational Logic Binding[J]. Journal of Computer Science and Technology, 2017, 32(2): 329-339. DOI: 10.1007/s11390-017-1700-8
    [3]Ji-Liang Zhang, Qiang Wu, Yi-Peng Ding, Yong-Qiang Lv, Qiang Zhou, Zhi-Hua Xia, Xing-Ming Sun, Xing-Wei Wang. Techniques for Design and Implementation of an FPGA-Specific Physical Unclonable Function[J]. Journal of Computer Science and Technology, 2016, 31(1): 124-136. DOI: 10.1007/s11390-016-1616-8
    [4]Chao Wang, Xi Li, Xue-Hai Zhou. CRAIS: A Crossbar-Based Interconnection Scheme on FPGA for Big Data[J]. Journal of Computer Science and Technology, 2015, 30(1): 84-96. DOI: 10.1007/s11390-015-1506-5
    [5]Hui Dai, Qiang Zhou, Ji-Nian Bian. Multilevel Optimization for Large-Scale Hierarchical FPGA Placement[J]. Journal of Computer Science and Technology, 2010, 25(5): 1083-1091. DOI: 10.1007/s11390-010-1085-4
    [6]Chang-Ji Wang, Yong Tang, Qing Li. ID-Based Fair Off-Line Electronic Cash System with Multiple Banks[J]. Journal of Computer Science and Technology, 2007, 22(3): 487-493.
    [7]Ehsan Atoofian, Zainalabedin Navabi. A Test Approach for Look-Up Table Based FPGAs[J]. Journal of Computer Science and Technology, 2006, 21(1): 141-146.
    [8]MA Huadong, LIU Shenquan. Multimedia Data Modeling Based on TemporalLogic and XYZ System[J]. Journal of Computer Science and Technology, 1999, 14(2): 188-193.
    [9]Wu Wei, Zhong Wanxie, Sheng Zhijin. Building Case-Based Preliminary Design Systems: A Hopfield Network Approach[J]. Journal of Computer Science and Technology, 1994, 9(4): 329-341.
    [10]Shi Zhongzhi. Knowledge-Based Decision Support System[J]. Journal of Computer Science and Technology, 1987, 2(1): 22-29.
    • Supplements (0)

Catalog

    Get Citation
    PDF
    XML
    Article views (25) 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