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

research-article

A New Label Propagation With Dams

Authors:

Jean-Philippe Attal,

Maria MalekAuthors Info & Claims

ASONAM '15: Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015

Pages 1292 - 1299

https://doi.org/10.1145/2808797.2808826

Published: 25 August 2015 Publication History

Abstract

Label propagation is one of the fastest methods for community detection, with a near linear time complexity. It's a local method, where each node interacts with its neighbourhood to change its own label. Unfortunately, this method has two major drawbacks. The first is a bad propagation which can lead to obtain huge communities without sense (monster communities problem). The second is the instability of the method. Each trial of a label propagation algorithm gives rarely the same result. In this paper, we propose to do a study on the label propagation by putting artificial dams on edges of some networks in order to limit the propagation and to observe if this can lead to better results. We then apply an existing method based on a co-occurrence frequency matrix in order to stabilise the algorithm.

References

[1]

M. Girvan and M. E. J. Newman, "Community structure in social and biological networks," Proceedings of the National Academy of Sciences, vol. 99, no. 12, pp. 7821--7826, 2002.

[2]

M. E. J. Newman, "Spectral methods for network community detection and graph partitioning," Jul. 2013. {Online}. Available: http://arxiv.org/abs/1307.7729

[3]

R. Guimera, M. Sales-Pardo, and L. Amaral, "Modularity from fluctuations in random graphs and complex networks," Physical Review E, vol. 70, no. 2, p. 025101, 2004.

[4]

S. Fortunato, "Community detection in graphs," Physics Reports, vol. 486, no. 3, pp. 75--174, 2010.

[5]

V. Blondel, J. Guillaume, R. Lambiotte, and E. Mech, "Fast unfolding of communities in large networks," J. Stat. Mech, p. P10008, 2008.

[6]

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

[7]

I. X. Leung, P. Hui, P. Lio, and J. Crowcroft, "Towards real-time community detection in large networks," Physical Review E, vol. 79, no. 6, p. 066107, 2009.

[8]

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

[9]

L.Subelj and M.Bajec, "Group detection in complex networks: an algorithm and comparison of the state of the art," Physica A: Statistical Mechanics and Its Applications, vol. 397, pp. 144--156, 2014.

[10]

R. Kanawati, "Licod: Leaders identification for community detection in complex networks," in Privacy, Security, Risk and Trust (PASSAT) and 2011 IEEE Third Inernational Conference on Social Computing (SocialCom), 2011 IEEE Third International Conference on. IEEE, 2011, pp. 577--582.

[11]

M. Seifi, I. Junier, J.-B. Rouquier, S. Iskrov, and J.-L. Guillaume, "Stable community cores in complex networks," in Complex Networks. Springer, 2013, pp. 87--98.

[12]

P. De Meo, E. Ferrara, G. Fiumara, and A. Provetti, "Enhancing community detection using a network weighting strategy," Information Sciences, vol. 222, pp. 648--668, 2013.

Digital Library

[13]

M. Ovelgönne and A. Geyer-Schulz, "An ensemble learning strategy for graph clustering." Graph Partitioning and Graph Clustering, vol. 588, p. 187, 2012.

[14]

M. Ovelgonne, "Distributed community detection in web-scale networks," in Advances in Social Networks Analysis and Mining (ASONAM), 2013 IEEE/ACM International Conference on. IEEE, 2013, pp. 66--73.

Digital Library

[15]

L. Ana and A. K. Jain, "Robust data clustering," in Computer Vision and Pattern Recognition, 2003. Proceedings. 2003 IEEE Computer Society Conference on, vol. 2. IEEE, 2003, pp. II--128.

[16]

L. Hubert and P. Arabie, "Comparing partitions," Journal of classification, vol. 2, no. 1, pp. 193--218, 1985.

[17]

R. Kannan, S. Vempala, and A. Vetta, "On clusterings: Good, bad and spectral," Journal of the ACM (JACM), vol. 51, no. 3, pp. 497--515, 2004.

Digital Library

[18]

J. Shi and J. Malik, "Normalized cuts and image segmentation," Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 22, no. 8, pp. 888--905, 2000.

Digital Library

[19]

M. E. J. Newman and M. Girvan, "Finding and evaluating community structure in networks," Phys. Rev. E, vol. 69, no. 2, p. 026113, Feb. 2004.

[20]

W. Zachary, "An information flow model for conflict and fission in small groups," Journal of Anthropological Research, vol. 33, pp. 452--473, 1977.

[21]

V. Krebs, "Books about US politics:," http://www.orgnet.com/, 20084.

[22]

D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M. Dawson, "The bottlenose dolphin community of doubtful sound features a large proportion of long-lasting associations," Behavioral Ecology and Sociobiology, vol. 54, no. 4, pp. 396--405, 2003.

[23]

M. E. J. Newman, "Finding community structure in networks using the eigenvectors of matrices," Physical review E, vol. 74, no. 3, 2006, cite arxiv:physics/0605087Comment: 22 pages, 8 figures, minor corrections in this version.

[24]

P. Ronhovde and Z. Nussinov, "Local resolution-limit-free potts model for community detection," Phys. Rev. E, vol. 81, p. 046114, Apr 2010.

[25]

M. Rosvall and C. Bergstrom, "Maps of information flow reveal community structure in complex networks," arXiv preprint physics.soc-ph/0707.0609, 2007.

[26]

P. Pons and M. Latapy, "Computing communities in large networks using random walks," Journal of Graph Algorithms and Applications, vol. 10, no. 2, pp. 191--218, 2006.

[27]

J. Dean and S. Ghemawat, "Mapreduce: simplified data processing on large clusters," Communications of the ACM, vol. 51, no. 1, pp. 107--113, 2008.

Digital Library

[28]

R. S. Xin, J. E. Gonzalez, M. J. Franklin, and I. Stoica, "Graphx: A resilient distributed graph system on spark," in First International Workshop on Graph Data Management Experiences and Systems. ACM, 2013, p. 2.

Digital Library

[29]

U. Kang, C. E. Tsourakakis, and C.Faloutsos, "Pegasus: A peta-scale graph mining system implementation and observations," in Data Mining, 2009. ICDM'09. Ninth IEEE International Conference on. IEEE, 2009, pp. 229--238.

Digital Library

[30]

S. Moon, J.-G. Lee, M. Kang et al., "Scalable community detection from networks by computing edge betweenness on mapreduce," in 2014 International Conference on Big Data and Smart Computing (BIGCOMP). IEEE, 2014, pp. 145--148.

Cited By

Attal JMalek MZolghadri M(2021)Overlapping community detection using core label propagation algorithm and belonging functionsApplied Intelligence10.1007/s10489-021-02250-4Online publication date: 24-Mar-2021
https://doi.org/10.1007/s10489-021-02250-4
Zhang SWang XQian XHuang M(2019)An intelligent SDN‐enabled CCN routing mechanism with community divisionTransactions on Emerging Telecommunications Technologies10.1002/ett.3698Online publication date: 29-Jul-2019
https://doi.org/10.1002/ett.3698
Šubelj L(2019)Label Propagation for ClusteringAdvances in Network Clustering and Blockmodeling10.1002/9781119483298.ch5(121-150)Online publication date: 13-Dec-2019
https://doi.org/10.1002/9781119483298.ch5
Show More Cited By

A New Label Propagation With Dams

Recommendations

Transductive Multilabel Learning via Label Set Propagation

The problem of multilabel classification has attracted great interest in the last decade, where each instance can be assigned with a set of multiple class labels simultaneously. It has a wide variety of real-world applications, e.g., automatic image ...
Semi-supervised partial label learning algorithm via reliable label propagation
Abstract
Partial label learning (PLL) is a weakly supervised learning method that is able to predict one label as the correct answer from a given candidate label set. In PLL, when all possible candidate labels are as signed to real-world training examples, ...
Logistic label propagation

In this paper, we propose a novel method for semi-supervised learning, called logistic label propagation (LLP). The proposed method employs the logistic function to classify input pattern vectors, similarly to logistic regression. To cope with unlabeled ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ASONAM '15: Proceedings of the 2015 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining 2015

August 2015

835 pages

ISBN:9781450338547

DOI:10.1145/2808797

Copyright © 2015 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 ACM 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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 25 August 2015

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

ASONAM '15

Sponsor:

SIGKDD

ASONAM '15: Advances in Social Networks Analysis and Mining 2015

August 25 - 28, 2015

Paris, France

Acceptance Rates

Overall Acceptance Rate 116 of 549 submissions, 21%

Upcoming Conference

KDD '25

Sponsor:
sigkdd
sigkdd

The 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining

August 3 - 7, 2025

Toronto , ON , Canada

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
83
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 14 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Attal JMalek MZolghadri M(2021)Overlapping community detection using core label propagation algorithm and belonging functionsApplied Intelligence10.1007/s10489-021-02250-4Online publication date: 24-Mar-2021
https://doi.org/10.1007/s10489-021-02250-4
Zhang SWang XQian XHuang M(2019)An intelligent SDN‐enabled CCN routing mechanism with community divisionTransactions on Emerging Telecommunications Technologies10.1002/ett.3698Online publication date: 29-Jul-2019
https://doi.org/10.1002/ett.3698
Šubelj L(2019)Label Propagation for ClusteringAdvances in Network Clustering and Blockmodeling10.1002/9781119483298.ch5(121-150)Online publication date: 13-Dec-2019
https://doi.org/10.1002/9781119483298.ch5
Attal JMalek MZolghadri M(2017)Parallel and distributed core label propagation with graph coloringConcurrency and Computation: Practice and Experience10.1002/cpe.435531:2Online publication date: 26-Nov-2017
https://doi.org/10.1002/cpe.4355
Attal JMalek MZolghadri M(2016)Overlapping Community Detection Using Core Label Propagation and Belonging FunctionNeural Information Processing10.1007/978-3-319-46675-0_19(165-174)Online publication date: 29-Sep-2016
https://doi.org/10.1007/978-3-319-46675-0_19

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