Journal Home > Volume 18 , Issue 4

Recently, complex networks have attracted considerable research attention. Community detection is an important problem in the field of complex networks and is useful in a variety of applications such as information propagation, link prediction, recommendation, and marketing. In this study, we focus on discovering overlapping community structures by using link partitions. We propose a Latent Dirichlet Allocation (LDA)-Based Link Partition (LBLP) method, which can find communities with an adjustable range of overlapping. This method employs the LDA model to detect link partitions, which can calculate the community belonging factor for each link. On the basis of this factor, link partitions with bridge links can be found efficiently. We validate the effectiveness of the proposed solution by using both real-world and synthesized networks. The experimental results demonstrate that the approach can find a meaningful and relevant link community structure.


menu
Abstract
Full text
Outline
About this article

LBLP: Link-Clustering-Based Approach for Overlapping Community Detection

Show Author's information Le YuBin Wu( )Bai Wang
School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China

Abstract

Recently, complex networks have attracted considerable research attention. Community detection is an important problem in the field of complex networks and is useful in a variety of applications such as information propagation, link prediction, recommendation, and marketing. In this study, we focus on discovering overlapping community structures by using link partitions. We propose a Latent Dirichlet Allocation (LDA)-Based Link Partition (LBLP) method, which can find communities with an adjustable range of overlapping. This method employs the LDA model to detect link partitions, which can calculate the community belonging factor for each link. On the basis of this factor, link partitions with bridge links can be found efficiently. We validate the effectiveness of the proposed solution by using both real-world and synthesized networks. The experimental results demonstrate that the approach can find a meaningful and relevant link community structure.

Keywords: community detection, overlapping community, latent Dirichlet allocation, link partition

References(29)

[1]
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.
[2]
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.
[3]
D. M. Blei, A. Y. Ng, and M. I. Jordan, Latent dirichlet allocation, Journal of Machine Learning Research, vol. 3, pp. 993-1022, 2003.
[4]
J. Xie, S. Kelley, and B. K. Szymanski, Overlapping community detection in networks: The state of the art and comparative study, ACM Computing Surveys, Arxiv preprint arxiv:1110.5013, pp. 2013.
[5]
I. Farkas, D. Ábel, G. Palla, and T. Vicsek, Weighted network modules, New Journal of Physics, vol. 9, no. 6, p.180, 2007.
[6]
J. M. Kumpula, M. Kivelä, K. Kaski, and J. Saramäki, Sequential algorithm for fast clique percolation, Physical Review E, vol. 78, no. 2, p. 026109, 2008.
[7]
Z. Wu, Y. Lin, H. Wan, and S. Tian, A fast and reasonable method for community detection with adjustable extent of overlapping, in Proc. 5th Int. Intelligent Systems and Knowledge Engineering Conf., Hangzhou, China, 2010, pp. 376-379.
[8]
Y. Kim and H. Jeong, Map equation for link community, Computing Research Repository, arxiv preprint arxiv: 1105.0257, 2011.
[9]
T. S. Evans, Clique graphs and overlapping communities, Journal of Statistical Mechanics: Theory and Experiment, vol. 12, no. 12, p. P12037, 2010.
[10]
Q. Ye, B. Wu, Z. Zhao, and B. Wang, Detecting link communities in massive networks, in Proc. 3th Int. Advances in Social Networks Analysis and Mining Conf., Taiwan, China, 2011, pp. 71-78.
DOI
[11]
C. Shi, Y. Cai, D. Fu, Y. Dong, and B. Wu, A link clustering based overlapping community detection algorithm, Data & Knowledge Engineering, , 2013.
[12]
A. Lancichinetti, S. Fortunato, and J. Kertész, Detecting the overlapping and hierarchical community structure in complex networks, New Journal of Physics, vol. 11, no. 3, p. 033015, 2009.
[13]
A. Lancichinetti, F. Radicchi, J. Ramasco, and S. Fortunato, Finding statistically significant communities in networks, PloS one, vol. 6, no. 4, p.e18961, 2011.
[14]
P. Arnau, P. Guillem, P. Julian, and M. Victor. Overlapping community search for social networks, in Proc. 26th Int. Data Engineering Conf., Long Beach, California, USA, 2010, pp. 992-995.
[15]
C. Lee, F. Reid, A. McDaid, and N. Hurley, Detecting highly overlapping community structure by greedy clique expansion, arXiv preprint arXiv:1002.1827, 2010.
[16]
N. Du, B. Wang, and B. Wu, Overlapping community structure detection in networks, in Proc. 17th Int. Information and Knowledge Management Conf., Napa Valley, USA, 2008, pp.1371-1372.
DOI
[17]
H. Zhang, B. Qiu, C. L. Giles, H. C. Foley, and J. Yen, An LDA-based community structure discovery approach for large-scale social networks, in Proc. 5th Int. Intelligence and Security Informatics Conf., New Brunswick, NJ, USA, 2007, pp. 200-207.
DOI
[18]
I. Psorakis, S. Roberts, M. Ebden, and B. Sheldon, Overlapping community detection using bayesian non-negative matrix factorization, Physical Review E, vol. 83, no. 6, p.066114, 2011.
[19]
T. Nepusz, A. Petróczi, L. Négyessy, and F. Bazsó, Fuzzy communities and the concept of bridgeness in complex networks, Physical Review E, vol. 77, no. 1, p.016107, 2008.
[20]
S. Zhang, R. Wang, and X. Zhang, Identification of overlapping community structure in complex networks using fuzzy c-means clustering, Physica A: Statistical Mechanics and Its Applications, vol. 374, no. 1, pp. 483-490, 2007.
[21]
S. Gregory, A fast algorithm to find overlapping communities in networks, Machine Learning and Knowledge Discovery in Databases. New York: Springer, 2008, pp. 408-423.
[22]
S. Gregory, Finding overlapping communities in networks by label propagation, New Journal of Physics, vol. 12, no. 10, p. 103018, 2010.
[23]
T. S. Evans and R. Lambiotte, Line graphs, link partitions, and overlapping communities, Physical Review E, vol. 80, no. 1, p. 016105, 2009.
[24]
I. Porteous, D. Newman, A. Ihler, A. Asuncion, P. Smyth, and M. Welling, Fast collapsed Gibbs sampling for latent dirichlet allocation, in Proc. 14th Int. Knowledge Discovery and Data Mining Conf., Las Vegas, USA, 2008, pp. 569-577.
DOI
[25]
T. L. Griffiths and M. Steyvers, Finding scientific topics, National Academy of Sciences of the United States of America, vol. 101, no. suppl, pp. 5228-5235, 2004.
[26]
T. Minka and J. Lafferty, Expectation-propagation for the generative aspect model, in Proc. th Int. Uncertainty in Artificial Intelligence Conf., Alberta, Canada, 2002, pp. 352-359.
[27]
M. Steyvers and T. Griffiths, Probabilistic topic models, Handbook of Latent Semantic Analysis, vol. 427, no. 7, pp. 424-440, 2007.
[28]
A. Lancichinetti and S. Fortunato, Community detection algorithms: A comparative analysis, Physical Review E, vol. 80, p. 056117, 2009.
[29]
X. Wei and W. B. Croft. LDA-based document models for ad-hoc retrieval, in Proc. 29th Int. Research and Development in Information Retrieval Conf., Seattle, Washington, USA, 2006, pp. 178-185.
DOI
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 02 July 2013
Accepted: 12 July 2013
Published: 05 August 2013
Issue date: August 2013

Copyright

© The author(s) 2013

Acknowledgements

This work was supported by the National Key Basic Research and Department (973) Program of China (No. 2013CB329603) and the National Natural Science Foundation of China (Nos. 61074128 and 71231002).

Rights and permissions

Return