Group degree centrality and centralization in networks

Krnc, Matjaž (author), Škrekovski, Riste (author)

The importance of individuals and groups in networks is modeled by various centrality measures. Additionally, 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. In this paper, we focus on degree-based measures of group centrality and centralization. We address the following related questions: For a fixed k, which k-subset S of members of G represents the most central group? Among all possible values of k, which is the one for which the corresponding set S is most central? How can we efficiently compute both k and S? To answer these questions, we relate with the well-studied areas of domination and set covers. Using this, we first observe that determining S from the first question is NP-hard. Then, we describe a greedy approximation algorithm which computes centrality values over all group sizes k from 1 to n in linear time, and achieve a group degree centrality value of at least (1 − 1/e)(w* − k), compared to the optimal value of w*. To achieve fast running time, we design a special data structure based on the related directed graph, which we believe is of independent interest.

• Language: English
• Keywords: vertex degree, group centrality, Freeman centralization
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2020
• Number of pages: 11 str.
• Numbering: Vol. 8, iss. 10, art. 1810
• PID: 20.500.12556/RUL-134465
• UDC: 519.17
• ISSN on article: 2227-7390
• DOI: 10.3390/math8101810
• COBISS.SI-ID: 33826563
• Publication date in RUL: 17.01.2022

Record is a part of a journal

• Title: Mathematics
• Shortened title: Mathematics
• Publisher: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.
• Licensing start date: 16.10.2020

Secondary language

• Language: Slovenian
• Keywords: stopnja vozlišča, skupinska centralnost, Freemanova centralizacija