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. 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. 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.
    7. 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.
    8. 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.
    9. 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.
    10. 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.
    11. 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.
    12. 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.
    13. 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. 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).
    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. 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.
    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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. Zhai, Li & Yan, Xiangbin, 2022. "A directed collaboration network for exploring the order of scientific collaboration," Journal of Informetrics, Elsevier, vol. 16(4).
    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. 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.
    9. 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.
    10. 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).
    11. 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.
    12. Aurora González-Teruel & Gregorio González-Alcaide & Maite Barrios & María-Francisca Abad-García, 2015. "Mapping recent information behavior research: an analysis of co-authorship and co-citation networks," Scientometrics, Springer;Akadémiai Kiadó, vol. 103(2), pages 687-705, May.
    13. 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.
    14. 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.
    15. Yun Liu & Mengya Zhang & Gupeng Zhang & Xiongxiong You, 2022. "Scientific elites versus other scientists: who are better at taking advantage of the research collaboration network?," Scientometrics, Springer;Akadémiai Kiadó, vol. 127(6), pages 3145-3166, June.
    16. 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.
    17. 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.
    18. 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).
    19. 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.
    20. 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).

    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.