TAO Haicheng, WANG Youquan, WU Zhi'ang, BU Zhan, CAO Jie. Discovering Overlapping Communities by Clustering Local Link Structures[J]. Chinese Journal of Electronics, 2017, 26(2): 430-434. doi: 10.1049/cje.2017.01.017
Citation: TAO Haicheng, WANG Youquan, WU Zhi'ang, BU Zhan, CAO Jie. Discovering Overlapping Communities by Clustering Local Link Structures[J]. Chinese Journal of Electronics, 2017, 26(2): 430-434. doi: 10.1049/cje.2017.01.017

Discovering Overlapping Communities by Clustering Local Link Structures

doi: 10.1049/cje.2017.01.017
Funds:  This work is supported by the National Natural Science Foundation of China (No.71571093, No.71372188, No.61502222), National Center for International Joint Research on E-Business Information Processing (No.2013B01035), and National Key Technologies R & D Program of China (No.2013BAH16F03).
More Information
  • Corresponding author: WANG Youquan (corresponding author) was born in 1984. He received the M.S. degree in computer science from Nanjing University of Finance and Economics in 2009. He is now a Ph.D. candidate of Nanjing University of Science and Technology. His research interests include social network analysis and data mining. (Email:youq.wang@gmail.com)
  • Received Date: 2014-12-17
  • Rev Recd Date: 2015-09-09
  • Publish Date: 2017-03-10
  • Recent advances point out that the existing community detection methods commonly face two challenges:incorrect base-structures and incorrect membership of weak-ties. To overcome both problems, a Local link structure (LLS) clustering based method for overlapping community detection is proposed. We extend the similarity of a pair of links to a group of links named LLS, and thus transform mining LLSs as a pattern mining problem. We prove that LLS with an appropriate threshold can filter weak-ties in the form of bridge and local bridge with its span being larger than 3. A compositive framework is presented for overlapping community detection based on LLS mining and clustering. Comparative experiments on both synthetical and real-world networks demonstrate that our method has advantage over six existing methods on discovering higher quality communities.
  • loading
  • J. Xie, S. Kelley and B. K. Szymanski, "Overlapping community detection in networks:The state of the art and comparative study", ACM Computing Surveys, Vol.45, No.4, 2013.
    G. Palla, I. Derenyi, I. Farkas and T. Vicsek, "Uncovering the overlapping community structure of complex networks in nature and society", Nature, Vol.435, No.7043, pp.814-818, 2005.
    Y.-Y. Ahn, J.P. Bagrow and S. Lehmann, "Link communities reveal multiscale complexity in networks", Nature, Vol.466, No.7307, pp.761-764, 2010.
    J. Zhang, K. Deng, et al., "Community detection in complex networks based on link label propagation", Chinese Journal of Electronics, Vol.43, No.6, pp.1113-1118, 2015.
    L. Pan, J. Jin, et al., "Detecting link communities based on local information in social networks", Chinese Journal of Electronics, Vol.40, No.11, pp.2255-2263, 2012.
    S. Lim, S. Ryu, S. Kwon, et al., "LinkSCAN*:Overlapping community detection using the link-space transformation", 2014 IEEE 30th International Conference on Data Engineering (ICDE), pp.292-303, 2014.
    L. Tang and H. Liu, "Community detection and mining in social media", Synthesis Lectures on Data Mining and Knowledge Discovery, Vol.2, No.1, pp.1-137, 2010.
    J. Cao, Z. Wu and J. Wu, "Scaling up cosine interesting pattern discovery:A depth-first method", Information Sciences, Vol.266, No.0, pp.31-46, 2014.
    Z. Wu, J. Cao, J. Wu, et al., "Detecting genuine communities from large-scale social networks:A pattern-based method", The Computer Journal, Vol.59, No.7, pp.1343-1357, 2014.
    M. Granovetter, "The strength of weak ties:A network theory revisited", Sociological Theory, Vol.1, No.1, pp.201-233, 1983.
    D. Easley, J. Kleinberg, "Networks, crowds, and markets:Reasoning about a highly connected world", Cambridge University Press, 2010.
    G. Karypis, R. Aggarwal, V. Kumar and S. Shekhar, "Multilevel hypergraph partitioning:Applications in vlsi domain", IEEE Transactions on Very Large Scale Integration (VLSI) Systems, Vol.7, No.1, pp.69-79, 1999.
  • 加载中

Catalog

    通讯作者: 陈斌, bchen63@163.com
    • 1. 

      沈阳化工大学材料科学与工程学院 沈阳 110142

    1. 本站搜索
    2. 百度学术搜索
    3. 万方数据库搜索
    4. CNKI搜索

    Article Metrics

    Article views (149) PDF downloads(1128) Cited by()
    Proportional views
    Related

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return