Critical arcs detection in influence networks. Issue 4 (24th August 2017)

• Record Type: Journal Article
• Authors: Gillen, Colin P.; Veremyev, Alexander; Prokopyev, Oleg A.; Pasiliao, Eduardo L.
• Is Part Of: Networks. Volume 71:Issue 4(2018)
• Page Start: 412
• Page End: 431
• Publication Date: 2017-08-24
• Subjects: critical elements detection -- influence networks -- mixed‐integer programming; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21761
• Languages: English
• ISSNs: 0028-3045

Abstract

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