Group degree centrality and centralization in networks
| Autor: | Matjaž Krnc, Riste Škrekovski |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2022 |
| Předmět: |
group centrality
General Mathematics 0211 other engineering and technologies skupinska centralnost 0102 computer and information sciences 02 engineering and technology 01 natural sciences Measure (mathematics) vertex degree Freeman centralization Set (abstract data type) freeman centralization Freemanova centralizacija Computer Science (miscellaneous) Engineering (miscellaneous) Time complexity Mathematics Discrete mathematics Degree (graph theory) Group (mathematics) lcsh:Mathematics 021107 urban & regional planning Directed graph lcsh:QA1-939 udc:519.17 010201 computation theory & mathematics Centrality Value (mathematics) stopnja vozlišča |
| Zdroj: | Mathematics, vol. 8, no. 10, 1810, 2020. Mathematics, Vol 8, Iss 1810, p 1810 (2020) Mathematics Volume 8 Issue 10 |
| ISSN: | 2227-7390 |
| Popis: | The importance of individuals and groups in networks is modeled by various centrality measures. Additionally, Freeman&rsquo 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&minus 1/e)(w*&minus 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|