article

Enhancing community detection using a network weighting strategy

Authors:

Pasquale De Meo,

Emilio Ferrara,

Giacomo Fiumara,

Alessandro ProvettiAuthors Info & Claims

Information Sciences—Informatics and Computer Science, Intelligent Systems, Applications: An International Journal, Volume 222

Pages 648 - 668

https://doi.org/10.1016/j.ins.2012.08.001

Published: 01 February 2013 Publication History

Abstract

A community within a network is a group of vertices densely connected to each other but less connected to the vertices outside. The problem of detecting communities in large networks plays a key role in a wide range of research areas, e.g. Computer Science, Biology and Sociology. Most of the existing algorithms to find communities count on the topological features of the network and often do not scale well on large, real-life instances. In this article we propose a strategy to enhance existing community detection algorithms by adding a pre-processing step in which edges are weighted according to their centrality, w.r.t. the network topology. In our approach, the centrality of an edge reflects its contribute to making arbitrary graph transversals, i.e., spreading messages over the network, as short as possible. Our strategy is able to effectively complements information about network topology and it can be used as an additional tool to enhance community detection. The computation of edge centralities is carried out by performing multiple random walks of bounded length on the network. Our method makes the computation of edge centralities feasible also on large-scale networks. It has been tested in conjunction with three state-of-the-art community detection algorithms, namely the Louvain method, COPRA and OSLOM. Experimental results show that our method raises the accuracy of existing algorithms both on synthetic and real-life datasets.

References

[1]

T. Alahakoon, R. Tripathi, N. Kourtellis, R. Simha, A. Iamnitchi. K-path centrality: a new centrality measure in social networks, in: Proceedings of 4th Workshop on Social Network Systems, 2011, pp. 1-6.

Digital Library

[2]

Berry, J., Hendrickson, B., LaViolette, R. and Phillips, C., Tolerating the community detection resolution limit with edge weighting. Physical Review E. v83 i5. 056119

[3]

Blondel, V., Guillaume, J., Lambiotte, R. and Lefebvre, E., Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment. P10008

[4]

Brandes, U., A faster algorithm for betweenness centrality. Journal of Mathematical Sociology. v25 i2. 163-177.

[5]

U. Brandes, D. Delling, M. Gaertler, R. Görke, M. Hoefer, Z. Nikoloski, D. Wagner, On finding graph clusterings with maximum modularity, in: Graph-Theoretic Concepts in Computer Science, 2007, pp. 121-132.

Digital Library

[6]

Clauset, A., Newman, M. and Moore, C., Finding community structure in very large networks. Physical Review E. v70 i6. 66111

[7]

Chua, V., Madej, J. and Wellmann, B., Personal communities: the world according to me. 2005. Sage Publications Ltd., California.

[8]

Cormen, T., Leiserson, C., Rivest, R. and Stein, C., Introduction to Algorithms. 2001. The MIT Press.

Digital Library

[9]

Danon, L., Diaz-Guilera, A., Duch, J. and Arenas, A., Comparing community structure identification. Journal of Statistical Mechanics: Theory and Experiment. P09008

[10]

De Meo, P., Ferrara, E., Fiumara, G. and Ricciardello, A., A novel measure of edge centrality in social networks. Knowledge-Based Systems. v30. 136-150.

Digital Library

[11]

P. De Meo, E. Ferrara, G. Fiumara, A. Provetti, Generalized Louvain method for community detection in large networks, in: Proceedings of the 11th International Conference on Intelligent Systems Design and Applications, 2011, pp. 88-93.

[12]

De Meo, P., Nocera, A., Terracina, G. and Ursino, D., Recommendation of similar users, resources and social networks in a social internetworking scenario. Information Sciences. v181 i7. 1285-1305.

Digital Library

[13]

Community detection in complex networks using extremal optimization. Physical Review E. v72 i2. 27104

[14]

Dunbar, R.I.M., Neocortex size as a constraint on group size in primates. Journal of Human Evolution. v22 i6. 469-493.

[15]

Durugbo, C., Hutabarat, W., Tiwari, A. and Alcock, J., Modelling collaboration using complex networks. Information Sciences. v181 i15. 3143-3161.

Digital Library

[16]

E. Ferrara, A Large-Scale Community Structure Analysis in Facebook, 2012, arxiv:1106.2503v4.

[17]

Ferrara, E., Community structure discovery in Facebook. International Journal of Social Network Mining. v1. 67-90.

[18]

Fortunato, S., Community detection in graphs. Physics Reports. v486 i3-5. 75-174.

[19]

Fortunato, S. and Barthélemy, M., Resolution limit in community detection. Proceedings of the National Academy of Sciences. v104 i1. 36

[20]

Fortunato, S., Latora, V. and Marchiori, M., Method to find community structures based on information centrality. Physical Review E. v70 i5. 056104

[21]

Grabowicz, P., Ramasco, J., Moro, E. and Eguiluz, J.Pujol.V., Social features of online networks: the strength of intermediary ties in online social media. PloS One. v7. e29358

[22]

Friedkin, N., Horizons of observability and limits of informal control in organizations. Social Forces. v62 i1. 55-77.

[23]

Girvan, M. and Newman, M., Community structure in social and biological networks. Proceedings of the National Academy of Sciences. v99 i12. 7821

[24]

M. Gjoka, M. Kurant, C. Butts, A. Markopoulou. Walking in Facebook: A case study of unbiased sampling of osns, in: INFOCOM, 2010 Proceedings IEEE, IEEE, 2010, pp. 1-9.

Digital Library

[25]

Gregory, S., An algorithm to find overlapping community structure in networks. Knowledge Discovery in Databases: PKDD 2007. 91-102.

Digital Library

[26]

Grunwald, S., Speer, A., Ackermann, J. and Koch, I., Petri net modelling of gene regulation of the duchenne muscular dystrophy. Biosystems. v92 i2. 189-205.

[27]

Guimera, R. and Amaral, L.N., Functional cartography of complex metabolic networks. Nature. v433 i7028. 895-900.

[28]

Guimera, R., Sales-Pardo, M. and Amaral, L., Modularity from fluctuations in random graphs and complex networks. Physical Review E. v70 i2. 025101

[29]

Hagen, L. and Kahng, A., New spectral methods for ratio cut partitioning and clustering. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems. v11 i9. 1074-1085.

Digital Library

[30]

Data Mining: Concepts and Techniques. 2006. second ed. Morgan Kaufman Publishers.

[31]

Hoeffding, W., Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association. 13-30.

[32]

Johnston, R. and Charles, P., Social networks, geography and neighbourhood effects. 2005. SAGE Publications, California.

[33]

Khadivi, A., Rad, A. and Hasler, M., Community detection enhancement in networks using proper weighting and partial synchronization. In: Proceedings of 2010 IEEE International Symposium on Circuits and Systems ISCAS, IEEE. pp. 3777-3780.

[34]

Khadivi, A., Rad, A. and Hasler, M., Network community-detection enhancement by proper weighting. Physical Review E. v83 i4. 046104

[35]

Lancichinetti, A. and Radicchi, F., Benchmark graphs for testing community detection algorithms. Physical Review E. v78 i4. 046110

[36]

Lancichinetti, A., Radicchi, F., Ramasco, J. and Fortunato, S., Finding statistically significant communities in networks. PloS One. v6 i4. e18961

[37]

J. Leskovec, C. Faloutsos, Sampling from large graphs, in: Proceedings of 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2006, pp. 631-636.

Digital Library

[38]

Li, Z., Zhang, S., Wang, R., Zhang, X. and Chen, L., Quantitative function for community detection. Physical Review E. v77 i3. 036109

[39]

Lin, N. and Dumin, M., Access to occupations through social ties. Social Networks. v8 i4. 365-385.

[40]

Mirkin, B. and Nascimento, S., Additive spectral method for fuzzy cluster analysis of similarity data including community structure and affinity matrices. Information Sciences. v183 i1. 16-34.

Digital Library

[41]

Newman, M., A measure of betweenness centrality based on random walks. Social networks. v27 i1. 39-54.

[42]

Newman, M. and Girvan, M., Finding and evaluating community structure in networks. Physical Review E. v69 i2. 26113

[43]

Ng, A., Jordan, M. and Weiss, Y., On Spectral clustering: analysis and an algorithm. Advances in Neural Information Processing Systems. v14.

[44]

Palla, G., Derenyi, I., Farkas, I. and Vicsek, T., Uncovering the overlapping community structure of complex networks in nature and society. Nature. v435 i7043. 814-818.

[45]

Porter, M., Onnela, J. and Mucha, P., Communities in networks. Notices of the American Mathematical Society. v56 i9. 1082-1097.

[46]

Near linear time algorithm to detect community structures in large-scale networks. Physical Review E. v76 i3. 036106

[47]

D. Shah, T. Zaman, Community detection in networks: the leader-follower algorithm, in: Proceedings of the Workshop on Networks Across Disciplines: Theory and Applications, 2010, pp. 1-8.

[48]

B. Viswanath, A. Mislove, M. Cha, K.P. Gummadi, On the evolution of user interaction in Facebook, in: Proceedings of the 2nd ACM SIGCOMM Workshop on Social Networks, 2009.

Digital Library

[49]

Von Mering, C., Zdobnov, E., Tsoka, S., Ciccarelli, F., Pereira-Leal, J., Ouzounis, C. and Bork, P., Genome evolution reveals biochemical networks and functional modules. Proceedings of the National Academy of Sciences. v100 i26. 15428

[50]

Y. Wei, C. Cheng, Towards efficient hierarchical designs by ratio cut partitioning, in: Proceedings of the IEEE International Conference on Computer-Aided Design, 1989, pp. 298-301.

Cited By

Rouhi ABouyer AArasteh BLiu X(2024)Two-pronged feature reduction in spectral clustering with optimized landmark selectionApplied Soft Computing10.1016/j.asoc.2024.111775161:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.111775
De Meo PLevene MProvetti A(2023)Branching processes reveal influential nodes in social networksInformation Sciences: an International Journal10.1016/j.ins.2023.119201644:COnline publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1016/j.ins.2023.119201
Zhu WChen CPeng B(2023)Unified robust network embedding framework for community detection via extreme adversarial attacksInformation Sciences: an International Journal10.1016/j.ins.2023.119200643:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.ins.2023.119200
Show More Cited By

Enhancing community detection using a network weighting strategy
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory

Recommendations

Network entropy based overlapping community detection in social networks
ICC '17: Proceedings of the Second International Conference on Internet of things, Data and Cloud Computing

The structural analysis of Social networks is gaining more importance over recent years. The most important structural property of social network is community structure and to detect such structures a novel approach is proposed by adopting the ...
Overlapping community detection on complex networks with Graph Convolutional Networks
Abstract
Discovering the community structure within networks is of significance with respect to many realistic applications, like recommendation systems and cyberattack detection. In this study, we propose an overlapping community detection ...
Highlights
- We propose a GCN-based method CDMG for overlapping community detection from the perspective of optimizing Markov stability, which can be used on both the ...
A comprehensive literature review on community detection: Approaches and applications
Abstract
Community detection has been designed as an axial field in Complex Network Analysis (CNA), since it allows to reveal cohesive and meaningful sub-graphs, recognize the features, functions, structure and dynamic of such complex networks. In this ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Information Sciences: an International Journal

Information Sciences: an International Journal Volume 222, Issue

February, 2013

824 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © © 2012.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 February 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Rouhi ABouyer AArasteh BLiu X(2024)Two-pronged feature reduction in spectral clustering with optimized landmark selectionApplied Soft Computing10.1016/j.asoc.2024.111775161:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.asoc.2024.111775
De Meo PLevene MProvetti A(2023)Branching processes reveal influential nodes in social networksInformation Sciences: an International Journal10.1016/j.ins.2023.119201644:COnline publication date: 1-Oct-2023
https://dl.acm.org/doi/10.1016/j.ins.2023.119201
Zhu WChen CPeng B(2023)Unified robust network embedding framework for community detection via extreme adversarial attacksInformation Sciences: an International Journal10.1016/j.ins.2023.119200643:COnline publication date: 1-Sep-2023
https://dl.acm.org/doi/10.1016/j.ins.2023.119200
Baltsou GTsichlas KVakali A(2022)Local community detection with hintsApplied Intelligence10.1007/s10489-021-02946-752:9(9599-9620)Online publication date: 7-Jan-2022
https://dl.acm.org/doi/10.1007/s10489-021-02946-7
Moradi-Jamei BKramer BCalderón JKorkmaz GKlamma RO'Halloran SRokne J(2021)Community formation and detection on GitHub collaboration networksProceedings of the 2021 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining10.1145/3487351.3488278(244-251)Online publication date: 8-Nov-2021
https://dl.acm.org/doi/10.1145/3487351.3488278
Tautenhain CNascimento M(2020)An ensemble based on a bi-objective evolutionary spectral algorithm for graph clusteringExpert Systems with Applications: An International Journal10.1016/j.eswa.2019.112911141:COnline publication date: 1-Mar-2020
https://dl.acm.org/doi/10.1016/j.eswa.2019.112911
de Santiago RLamb L(2020)A ground truth contest between modularity maximization and modularity density maximizationArtificial Intelligence Review10.1007/s10462-019-09802-853:6(4575-4599)Online publication date: 1-Aug-2020
https://dl.acm.org/doi/10.1007/s10462-019-09802-8
Luo WZhang DJiang HNi LHu Y(2018)Local Community Detection With the Dynamic Membership FunctionIEEE Transactions on Fuzzy Systems10.1109/TFUZZ.2018.281214826:5(3136-3150)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1109/TFUZZ.2018.2812148
Lu XKuzmin KChen MSzymanski B(2018)Adaptive modularity maximization via edge weighting schemeInformation Sciences: an International Journal10.1016/j.ins.2017.09.063424:C(55-68)Online publication date: 1-Jan-2018
https://dl.acm.org/doi/10.1016/j.ins.2017.09.063
Gao GCao JBu ZLi HWu Z(2018)A generalized game theoretic framework for mining communities in complex networksExpert Systems with Applications: An International Journal10.1016/j.eswa.2017.10.05896:C(450-461)Online publication date: 15-Apr-2018
https://dl.acm.org/doi/10.1016/j.eswa.2017.10.058
Show More Cited By

View Options

View options

Get Access

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

Media

Figures

Other

Tables

View Issue’s Table of Contents