Network cascades represent a number of real-life applications: social influence, electrical grid failures, viral spread, and so on. The commonality between these phenomena is that they begin from a set of seed nodes and spread to other regions of the network. We consider a variant of a critical node detection problem dubbed the robust critical node fortification problem, wherein the decision maker wishes to fortify nodes (within a budget) to limit the spread of cascading behavior under uncertain conditions. In particular, the arc weights—how much influence one node has on another in the cascade process—are uncertain but are known to lie in some range bounded by a worst-case budget uncertainty. This problem is shown to be [Formula: see text]-hard even in the deterministic case. We formulate a mixed-integer program (MIP) to solve the deterministic problem and improve its continuous relaxation via nonlinear constraints and convexification. The robust problem is computationally more difficult, and we present an MIP-based expand-and-cut exact solution algorithm, in which the expansion is enhanced by cutting planes, which are themselves tied to the expansion process. Insights from these exact solutions motivate two novel (interrelated) centrality measures, and a centrality-based heuristic that obtains high-quality solutions within a few seconds. Finally, extensive computational results are given to validate our theoretical developments as well as provide insights into structural properties of the robust problem and its solution.

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 [Formula: see text]-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. The online appendices are available at https://doi.org/10.1287/ijoc.2018.0829 .

Abstract We consider the problem of detecting a collection of critical node structures of a graph whose deletion results in the maximum deterioration of the graph's connectivity. The proposed approach is aimed to generalize other existing models whose scope is restricted to removing individual and unrelated nodes. We consider two common metrics to quantify the connectivity of the residual graph: the total number of connected node pairs and the size of the largest connected component. We first discuss the computational complexity of the problem and then introduce a general mixed‐integer linear formulation, which depending on the kind of node structures, may have an exponentially large number of variables and constraints. To solve this potentially large model, we develop a branch‐price‐and‐cut framework, along with some valid inequalities and preprocessing algorithms to strengthen the formulation and reduce the overall execution time. We use the proposed approach to solve the problem for the cases, where the node structures form cliques or stars and provide further directions on how to extend the framework for detecting other kinds of critical structures as well. Finally, we test the quality of our approach by solving a collection of real‐life and randomly generated instances with various configurations, analyze the benefits of our model, and propose further enhancements.

The influence class of network problems models the propagation of influence (an abstraction of cascading beliefs, behaviors, or physical phenomena) in a network. Such problems have applications in social networks, electrical networks, computer networks, viral spreading, and so on. These types of networks have also been studied through the lens of critical arcs detection; that is, which arcs (edges) are the most important for maintaining some property of the network (e.g., connectivity). We introduce a new class of problems at the intersection of these two models. Specifically, given a set of seed nodes and the linear threshold influence propagation model, our work proposes to determine which arcs (e.g., relationships in a social network or communication pathways in a telecommunication network) are most critical to the influence propagation process. We prove NP‐hardness of the problem. Time‐dependent and time‐independent mixed‐integer programming (MIP) models are introduced. Insights gleaned from MIP solutions leads to the development of an improved MIP‐based exact algorithm rooted in the idea of diffusion expansion. A heuristic based upon a new centrality measure is also proposed, and computational results are presented. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 412–431 2018

We consider the problem of finding a degree‐based ‐quasi‐clique of maximum cardinality in a given graph for some fixed . A degree‐based ‐quasi‐clique (often referred to as simply a quasi‐clique) is a subgraph, where the degree of each vertex is at least times the maximum possible degree of a vertex in the subgraph. A degree‐based ‐quasi‐clique is a relative clique relaxation model, where the case of corresponds to the well‐known concept of a clique. In this article, we first prove that the problem is ‐hard for any fixed , which addresses one of the open questions in the literature. More importantly, we also develop new exact solution methods for solving the problem and demonstrate their advantages and limitations in extensive computational experiments with both random and real‐world networks. Finally, we outline promising directions of future research including possible functional generalizations of the considered clique relaxation model. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(2), 136–152 2018

This study considers a class of critical node detection problems that involves minimization of a distance‐based connectivity measure of a given unweighted graph via the removal of a subset of nodes (referred to as critical nodes) subject to a budgetary constraint. The distance‐based connectivity measure of a graph is assumed to be a function of the actual pairwise distances between nodes in the remaining graph (e.g., graph efficiency, Harary index, characteristic path length, residual closeness) rather than simply whether nodes are connected or not, a typical assumption in the literature. We derive linear integer programming (IP) formulations, along with additional enhancements, aimed at improving the performance of standard solvers. For handling larger instances, we develop an effective exact algorithm that iteratively solves a series of simpler IPs to obtain an optimal solution for the original problem. The edge‐weighted generalization is also considered, which results in some interesting implications for distance‐based clique relaxations, namely, ‐clubs. Finally, we conduct extensive computational experiments with real‐world and randomly generated network instances under various settings that reveal interesting insights and demonstrate the advantages and limitations of the proposed approach. In particular, one important conclusion of our work is that vulnerability of real‐world networks to targeted attacks can be significantly more pronounced than what can be estimated by centrality‐based heuristic methods commonly used in the literature. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 66(3), 170–195 2015