Group degree centrality and centralization in networksKrnc, Matjaž (Avtor) Škrekovski, Riste (Avtor) vertex degreegroup centralityFreeman centralizationThe 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.20202022-01-17 10:27:07Članek v reviji134465UDK: 519.17ISSN pri članku: 2227-7390DOI: 10.3390/math8101810COBISS_ID: 33826563sl