Pre-emptive spectral graph protection strategies on multiplex social networks

Abstract

Constructing effective and scalable protection strategies over epidemic propagation is a challenging issue. It has been attracting interests in both theoretical and empirical studies. However, most of the recent developments are limited to the simplified single-layered networks. Multiplex social networks are social networks with multiple layers where the same set of nodes appear in different layers. Consequently, a single attack can trigger simultaneous propagation in all corresponding layers. Therefore, suppressing propagation in multiplex topologies is more challenging given the fact that each layer also has a different structure. In this paper, we address the problem of suppressing the epidemic propagation in multiplex social networks by allocating protection resources throughout different layers. Given a multiplex graph, such as a social network, and k budget of protection resources, we aim to protect a set of nodes such that the percentage of survived nodes at the end of epidemics is maximized. We propose MultiplexShield, which employs the role of graph spectral properties, degree centrality and layer-wise stochastic propagation rate to pre-emptively select k nodes for protection. We also comprehensively evaluate our proposal in two different approaches: multiplex-based and layer-based node protection schemes. Furthermore, two kinds of common attacks are also evaluated: random and targeted attack. Experimental results show the effectiveness of our proposal on real-world datasets.

Keywords: Epidemic contagion; Graph mining; Multiplex networks; Node immunization.

Fig. 1

Schematic Illustration of Different Protection Scheme. a Input graph. b Initial epidemics and protection condition at timestamp t=0. c Infected nodes start to infect their neighbors at timestamp t=1. d Input graph. e Initial epidemics and protection condition at timestamp t=0. f Infected nodes start to infect their neighbors at timestamp t=1

Fig. 2

Schematic Illustration of Finding Centers and Bridges in Graph. The red dots represent the protected nodes. Shaded lines represent the removed edges. a Initial Input Graph. b Protecting the Bridges, nodes with highest value of Random Walk Normalized Fiedler Vector (μ). c Protecting the Centers, nodes with highest value of Degree Centrality (d). d Combining (b) and (c) objectives in MultiplexShield

Fig. 3

Scalability evaluation of proposed MULTIPLEXSHIELD