20.500.12556/RUL-134465 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 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. vertex degree group centrality Freeman centralization stopnja vozlišča skupinska centralnost Freemanova centralizacija true false true Angleški jezik Slovenski jezik Članek v reviji 2022-01-17 10:27:07 2022-01-17 10:27:09 2022-09-13 03:55:20 0000-00-00 00:00:00 2020 0 0 11 str. iss. 10, art. 1810 Vol. 8 2020 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 519.17 2227-7390 10.3390/math8101810 33826563 RAZ_Krnc_Matjaz_2020.pdf RAZ_Krnc_Matjaz_2020.pdf 1 DBF3D9CA139979A8B981D77DD3410BB1 38c036eef943613c6323d36c2fdb290f9d9bd437b883ab567104b4c049adc7da b3bb09df-7777-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=152935 https://www.mdpi.com/2227-7390/8/10/1810 0 924268bc-7777-11ec-abdb-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=152934 Fakulteta za matematiko in fiziko 0 0 0