Evaluating group degree centrality and centralization in networks

Mario Karlovčec, Matjaž Krnc, Riste Škrekovski


Given a network G, the importance of groups can be modelled by group centrality measures. Freeman’s centralization is a way to normalize any given centrality or group centrality measure, which enables us to compare individuals or groups from different networks. We focus on a degree-based measure of group centrality and centralization, presented by Krnc and Škrekovski (2020). We describe its efficient implementation and study the behaviour of various real-world networks within this context. We conclude that very small groups, as well as very big ones, are not very central, i.e. as the group is growing, its value is increasing but, at some point it starts decreasing. Such unimodular behaviour is confirmed by our analysis of group degree centralization of six real-world networks. At the end, we provide some challenges for future work. 

Full Text:



Bavelas, A.: A mathematical model for group structures. Hum. Organ. 7(3), 16–30 (1948)

Bavelas, A.: Communication patterns in task-oriented groups. J. Acoust. Soc. Am. pp. 725–730 (1950)

Bell, J.R.: Subgroup centrality measures. Network Science 2(02), 277–297 (2014)

Borgatti, S.P.: Identifying sets of key players in a social network. Comput. Math. Organ. Theory 12(1), 21–34 (2006)

Brandes, U., Erlebach, T.: Network analysis: methodological foundations, vol. 3418. Springer Science & Business Media (2005)

Estrada, E., Rodriguez-Velazquez, J.A.: Subgraph centrality in complex net- works. Physical Review E 71(5), 056103 (2005)

Everett, M.G., Borgatti, S.P.: The centrality of groups and classes. J. Math. Sociol. 23(3), 181–201 (1999)

Everett, M.G., Borgatti, S.P.: Extending centrality. Models and methods in social network analysis 35(1), 57–76 (2005)

Everett, M.G., Sinclair, P., Dankelmann, P.: Some centrality results new and old. J. Math. Sociol. 28(4), 215–227 (2004)

Freeman, L.C.: Centrality in social networks conceptual clarification. Social Networks 1(3), 215–239 (1979)

Hall, B.H., Jaffe, A.B., Trajtenberg, M.: The NBER Patent Citation Data File: Lessons, Insights and Methodological Tools. NBER Working Pa- pers 8498, National Bureau of Economic Research, Inc (Oct 2001)

Hochbaum, D.S., Pathria, A.: Analysis of the greedy approach in problems of maximum k-coverage. Naval Research Logistics 45(6), 615–627 (1998)

Jordan, C.: Sur les assemblages de lignes. J. Reine Angew. Math 70(185), 81 (1869)

Koschu ̈tzki, D., Lehmann, K.A., Peeters, L., Richter, S., Tenfelde-Podehl, D., Zlotowski, O.: Centrality indices. In: Network analysis, pp. 16–61. Springer (2005)

Krnc, M., Sˇkrekovski, R.: Group degree centrality and centralization in net- works. Mathematics 8(10) (2020). https://doi.org/10.3390/math8101810

Krnc, M., Sˇkrekovski, R.: Group centralization of network indices. Discrete Appl. Math. 186, 147–157 (2015)

Leskovec, J., Adamic, L.A., Huberman, B.A.: The dynamics of viral mar- keting. ACM Trans. Web 1(1) (May 2007)

Leskovec, J., Kleinberg, J., Faloutsos, C.: Graphs over time: Densification laws, shrinking diameters and possible explanations. In: Proceedings of the Eleventh ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. pp. 177–187. KDD ’05, ACM, New York, NY, USA (2005)

Leskovec, J., Mcauley, J.J.: Learning to discover social circles in ego net- works. In: Bartlett, P., Pereira, F., Burges, C., Bottou, L., Weinberger, K. (eds.) Advances in Neural Information Processing Systems 25, pp. 548–556 (2012)

Mislove, A., Marcon, M., Gummadi, K.P., Druschel, P., Bhattacharjee, B.: Measurement and Analysis of Online Social Networks. In: Proceedings of the 5th ACM/Usenix Internet Measurement Conference (IMC’07). San Diego, CA (October 2007)

Miyano, E., Ono, H.: Maximum domination problem. In: Proceedings of the Seventeenth Computing: The Australasian Theory Symposium-Volume 119. pp. 55–62. Australian Computer Society, Inc. (2011)

Proctor, C.H., Loomis, C.P.: Research Methods in Social Relations, chap. Analysis of sociometric data, pp. 561–586. Dryden Press, New York (1951)

Seeley, J.R.: The net of reciprocal influence; a problem in treating sociometric data. Can. J. Psychol. (3), 234–240 (1949)

Vohra, R.V., Hall, N.G.: A probabilistic analysis of the maximal covering location problem. Discrete Applied Mathematics 43(2), 175–183 (1993)

White, S., Smyth, P.: Algorithms for estimating relative importance in net- works. In: Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 266–275. ACM (2003)

DOI: https://doi.org/10.31449/inf.v46i5.3817

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.