ABSTRACT The strength of a graph was introduced by Cunningham (1985) as the minimum ratio of the number of edges that could be removed from the graph to the number (minus one) of the connected components created by such a removal. The role of the strength of a graph as a connectivity and resilience measure is further highlighted by its connection to the spanning tree packing number of a graph, namely, the maximum number of edge‐disjoint spanning trees that can be contained in a graph. In this work, we investigate the question of determining a subset of a given graph's vertices of maximum cardinality that induces a subgraph of at least the prescribed strength. We show that the stated problem is polynomially solvable, and present the corresponding algorithm. In addition, we propose a mathematical programming‐based cutting plane method for computing graph strength, which can be integrated into larger mathematical programming models. Numerical experiments on a diverse array of real‐world graphs illustrate the computational properties of the proposed algorithms.

Abstract Graph clustering is an important problem in network analysis. This problem can be approached by first finding a large cluster subgraph (i.e., a subgraph in which every connected component is a complete graph), perhaps in a relaxed form (connected components may have missing edges), and then assigning each of the remaining vertices to one of the connected components of the cluster subgraph according to some optimization criteria. The more vertices can be included in the initial cluster subgraph (also referred to as independent union of clusters), the more “clusterable” the graph is. This paper proposes a framework for establishing asymptotic bounds on the cardinality of independent unions of clusters in Erdős‐Rényi random graphs with constant , referred to as uniform random graphs. In particular, sufficient conditions ensuring (where is the number of nodes) upper bounds with probability 1 are developed and shown to be applicable for the maximum independent union of cliques as well as some clique relaxations. In addition, it is shown that every graph must have an independent union of cliques of cardinality at least . Since this bound is asymptotically tight on uniform random graphs, this suggests that these graphs can be viewed as a “least clusterable” class of graphs.

Abstract We propose an approach to constructing metrics of network resilience, where resilience is understood as the network's amenability to restoring its optimal or near‐optimal operations subsequent to unforeseen (stochastic) disruptions of its topology or operational parameters, and illustrated it on the examples of the resilient maximum network flow problem and the resilient minimum cost network problem. Specifically, the network flows in these problems are designed for resilience against unpredictable losses of network carrying capacity, and the mechanism of attaining a degree of resilience is through preallocation of resources toward (at least partial) restoration of the capacities of the arcs. The obtained formulations of resilient network flow problems possess a number of useful properties, for example, similarly to the standard network flow problems, the network flow is integral if the arc capacities, costs, and so forth, are integral. It is also shown that the proposed formulations of resilient network flow problems can be viewed as “network measures of risk”, similar in properties and behavior to convex measures of risk. Efficient decomposition algorithms have been proposed for both the resilient maximum network flow problem and the resilient minimum cost network flow problem, and a study of the network flow resilience as a function of network's structure has been conducted on networks with three types of topology: that of uniform random graphs, scale‐free graphs, and grid graphs.

We propose a two-stage stochastic programming framework for designing or identifying “resilient,” or “reparable” structures in graphs whose topology may undergo a stochastic transformation. The reparability of a subgraph satisfying a given property is defined in terms of a budget constraint, which allows for a prescribed number of vertices to be added to or removed from the subgraph so as to restore its structural properties after the observation of random changes to the graph's set of edges. A two-stage stochastic programming model is formulated and is shown to be -complete for a broad range of graph-theoretical properties that the resilient subgraph is required to satisfy. A general combinatorial branch-and-bound algorithm is developed, and its computational performance is illustrated on the example of a two-stage stochastic maximum clique problem. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 69(2), 189–204 2017

We present an efficient scenario decomposition algorithm for solving large-scale convex stochastic programming problems that involve a particular class of downside risk measures. The considered risk functionals encompass coherent and convex measures of risk that can be represented as an infimal convolution of a convex certainty equivalent, and include well-known measures, such as conditional value-at-risk, as special cases. The resulting structure of the feasible set is then exploited via iterative solving of relaxed problems, and it is shown that the number of iterations is bounded by a parameter that depends on the problem size. The computational performance of the developed scenario decomposition method is illustrated on portfolio optimization problems involving two families of nonlinear measures of risk, the higher-moment coherent risk measures, and log-exponential convex risk measures. It is demonstrated that for large-scale nonlinear problems the proposed approach can provide up to an order-of-magnitude improvement in computational time in comparison to state-of-the-art solvers, such as CPLEX, Gurobi, and MOSEK.