More Web Proxy on the site http://driver.im/

research-article

SkipLPA: An Efficient Label Propagation Algorithm for Community Detection in Sparse Network

Authors:

Sanjay B. Thakare,

Arvind W. KiwelekarAuthors Info & Claims

COMPUTE '16: Proceedings of the 9th Annual ACM India Conference

Pages 97 - 106

https://doi.org/10.1145/2998476.2998486

Published: 21 October 2016 Publication History

Abstract

The propagation phase of label propagation algorithm is a computationally intensive process and overall performance of algorithm depends on it. This phase determines the label of all the nodes by processing nodes recursively in the network. Rather processing all the nodes if it is possible to skip certain nodes from the propagation phase, then the process will speed-up.

We propose an efficient algorithm SkipLPA based on label propagation algorithm for the discovering community structure in the sparse network. The initialization phase is split into two sub-phases. First sub-phase: only certain nodes are initialized with unique labels. Second sub-phase: remaining nodes will get initial labels from connected nodes and excluded from the propagation phase. The algorithm is tested not only on benchmark networks but also on the real world networks, and efficiently recovers community structure. The performance of this algorithm improves drastically without compromising the quality of community detected, as well as the number of iterations are reduced by skipping certain nodes from the propagation phase.

References

[1]

R. Albert and A.-L. Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.

[2]

M. J. Barber and J. W. Clark. Detecting network communities by propagating labels under constraints. Physical Review E, 80(2):026129, 2009.

[3]

P. Boldi, M. Rosa, M. Santini, and S. Vigna. Layered label propagation: A multiresolution coordinate-free ordering for compressing social networks. In Proceedings of the 20th international conference on World Wide Web, pages 587--596. ACM, 2011.

Digital Library

[4]

G. Cordasco and L. Gargano. Label propagation algorithm: a semi-synchronous approach. International Journal of Social Network Mining, 1(1):3--26, 2012.

[5]

S. Fortunato and M. Barthelemy. Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1):36--41, 2007.

[6]

M. Girvan and M. E. Newman. Community structure in social and biological networks. Proceedings of the national academy of sciences, 99(12):7821--7826, 2002.

[7]

S. Gregory. Finding overlapping communities in networks by label propagation. New Journal of Physics, 12(10):103018, 2010.

[8]

http://www-personal.umich.edu/mejn/netdata/.

[9]

W. Hu. Finding statistically significant communities in networks with weighted label propagation. 2013.

[10]

X. Hu, W. He, H. Li, and J. Pan. Role-based label propagation algorithm for community detection. arXiv preprint arXiv:1601.06307, 2016.

[11]

K. Kothapalli, S. V. Pemmaraju, and V. Sardeshmukh. On the analysis of a label propagation algorithm for community detection. In Distributed Computing and Networking, pages 255--269. Springer, 2013.

[12]

M. Leng, Y. Yao, J. Cheng, W. Lv, and X. Chen. Active semi-supervised community detection algorithm with label propagation. In Database Systems for Advanced Applications, pages 324--338. Springer, 2013.

[13]

J. Leskovec and A. Krevl. SNAP Datasets: Stanford large network dataset collection. http://snap.stanford.edu/data, jun 2014.

[14]

I. X. Leung, P. Hui, P. Lio, and J. Crowcroft. Towards real-time community detection in large networks. Physical Review E, 79(6):066107, 2009.

[15]

S. Li, H. Lou, W. Jiang, and J. Tang. Detecting community structure via synchronous label propagation. Neurocomputing, 151:1063--1075, 2015.

[16]

Z. Lin, X. Zheng, N. Xin, and D. Chen. Ck-lpa: Efficient community detection algorithm based on label propagation with community kernel. Physica A: Statistical Mechanics and its Applications, 416:386--399, 2014.

[17]

K. Liu, J. Huang, H. Sun, M. Wan, Y. Qi, and H. Li. Label propagation based evolutionary clustering for detecting overlapping and non-overlapping communities in dynamic networks. Knowledge-Based Systems, 89:487--496, 2015.

Digital Library

[18]

W. Liu, X. Jiang, M. Pellegrini, and X. Wang. Discovering communities in complex networks by edge label propagation. Scientific reports, 6, 2016.

[19]

X. Liu and T. Murata. Advanced modularity-specialized label propagation algorithm for detecting communities in networks. Physica A: Statistical Mechanics and its Applications, 389(7):1493--1500, 2010.

[20]

M. E. Newman. Fast algorithm for detecting community structure in networks. Physical review E, 69(6):066133, 2004.

[21]

M. E. Newman. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 103(23):8577--8582, 2006.

[22]

S. Pang, C. Chen, and T. Wei. A realtime community detection algorithm: incremental label propagation. In Future Information Networks, 2009. ICFIN 2009. First International Conference on, pages 313--317. IEEE, 2009.

[23]

F. Radicchi, C. Castellano, F. Cecconi, V. Loreto, and D. Parisi. Defining and identifying communities in networks. Proceedings of the National Academy of Sciences of the United States of America, 101(9):2658--2663, 2004.

[24]

U. N. Raghavan, R. Albert, and S. Kumara. Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3):036106, 2007.

[25]

A. Rezaei, S. M. Far, and M. Soleymani. Controlled label propagation: Preventing over-propagation through gradual expansion. arXiv preprint arXiv:1503.04694, 2015.

[26]

Q. Song, B. Li, W. Yu, J. Li, and B. Shi. Nslpa: A node similarity based label propagation algorithm for real-time community detection. In Proceedings of the 2014 IEEE/ACM 7th International Conference on Utility and Cloud Computing, pages 896--901. IEEE Computer Society, 2014.

Digital Library

[27]

S. H. Strogatz. Exploring complex networks. Nature, 410(6825):268--276, 2001.

[28]

L. Šubelj and M. Bajec. Unfolding communities in large complex networks: Combining defensive and offensive label propagation for core extraction. Physical Review E, 83(3):036103, 2011.

[29]

H. Sun, J. Huang, X. Zhong, K. Liu, J. Zou, and Q. Song. Label propagation with α-degree neighborhood impact for network community detection. Computational intelligence and neuroscience, 2014:45, 2014.

Digital Library

[30]

G. Tibély and J. Kertész. On the equivalence of the label propagation method of community detection and a potts model approach. Physica A: Statistical Mechanics and its Applications, 387(19):4982--4984, 2008.

[31]

J. Ugander and L. Backstrom. Balanced label propagation for partitioning massive graphs. In Proceedings of the sixth ACM international conference on Web search and data mining, pages 507--516. ACM, 2013.

Digital Library

[32]

Z.-H. Wu, Y.-F. Lin, S. Gregory, H.-Y. Wan, and S.-F. Tian. Balanced multi-label propagation for overlapping community detection in social networks. Journal of Computer Science and Technology, 27(3):468--479, 2012.

[33]

J. Xie, M. Chen, and B. K. Szymanski. Labelrankt: Incremental community detection in dynamic networks via label propagation. In Proceedings of the Workshop on Dynamic Networks Management and Mining, pages 25--32. ACM, 2013.

Digital Library

[34]

J. Xie and B. K. Szymanski. Community detection using a neighborhood strength driven label propagation algorithm. In Network Science Workshop (NSW), 2011 IEEE, pages 188--195. IEEE, 2011.

Digital Library

[35]

J. Xie, B. K. Szymanski, and X. Liu. Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. In Data Mining Workshops (ICDMW), 2011 IEEE 11th International Conference on, pages 344--349. IEEE, 2011.

Digital Library

[36]

A. Zhang, G. Ren, Y. Lin, B. Jia, H. Cao, J. Zhang, and S. Zhang. Detecting community structures in networks by label propagation with prediction of percolation transition. The Scientific World Journal, 2014, 2014.

[37]

L. Zong-Wen, L. Jian-Ping, Y. Fan, and A. Petropulu. Detecting community structure using label propagation with consensus weight in complex network. Chinese Physics B, 23(9):098902, 2014.

Cited By

Yin XZhao SLi XSu H(2022)A Community Detection Algorithm Based on Correlation Analysis of Connection PatternProceedings of the 2022 14th International Conference on Machine Learning and Computing10.1145/3529836.3529949(347-357)Online publication date: 18-Feb-2022
https://dl.acm.org/doi/10.1145/3529836.3529949
Tang MLiao HFujita H(2022)Delegation Mechanism-Based Large-Scale Group Decision Making With Heterogeneous Experts and Overlapping CommunitiesIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2021.307090252:6(3542-3555)Online publication date: Jun-2022
https://doi.org/10.1109/TSMC.2021.3070902
Yang HCheng JYang ZZhang HZhang WYang KChen X(2021)A Node Similarity and Community Link Strength-Based Community Discovery AlgorithmComplexity10.1155/2021/88485662021(1-17)Online publication date: 12-Mar-2021
https://doi.org/10.1155/2021/8848566
Show More Cited By

Recommendations

SELP

A semi-supervised community detection approach in the theory of belief functions.An evidential label propagation algorithm for graph data.The performance of the proposed method is significantly improved compared with LPA. With the increasing size of ...
User Interface for Community Detection in Social Networks
ICECCS '14: Proceedings of the 2014 3rd International Conference on Eco-friendly Computing and Communication Systems

The ongoing issue in social network is detecting the communities for large data sets efficiently, stabilizing the communities in the network so that we get same structure over different runs for same network data set pose a challenging problem in the ...
LocalCom: a community-based epidemic forwarding scheme in disruption-tolerant networks
SECON'09: Proceedings of the 6th Annual IEEE communications society conference on Sensor, Mesh and Ad Hoc Communications and Networks

In disruption-tolerant networks (DTNs), network topology constantly changes and end-to-end paths can hardly be sustained. However, social network properties are observed in many DTNs and tend to be stable over time. To utilize the social network ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

COMPUTE '16: Proceedings of the 9th Annual ACM India Conference

October 2016

178 pages

ISBN:9781450348089

DOI:10.1145/2998476

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 21 October 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ACM COMPUTE '16

ACM COMPUTE '16: Ninth Annual ACM India Conference

October 21 - 23, 2016

Gandhinagar, India

Acceptance Rates

COMPUTE '16 Paper Acceptance Rate 22 of 117 submissions, 19%;

Overall Acceptance Rate 114 of 622 submissions, 18%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
140
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 15 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Yin XZhao SLi XSu H(2022)A Community Detection Algorithm Based on Correlation Analysis of Connection PatternProceedings of the 2022 14th International Conference on Machine Learning and Computing10.1145/3529836.3529949(347-357)Online publication date: 18-Feb-2022
https://dl.acm.org/doi/10.1145/3529836.3529949
Tang MLiao HFujita H(2022)Delegation Mechanism-Based Large-Scale Group Decision Making With Heterogeneous Experts and Overlapping CommunitiesIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2021.307090252:6(3542-3555)Online publication date: Jun-2022
https://doi.org/10.1109/TSMC.2021.3070902
Yang HCheng JYang ZZhang HZhang WYang KChen X(2021)A Node Similarity and Community Link Strength-Based Community Discovery AlgorithmComplexity10.1155/2021/88485662021(1-17)Online publication date: 12-Mar-2021
https://doi.org/10.1155/2021/8848566
Yang HCheng JLeng MSu XZhang WChen X(2019)Detecting communities from networks based on their intrinsic propertiesInternational Journal of Modern Physics C10.1142/S012918311950104330:12(1950104)Online publication date: 18-Dec-2019
https://doi.org/10.1142/S0129183119501043
Cheng JZhao SYang HZhang JSu XChen X(2019)Detecting communities from networks using an improved self-organizing mapInternational Journal of Modern Physics C10.1142/S012918311950054230:06(1950054)Online publication date: 16-Jul-2019
https://doi.org/10.1142/S0129183119500542
Muthuman AKavitha RMahalakshmi G(undefined)Exploring Citation Networks for Community DetectionSSRN Electronic Journal10.2139/ssrn.4142755
https://doi.org/10.2139/ssrn.4142755

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents