Group Degree Centrality and Centralization in Networks
Matjaž Krnc, Riste Škrekovski
Abstract
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.