article

Maximizing modularity intensity for community partition and evolution

Authors:

Yang YangAuthors Info & Claims

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

Pages 83 - 92

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

Published: 01 July 2013 Publication History

Abstract

Most previous studies of community partition have often focused on the network topology, the topology and link weights are in fact closely associated with each other for community formation in complex networks. This paper proposes a function-modularity intensity, a variation of modularity density (D-value) for evaluating the cohesiveness of a community, which considers links between vertices as well as link weights. The results showed that maximizing the modularity intensity not only can resolve the resolution limits problem, but also achieve better performance for community partition. To further evaluate the function and clarify the weight-topology correlation with communities, we give a simple model to simulate the topology and link weights development for community evolution, and use the modularity intensity to capture communities of networks in each step of this process. In this model, a network is treated as a fuzzy relation, and two operations of the fuzzy relation are used to make the link weights stronger and weaker respectively with the growth of the network in each evolutionary step. By simulation experiments, we found that in the model the modularity intensity catches communities of networks that undergo a gradual transition from faintness to clearness. Our model also reproduces the finding of Granovetter that strong links are confined mainly in tight communities and the links between communities are predominantly weak. From the results above, we believe that the modularity intensity gives a more comprehensive evaluation for communities, and by studying the weight-topology correlation, this model provides a new view for community evolution.

References

[1]

Ahn, Y.-Y., Bagrow, J.P. and Lehmann, S., Link communities reveal multiscale complexity in networks. Nature. v455. 761-764.

[2]

Albert, R. and Barabasi, A.-L., Statistical mechanics of complex networks. Rev. Mod. Phys. v74. 47-97.

[3]

Alves, N.A., Unveiling community structures in weighted networks. Phys. Rev. E. v76. 036101

[4]

Bagrow, J.P., Communities and bottlenecks: trees and treelike networks have high modularity. Phys. Rev. E. v85. 066118

[5]

Chen, S.L., Li, J.G. and Wang, X.G., Fuzzy Set Theory and its Application. 2005. Science Press, Beijing.

[6]

Enhancing community detection using a network weighting strategy. Inform. Sci. v222. 648-668.

Digital Library

[7]

Danon, L., Diaz-Guilera, A., Duch, J. and Arenas, A., Comparing community structure identification. J. Statist. Mech.: Theory Exp. v09. P09008

[8]

Fortunato, S., Community detection in graphs. Phys. Reports. v486. 75-174.

[9]

Fortunato, S. and Barthélemy, M., Resolution limit in community detection. Proc. Natl. Acad. Sci. v104. 36-41.

[10]

Farkas, I., Abel, D., Palla, G. and Vicsek, T., Weighted network modules. New J. Phys. v9. 1-18.

[11]

Girvan, M. and Newman, M.E.J., Community structure in social and biological networks. Proc. Natl. Acad. Sci. v99. 7821-7826.

[12]

Granovetter, M.S., The strength of weak ties. Am. J. Sociol. v78. 1360-1380.

[13]

Granovetter, M.S., Economic action and social structure: the problem of embeddedness. Sociol. Econom. Life. v91. 481-510.

[14]

Kossinets, G. and Watts, D.J., Empirical analysis of an evolving social network. Science. v311. 88-90.

[15]

Kumpula, J.M., Onnela, J.-P., Saramäki, J., Kaski, K. and Kertész, J., Model of community emergence in weighted social networks. Comput. Phys. Commun. v180. 517-522.

[16]

Kumpula, J.M., Onnela, J.-P., Saramäki, J., Kaski, K. and Kertész, J., Emergence of communities in weighted networks. Phys. Rev. Lett. v99. 228701

[17]

Lancichinetti, A. and Fortunato, S., Limits of modularity maximization in community detection. Phys. Rev. E. v84. 066122

[18]

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

[19]

Consensus clustering in complex networks. Sci. Reports. v2. 1-7.

[20]

Lancichinetti, A. and Fortunato, S., Community detection algorithms: a comparative analysis. Phys. Rev. E. v80. 056117

[21]

Li, Z., Zhang, S., Wang, R.-S., Zhang, X.-S. and Chen, L., Quantitative function for community detection. Phys. Rev. E. v77. 036109

[22]

Li, W., Revealing network communities with a nonlinear programming method. Inform. Sci. v229. 18-28.

Digital Library

[23]

Medus, A.D. and Dorso, C.O., Alternative approach to community detection in networks. Phys. Rev. E. v79. 066111

[24]

Muff, S., Rao, F. and Caflisch, A., Local modularity measure for network clusterizations. Phys. Rev. E. v72. 056107

[25]

Additive spectral method for fuzzy cluster analysis of similarity data including community structure and affinity matrices. Inform. Sci. v183. 16-34.

Digital Library

[26]

Newman, M.E.J., Detecting community structure in networks. Eur. Phys. J. B. v3. 8321-8330.

[27]

Newman, M.E.J., Modularity and community structure in networks. Proc. Natl. Acad. Sci. v103. 8577-8582.

[28]

Newman, M.E.J., Analysis of weighted networks. Phys. Rev. E. v70. 056131

[29]

Orman, G.K., Labatut, V. and Cherifi, H., Comparative evaluation of community detection algorithms: a topological approach. J. Statist. Mech.: Theory Exp. P08001

[30]

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

[31]

Pujol, J.M., Béjar, J. and Delgado, J., Clustering algorithms for determining community in large networks. Phys. Rev. E. v74. 016107

[32]

Radicchi, F., Lancichinetti, A. and Ramasco, J.J., Combinatorial approach to modularity. Phys. Rev. E. v82. 026102

[33]

Reichardt, J. and Bornholdt, S., Detecting fuzzy community structures in complex networks with a potts model. Phys. Rev. Lett. v93. 218701

[34]

Ronhovde, P. and Nussinov, Z., Local resolution-limit-free potts model for community detection. Phys. Rev. E. v81. 046114

[35]

Rosvall, M. and Bergstrom, C.T., An information-theoretic framework for resolving community structure in complex networks. Proc. Natl. Acad. Sci. v104. 7327-7331.

[36]

P.G. Sun, Clustering Algorithms and Its Application for Network Modularity Analysis, PhD thesis, Xidian University, 2011.

[37]

Sun, P.G., Gao, L. and Han, S., Identification of overlapping and non-overlapping community structure by fuzzy clustering. Inform. Sci. v181. 1060-1071.

Digital Library

[38]

Sun, P.G. and Yang, Y., The methods to find community based on edge centrality. Nature.

[39]

Strogatz, S.H., Exploring complex networks. Nature. v410. 268-276.

[40]

Sales-Pardo, M., Guimer'a, R. and Amaral, L.A.N., Extracting the hierarchical a organization of complex systems. Proc. Natl. Acad. Sci. v4. 15224

[41]

Wu, J., Jiao, L., Jin, C., Liu, F., Gong, M., Shang, R. and Chen, W., Overlapping community detection via network dynamics. Phys. Rev. E. v85. 016115

[42]

Xie, J., Kelley, S. and Szymanski, B.K., Overlapping community detection in networks: the state of the art and comparative study. ACM Comput. Surveys. v45. 1-37.

Digital Library

[43]

Zachary, W.W., An information flow model for conflict and fission in small groups. J. Anthropol. Res. v33. 452-473.

Cited By

Li CChen HLi TYang X(2022)A stable community detection approach for complex network based on density peak clustering and label propagationApplied Intelligence10.1007/s10489-021-02287-552:2(1188-1208)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10489-021-02287-5
Hao YZhang F(2021)An unsupervised detection method for shilling attacks based on deep learning and community detectionSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-020-05162-625:1(477-494)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s00500-020-05162-6
Sun P(2019)Controllability and modularity of complex networksInformation Sciences: an International Journal10.1016/j.ins.2015.07.024325:C(20-32)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2015.07.024
Show More Cited By

Recommendations

Community Interaction and Conflict on the Web
WWW '18: Proceedings of the 2018 World Wide Web Conference

Users organize themselves into communities on web platforms. These communities can interact with one another, often leading to conflicts and toxic interactions. However, little is known about the mechanisms of interactions between communities and how ...
Characterizing the Evolution of Communities on Reddit
SMSociety'20: International Conference on Social Media and Society

One of the most important structures in social networks is communities. Communities in social networks evolve over time. Understanding the evolution of communities is useful in many applications, such as building successful communities, maintaining the ...
Analyzing communities and their evolutions in dynamic social networks

We discover communities from social network data and analyze the community evolution. These communities are inherent characteristics of human interaction in online social networks, as well as paper citation networks. Also, communities may evolve over ...

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 236, Issue

July, 2013

236 pages

ISSN:0020-0255

Issue’s Table of Contents

Copyright © Elsevier Inc. © 2013.

Publisher

Elsevier Science Inc.

United States

Publication History

Published: 01 July 2013

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
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

Li CChen HLi TYang X(2022)A stable community detection approach for complex network based on density peak clustering and label propagationApplied Intelligence10.1007/s10489-021-02287-552:2(1188-1208)Online publication date: 1-Jan-2022
https://dl.acm.org/doi/10.1007/s10489-021-02287-5
Hao YZhang F(2021)An unsupervised detection method for shilling attacks based on deep learning and community detectionSoft Computing - A Fusion of Foundations, Methodologies and Applications10.1007/s00500-020-05162-625:1(477-494)Online publication date: 1-Jan-2021
https://dl.acm.org/doi/10.1007/s00500-020-05162-6
Sun P(2019)Controllability and modularity of complex networksInformation Sciences: an International Journal10.1016/j.ins.2015.07.024325:C(20-32)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2015.07.024
(2019)Visualizing network communities with a semi-definite programming methodInformation Sciences: an International Journal10.1016/j.ins.2015.05.037321:C(1-13)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2015.05.037
Sun P(2019)The human Drug-Disease-Gene NetworkInformation Sciences: an International Journal10.1016/j.ins.2015.01.036306:C(70-80)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2015.01.036
Lin CKang JChen J(2019)An integer programming approach and visual analysis for detecting hierarchical community structures in social networksInformation Sciences: an International Journal10.1016/j.ins.2014.12.009299:C(296-311)Online publication date: 6-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2014.12.009
Sun PGao L(2019)A framework of mapping undirected to directed graphs for community detectionInformation Sciences: an International Journal10.1016/j.ins.2014.10.069298:C(330-343)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.ins.2014.10.069
Zhang RJin ZXu PLiu X(2019)RETRACTED ARTICLE: A dynamic clustering based method in community detectionCluster Computing10.1007/s10586-017-1472-522:Suppl 3(5703-5717)Online publication date: 1-May-2019
https://dl.acm.org/doi/10.1007/s10586-017-1472-5
Tsugawa SMatsumoto YOhsaki H(2018)On the robustness of centrality measures against link weight quantization in social networksComputational & Mathematical Organization Theory10.1007/s10588-015-9188-721:3(318-339)Online publication date: 23-Dec-2018
https://dl.acm.org/doi/10.1007/s10588-015-9188-7
Karimi-Majd AFathian MGholamian M(2017)Behavior-based indices for evaluating communities in online social networksIntelligent Data Analysis10.3233/IDA-15034921:1(205-220)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.3233/IDA-150349
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