 Group Degree Centrality and Centralization in NetworksMatjaž Krnc and
Riste Škrekovski
Mathematics, 2020, vol. 8, issue 10, 1-11 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. Keywords: vertex degree; group centrality; freeman centralization (search for similar items in EconPapers) Downloads: (external link) Related works: Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:10:p:1810-:d:429165 Access Statistics for this article Mathematics is currently edited by Ms. Emma He More articles in Mathematics from MDPI |
Is your work missing from RePEc? Here is how to contribute.
Questions or problems? Check the EconPapers FAQ or send mail to .
EconPapers is hosted by the
School of Business at Örebro University.