IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v271y2018i1p155-164.html
   My bibliography  Save this article

Finding clique clusters with the highest betweenness centrality

Author

Listed:
  • Rysz, Maciej
  • Mahdavi Pajouh, Foad
  • Pasiliao, Eduardo L.

Abstract

This article introduces and studies the most betweenness-central clique problem, which involves finding a clique cluster of maximum betweenness centrality in a connected network. This problem allows one to extend the traditional notion of finding a single most influential (or central) member, to one of identifying central groups whose members collectively satisfy a structural property that is meaningful relative to the underlying system. Among others, betweenness-central cliques find application in corporate, social, communication, power grid, and biological network analysis. In this study, the betweenness centrality measure adopted to define our problem is based on the summation of the percentages representing the ratio of the shortest paths between every pair of vertices in a network that intersect a given clique. The decision version of this problem is proven to be NP-complete, and it is shown that an optimal solution to this problem is either a maximal clique, or contained in a maximal clique with the same objective value. We also propose an analytical upper bound for the betweenness centrality of any maximal clique containing a given clique, and employ it to develop a combinatorial branch-and-bound algorithm for solving this problem. Computational performance of the proposed algorithm is then compared with that of a mixed integer programming technique on a test-bed of randomly generated graphs and real-life power-law networks.

Suggested Citation

  • Rysz, Maciej & Mahdavi Pajouh, Foad & Pasiliao, Eduardo L., 2018. "Finding clique clusters with the highest betweenness centrality," European Journal of Operational Research, Elsevier, vol. 271(1), pages 155-164.
    • Handle: RePEc:eee:ejores:v:271:y:2018:i:1:p:155-164
    DOI: 10.1016/j.ejor.2018.05.006
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221718303849
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2018.05.006?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. repec:cup:cbooks:9780511771576 is not listed on IDEAS
    2. Hellmann, Tim & Staudigl, Mathias, 2014. "Evolution of social networks," European Journal of Operational Research, Elsevier, vol. 234(3), pages 583-596.
    3. Dimitrios Tsiotas & Serafeim Polyzos, 2015. "Introducing a new centrality measure from the transportation network analysis in Greece," Annals of Operations Research, Springer, vol. 227(1), pages 93-117, April.
    4. Foad Mahdavi Pajouh & Zhuqi Miao & Balabhaskar Balasundaram, 2014. "A branch-and-bound approach for maximum quasi-cliques," Annals of Operations Research, Springer, vol. 216(1), pages 145-161, May.
    5. Gilsing, Victor & Nooteboom, Bart & Vanhaverbeke, Wim & Duysters, Geert & van den Oord, Ad, 2008. "Network embeddedness and the exploration of novel technologies: Technological distance, betweenness centrality and density," Research Policy, Elsevier, vol. 37(10), pages 1717-1731, December.
    6. Easley,David & Kleinberg,Jon, 2010. "Networks, Crowds, and Markets," Cambridge Books, Cambridge University Press, number 9780521195331, January.
    7. 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.
    8. Dyer, M. E. & Foulds, L. R. & Frieze, A. M., 1985. "Analysis of heuristics for finding a maximum weight planar subgraph," European Journal of Operational Research, Elsevier, vol. 20(1), pages 102-114, April.
    9. Paschos, Vangelis Th. & Demange, Marc, 1997. "A generalization of Konig-Egervary graphs and heuristics for the maximum independent set problem with improved approximation ratios," European Journal of Operational Research, Elsevier, vol. 97(3), pages 580-592, March.
    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. Mustafa C. Camur & Thomas Sharkey & Chrysafis Vogiatzis, 2022. "The Star Degree Centrality Problem: A Decomposition Approach," INFORMS Journal on Computing, INFORMS, vol. 34(1), pages 93-112, January.
    2. Camur, Mustafa C. & Sharkey, Thomas C. & Vogiatzis, Chrysafis, 2023. "The stochastic pseudo-star degree centrality problem," European Journal of Operational Research, Elsevier, vol. 308(2), pages 525-539.
    3. Furini, Fabio & Ljubić, Ivana & Martin, Sébastien & San Segundo, Pablo, 2019. "The maximum clique interdiction problem," European Journal of Operational Research, Elsevier, vol. 277(1), pages 112-127.
    4. Matsypura, Dmytro & Veremyev, Alexander & Pasiliao, Eduardo L. & Prokopyev, Oleg A., 2023. "Finding the most degree-central walks and paths in a graph: Exact and heuristic approaches," European Journal of Operational Research, Elsevier, vol. 308(3), pages 1021-1036.
    5. Zhong, Haonan & Mahdavi Pajouh, Foad & Prokopyev, Oleg A., 2021. "Finding influential groups in networked systems: The most degree-central clique problem," Omega, Elsevier, vol. 101(C).
    6. San Segundo, Pablo & Coniglio, Stefano & Furini, Fabio & Ljubić, Ivana, 2019. "A new branch-and-bound algorithm for the maximum edge-weighted clique problem," European Journal of Operational Research, Elsevier, vol. 278(1), pages 76-90.
    7. Nasirian, Farzaneh & Mahdavi Pajouh, Foad & Balasundaram, Balabhaskar, 2020. "Detecting a most closeness-central clique in complex networks," European Journal of Operational Research, Elsevier, vol. 283(2), pages 461-475.
    8. Ali Tosyali & Jeongsub Choi & Byunghoon Kim & Hoshin Lee & Myong K. Jeong, 2021. "A dynamic graph-based approach to ranking firms for identifying key players using inter-firm transactions," Annals of Operations Research, Springer, vol. 303(1), pages 5-27, August.
    9. Melda Kevser Akgün & Mustafa Kemal Tural, 2020. "k-step betweenness centrality," Computational and Mathematical Organization Theory, Springer, vol. 26(1), pages 55-87, March.

    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. Arcagni, Alberto & Grassi, Rosanna & Stefani, Silvana & Torriero, Anna, 2017. "Higher order assortativity in complex networks," European Journal of Operational Research, Elsevier, vol. 262(2), pages 708-719.
    2. Hellmann, Tim & Landwehr, Jakob, 2014. "Stable Networks in Homogeneous Societies," Center for Mathematical Economics Working Papers 517, Center for Mathematical Economics, Bielefeld University.
    3. Ghaderi, Mohammad, 2022. "Public health interventions in the face of pandemics: Network structure, social distancing, and heterogeneity," European Journal of Operational Research, Elsevier, vol. 298(3), pages 1016-1031.
    4. Guan, Jiancheng & Zhang, Jingjing & Yan, Yan, 2015. "The impact of multilevel networks on innovation," Research Policy, Elsevier, vol. 44(3), pages 545-559.
    5. Ballings, Michel & Van den Poel, Dirk, 2015. "CRM in social media: Predicting increases in Facebook usage frequency," European Journal of Operational Research, Elsevier, vol. 244(1), pages 248-260.
    6. Li, Libo, 2018. "Predicting online invitation responses with a competing risk model using privacy-friendly social event data," European Journal of Operational Research, Elsevier, vol. 270(2), pages 698-708.
    7. Molinero, Xavier & Riquelme, Fabián & Serna, Maria, 2015. "Cooperation through social influence," European Journal of Operational Research, Elsevier, vol. 242(3), pages 960-974.
    8. Blazquez-Soriano, Amparo & Ramos-Sandoval, Rosmery, 2022. "Information transfer as a tool to improve the resilience of farmers against the effects of climate change: The case of the Peruvian National Agrarian Innovation System," Agricultural Systems, Elsevier, vol. 200(C).
    9. Martin L. Weitzman, 2015. "A Voting Architecture for the Governance of Free-Driver Externalities, with Application to Geoengineering," Scandinavian Journal of Economics, Wiley Blackwell, vol. 117(4), pages 1049-1068, October.
    10. Wei Zhong, 2017. "Simulating influenza pandemic dynamics with public risk communication and individual responsive behavior," Computational and Mathematical Organization Theory, Springer, vol. 23(4), pages 475-495, December.
    11. Markus Kinateder & Luca Paolo Merlino, 2021. "The Evolution of Networks and Local Public Good Provision: A Potential Approach," Games, MDPI, vol. 12(3), pages 1-12, July.
    12. Guo Weilong & Minca Andreea & Wang Li, 2016. "The topology of overlapping portfolio networks," Statistics & Risk Modeling, De Gruyter, vol. 33(3-4), pages 139-155, December.
    13. de Jong, Jeroen P.J. & Freel, Mark, 2010. "Absorptive capacity and the reach of collaboration in high technology small firms," Research Policy, Elsevier, vol. 39(1), pages 47-54, February.
    14. Guiyang Zhang, 2021. "Employee co-invention network dynamics and firm exploratory innovation: the moderation of employee co-invention network centralization and knowledge-employee network equilibrium," Scientometrics, Springer;Akadémiai Kiadó, vol. 126(9), pages 7811-7836, September.
    15. 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.
    16. Thomas J. Sargent & John Stachurski, 2022. "Economic Networks: Theory and Computation," Papers 2203.11972, arXiv.org, revised Jul 2022.
    17. Lorenzo Cassi & Anne Plunket, 2014. "Proximity, network formation and inventive performance: in search of the proximity paradox," The Annals of Regional Science, Springer;Western Regional Science Association, vol. 53(2), pages 395-422, September.
    18. Battke, Benedikt & Schmidt, Tobias S. & Stollenwerk, Stephan & Hoffmann, Volker H., 2016. "Internal or external spillovers—Which kind of knowledge is more likely to flow within or across technologies," Research Policy, Elsevier, vol. 45(1), pages 27-41.
    19. Bernd (B.) Heidergott & Jia-Ping Huang & Ines (I.) Lindner, 2018. "Naive Learning in Social Networks with Random Communication," Tinbergen Institute Discussion Papers 18-018/II, Tinbergen Institute.
    20. Johannes M. Bauer & Michael Latzer, 2016. "The economics of the Internet: an overview," Chapters, in: Johannes M. Bauer & Michael Latzer (ed.), Handbook on the Economics of the Internet, chapter 1, pages 3-20, Edward Elgar Publishing.

    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:eee:ejores:v:271:y:2018:i:1:p:155-164. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    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.