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

A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection

Author

Listed:
  • Daniel Gómez

    (Faculty of Statistics, Complutense University Puerta de Hierro, 28040 Madrid, Spain
    Instituto de Evaluación Sanitaria, Complutense University, 28040 Madrid, Spain)

  • Javier Castro

    (Faculty of Statistics, Complutense University Puerta de Hierro, 28040 Madrid, Spain
    Instituto de Evaluación Sanitaria, Complutense University, 28040 Madrid, Spain)

  • Inmaculada Gutiérrez

    (Faculty of Statistics, Complutense University Puerta de Hierro, 28040 Madrid, Spain)

  • Rosa Espínola

    (Faculty of Statistics, Complutense University Puerta de Hierro, 28040 Madrid, Spain
    Instituto de Evaluación Sanitaria, Complutense University, 28040 Madrid, Spain)

Abstract

In this paper we formally define the hierarchical clustering network problem (HCNP) as the problem to find a good hierarchical partition of a network. This new problem focuses on the dynamic process of the clustering rather than on the final picture of the clustering process. To address it, we introduce a new hierarchical clustering algorithm in networks, based on a new shortest path betweenness measure. To calculate it, the communication between each pair of nodes is weighed by the importance of the nodes that establish this communication. The weights or importance associated to each pair of nodes are calculated as the Shapley value of a game, named as the linear modularity game. This new measure, ( the node-game shortest path betweenness measure ), is used to obtain a hierarchical partition of the network by eliminating the link with the highest value. To evaluate the performance of our algorithm, we introduce several criteria that allow us to compare different dendrograms of a network from two point of view: modularity and homogeneity. Finally, we propose a faster algorithm based on a simplification of the node-game shortest path betweenness measure , whose order is quadratic on sparse networks. This fast version is competitive from a computational point of view with other hierarchical fast algorithms, and, in general, it provides better results.

Suggested Citation

  • Daniel Gómez & Javier Castro & Inmaculada Gutiérrez & Rosa Espínola, 2021. "A New Edge Betweenness Measure Using a Game Theoretical Approach: An Application to Hierarchical Community Detection," Mathematics, MDPI, vol. 9(21), pages 1-29, October.
  • Handle: RePEc:gam:jmathe:v:9:y:2021:i:21:p:2666-:d:661694
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/21/2666/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/9/21/2666/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Gomez, Daniel & Gonzalez-Aranguena, Enrique & Manuel, Conrado & Owen, Guillermo & del Pozo, Monica & Tejada, Juan, 2003. "Centrality and power in social networks: a game theoretic approach," Mathematical Social Sciences, Elsevier, vol. 46(1), pages 27-54, August.
    2. Pradeep Dubey & Abraham Neyman & Robert James Weber, 1981. "Value Theory Without Efficiency," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 122-128, February.
    3. Mahendra Piraveenan, 2019. "Applications of Game Theory in Project Management: A Structured Review and Analysis," Mathematics, MDPI, vol. 7(9), pages 1-31, September.
    4. Gómez, Daniel & Figueira, José Rui & Eusébio, Augusto, 2013. "Modeling centrality measures in social network analysis using bi-criteria network flow optimization problems," European Journal of Operational Research, Elsevier, vol. 226(2), pages 354-365.
    5. Daniel Gómez & Enrique González–Arangüena & Conrado Manuel & Guillermo Owen & Mónica Pozo & Martha Saboyá, 2008. "The cohesiveness of subgroups in social networks: A view from game theory," Annals of Operations Research, Springer, vol. 158(1), pages 33-46, February.
    6. Aaron Clauset & Cristopher Moore & M. E. J. Newman, 2008. "Hierarchical structure and the prediction of missing links in networks," Nature, Nature, vol. 453(7191), pages 98-101, May.
    7. Artem Sedakov, 2020. "Characteristic Function and Time Consistency for Two-Stage Games with Network Externalities," Mathematics, MDPI, vol. 8(1), pages 1-9, January.
    8. Shi Chen & Zhi-Zhong Wang & Liang Tang & Yan-Ni Tang & Yuan-Yuan Gao & Hui-Jia Li & Ju Xiang & Yan Zhang, 2018. "Global vs local modularity for network community detection," PLOS ONE, Public Library of Science, vol. 13(10), pages 1-21, October.
    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. Yelai Feng & Huaixi Wang & Chao Chang & Hongyi Lu, 2022. "Intrinsic Correlation with Betweenness Centrality and Distribution of Shortest Paths," Mathematics, MDPI, vol. 10(14), pages 1-18, July.
    2. Inmaculada Gutiérrez & Daniel Gómez & Javier Castro & Rosa Espínola, 2022. "From Fuzzy Information to Community Detection: An Approach to Social Networks Analysis with Soft Information," Mathematics, MDPI, vol. 10(22), pages 1-22, 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. Inmaculada Gutiérrez & Juan Antonio Guevara & Daniel Gómez & Javier Castro & Rosa Espínola, 2021. "Community Detection Problem Based on Polarization Measures: An Application to Twitter: The COVID-19 Case in Spain," Mathematics, MDPI, vol. 9(4), pages 1-27, February.
    2. Laruelle, Annick & Valenciano, Federico, 2008. "Noncooperative foundations of bargaining power in committees and the Shapley-Shubik index," Games and Economic Behavior, Elsevier, vol. 63(1), pages 341-353, May.
    3. Felix Fritz & Stefano Moretti & Jochen Staudacher, 2023. "Social Ranking Problems at the Interplay between Social Choice Theory and Coalitional Games," Mathematics, MDPI, vol. 11(24), pages 1-22, December.
    4. Albizuri, M.J., 2008. "Axiomatizations of the Owen value without efficiency," Mathematical Social Sciences, Elsevier, vol. 55(1), pages 78-89, January.
    5. Sridhar Mandyam & Usha Sridhar, 2017. "DON and Shapley Value for Allocation among Cooperating Agents in a Network: Conditions for Equivalence," Studies in Microeconomics, , vol. 5(2), pages 143-161, December.
    6. Saari, Donald G. & Sieberg, Katri K., 2001. "Some Surprising Properties of Power Indices," Games and Economic Behavior, Elsevier, vol. 36(2), pages 241-263, August.
    7. Ding, Ying, 2011. "Community detection: Topological vs. topical," Journal of Informetrics, Elsevier, vol. 5(4), pages 498-514.
    8. Lange, Fabien & Grabisch, Michel, 2009. "Values on regular games under Kirchhoff's laws," Mathematical Social Sciences, Elsevier, vol. 58(3), pages 322-340, November.
    9. Gräbner, Claudius, 2016. "From realism to instrumentalism - and back? Methodological implications of changes in the epistemology of economics," MPRA Paper 71933, University Library of Munich, Germany.
    10. Tamás Nepusz & Tamás Vicsek, 2013. "Hierarchical Self-Organization of Non-Cooperating Individuals," PLOS ONE, Public Library of Science, vol. 8(12), pages 1-9, December.
    11. C. Manuel & D. Martín, 2021. "A value for communication situations with players having different bargaining abilities," Annals of Operations Research, Springer, vol. 301(1), pages 161-182, June.
    12. Nora Connor & Albert Barberán & Aaron Clauset, 2017. "Using null models to infer microbial co-occurrence networks," PLOS ONE, Public Library of Science, vol. 12(5), pages 1-23, May.
    13. Gomez, Daniel & Gonzalez-Aranguena, Enrique & Manuel, Conrado & Owen, Guillermo & del Pozo, Monica & Tejada, Juan, 2003. "Centrality and power in social networks: a game theoretic approach," Mathematical Social Sciences, Elsevier, vol. 46(1), pages 27-54, August.
    14. Leto Peel & Tiago P. Peixoto & Manlio De Domenico, 2022. "Statistical inference links data and theory in network science," Nature Communications, Nature, vol. 13(1), pages 1-15, December.
    15. O'Neill, Barry & Peleg, Bezalel, 2008. "Lexicographic composition of simple games," Games and Economic Behavior, Elsevier, vol. 62(2), pages 628-642, March.
    16. Xinyi Liu & Bin Liu & Zhimin Huang & Ting Shi & Yingyi Chen & Jian Zhang, 2012. "SPPS: A Sequence-Based Method for Predicting Probability of Protein-Protein Interaction Partners," PLOS ONE, Public Library of Science, vol. 7(1), pages 1-6, January.
    17. Dubey, Pradeep & Einy, Ezra & Haimanko, Ori, 2005. "Compound voting and the Banzhaf index," Games and Economic Behavior, Elsevier, vol. 51(1), pages 20-30, April.
    18. Geoffroy de Clippel & Roberto Serrano, 2008. "Marginal Contributions and Externalities in the Value," Econometrica, Econometric Society, vol. 76(6), pages 1413-1436, November.
    19. Amulyashree Sridhar & Sharvani GS & AH Manjunatha Reddy & Biplab Bhattacharjee & Kalyan Nagaraj, 2019. "The Eminence of Co-Expressed Ties in Schizophrenia Network Communities," Data, MDPI, vol. 4(4), pages 1-23, November.
    20. Li, Qing & Zhang, Huaige & Hong, Xianpei, 2020. "Knowledge structure of technology licensing based on co-keywords network: A review and future directions," International Review of Economics & Finance, Elsevier, vol. 66(C), pages 154-165.

    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:9:y:2021:i:21:p:2666-:d:661694. 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.