A new label progagation with dams

A new label progagation with dams

Jean-Philippe AttalMaria Malek 

EISTI, Ecole Internationale des Sciences du Traitement de l'Information, Laboratoire Quartz, Cergy-France, 95000, France

Corresponding Author Email: 
jal@eisti.eu,mma@eisti.eu
Page: 
393-418
|
DOI: 
https://doi.org/10.3166/RIA.30.393-418
Received: 
N/A
| |
Accepted: 
N/A
| | Citation
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 has its own label which changes by interaction with its neighbourhood. Unfortunately, this method has two major drawbacks. The first is a bad propagation which can lead to huge communities without sense (giant 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 algorithms and a study on the label propagation by putting artificial dams on edges in order to avoid bad propagations. We then apply an ensemble learning clustering method based on a frequency matrix in order to stabilize the algorithm.

Keywords: 

community detection, label propagation, dams, ensemble learning, core detection.

1. Introduction
2. L'approche par propagation de labels
3. Approche proposée
4. Expérimentations et analyse
5. Conclusion
  References

Ana L., Jain A. K. (2003). Robust data clustering. In Computer vision and pattern recognition,2003. proceedings. 2003 ieee computer society conference on, vol. 2, p. II–128.

Bader D. A., Kintali S., Madduri K., Mihail M. (2007). Approximating betweenness centrality. In Algorithms and models for the web-graph, p. 124–137. Springer.

Barber M. J., Clark J. W. (2009). Fast unfolding of communities in large networks. J. Stat. Mech, p. P10008.

Batagelj V., Mrvar A. (2006). Pajek datasets.

Blondel V., Guillaume J., Lambiotte R., Mech E. (2008). Detecting network communities by propagating labels under constraints. Physical Review E, vol. 80, n° 2, p. 026129.

Brandes U. (2001). A faster algorithm for betweenness centrality. Physical Review E, Journal of mathematical sociology, vol. 25, n° 2, p. 163–177.

Dean J., Ghemawat S. (2008). Mapreduce: simplified data processing on large clusters. Communications of the ACM, vol. 51, n° 1, p. 107–113.

Fortunato S. (2010). Community detection in graphs. Communications of the ACM, Physics Reports, vol. 486, n° 3, p. 75–174.

Geisberger R., Sanders P., Schultes D. (2008). Community detection in graphs., In Proceedings of the meeting on algorithm engineering & expermiments, p. 90–100.

Girvan M., Newman M. E. J. (2002). Community structure in social and biological networks. Proceedings of the National Academy of Sciences, vol. 6, p. 565.

Gleiser P., Danon L. (2003). Community structure in jazz. Advances in Complex Systems, vol. 99, n° 12, p. 7821-7826.

Kannan R., Vempala S., Vetta A. (2004). On clusterings: Good, bad and spectral. Journal of the ACM (JACM), vol. 51, n° 3, p. 497–515.

Kanawati R. (2011). Licod: Leaders identification for community detection in complex networks, ieee third international conference on social computing (socialcom), p. 577–582.

Krebs V. (2004). Books about US politics : http://www.orgnet.com/.

Leung I. X., Hui P., Lio P., Crowcroft J. (2009). Towards real-time community detection inlarge networks. Physical Review E, vol. 79, n° 6, p. 066107.

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

Lusseau D., Schneider K., Boisseau O. J., Haase P., Slooten E., Dawson S. M. (2003). The bottlenose dolphin community of doubtful sound features a large proportion of longlasting associations. Behavioral Ecology and Sociobiology, vol. 54, n° 4, p. 396–405.

Newman M. E. J. (2006). Finding community structure in networks using the eigenvectors of matrices. Physical review E, vol. 74, n° 3.

Newman M. E. J., Girvan M. (2004). Finding and evaluating community structure in networks. Phys. Rev. E, vol. 69, n° 2, p. 026113.

Ovelgönne M., Geyer-Schulz A. (2012). Le plaisir de l’interaction entre l’usager et les objets TIC numériques. An ensemble learning strategy for graph clustering. Graph Partitioning and Graph Clustering, vol. 588, p. 187.

Pons P., Latapy M. (2006). Computing communities in large networks using random walks. Journal of Graph Algorithms and Applications, vol. 10, n° 2, p. 191–218.

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

Rand W. M. (1971). Objective criteria for the evaluation of clustering methods. Journal of the American Statistical association, vol. 66, n° 336, p. 846–850.

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

Rosvall M., Bergstrom C. (2007). Maps of information flow reveal community structure in complex networks. Technical report.

Seifi M., Junier I., Rouquier J.-B., Iskrov S., Guillaume J.-L. (2013). Stable community cores in complex networks. In Complex networks, vol. 1, p. 87–98. Springer.

Shi J., Malik J. (2000). Normalized cuts and image segmentation. Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. 22, n° 8, p. 888–905.

Staudt,C,L. & Meyerhenke,H. Engineering High-Performance Community Detection Heuristics for Massive Graphs. In the42nd International Conference on Parallel Processing IEEE, (pp. 180-189)

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

Topchy A., Jain A. K., PunchW. (2005). Clustering ensembles: Models of consensus and weak partitions. Pattern Analysis and Machine Intelligence, IEEE Transactions on, vol. vol. 27, n° 12, p. 1866–1881

ZacharyW. (1977). An information flow model for conflict and fission in small groups. Journal of Anthropological Research, vol. 33, p. 452-473.

Zaharia M., Chowdhury M., Franklin M. J., Shenker S., Stoica I. (2010). Spark: cluster computing with working sets. In Proceedings of the 2nd usenix conference on hot topics in cloud computing, p. 10–10.

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