Critical arcs detection in influence networks
Abstract
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
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Aug 24, 2017
- Source ID
- 10.1002/net.21761
Entities
People
- Alexander Veremyev
- Colin P. Gillen
- Eduardo Pasiliao
- Oleg A. Prokopyev
Organizations
- Air Force Office of Scientific Research
- Air Force Research Laboratory
- Defense Threat Reduction Agency
- University of Florida
- University of Pittsburgh