nach oben

Erschienen in:

2021 | OriginalPaper | Buchkapitel

Correlations Among Game of Thieves and Other Centrality Measures in Complex Networks

verfasst von : Annamaria Ficara, Giacomo Fiumara, Pasquale De Meo, Antonio Liotta

Erschienen in: Data Science and Internet of Things

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Social Network Analysis (SNA) is used to study the exchange of resources among individuals, groups, or organizations. The role of individuals or connections in a network is described by a set of centrality metrics which represent one of the most important results of SNA. Degree, closeness, betweenness and clustering coefficient are the most used centrality measures. Their use is, however, severely hampered by their computation cost. This issue can be overcome by an algorithm called Game of Thieves (GoT). Thanks to this new algorithm, we can compute the importance of all elements in a network (i.e. vertices and edges), compared to the total number of vertices. This calculation is done not in a quadratic time, as when we use the classical methods, but in polylogarithmic time. Starting from this we present our results on the correlation existing between GoT and the most widely used centrality measures. From our experiments emerge that a strong correlation exists, which makes GoT eligible as a centrality measure for large scale complex networks.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Evolutionary Dynamics and Multiplexity for Mobile Edge Computing in a Healthcare Scenario

Nächstes Kapitel A LPWAN Case Study for Asset Tracking

Barabási, A.L., Albert, R.: Emergence of scaling in random networks. Science 286(5439), 509–512 (1999). https://doi.org/10.1126/science.286.5439.509.

Bolland, J.M.: Sorting out centrality: an analysis of the performance of four centrality models in real and simulated networks. Soc. Netw. 10(3), 233–253 (1988). https://doi.org/10.1016/0378-8733(88)90014-7.

Bonacich, P.: Power and centrality: a family of measures. Am. J. Soc. 92(5), 1170–1182 (1987). https://doi.org/10.1086/228631

Brandes, U.: On variants of shortest-path betweenness centrality and their generic computation. Soc. Netw. 30(2), 136–145 (2008). https://doi.org/10.1016/j.socnet.2007.11.001.

Calderoni, F., Catanese, S., De Meo, P., Ficara, A., Fiumara, G.: Robust link prediction in criminal networks: a case study of the Sicilian Mafia. Expert Syst. Appl. 161, 113666 (2020). https://doi.org/10.1016/j.eswa.2020.113666.

Chen, P., Popovich, P.: Correlation: parametric and nonparametric measures. Sage university papers series. No. 07-139. Sage Publications (2002). https://books.google.it/books?id=UN4nAQAAIAAJ

De Meo, P., Ferrara, E., Fiumara, G., Provetti, A.: Enhancing community detection using a network weighting strategy. Inf. Sci. 222, 648–668 (2013). https://doi.org/10.1016/j.ins.2012.08.001.

De Meo, P., Ferrara, E., Fiumara, G., Provetti, A.: Mixing local and global information for community detection in large networks. J. Comput. Syst. Sci. 80(1), 72–87 (2014). https://doi.org/10.1016/j.jcss.2013.03.012.

De Meo, P., Ferrara, E., Fiumara, G., Ricciardello, A.: A novel measure of edge centrality in social networks. Knowl. Based Syst. 30, 136–150 (2012). https://doi.org/10.1016/j.knosys.2012.01.007.

10.

Duan, Y., Fu, X., Li, W., Zhang, Y., Fortino, G.: Evolution of scale-free wireless sensor networks with feature of small-world networks. Complexity 2017, 1–15 (2017). https://doi.org/10.1155/2017/2516742

11.

Erdös, P., Rényi, A.: On random graphs i. Publicationes Mathematicae Debrecen 6, 290 (1959)MathSciNetMATH

12.

Faust, K.: Centrality in affiliation networks. Soc. Netw. 19(2), 157–191 (1997). https://doi.org/10.1016/S0378-8733(96)00300-0.

13.

Ficara, A., Cavallaro, L., De Meo, P., Fiumara, G., Catanese, S., Bagdasar, O., Liotta, A.: Social network analysis of Sicilian Mafia interconnections. In: Cherifi, H., Gaito, S., Mendes, J.F., Moro, E., Rocha, L.M. (eds.) Complex Networks and Their Applications VIII, pp. 440–450. Springer International Publishing, Cham (2020). https://doi.org/10.1007/978-3-030-36683-4_36

14.

Fortino, G., Liotta, A., Messina, F., Rosaci, D., Sarne, G.M.L.: Evaluating group formation in virtual communities. IEEE/CAA J. Autom. Sin. 7(4), 1003–1015 (2020). https://doi.org/10.1109/JAS.2020.1003237

15.

Freeman, L.C.: Centrality in social networks conceptual clarification. Soc. Netw. 1(3), 215–239 (1978). https://doi.org/10.1016/0378-8733(78)90021-7.

16.

Friedkin, N.E.: Theoretical foundations for centrality measures. Am. J. Soc. 96(6), 1478–1504 (1991). https://doi.org/10.1086/229694

17.

Galaskiewicz, J.: Social Organization of an Urban Grants Economy: A Study of Business Philanthropy and Non-Profit Organizations. Academic Press (1985). https://books.google.it/books?id=Vd25AAAAIAAJ

18.

Gilbert, E.N.: Random graphs. Ann. Math. Statist. 30(4), 1141–1144 (1959). https://doi.org/10.1214/aoms/1177706098

19.

Gkoulalas-Divanis, A., Labbi, A.: Large-Scale Data Analytics. SpringerLink : Bücher. Springer, New York (2014). https://books.google.it/books?id=1F24BAAAQBAJ

20.

Grando, F., Noble, D., Lamb, L.C.: An analysis of centrality measures for complex and social networks. In: 2016 IEEE Global Communications Conference (GLOBECOM), pp. 1–6 (2016). https://doi.org/10.1109/GLOCOM.2016.7841580

21.

Hagberg, A.A., Schult, D.A., Swart, P.J.: Exploring network structure, dynamics, and function using networkx. In: Varoquaux, G., Vaught, T., Millman J. (eds.) Proceedings of the 7th Python in Science Conference, pp. 11–15. Pasadena, CA USA (2008)

22.

Holme, P., Kim, B.J.: Growing scale-free networks with tunable clustering. Phys. Rev. E 65, 026107 (2002). https://doi.org/10.1103/PhysRevE.65.026107

23.

Kendall, M., Gibbons, J.: Rank Correlation Methods. Charles Griffin Book. E. Arnold (1990). https://books.google.it/books?id=ly4nAQAAIAAJ

24.

Li, C., Li, Q., Van Mieghem, P., Stanley, H.E., Wang, H.: Correlation between centrality metrics and their application to the opinion model. Eur. Phys. J. B 88(3), 65 (2015). https://doi.org/10.1140/epjb/e2015-50671-y

25.

Lusseau, D., Schneider, K., Boisseau, O.J., Haase, P., Slooten, E., Dawson, S.M.: The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations. Behav. Ecol. Sociobiol. 54(4), 396–405 (2003). https://doi.org/10.1007/s00265-003-0651-y

26.

Mocanu, D.C., Exarchakos, G., Liotta, A.: Decentralized dynamic understanding of hidden relations in complex networks. Sci. Rep. 8(1), 1571 (2018). https://doi.org/10.1038/s41598-018-19356-4

27.

Newman, M., Watts, D.: Renormalization group analysis of the small-world network model. Phys. Lett. A 263(4), 341–346 (1999). https://doi.org/10.1016/S0375-9601(99)00757-4.

28.

Newman, M.E.J.: The structure of scientific collaboration networks. Proc. Natl. Acad. Sci. 98(2), 404–409 (2001). https://doi.org/10.1073/pnas.98.2.404.

29.

Oldham, S., Fulcher, B., Parkes, L., Arnatkeviciute, A., Suo, C., Fornito, A.: Consistency and differences between centrality measures across distinct classes of networks. PLOS ONE 14(7), 1–23 (2019). https://doi.org/10.1371/journal.pone.0220061

30.

Pace, P., Fortino, G., Zhang, Y., Liotta, A.: Intelligence at the edge of complex networks: the case of cognitive transmission power control. IEEE Wirel. Commun. 26(3), 97–103 (2019). https://doi.org/10.1109/MWC.2019.1800354

31.

Ronqui, J.R.F., Travieso, G.: Analyzing complex networks through correlations in centrality measurements. J. Stat. Mech. Theory Exp. 2015(5), P05030 (2015). https://doi.org/10.1088/1742-5468/2015/05/p05030

32.

Rothenberg, R.B., Potterat, J.J., Woodhouse, D.E., Darrow, W.W., Muth, S.Q., Klovdahl, A.S.: Choosing a centrality measure: Epidemiologic correlates in the Colorado Springs study of social networks. Soc. Netw. 17(3), 273–297 (1995). https://doi.org/10.1016/0378-8733(95)00267-R.

33.

Scott, J.: Social Network Analysis: A Handbook. SAGE Publications (2000). https://books.google.it/books?id=Ww3_bKcz6kgC

34.

Shao, C., Cui, P., Xun, P., Peng, Y., Jiang, X.: Rank correlation between centrality metrics in complex networks: an empirical study. Open Phys. 16(1), 1009–1023 (2018). https://doi.org/10.1515/phys-2018-0122CrossRef

35.

Spearman, C.: General intelligence, objectively determined and measured. Am. J. Psychol. 15(2), 201–292 (1904). https://doi.org/10.2307/1412107.

36.

Stephenson, K., Zelen, M.: Rethinking centrality: methods and examples. Soc. Netw. 11(1), 1–37 (1989). https://doi.org/10.1016/0378-8733(89)90016-6.

37.

Valente, T.W., Coronges, K., Lakon, C., Costenbader, E.: How correlated are network centrality measures? Connections (Toronto, Ont.) 28(1), 16–26 (2008). https://pubmed.ncbi.nlm.nih.gov/20505784

38.

Valente, T.W., Foreman, R.K.: Integration and radiality: measuring the extent of an individual’s connectedness and reachability in a network. Soc. Netw. 20(1), 89–105 (1998). https://doi.org/10.1016/S0378-8733(97)00007-5.

39.

Wasserman, S., Faust, K., Granovetter, M., Iacobucci, D.: Social Network Analysis: Methods and Applications. Structural Analysis in the Social Sciences. Cambridge University Press, Cambridge (1994). https://books.google.it/books?id=CAm2DpIqRUIC

40.

Watts, D.J., Strogatz, S.H.: Collective dynamics of ‘small-world’ networks. Nature 393(6684), 440–442 (1998). https://doi.org/10.1038/30918

Titel: Correlations Among Game of Thieves and Other Centrality Measures in Complex Networks
verfasst von: Annamaria Ficara
Giacomo Fiumara
Pasquale De Meo
Antonio Liotta
Verlag: Springer International Publishing
Buch: Data Science and Internet of Things
Print ISBN: 978-3-030-67196-9

Electronic ISBN: 978-3-030-67197-6

Copyright-Jahr: 2021
DOI: https://doi.org/10.1007/978-3-030-67197-6_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"