IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v31y2019i2p367-389.html
   My bibliography  Save this article

Finding Critical Links for Closeness Centrality

Author

Listed:
  • Alexander Veremyev

    (Industrial Engineering and Management Systems, University of Central Florida, Orlando, Florida 32816)

  • Oleg A. Prokopyev

    (Industrial Engineering, University of Pittsburgh, Pittsburgh, Pennsylvania 15261)

  • Eduardo L. Pasiliao

    (Munitions Directorate, Air Force Research Laboratory, Eglin AFB, Florida 32542)

Abstract

Closeness centrality is a class of distance-based measures in the network analysis literature to quantify reachability of a given vertex (or a group of vertices) by other network agents. In this paper, we consider a new class of critical edge detection problems, in which given a group of vertices that represent an important subset of network elements of interest (e.g., servers that provide an essential service to the network), the decision maker is interested in identifying a subset of critical edges whose removal maximally degrades the closeness centrality of those vertices. We develop a general optimization framework, in which the closeness centrality measure can be based on any nonincreasing function of distances between vertices, which, in turn, can be interpreted as communication efficiency between them. Our approach includes three well-known closeness centrality measures as special cases: harmonic centrality , decay centrality , and k -step reach centrality . Furthermore, for quantifying the centrality of a group of vertices we consider three different approaches for measuring the reachability of the group from any vertex in the network: minimum distance to a vertex in the group, maximum distance to a vertex in the group, and the average centrality of vertices in the group. We study the theoretical computational complexity of the proposed models and describe the corresponding mixed integer programming formulations. For solving medium- and large-scale instances of the problem, we first develop an exact algorithm that exploits the fact that real-life networks often have rather small diameters. Then we propose two conceptually different heuristic algorithms. Finally, we conduct computational experiments with real-world and synthetic network instances under various settings, which reveal interesting insights and demonstrate the advantages and limitations of the proposed models and algorithms.

Suggested Citation

  • 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.
  • Handle: RePEc:inm:orijoc:v:31:y:2019:i:2:p:367-389
    DOI: 10.1287/ijoc.2018.0829
    as

    Download full text from publisher

    File URL: https://doi.org/10.1287/ijoc.2018.0829
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2018.0829?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
    ---><---

    References listed on IDEAS

    as
    1. C. Audet & P. Hansen & B. Jaumard & G. Savard, 1997. "Links Between Linear Bilevel and Mixed 0–1 Programming Problems," Journal of Optimization Theory and Applications, Springer, vol. 93(2), pages 273-300, May.
    2. Jose L. Walteros & Panos M. Pardalos, 2012. "Selected Topics in Critical Element Detection," Springer Optimization and Its Applications, in: Nicholas J. Daras (ed.), Applications of Mathematics and Informatics in Military Science, edition 127, chapter 0, pages 9-26, Springer.
    3. David L. Alderson & Gerald G. Brown & W. Matthew Carlyle & R. Kevin Wood, 2018. "Assessing and Improving the Operational Resilience of a Large Highway Infrastructure System to Worst-Case Losses," Transportation Science, INFORMS, vol. 52(4), pages 1012-1034, August.
    4. Crucitti, Paolo & Latora, Vito & Marchiori, Massimo & Rapisarda, Andrea, 2004. "Error and attack tolerance of complex networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 340(1), pages 388-394.
    5. Benoît Colson & Patrice Marcotte & Gilles Savard, 2007. "An overview of bilevel optimization," Annals of Operations Research, Springer, vol. 153(1), pages 235-256, September.
    6. Stephen P. Borgatti, 2006. "Identifying sets of key players in a social network," Computational and Mathematical Organization Theory, Springer, vol. 12(1), pages 21-34, April.
    7. Dangalchev, Chavdar, 2006. "Residual closeness in networks," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 365(2), pages 556-564.
    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. Colin P. Gillen & Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2021. "Fortification Against Cascade Propagation Under Uncertainty," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1481-1499, October.
    4. Zhong, Haonan & Mahdavi Pajouh, Foad & A. Prokopyev, Oleg, 2023. "On designing networks resilient to clique blockers," European Journal of Operational Research, Elsevier, vol. 307(1), pages 20-32.
    5. 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.
    6. 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.

    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. Nair, Rahul & Miller-Hooks, Elise, 2014. "Equilibrium network design of shared-vehicle systems," European Journal of Operational Research, Elsevier, vol. 235(1), pages 47-61.
    3. Alexander Veremyev & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2014. "An integer programming framework for critical elements detection in graphs," Journal of Combinatorial Optimization, Springer, vol. 28(1), pages 233-273, July.
    4. Juan S. Borrero & Oleg A. Prokopyev & Denis Sauré, 2019. "Sequential Interdiction with Incomplete Information and Learning," Operations Research, INFORMS, vol. 67(1), pages 72-89, January.
    5. Bo Zeng, 2020. "A Practical Scheme to Compute the Pessimistic Bilevel Optimization Problem," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1128-1142, October.
    6. Gabriel Lopez Zenarosa & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2021. "On exact solution approaches for bilevel quadratic 0–1 knapsack problem," Annals of Operations Research, Springer, vol. 298(1), pages 555-572, March.
    7. M. Hosein Zare & Juan S. Borrero & Bo Zeng & Oleg A. Prokopyev, 2019. "A note on linearized reformulations for a class of bilevel linear integer problems," Annals of Operations Research, Springer, vol. 272(1), pages 99-117, January.
    8. 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.
    9. Mofidi, Seyed Shahab & Pazour, Jennifer A., 2019. "When is it beneficial to provide freelance suppliers with choice? A hierarchical approach for peer-to-peer logistics platforms," Transportation Research Part B: Methodological, Elsevier, vol. 126(C), pages 1-23.
    10. M. Hosein Zare & Oleg A. Prokopyev & Denis Sauré, 2020. "On Bilevel Optimization with Inexact Follower," Decision Analysis, INFORMS, vol. 17(1), pages 74-95, March.
    11. M. Hosein Zare & Osman Y. Özaltın & Oleg A. Prokopyev, 2018. "On a class of bilevel linear mixed-integer programs in adversarial settings," Journal of Global Optimization, Springer, vol. 71(1), pages 91-113, May.
    12. Huff, Johnathon D. & Leonard, William B. & Medal, Hugh R., 2022. "The wireless network jamming problem subject to protocol interference using directional antennas and with battery capacity constraints," International Journal of Critical Infrastructure Protection, Elsevier, vol. 39(C).
    13. Vladimir Stozhkov & Vladimir Boginski & Oleg A. Prokopyev & Eduardo L. Pasiliao, 2017. "A simple greedy heuristic for linear assignment interdiction," Annals of Operations Research, Springer, vol. 249(1), pages 39-53, February.
    14. Junlong Zhang & Osman Y. Özaltın, 2021. "Bilevel Integer Programs with Stochastic Right-Hand Sides," INFORMS Journal on Computing, INFORMS, vol. 33(4), pages 1644-1660, October.
    15. Carvalho, Margarida & Lodi, Andrea, 2023. "A theoretical and computational equilibria analysis of a multi-player kidney exchange program," European Journal of Operational Research, Elsevier, vol. 305(1), pages 373-385.
    16. Andreas Lanz & Gregor Reich & Ole Wilms, 2022. "Adaptive grids for the estimation of dynamic models," Quantitative Marketing and Economics (QME), Springer, vol. 20(2), pages 179-238, June.
    17. Shi, Yi & Deng, Yawen & Wang, Guoan & Xu, Jiuping, 2020. "Stackelberg equilibrium-based eco-economic approach for sustainable development of kitchen waste disposal with subsidy policy: A case study from China," Energy, Elsevier, vol. 196(C).
    18. Lucio Bianco & Massimiliano Caramia & Stefano Giordani & Veronica Piccialli, 2016. "A Game-Theoretic Approach for Regulating Hazmat Transportation," Transportation Science, INFORMS, vol. 50(2), pages 424-438, May.
    19. Quayle, A.P. & Siddiqui, A.S. & Jones, S.J.M., 2006. "Preferential network perturbation," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 371(2), pages 823-840.
    20. M. Köppe & M. Queyranne & C. T. Ryan, 2010. "Parametric Integer Programming Algorithm for Bilevel Mixed Integer Programs," Journal of Optimization Theory and Applications, Springer, vol. 146(1), pages 137-150, July.

    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:inm:orijoc:v:31:y:2019:i:2:p:367-389. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.