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
    File URL: https://libkey.io/10.1016/j.ejor.2019.11.035?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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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.
    10. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2019. "Finding Critical Links for Closeness Centrality," INFORMS Journal on Computing, INFORMS, vol. 31(2), pages 367-389, April.
    11. Steffen Rebennack & Marcus Oswald & Dirk Oliver Theis & Hanna Seitz & Gerhard Reinelt & Panos M. Pardalos, 2011. "A Branch and Cut solver for the maximum stable set problem," Journal of Combinatorial Optimization, Springer, vol. 21(4), pages 434-457, May.
    12. 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.
    13. 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.
    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. 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.
    2. 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.
    3. Alboqami, Hassan, 2023. "Trust me, I'm an influencer! - Causal recipes for customer trust in artificial intelligence influencers in the retail industry," Journal of Retailing and Consumer Services, Elsevier, vol. 72(C).
    4. 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. 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.
    3. Stefano Coniglio & Stefano Gualandi, 2022. "Optimizing over the Closure of Rank Inequalities with a Small Right-Hand Side for the Maximum Stable Set Problem via Bilevel Programming," INFORMS Journal on Computing, INFORMS, vol. 34(2), pages 1006-1023, March.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. Zhai, Li & Yan, Xiangbin, 2022. "A directed collaboration network for exploring the order of scientific collaboration," Journal of Informetrics, Elsevier, vol. 16(4).
    9. Lee, O-Joun & Jeon, Hyeon-Ju & Jung, Jason J., 2021. "Learning multi-resolution representations of research patterns in bibliographic networks," Journal of Informetrics, Elsevier, vol. 15(1).
    10. 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.
    11. 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).
    12. 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.
    13. 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.
    14. Guijie Zhang & Luning Liu & Yuqiang Feng & Zhen Shao & Yongli Li, 2014. "Cext-N index: a network node centrality measure for collaborative relationship distribution," Scientometrics, Springer;Akadémiai Kiadó, vol. 101(1), pages 291-307, October.
    15. Enrico di Bella & Luca Gandullia & Sara Preti, 2021. "Analysis of scientific collaboration network of Italian Institute of Technology," Scientometrics, Springer;Akadémiai Kiadó, vol. 126(10), pages 8517-8539, October.
    16. 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.
    17. Ferrarini, Luca & Gualandi, Stefano, 2022. "Total Coloring and Total Matching: Polyhedra and Facets," European Journal of Operational Research, Elsevier, vol. 303(1), pages 129-142.
    18. Liu, Qiuling & Guo, Lei & Sun, Yiping & Ren, Linlin & Wang, Xinhua & Han, Xiaohui, 2024. "Do scholars' collaborative tendencies impact the quality of their publications? A generalized propensity score matching analysis," Journal of Informetrics, Elsevier, vol. 18(1).
    19. 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.
    20. Coniglio, Stefano & Furini, Fabio & San Segundo, Pablo, 2021. "A new combinatorial branch-and-bound algorithm for the Knapsack Problem with Conflicts," European Journal of Operational Research, Elsevier, vol. 289(2), pages 435-455.

    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.

    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.