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. 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).
    2. 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.

    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. 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.
    2. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    3. Raddant, Matthias & Takahashi, Hiroshi, 2019. "The Japanese corporate board network," Kiel Working Papers 2130, Kiel Institute for the World Economy (IfW Kiel).
    4. Marco Di Summa & Syed Md Omar Faruk, 2023. "Critical node/edge detection problems on trees," 4OR, Springer, vol. 21(3), pages 439-455, September.
    5. 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.
    6. 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.
    7. Lindquist, Matthew J. & Zenou, Yves, 2019. "Crime and Networks: 10 Policy Lessons," IZA Discussion Papers 12534, Institute of Labor Economics (IZA).
    8. 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.
    9. Mishael Milaković & Simone Alfarano & Thomas Lux, 2010. "The small core of the German corporate board network," Computational and Mathematical Organization Theory, Springer, vol. 16(2), pages 201-215, June.
    10. Deb Verhoeven & Katarzyna Musial & Stuart Palmer & Sarah Taylor & Shaukat Abidi & Vejune Zemaityte & Lachlan Simpson, 2020. "Controlling for openness in the male-dominated collaborative networks of the global film industry," PLOS ONE, Public Library of Science, vol. 15(6), pages 1-23, June.
    11. César Yajure & Darihelen Montilla & Jose Emmanuel Ramirez-Marquez & Claudio M Rocco S, 2013. "Network vulnerability assessment via bi-objective optimization with a fragmentation approach as proxy," Journal of Risk and Reliability, , vol. 227(6), pages 576-585, December.
    12. repec:hal:pseose:halshs-00977005 is not listed on IDEAS
    13. Caterina Liberati & Massimiliano Marzo & Paolo Zagaglia & Paola Zappa, 2012. "Structural Distortions in the Euro Interbank Market: The Role of 'Key Players' during the Recent Market Turmoil," Working Paper series 57_12, Rimini Centre for Economic Analysis.
    14. Shu-Hao Chang, 2017. "The evolutionary growth estimation model of international cooperative patent networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 112(2), pages 711-729, August.
    15. Reini Schrama & Dorte Sindbjerg Martinsen & Ellen Mastenbroek, 2020. "Going Nordic in European Administrative Networks?," Politics and Governance, Cogitatio Press, vol. 8(4), pages 65-77.
    16. Adam R. Cocco & Matthew Katz & Marion E. Hambrick, 2021. "Co-Attendance Communities: A Multilevel Egocentric Network Analysis of American Soccer Supporters’ Groups," IJERPH, MDPI, vol. 18(14), pages 1-18, July.
    17. Zacharie Ales & Céline Engelbeen & Rosa Figueiredo, 2024. "Correlation Clustering Problem Under Mediation," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 672-689, March.
    18. Stefano Breschi & Camilla Lenzi, 2015. "The Role of External Linkages and Gatekeepers for the Renewal and Expansion of US Cities' Knowledge Base, 1990-2004," Regional Studies, Taylor & Francis Journals, vol. 49(5), pages 782-797, May.
    19. Dufhues, Thomas & Buchenrieder, Gertrud & Fischer, Isabel, 2006. "Social capital and rural development: literature review and current state of the art [Sozialkapital und ländliche Entwicklung: Literaturüberblick und gegenwärtiger Stand der Forschung]," IAMO Discussion Papers 96, Leibniz Institute of Agricultural Development in Transition Economies (IAMO).
    20. Dell’Apa, Andrea & Fullerton, Adam & Schwing, Franklin & Brady, Margaret M., 2015. "The status of marine and coastal ecosystem-based management among the network of U.S. federal programs," Marine Policy, Elsevier, vol. 60(C), pages 249-258.
    21. Jordán, Ferenc, 2022. "The network perspective: Vertical connections linking organizational levels," Ecological Modelling, Elsevier, vol. 473(C).

    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.