IDEAS home Printed from https://ideas.repec.org/a/eee/phsmap/v534y2019ics0378437119313408.html

Detecting multiple key players under the positive effect by using a distance-based connectivity approach

Author

Listed:
  • Jiang, Cheng
  • Liu, Zhonghua

Abstract

Key players problems aim to detect multiple players that optimize certain metrics on the network structure and function from two aspects, i.e., the negative effect and positive effect. However, most existing researches focus on modeling for the former, and how to model for the latter needs further exploration. In this paper, we first propose an integer linear programming model with distance-based connectivity for the positive effect. Then, to solve the proposed model, we design a novel heuristic algorithm by combining with local search enforcement in a greedy framework. Finally, we conduct many synthetic and real-world networks to validate the effectiveness and efficiency of the proposed approach. The experimental results show that the proposed approach achieves superior performance on detecting multiple key players, compared with some traditional methods.

Suggested Citation

  • Jiang, Cheng & Liu, Zhonghua, 2019. "Detecting multiple key players under the positive effect by using a distance-based connectivity approach," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 534(C).
    • Handle: RePEc:eee:phsmap:v:534:y:2019:i:c:s0378437119313408
    DOI: 10.1016/j.physa.2019.122322
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0378437119313408
    Download Restriction: Full text for ScienceDirect subscribers only. Journal offers the option of making the article available online on Science direct for a fee of $3,000
    File URL: https://libkey.io/10.1016/j.physa.2019.122322?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

    for a different version of it.

    References listed on IDEAS

    as
    1. Jiang, Cheng & Liu, Zhonghua & Wang, Juyun & Yu, Hua & Guo, Xiaoling, 2017. "An optimal approach for the critical node problem using semidefinite programming," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 471(C), pages 315-324.
    2. Al-garadi, Mohammed Ali & Varathan, Kasturi Dewi & Ravana, Sri Devi, 2017. "Identification of influential spreaders in online social networks using interaction weighted K-core decomposition method," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 468(C), pages 278-288.
    3. Fei, Liguo & Zhang, Qi & Deng, Yong, 2018. "Identifying influential nodes in complex networks based on the inverse-square law," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 512(C), pages 1044-1059.
    4. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.
    5. Hu, Jiantao & Du, Yuxian & Mo, Hongming & Wei, Daijun & Deng, Yong, 2016. "A modified weighted TOPSIS to identify influential nodes in complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 444(C), pages 73-85.
    6. Bernardetta Addis & Roberto Aringhieri & Andrea Grosso & Pierre Hosteins, 2016. "Hybrid constructive heuristics for the critical node problem," Annals of Operations Research, Springer, vol. 238(1), pages 637-649, March.
    7. Faramondi, Luca & Setola, Roberto & Panzieri, Stefano & Pascucci, Federica & Oliva, Gabriele, 2018. "Finding critical nodes in infrastructure networks," International Journal of Critical Infrastructure Protection, Elsevier, vol. 20(C), pages 3-15.
    Full references (including those not matched with items on IDEAS)

    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. Chen, Wei & Jiang, Manrui & Jiang, Cheng & Zhang, Jun, 2020. "Critical node detection problem for complex network in undirected weighted networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 538(C).
    2. Sheng-Jie Chen & Liang Chen & Guang-Ming Li & Yu-Hong Dai, 2025. "Preprocessing and valid inequalities for exact detection of critical nodes via integer programming," Computational Optimization and Applications, Springer, vol. 92(1), pages 215-263, September.
    3. Hosseinali Salemi & Austin Buchanan, 2022. "Solving the Distance-Based Critical Node Problem," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1309-1326, May.
    4. Marco Di Summa & Syed Md Omar Faruk, 2023. "Critical node/edge detection problems on trees," 4OR, Springer, vol. 21(3), pages 439-455, September.
    5. Zhou, Yangming & Wang, Gezi & Hao, Jin-Kao & Geng, Na & Jiang, Zhibin, 2023. "A fast tri-individual memetic search approach for the distance-based critical node problem," European Journal of Operational Research, Elsevier, vol. 308(2), pages 540-554.
    6. Malena Schmidt & Bismark Singh, 2026. "The Balanced Facility Location Problem: Complexity and Heuristics," INFORMS Journal on Computing, INFORMS, vol. 38(1), pages 16-38, January.
    7. Roberto Aringhieri & Sara Bigharaz & Alessandro Druetto & Davide Duma & Andrea Grosso & Alberto Guastalla, 2024. "The daily swab test collection problem," Annals of Operations Research, Springer, vol. 335(3), pages 1449-1470, April.
    8. Yibo Dong & Jin Liu & Jiaqi Ren & Zhe Li & Weili Li, 2023. "Protecting Infrastructure Networks: Solving the Stackelberg Game with Interval-Valued Intuitionistic Fuzzy Number Payoffs," Mathematics, MDPI, vol. 11(24), pages 1-18, December.
    9. Ahmad, Amreen & Ahmad, Tanvir & Bhatt, Abhishek, 2020. "HWSMCB: A community-based hybrid approach for identifying influential nodes in the social network," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 545(C).
    10. Ventresca, Mario & Harrison, Kyle Robert & Ombuki-Berman, Beatrice M., 2018. "The bi-objective critical node detection problem," European Journal of Operational Research, Elsevier, vol. 265(3), pages 895-908.
    11. Haritha, P.C. & Anjaneyulu, M.V.L.R., 2026. "A simple and efficient pre-selection method for partial network scan in critical link identification," Reliability Engineering and System Safety, Elsevier, vol. 265(PB).
    12. Wang, Xiaojie & Slamu, Wushour & Guo, Wenqiang & Wang, Sixiu & Ren, Yan, 2022. "A novel semi local measure of identifying influential nodes in complex networks," Chaos, Solitons & Fractals, Elsevier, vol. 158(C).
    13. Chen Zhang & Yichen Liang & Tian Tian & Peng Peng, 2024. "Sustainable Transportation: Exploring the Node Importance Evolution of Rail Transit Networks during Peak Hours," Sustainability, MDPI, vol. 16(16), pages 1-22, August.
    14. Fink, Christian G. & Fullin, Kelly & Gutierrez, Guillermo & Omodt, Nathan & Zinnecker, Sydney & Sprint, Gina & McCulloch, Sean, 2023. "A centrality measure for quantifying spread on weighted, directed networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 626(C).
    15. Lili Sun & Xueyan Liu & Min Zhao & Bo Yang, 2021. "Interpretable Variational Graph Autoencoder with Noninformative Prior," Future Internet, MDPI, vol. 13(2), pages 1-15, February.
    16. Chaharborj, Sarkhosh Seddighi & Nabi, Khondoker Nazmoon & Feng, Koo Lee & Chaharborj, Shahriar Seddighi & Phang, Pei See, 2022. "Controlling COVID-19 transmission with isolation of influential nodes," Chaos, Solitons & Fractals, Elsevier, vol. 159(C).
    17. Chen, Wei & Hou, Xiaoli & Jiang, Manrui & Jiang, Cheng, 2022. "Identifying systemically important financial institutions in complex network: A case study of Chinese stock market," Emerging Markets Review, Elsevier, vol. 50(C).
    18. Duan, Shuyu & Wen, Tao & Jiang, Wen, 2019. "A new information dimension of complex network based on Rényi entropy," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 516(C), pages 529-542.
    19. Gao, Wenlian & Liu, Kai & Dong, Hongsong & Gao, Guojun & Rezaeipanah, Amin, 2025. "Towards a scalable semi-local centrality for weighted complex networks using information entropy and shortest path analysis," Chaos, Solitons & Fractals, Elsevier, vol. 200(P1).
    20. Jinping Lin & Kangmin Wu, 2023. "Intercity asymmetrical linkages influenced by Spring Festival migration and its multivariate distance determinants: a case study of the Yangtze River Delta Region in China," Humanities and Social Sciences Communications, Palgrave Macmillan, vol. 10(1), pages 1-10, December.

    More about this item

    Keywords

    ;
    ;
    ;
    ;
    ;

    Statistics

    Access and download statistics

    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:phsmap:v:534:y:2019:i:c:s0378437119313408. 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.journals.elsevier.com/physica-a-statistical-mechpplications/ .

    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.