Using Density Criterion and Increasing Modularity to Detect Communities in Complex Networks

Authors

  • Iman Hasan Abed Department of Computer Engineering, Islamic Azad University, Isfahan , Iran
  • Sondos Bahadori Department of Computer Engineering, Ilam Branch, Islamic Azad University, Ilam, Iran,‎ https://orcid.org/0009-0004-5365-6182

DOI:

https://doi.org/10.51173/ijds.v2i1.12

Abstract

The selection of the initial centers of the communities is also significant in iteration-based methods for finding the communities in the networks. This is the reason why, if the initial centers of the communities are not chosen correctly, the errors and the time required for the application of the algorithm in the detection of the communities will be higher. Hence, selecting more significant nodes as starting points of communities can be the appropriate solution. Various techniques can be employed to achieve the selection of more significant nodes. In this thesis, the algorithm under discussion employs density and modularity criteria in the identification of communities in complex networks. This algorithm initially, defines the number of nodes or the distinctive members of the community, which these nodes have higher density levels and all the other nodes in their neighborhood have lower density levels. Next, the local communities are defined as the nodes that are in some way connected to the core nodes. Finally, the final communities are defined with the assistance of the merging algorithm, which is based on increasing modularity. In this algorithm, increasing modularity is used as a criterion for joining local communities together. Modularity is a criterion that indicates how the graph is like a modular or an organized community. When modularity becomes higher, local communities merge to form the final community. This means that it is possible to apply the presented algorithm and to use both density and modularity criteria to detect communities in complex networks. When the core nodes and local communities are first detected, and then merged based on the increasing value of modularity, the resultant communities are more accurate. The results of the conducted experiments prove that the method applied in the Karate Club network clustering is equal to 0. 6913 for the NMI criterion and a value of 0. 733 for the accuracy criterion.

Downloads

Download data is not yet available.

References

S. Zhao, X. Yue, S. Zhang, B. Li, H. Zhao, B. Wu, R. Krishna, J.E. Gonzalez, A.L. Sangiovanni-Vincentelli, S.A. Seshia, K. Keutzer, A review of single- source deep unsupervised visual domain adaptation, IEEE Transactions on Neural Networks and Learning Systems (2020) 1–21, https://doi.org/10.1109/TNNLS.2020.3028503.

J. Yu, M. Tan, H. Zhang, D. Tao, Y. Rui, Hierarchical deep click feature prediction for fine-grained image recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence (2019) 1, https://doi.org/10.1109/TPAMI.2019.293 2058.

A.A. Baffour, Z. Qin, Y. Wang, Z. Qin, K.-K.R. Choo, Spatial self-attention network with self-attention distillation for fine-grained image recognition, Journal of Visual Communication and Image Representation 81 (2021), https://doi.org/10.1016/j.jvcir.2021.103368.

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

Blondel, V. D., Guillaume, J. L., Lambiotte, R., & Lefebvre, E. (2019). Fast unfolding of communities in large networks. Journal of Statistical Mechanics: Theory and Experiment, 2008(10), P10008.

Fortunato, S., & Barthélemy, M. (2020). Resolution limit in community detection. Proceedings of the National Academy of Sciences, 104(1), 36-41.

Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2019). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814-818.

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

Lancichinetti, A., Fortunato, S., & Kertész, J. (2021). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3), 033015.

Chen, X., Li, M., Wang, J., Zhou, T., & Zhang, Y. (2020). A balance-based modularity and density optimization framework for community detection. Physica A: Statistical Mechanics and its Applications, 395, 236-243.

Aynaud, T., Guillaume, J. L., & Vaillant, J. (2019). Multi-level modularity maximization: A scalable community detection method. Proceedings of the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM).

J. Yang, H. Zou, Y. Zhou, L. Xie, Robust adversarial discriminative domain adaptation for real-world cross-domain visual recognition, Neurocomputing 433 (2021) 28–36, https://doi.org/10.1016/j.neucom.2020.12.046 .

Y. Zhang, M. Li, Z. Ji, W. Fan, S. Yuan, Q. Liu, Q. Chen, Twin self- supervision based semi-supervised learning (ts-ssl): Retinal anomaly classification in sd-octimages, Neurocomputing 462 (2021) 491–505, https://doi.org/10.1016/j.neucom.2021.08.051

R. Wang, P. Chaudhari, C. Davatzikos, Embracing the disharmony in medical imaging: A simple and effective framework for domain adaptation, Medical Image Analysis (2021), https://doi.org/10.1016/j.media.2021.102309

Salman, H.S., Mansour, M.M., Lafta, A.M., Shkarah, A.J. (2024). Modification design and process of pipeline to reduce erosion rate and deposited. International Journal of Computational Methods and Experimental Measurements, Vol. 12, No. 2, June, pp. 165-173. https://doi.org/10.18280/ijcmem.120206

Mansour, M.M., Hamood, H.M., Lafta, A.M., Nashee, S.R., Shkarah, A.J. (2024). Enhancing the efficacy of adsorption-based carbon storage systems: A finite element analysis approach. International Journal of Energy Production and Management, Vol. 9, No. 1, pp. 19-24. https://doi.org/10.18280/ijepm.090103

Najm, N., Mansour, M.M. (2024). The role of waste reduction technology in sustainable recycling of waste paper at Thi-Qar University. International Journal of Sustainable Development and Planning, Vol. 19, No. 8, pp. 3153-3163. https://doi.org/10.18280/ijsdp.190828

Mansour, M.M., Salman, H.S., Lafta, A.M., Nashee, S.R., Shkarah, A.J. (2024). Simulation analysis of protection oil pipe in platform to reduced corrosion and erosion defect with sustainability technique. Mathematical Modelling of Engineering Problems, Vol. 11, No. 5, pp. 1171-1178. https://doi.org/10.18280/mmep.110505

M. Ghifary, W.B. Kleijn, M. Zhang, D. Balduzzi, Domain generalization for object recognition with multi-task autoencoders, in: 2015 IEEE International Conference on Computer Vision, ICCV 2015, IEEE Computer Society, 2015, pp. 2551–2559, https://doi.org/10.1109/ICCV.2015.293

M. Ghifary, W.B. Kleijn, M. Zhang, D. Balduzzi, W. Li, Deep reconstruction-classification networks for unsupervised domain adaptation, in: B. Leibe, J. Matas, N. Sebe, M. Welling (Eds.), Computer Vision - ECCV 2016–14th European Conference, Amsterdam, The Netherlands, October 11–14, 2016, Proceedings, Part IV, Vol. 9908 of Lecture Notes in Computer Science, Springer,2016, pp. 597–613. https://doi.org/10.1007/978-3-319-46493-0_36

K. Bousmalis, G. Trigeorgis, N. Silberman, D.Krishnan,D. Erhan, Domain separation networks, in: D.D. Lee, M. Sugiyama, U. von Luxburg, I. Guyon, R. Garnett (Eds.), Advances in Neural Information Processing Systems 29:Annual Conference on Neural Information Processing Systems 2016, December 5–10, 2016, Barcelona, Spain, 2016,pp. 343–351.

Guo, K., Huang, X., Wu, L., & Chen, Y. (2021). Local community detection algorithm based on local modularity density. Applied Intelligence, 52(2), 1238–1253. https://doi.org/10.1007/s10489-020-02052-0

Gupta, S., & Singh, D. P. (2020). Recent trends on community detection algorithms: A survey. Modern Physics Letters B, 34(35), 2050408. https://doi.org/10.1142/s0217984920504084

Jin, D., Zhang, B., Song, Y., He, D., Feng, Z., Chen, S., Li, W., & Musial, K. (2020). ModMRF: A modularity-based Markov Random Field method for community detection. Neurocomputing, 405, 218–228. https://doi.org/10.1016/j.neucom.2020.04.067

Li, H., Zhang, R., Zhao, Z., & Liu, X. (2021). LPA-MNI: An Improved Label Propagation Algorithm Based on Modularity and Node Importance for Community Detection. Entropy, 23(5), 497. https://doi.org/10.3390/e23050497

Salha-Galvan, G., Lutzeyer, J., Dasoulas, G., Hennequin, R., & Vazirgiannis, M. (2022). Modularity-aware graph autoencoders for joint community detection and link prediction. Neural Networks, 153, 474–495. https://doi.org/10.1016/j.neunet.2022.06.021

Zhou, J., Chen, Z., Du, M., Chen, L., Yu, S., Chen, G., & Xuan, Q. (2021). RobustECD: Enhancement of Network Structure for Robust Community Detection. IEEE Transactions on Knowledge and Data Engineering, 1. https://doi.org/10.1109/tkde.2021.3088844 16.

Öztemiz, F., & Karcı, A. (2023). KO: Modularity optimization in community detection. Neural Computing & Applications, 35(15), 11073–11087. https://doi.org/10.1007/s00521-023-08284-8

Chaudhary, L., & Singh, B. (2019). Community Detection Using Maximizing Modularity and Similarity Measures in Social Networks. In Smart innovation, systems and technologies (pp. 197–206). https://doi.org/10.1007/978-981-13-8406-6_20

Magelinski, T., Bartulovic, M., & Carley, K. M. (2021). Measuring Node Contribution to Community Structure With Modularity Vitality. IEEE Transactions on Network Science and Engineering, 8(1), 707–723. https://doi.org/10.1109/tnse.2020.3049068

Downloads

Published

2024-12-28

How to Cite

Iman Hasan Abed, & Bahadori, S. (2024). Using Density Criterion and Increasing Modularity to Detect Communities in Complex Networks. InfoTech Spectrum: Iraqi Journal of Data Science , 2(1), 1–15. https://doi.org/10.51173/ijds.v2i1.12

Issue

Section

Data Mining and Knowledge Discovery