Top

Computing

Published in:

29-01-2024 | Regular Article

Community detection of weighted complex networks via transitive closure

Authors: Ahmadi Hasan, Ahmad Kamal

Published in: Computing | Issue 3/2024

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The K-means algorithm has been successfully applied to many complex network analysis problems. However, this method is sensitive to how the first cluster centers are chosen. It is possible to minimize superfluous runs by choosing the first cluster center in advance because each run produces a unique set of results. To overcome this issue, an algorithm for Community Detection based on Transitive Closure (CoDTC) has been introduced. In this algorithm, the initial cluster center is provided by degree centrality and T-transitive closure. The algorithm initializes with the calculation of the similarity relation matrix. Then, to avoid the limitation of sparse problems in complex network analysis, we offer the idea of transitive closure on weighted networks to solve the sparsity issue. This notion is based on imposing a t-norm inequality on the connection weights and providing a method to compute them. Finally, based on T-transitive closure, new cluster centers are calculated iteratively to avoid random selection of cluster centers. In this paper, we demonstrate the efficacy of the CoDTC approach on a diverse range of real and artificial networks, encompassing both big and small communities.

previous article TEDA: a trusted execution environment-and-blockchain-based data protection architecture for Internet of Things

next article A priority aware local mutual exclusion algorithm for flying ad hoc networks

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Zarandi FD, Rafsanjani MK (2018) Community detection in complex networks using structural similarity. Phys A: Stat Mech Appl 503:882–891CrossRef

Hu L, Pan X, Tang Z, Luo X (2021) A fast fuzzy clustering algorithm for complex networks via a generalized momentum method. IEEE Trans Fuzzy Syst 30(9):3473–3485CrossRef

Cheng S, Giesen J, Huang T, Lucas P, Mueller K (2022) Identifying the skeptics and the undecided through visual cluster analysis of local network geometry. Vis Infor 6(3):11–22

Wu C, Peng Q, Lee J, Leibnitz K, Xia Y (2021) Effective hierarchical clustering based on structural similarities in nearest neighbor graphs. Knowl-Based Syst 228:107295CrossRef

Uppada SK (2014) Centroid based clustering algorithms-a clarion study. Int J Comput Sci Inform Technol 5(6):7309–7313

Rezaei M (2020) Improving a centroid-based clustering by using suitable centroids from another clustering. J Classif 37(2):352–365MathSciNetCrossRef

Bhattacharjee P, Mitra P (2021) A survey of density based clustering algorithms. Front Comput Sci 15(1):1–27CrossRef

Von Luxburg U (2007) A tutorial on spectral clustering. Stat Comput 17(4):395–416MathSciNetCrossRef

Berahmand K, Mohammadi M, Faroughi A, Mohammadiani RP (2022) A novel method of spectral clustering in attributed networks by constructing parameter-free affinity matrix. Clust Comput 25(2):869–888CrossRef

10.

Raghavan UN, Albert R, Kumara S (2007) Near linear time algorithm to detect community structures in large-scale networks. Phys Rev E 76(3):036106ADSCrossRef

11.

J. B. MacQueen (1967) Some methods for classification and analysis of multivariate observations. In: Proceedings of 5th Berkeley Symposium on Mathematical Statistics and Probability, vol 1(14), pp 281–297

12.

Jiang Y, Jia C, Yu J (2013) An efficient community detection method based on rank centrality. Phys A: Stat Mech Appl 392(9):2182–2194MathSciNetCrossRef

13.

Li Y, Jia C, Yu J (2015) A parameter-free community detection method based on centrality and dispersion of nodes in complex networks. Phys A: Stat Mech Appl 438:321–334CrossRef

14.

Wang T, Wang H, Wang X (2015) A novel cosine distance for detecting communities in complex networks. Phys A: Stat Mech Appl 437:21–35MathSciNetCrossRef

15.

Popat SK, Emmanuel M (2014) Review and comparative study of clustering techniques.Int J Comput Sci Inform Technol 5(1):805–812

16.

Celebi ME, Kingravi HA, Vela PA (2013) A comparative study of efficient initialization methods for the k-means clustering algorithm. Expert Syst Appl 40(1):200–210CrossRef

17.

Vassilvitskii S and Arthur D (2006) k-means++: the advantages of careful seeding. In: Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, pp 1027–1035

18.

Girvan M, Newman ME (2002) Community structure in social and biological networks. Proc Natl Acad Sci 99(12):7821–7826ADSMathSciNetCrossRefPubMedPubMedCentral

19.

Dilmaghani S, Brust MR, Danoy G, and Bouvry P (2021) Community detection in complex networks: a survey on local approaches. In: Asian Conference on Intelligent Information and Database Systems, Springer, pp 757–767

20.

Sun PG, Gao L, Han SS (2011) Identification of overlapping and non-overlapping community structure by fuzzy clustering in complex networks. Inform Sci 181(6):1060–1071CrossRef

21.

Zeng S, Tong X, Sang N (2014) Study on multi-center fuzzy c-means algorithm based on transitive closure and spectral clustering. Appl Soft Comput 16:89–101CrossRef

22.

Wang X, Liu G, Li J, Nees JP (2017) Locating structural centers: A density-based clustering method for community detection. PloS one 12(1):e0169355CrossRefPubMedPubMedCentral

23.

Wang X, Liu G, Li J (2017) Overlapping community detection based on structural centrality in complex networks. IEEE Access 5:25258–25269CrossRef

24.

Cai B, Zeng L, Wang Y, Li H, Hu Y (2019) Community detection method based on node density, degree centrality, and k-means clustering in complex network. Entropy 21(12):1145ADSMathSciNetCrossRefPubMedCentral

25.

Rukmi AM, Utomo DB, Sholikhah NI (2018) Study of parameters of the nearest neighbour shared algorithm on clustering documents. J Phys: Conf Ser 974:012061

26.

Klement EP, Mesiar R, Pap E (2004) Triangular norms. position paper I: basic analytical and algebraic properties. Fuzzy Sets Syst 143(1):5–26MathSciNetCrossRef

27.

Menger K (2003) Statistical metrics. Selecta Mathematica 2:433–435CrossRef

28.

Schweizer B and Sklar A (2011) Probabilistic metric spaces. Courier Corporation

29.

Patel AM (2020) Accelerating transitive closure of large-scale sparse graphs. New Jersey Institute of Technology

30.

Newman ME (2006) Modularity and community structure in networks. Proc Natl Acad Sci 103(23):8577–8582ADSCrossRefPubMedPubMedCentral

31.

Xuan N, Julien V, Wales S, Bailey J (2010) Information theoretic measures for clusterings comparison: variants, properties, normalization and correction for chance. J Machine Learning Res 11:2837–2854MathSciNet

32.

Hubert L, Arabie P (1985) Comparing partitions. J Classif 2(1):193–218CrossRef

33.

Floyd RW (1962) Algorithm 97: shortest path. Commun ACM 5(6):345CrossRef

34.

Naessens H, De Meyer H, De Baets B (2002) Algorithms for the computation of t-transitive closures. IEEE Trans Fuzzy Syst 10(4):541–551CrossRef

35.

Zachary WW (1977) An information flow model for conflict and fission in small groups. J Anthropol Res 33(4):452–473CrossRef

36.

Lusseau D (2003) The emergent properties of a dolphin social network. Proc R Soc Lond Ser B: Biol Sci 270(suppl_2):S186–S188

37.

Benham T, Duan Q, Kroese DP, and Liquet B (2015) Ceoptim: cross-entropy r package for optimization, arXiv preprint arXiv:1503.01842

38.

Adamic LA and Glance N (2005) The political blogosphere and the 2004 us election: divided they blog. In: Proceedings of the 3rd international workshop on Link discovery, pp 36–43, ACM

39.

Gleiser PM, Danon L (2003) Community structure in jazz. Adv Compl Syst 6(04):565–573CrossRef

40.

Newman ME, Girvan M (2004) Finding and evaluating community structure in networks. Phys Rev E 69(2):026113ADSCrossRef

41.

Guimera R, Danon L, Diaz-Guilera A, Giralt F, Arenas A (2003) Self-similar community structure in a network of human interactions. Phys Rev E 68(6):065103ADSCrossRef

42.

Kunegis J (2013) Konect: the koblenz network collection. In: Proceedings of the 22nd international conference on world wide web, pp 1343–1350

43.

Hartigan JA and Wong MA (1979) Algorithm as 136: a k-means clustering algorithm. J R Stat Soc Ser c (Appl Stat) 28(1):100–108

44.

Clauset A, Newman ME, Moore C (2004) Finding community structure in very large networks. Phys Rev E 70(6):066111ADSCrossRef

45.

Albert R, Barabási A-L (2002) Statistical mechanics of complex networks. Rev Mod Phys 74(1):47ADSMathSciNetCrossRef

Title: Community detection of weighted complex networks via transitive closure
Authors: Ahmadi Hasan
Ahmad Kamal
Publication date: 29-01-2024
Publisher: Springer Vienna
Published in: Computing / Issue 3/2024
Print ISSN: 0010-485X
Electronic ISSN: 1436-5057
DOI: https://doi.org/10.1007/s00607-023-01249-8

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Springer Professional "Wirtschaft+Technik"

Other articles of this Issue 3/2024

Distributed mobile CEP for collaborative social computing

HHSE: heterogeneous graph neural network via higher-order semantic enhancement

UAV-assisted wireless charging and data processing of power IoT devices

A novel energy-aware method for clustering and routing in IoT based on whale optimization algorithm & Harris Hawks optimization

Nature-inspired donkey and smuggler algorithm for optimal data gathering in partitioned wireless sensor networks for restoring network connectivity

Quantifying influential nodes in complex networks using optimization and particle dynamics: a comparative study

Premium Partner