AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2.7 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

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

School of Computer Science, Beijing University of Posts and Telecommunications, Beijing 100876, China
Show Author Information

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 detectionoverlapping communitylatent Dirichlet allocationlink partition

References

[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[5]
I. Farkas, D. Ábel, G. Palla, and T. Vicsek, Weighted network modules, New Journal of Physics, vol. 9, no. 6, p.180, 2007.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[9]
T. S. Evans, Clique graphs and overlapping communities, Journal of Statistical Mechanics: Theory and Experiment, vol. 12, no. 12, p. P12037, 2010.
Crossref Google Scholar
[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.
Crossref
[11]
C. Shi, Y. Cai, D. Fu, Y. Dong, and B. Wu, A link clustering based overlapping community detection algorithm, Data & Knowledge Engineering, , 2013.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[23]
T. S. Evans and R. Lambiotte, Line graphs, link partitions, and overlapping communities, Physical Review E, vol. 80, no. 1, p. 016105, 2009.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Google Scholar
[28]
A. Lancichinetti and S. Fortunato, Community detection algorithms: A comparative analysis, Physical Review E, vol. 80, p. 056117, 2009.
Crossref Google Scholar
[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.
Crossref
Tsinghua Science and Technology
Volume 18 Issue 4,
August 2013
Pages 387-397
DOI: 10.1109/TST.2013.6574677
Cite this article:
Yu L, Wu B, Wang B. LBLP: Link-Clustering-Based Approach for Overlapping Community Detection. Tsinghua Science and Technology, 2013, 18(4): 387-397. https://doi.org/10.1109/TST.2013.6574677

716

Views

16

Downloads

7

Crossref

N/A

Web of Science

11

Scopus

0

CSCD

Altmetrics
Received: 02 July 2013
Accepted: 12 July 2013
Published: 05 August 2013
© The author(s) 2013
Return