Group degree centrality and centralization in networks

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

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.

• Jezik: Angleški jezik
• Ključne besede: vertex degree, group centrality, Freeman centralization
• Vrsta gradiva: Članek v reviji
• Tipologija: 1.01 - Izvirni znanstveni članek
• Organizacija: FMF - Fakulteta za matematiko in fiziko
• Status publikacije: Objavljeno
• Različica publikacije: Objavljena publikacija
• Leto izida: 2020
• Št. strani: 11 str.
• Številčenje: Vol. 8, iss. 10, art. 1810
• PID: 20.500.12556/RUL-134465
• UDK: 519.17
• ISSN pri članku: 2227-7390
• DOI: 10.3390/math8101810
• COBISS.SI-ID: 33826563
• Datum objave v RUL: 17.01.2022

Gradivo je del revije

• Naslov: Mathematics
• Skrajšan naslov: Mathematics
• Založnik: MDPI AG
• ISSN: 2227-7390
• COBISS.SI-ID: 523267865

Licence

• Licenca: CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
• Povezava: http://creativecommons.org/licenses/by/4.0/deed.sl
• Opis: To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.
• Začetek licenciranja: 16.10.2020

Sekundarni jezik

• Jezik: Slovenski jezik
• Ključne besede: stopnja vozlišča, skupinska centralnost, Freemanova centralizacija