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. Rusinowska, Agnieszka & Taalaibekova, Akylai, 2019. "Opinion formation and targeting when persuaders have extreme and centrist opinions," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 9-27.
    5. Albizuri, M.J., 2008. "Axiomatizations of the Owen value without efficiency," Mathematical Social Sciences, Elsevier, vol. 55(1), pages 78-89, January.
    6. Giulia Cesari & Roberto Lucchetti & Stefano Moretti, 2017. "Generalized additive games," International Journal of Game Theory, Springer;Game Theory Society, vol. 46(4), pages 919-939, November.
    7. Yao Hongxing & Lu Yunxia, 2017. "Analyzing the Potential Influence of Shanghai Stock Market Based on Link Prediction Method," Journal of Systems Science and Information, De Gruyter, vol. 5(5), pages 446-461, October.
    8. 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.
    9. 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.
    10. Manuel, Paul & Brešar, Boštjan & Klavžar, Sandi, 2022. "The geodesic-transversal problem," Applied Mathematics and Computation, Elsevier, vol. 413(C).
    11. Gergely Tibély & David Sousa-Rodrigues & Péter Pollner & Gergely Palla, 2016. "Comparing the Hierarchy of Keywords in On-Line News Portals," PLOS ONE, Public Library of Science, vol. 11(11), pages 1-15, November.
    12. Ding, Ying, 2011. "Community detection: Topological vs. topical," Journal of Informetrics, Elsevier, vol. 5(4), pages 498-514.
    13. Fujimoto, Katsushige & Kojadinovic, Ivan & Marichal, Jean-Luc, 2006. "Axiomatic characterizations of probabilistic and cardinal-probabilistic interaction indices," Games and Economic Behavior, Elsevier, vol. 55(1), pages 72-99, April.
    14. Lange, Fabien & Grabisch, Michel, 2009. "Values on regular games under Kirchhoff's laws," Mathematical Social Sciences, Elsevier, vol. 58(3), pages 322-340, November.
    15. González–Arangüena, E. & Manuel, C. & Owen, G. & del Pozo, M., 2017. "The within groups and the between groups Myerson values," European Journal of Operational Research, Elsevier, vol. 257(2), pages 586-600.
    16. 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.
    17. Liu, Chuang & Zhou, Wei-Xing, 2012. "Heterogeneity in initial resource configurations improves a network-based hybrid recommendation algorithm," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 391(22), pages 5704-5711.
    18. Albizuri, M. Josune, 2009. "Generalized coalitional semivalues," European Journal of Operational Research, Elsevier, vol. 196(2), pages 578-584, July.
    19. 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.
    20. Francesc Carreras & María Albina Puente, 2015. "Multinomial Probabilistic Values," Group Decision and Negotiation, Springer, vol. 24(6), pages 981-991, November.

    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.