Group Degree Centrality and Centralization in Networks
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2020-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/8/10/1810 |
| _version_ | 1797550721275527168 |
|---|---|
| author | Matjaž Krnc Riste Škrekovski |
| author_facet | Matjaž Krnc Riste Škrekovski |
| author_sort | Matjaž Krnc |
| collection | DOAJ |
| description | 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 <i>k</i>, which <i>k</i>-subset <i>S</i> of members of <i>G</i> represents the most central group? Among all possible values of <i>k</i>, which is the one for which the corresponding set <i>S</i> is most central? How can we efficiently compute both <i>k</i> and <i>S</i>? To answer these questions, we relate with the well-studied areas of domination and set covers. Using this, we first observe that determining <i>S</i> from the first question is <inline-formula><math display="inline"><semantics><mi mathvariant="script">NP</mi></semantics></math></inline-formula>-hard. Then, we describe a greedy approximation algorithm which computes centrality values over all group sizes <i>k</i> from 1 to <i>n</i> in linear time, and achieve a group degree centrality value of at least <inline-formula><math display="inline"><semantics><mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo>)</mo></mrow><mrow><mo>(</mo><msup><mi>w</mi><mo>*</mo></msup><mo>−</mo><mi>k</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, compared to the optimal value of <inline-formula><math display="inline"><semantics><msup><mi>w</mi><mo>*</mo></msup></semantics></math></inline-formula>. To achieve fast running time, we design a special data structure based on the related directed graph, which we believe is of independent interest. |
| first_indexed | 2024-03-10T15:34:20Z |
| format | Article |
| id | doaj.art-41e2cb8c6a944df29d4f7ff9e6c59b84 |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T15:34:20Z |
| publishDate | 2020-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-41e2cb8c6a944df29d4f7ff9e6c59b842023-11-20T17:22:09ZengMDPI AGMathematics2227-73902020-10-01810181010.3390/math8101810Group Degree Centrality and Centralization in NetworksMatjaž Krnc0Riste Škrekovski1FAMNIT, University of Primorska, 6000 Koper, SloveniaFAMNIT, University of Primorska, 6000 Koper, SloveniaThe 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 <i>k</i>, which <i>k</i>-subset <i>S</i> of members of <i>G</i> represents the most central group? Among all possible values of <i>k</i>, which is the one for which the corresponding set <i>S</i> is most central? How can we efficiently compute both <i>k</i> and <i>S</i>? To answer these questions, we relate with the well-studied areas of domination and set covers. Using this, we first observe that determining <i>S</i> from the first question is <inline-formula><math display="inline"><semantics><mi mathvariant="script">NP</mi></semantics></math></inline-formula>-hard. Then, we describe a greedy approximation algorithm which computes centrality values over all group sizes <i>k</i> from 1 to <i>n</i> in linear time, and achieve a group degree centrality value of at least <inline-formula><math display="inline"><semantics><mrow><mrow><mo>(</mo><mn>1</mn><mo>−</mo><mn>1</mn><mo>/</mo><mi>e</mi><mo>)</mo></mrow><mrow><mo>(</mo><msup><mi>w</mi><mo>*</mo></msup><mo>−</mo><mi>k</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, compared to the optimal value of <inline-formula><math display="inline"><semantics><msup><mi>w</mi><mo>*</mo></msup></semantics></math></inline-formula>. To achieve fast running time, we design a special data structure based on the related directed graph, which we believe is of independent interest.https://www.mdpi.com/2227-7390/8/10/1810vertex degreegroup centralityfreeman centralization |
| spellingShingle | Matjaž Krnc Riste Škrekovski Group Degree Centrality and Centralization in Networks Mathematics vertex degree group centrality freeman centralization |
| title | Group Degree Centrality and Centralization in Networks |
| title_full | Group Degree Centrality and Centralization in Networks |
| title_fullStr | Group Degree Centrality and Centralization in Networks |
| title_full_unstemmed | Group Degree Centrality and Centralization in Networks |
| title_short | Group Degree Centrality and Centralization in Networks |
| title_sort | group degree centrality and centralization in networks |
| topic | vertex degree group centrality freeman centralization |
| url | https://www.mdpi.com/2227-7390/8/10/1810 |
| work_keys_str_mv | AT matjazkrnc groupdegreecentralityandcentralizationinnetworks AT risteskrekovski groupdegreecentralityandcentralizationinnetworks |