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

Detecting a most closeness-central clique in complex networks

Author

Listed:
  • Nasirian, Farzaneh
  • Mahdavi Pajouh, Foad
  • Balasundaram, Balabhaskar

Abstract

Centrality is a powerful concept for detecting influential components of a network applicable to various areas such as analysis of social, collaboration, and biological networks. In this study, we employ one of the well-known centrality measures, closeness centrality, to detect a group of pairwise connected members (a highly connected community known as a clique) with the highest accessibility to the entire network. To measure the accessibility of a clique, we use two metrics, the maximum distance and the total distance to the clique from other members of the network. Hence, we are dealing with two variants of the most central clique problem referred to as maximum-distance-closeness-central clique and total-distance-closeness-central clique problems. We study the computational complexity of these two problems and prove that their decision versions are NP-complete. We also propose new mixed 0–1 integer programming formulations and the first combinatorial branch-and-bound algorithms to solve these problems exactly. We show that our algorithmic approaches offer at least 83-fold speed-up on over 96% of benchmark instances in comparison to existing approaches.

Suggested Citation

  • 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.
  • Handle: RePEc:eee:ejores:v:283:y:2020:i:2:p:461-475
    DOI: 10.1016/j.ejor.2019.11.035
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221719309464
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. 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.
    2. Cho, Youngsang & Hwang, Junseok & Lee, Daeho, 2012. "Identification of effective opinion leaders in the diffusion of technological innovation: A social network approach," Technological Forecasting and Social Change, Elsevier, vol. 79(1), pages 97-106.
    3. Bordons, María & Aparicio, Javier & González-Albo, Borja & Díaz-Faes, Adrián A., 2015. "The relationship between the research performance of scientists and their position in co-authorship networks in three fields," Journal of Informetrics, Elsevier, vol. 9(1), pages 135-144.
    4. Mahendra Piraveenan & Mikhail Prokopenko & Liaquat Hossain, 2013. "Percolation Centrality: Quantifying Graph-Theoretic Impact of Nodes during Percolation in Networks," PLOS ONE, Public Library of Science, vol. 8(1), pages 1-14, January.
    5. Yan, Xiangbin & Zhai, Li & Fan, Weiguo, 2013. "C-index: A weighted network node centrality measure for collaboration competence," Journal of Informetrics, Elsevier, vol. 7(1), pages 223-239.
    6. Kuzubaş, Tolga Umut & Ömercikoğlu, Inci & Saltoğlu, Burak, 2014. "Network centrality measures and systemic risk: An application to the Turkish financial crisis," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 405(C), pages 203-215.
    7. Butenko, S. & Wilhelm, W.E., 2006. "Clique-detection models in computational biochemistry and genomics," European Journal of Operational Research, Elsevier, vol. 173(1), pages 1-17, August.
    8. Kamal Badar & Julie M. Hite & Yuosre F. Badir, 2013. "Examining the relationship of co-authorship network centrality and gender on academic research performance: the case of chemistry researchers in Pakistan," Scientometrics, Springer;Akadémiai Kiadó, vol. 94(2), pages 755-775, February.
    9. 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.
    10. R. Luce & Albert Perry, 1949. "A method of matrix analysis of group structure," Psychometrika, Springer;The Psychometric Society, vol. 14(2), pages 95-116, June.
    11. Erjia Yan & Ying Ding, 2009. "Applying centrality measures to impact analysis: A coauthorship network analysis," Journal of the American Society for Information Science and Technology, Association for Information Science & Technology, vol. 60(10), pages 2107-2118, 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. Tavasoli, Ali & Shakeri, Heman & Ardjmand, Ehsan & Young, William A., 2021. "Incentive rate determination in viral marketing," European Journal of Operational Research, Elsevier, vol. 289(3), pages 1169-1187.

    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. Gregorio González-Alcaide & Héctor Pinargote & José M. Ramos, 2020. "From cut-points to key players in co-authorship networks: a case study in ventilator-associated pneumonia research," Scientometrics, Springer;Akadémiai Kiadó, vol. 123(2), pages 707-733, May.
    2. Marian-Gabriel Hâncean & Matjaž Perc & Jürgen Lerner, 2021. "The coauthorship networks of the most productive European researchers," Scientometrics, Springer;Akadémiai Kiadó, vol. 126(1), pages 201-224, January.
    3. Zhuqi Miao & Balabhaskar Balasundaram & Eduardo L. Pasiliao, 2014. "An exact algorithm for the maximum probabilistic clique problem," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 105-120, July.
    4. Oleksandra Yezerska & Sergiy Butenko & Vladimir L. Boginski, 2018. "Detecting robust cliques in graphs subject to uncertain edge failures," Annals of Operations Research, Springer, vol. 262(1), pages 109-132, March.
    5. 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.
    6. Qin Zhang & Juneman Abraham & Hui-Zhen Fu, 2020. "Collaboration and its influence on retraction based on retracted publications during 1978–2017," Scientometrics, Springer;Akadémiai Kiadó, vol. 125(1), pages 213-232, October.
    7. Way-Ren Huang & Chia-Jen Hsieh & Ke-Chiun Chang & Yen-Jo Kiang & Chien-Chung Yuan & Woei-Chyn Chu, 2017. "Network characteristics and patent value—Evidence from the Light-Emitting Diode industry," PLOS ONE, Public Library of Science, vol. 12(8), pages 1-14, August.
    8. Zhuqi Miao & Balabhaskar Balasundaram, 2020. "An Ellipsoidal Bounding Scheme for the Quasi-Clique Number of a Graph," INFORMS Journal on Computing, INFORMS, vol. 32(3), pages 763-778, July.
    9. Pattillo, Jeffrey & Youssef, Nataly & Butenko, Sergiy, 2013. "On clique relaxation models in network analysis," European Journal of Operational Research, Elsevier, vol. 226(1), pages 9-18.
    10. Kamal Badar & Julie M. Hite & Naeem Ashraf, 2015. "Knowledge network centrality, formal rank and research performance: evidence for curvilinear and interaction effects," Scientometrics, Springer;Akadémiai Kiadó, vol. 105(3), pages 1553-1576, December.
    11. Veremyev, Alexander & Prokopyev, Oleg A. & Boginski, Vladimir & Pasiliao, Eduardo L., 2014. "Finding maximum subgraphs with relatively large vertex connectivity," European Journal of Operational Research, Elsevier, vol. 239(2), pages 349-362.
    12. Elsa Alvaro & Angel Yanguas-Gil, 2018. "Characterizing the field of Atomic Layer Deposition: Authors, topics, and collaborations," PLOS ONE, Public Library of Science, vol. 13(1), pages 1-19, January.
    13. Kuzubaş, Tolga Umut & Saltoğlu, Burak & Sever, Can, 2016. "Systemic risk and heterogeneous leverage in banking networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 462(C), pages 358-375.
    14. Simone Celant, 2013. "Two-mode networks: the measurement of efficiency in the profiles of actors’ participation in the occasions," Quality & Quantity: International Journal of Methodology, Springer, vol. 47(6), pages 3289-3302, October.
    15. Le Breton, Michel & Weber, Shlomo, 2009. "Existence of Pure Strategies Nash Equilibria in Social Interaction Games with Dyadic Externalities," CEPR Discussion Papers 7279, C.E.P.R. Discussion Papers.
    16. Foad Mahdavi Pajouh, 2020. "Minimum cost edge blocker clique problem," Annals of Operations Research, Springer, vol. 294(1), pages 345-376, November.
    17. Zhu, Yongjun & Yan, Erjia, 2017. "Examining academic ranking and inequality in library and information science through faculty hiring networks," Journal of Informetrics, Elsevier, vol. 11(2), pages 641-654.
    18. Svyatoslav Trukhanov & Chitra Balasubramaniam & Balabhaskar Balasundaram & Sergiy Butenko, 2013. "Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations," Computational Optimization and Applications, Springer, vol. 56(1), pages 113-130, September.
    19. Giulia Masi & Giorgio Ricchiuti, 2020. "From FDI network topology to macroeconomic instability," Journal of Economic Interaction and Coordination, Springer;Society for Economic Science with Heterogeneous Interacting Agents, vol. 15(1), pages 133-158, January.
    20. Carvalho, Filipa D. & Almeida, M. Teresa, 2011. "Upper bounds and heuristics for the 2-club problem," European Journal of Operational Research, Elsevier, vol. 210(3), pages 489-494, May.

    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:283:y:2020:i:2:p:461-475. See general information about how to correct material in RePEc.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Nithya Sathishkumar). General contact details of provider: http://www.elsevier.com/locate/eor .

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

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

    IDEAS is a RePEc service hosted by the Research Division of the Federal Reserve Bank of St. Louis . RePEc uses bibliographic data supplied by the respective publishers.