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 a...
详细信息
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 NP-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.
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, ele...
详细信息
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. (c) 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 412-431 2018
This paper introduces and studies the minimum edge blocker dominating set problem (EBDP), which is formulated as follows. Given a vertex-weighted undirected graph and r> 0, remove a minimum number of edges so that ...
详细信息
This paper introduces and studies the minimum edge blocker dominating set problem (EBDP), which is formulated as follows. Given a vertex-weighted undirected graph and r> 0, remove a minimum number of edges so that the weight of any dominating set in the remaining graph is at least r. Dominating sets are used in a wide variety of graph-based applications such as the analysis of wireless and social networks. We show that the decision version of EBDP is NP-hard for any fixed r> 0. We present an analytical lower bound for the value of an optimal solution to EBDP and formulate this problem as a linear 0-1 program with a large number of constraints. We also study the convex hull of feasible solutions to EBDP and identify facet-inducing inequalities for this polytope. Furthermore, we develop the first exact algorithm for solving EBDP, which solves the proposed formulation by a branch-and-cut approach where nontrivial constraints are applied in a lazy fashion. Finally, we also provide the computational results obtained by using our approach on a test-bed of randomly generated instances and real-life power-law graphs. (C) 2015 Elsevier B.V. and Association of European Operational Research Societies (EURO) within the International Federation of Operational Research Societies (IFORS). All rights reserved.
暂无评论