IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v8y2020i10p1810-d429165.html
   My bibliography  Save this article

Group Degree Centrality and Centralization in Networks

Author

Listed:
  • Matjaž Krnc

    (FAMNIT, University of Primorska, 6000 Koper, Slovenia
    These authors contributed equally to this work.)

  • Riste Škrekovski

    (FAMNIT, University of Primorska, 6000 Koper, Slovenia
    Faculty of Information Studies, 8000 Novo Mesto, Slovenia
    Faculty of Mathematics and Physics, University of Ljubljana, 1000 Ljubljna, Slovenia
    These authors contributed equally to this work.)

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.

Suggested Citation

  • Matjaž Krnc & Riste Škrekovski, 2020. "Group Degree Centrality and Centralization in Networks," Mathematics, MDPI, vol. 8(10), pages 1-11, October.
    • Handle: RePEc:gam:jmathe:v:8:y:2020:i:10:p:1810-:d:429165
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/10/1810/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/8/10/1810/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Bell, Jocelyn R., 2014. "Subgroup centrality measures," Network Science, Cambridge University Press, vol. 2(2), pages 277-297, August.
    2. Dorit S. Hochbaum & Anu Pathria, 1998. "Analysis of the greedy approach in problems of maximum k‐coverage," Naval Research Logistics (NRL), John Wiley & Sons, vol. 45(6), pages 615-627, September.
    3. Stephen P. Borgatti, 2006. "Identifying sets of key players in a social network," Computational and Mathematical Organization Theory, Springer, vol. 12(1), pages 21-34, April.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Leila Mirtajadini & Shamsollah Shirin Bakhsh & Mir Hossein Mousavi & Kioumars Heydari & Saman Yousefvand, 2023. "Prediction of Electricity Trade Partners Based on the Network Theory: The West Asia Community," Foreign Trade Review, , vol. 58(4), pages 544-557, November.
    2. Zhang, Yihan & Xu, Jinwen & Yang, Wancheng, 2024. "Analysis of the evolution characteristics of international ICT services trade based on complex network," Telecommunications Policy, Elsevier, vol. 48(3).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Goldrosen, Nicholas, 2024. "Is corrections officers' use of illegal force networked? Network structure, brokerage, and key players in the New York City Department of Correction," Journal of Criminal Justice, Elsevier, vol. 92(C).
    2. Mark J. O. Bagley, 2019. "Networks, geography and the survival of the firm," Journal of Evolutionary Economics, Springer, vol. 29(4), pages 1173-1209, September.
    3. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    4. Capponi, Agostino & Corell, Felix & Stiglitz, Joseph E., 2022. "Optimal bailouts and the doom loop with a financial network," Journal of Monetary Economics, Elsevier, vol. 128(C), pages 35-50.
    5. Zhao, Shuying & Sun, Shaowei, 2023. "Identification of node centrality based on Laplacian energy of networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 609(C).
    6. Raddant, Matthias & Takahashi, Hiroshi, 2019. "The Japanese corporate board network," Kiel Working Papers 2130, Kiel Institute for the World Economy (IfW Kiel).
    7. Liberati, Caterina & Marzo, Massimiliano & Zagaglia, Paolo & Zappa, Paola, 2012. "Structural distortions in the Euro interbank market: the role of 'key players' during the recent market turmoil," MPRA Paper 40223, University Library of Munich, Germany.
    8. Michel Grabisch & Agnieszka Rusinowska, 2015. "Lattices in Social Networks with Influence," International Game Theory Review (IGTR), World Scientific Publishing Co. Pte. Ltd., vol. 17(01), pages 1-18.
    9. Andrea Galeotti & Benjamin Golub & Sanjeev Goyal, 2020. "Targeting Interventions in Networks," Econometrica, Econometric Society, vol. 88(6), pages 2445-2471, November.
    10. Marco Di Summa & Syed Md Omar Faruk, 2023. "Critical node/edge detection problems on trees," 4OR, Springer, vol. 21(3), pages 439-455, September.
    11. Venel, Xavier, 2021. "Regularity of dynamic opinion games," Games and Economic Behavior, Elsevier, vol. 126(C), pages 305-334.
    12. Gallo, Julie Le & Plunket, Anne, 2020. "Regional gatekeepers, inventor networks and inventive performance: Spatial and organizational channels," Research Policy, Elsevier, vol. 49(5).
    13. Yadira Méndez-Lemus & Antonio Vieyra & Lorena Poncela, 2017. "Peri-urban local governance? Intra-government relationships and social capital in a peripheral municipality of Michoacán, Mexico," Progress in Development Studies, , vol. 17(1), pages 1-23, January.
    14. Yuming Guo, 2023. "Towards the efficient generation of variant design in product development networks: network nodes importance based product configuration evaluation approach," Journal of Intelligent Manufacturing, Springer, vol. 34(2), pages 615-631, February.
    15. Vincent Leon & S. Rasoul Etesami & Rakesh Nagi, 2022. "Limited-Trust in Diffusion of Competing Alternatives over Social Networks," Papers 2206.06318, arXiv.org, revised Oct 2023.
    16. Mahyar, Hamidreza & Hasheminezhad, Rouzbeh & Ghalebi K., Elahe & Nazemian, Ali & Grosu, Radu & Movaghar, Ali & Rabiee, Hamid R., 2018. "Compressive sensing of high betweenness centrality nodes in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 497(C), pages 166-184.
    17. Heetae Kim & Petter Holme, 2015. "Network Theory Integrated Life Cycle Assessment for an Electric Power System," Sustainability, MDPI, vol. 7(8), pages 1-15, August.
    18. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    19. Lindquist, Matthew J. & Zenou, Yves, 2019. "Crime and Networks: 10 Policy Lessons," IZA Discussion Papers 12534, Institute of Labor Economics (IZA).
    20. Caterina Liberati & Massimiliano Marzo & Paolo Zagaglia & Paola Zappa, 2015. "Drivers of demand and supply in the Euro interbank market: the role of “Key Players” during the recent turmoil," Financial Markets and Portfolio Management, Springer;Swiss Society for Financial Market Research, vol. 29(3), pages 207-250, August.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:8:y:2020:i:10:p:1810-:d:429165. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.