Predicting the evolution of spreading on complex networks

Spreading predictability in complex networks

Many state-of-the-art researches focus on predicting infection scale or threshold in infectious diseases or rumor and give the vaccination strategies correspondingly. In these works, most of them assume that the infection probability and initially infected individuals are known at the very beginning. Generally, infectious diseases or rumor has been spreading for some time when it is noticed. How to predict which individuals will be infected in the future only by knowing the current snapshot becomes a key issue in infectious diseases or rumor control. In this report, a prediction model based on snapshot is presented to predict the potentially infected individuals in the future, not just the macro scale of infection. Experimental results on synthetic and real networks demonstrate that the infected individuals predicted by the model have good consistency with the actual infected ones based on simulations.

Benchmarking seeding strategies for spreading processes in social networks: an interplay between influencers, topologies and sizes

The explosion of network science has permitted an understanding of how the structure of social networks affects the dynamics of social contagion. In community-based interventions with spill-over effects, identifying influential spreaders may be harnessed to increase the spreading efficiency of social contagion, in terms of time needed to spread all the largest connected component of the network. Several strategies have been proved to be efficient using only data and simulation-based models in specific network topologies without a consensus of an overall result. Hence, the purpose of this paper is to benchmark the spreading efficiency of seeding strategies related to network structural properties and sizes. We simulate spreading processes on empirical and simulated social networks within a wide range of densities, clustering coefficients, and sizes. We also propose three new decentralized seeding strategies that are structurally different from well-known strategies: community hubs, ambassadors, and random hubs. We observe that the efficiency ranking of strategies varies with the network structure. In general, for sparse networks with community structure, decentralized influencers are suitable for increasing the spreading efficiency. By contrast, when the networks are denser, centralized influencers outperform. These results provide a framework for selecting efficient strategies according to different contexts in which social networks emerge.

Waves of novelties in the expansion into the adjacent possible

The emergence of novelties and their rise and fall in popularity is an ubiquitous phenomenon in human activities. The coexistence of popular evergreens with novel and sometimes ephemeral trends pervades technological, scientific and artistic production. Though this phenomenon is very intuitively captured by our common sense, a comprehensive explanation of how waves of novelties are not hampered by well established old-comers is still lacking. Here we first quantify this phenomenology by empirically looking at different systems that display innovation at very different levels: the creation of hashtags in Twitter, the evolution of online code repositories, the creation of texts and the listening of songs on online platforms. In all these systems surprisingly similar patterns emerge as the non-trivial outcome of two contrasting forces: the tendency of retracing already explored avenues (exploit) and the inclination to explore new possibilities. These findings are naturally explained in the framework of the expansion of the adjacent possible, a recently introduced theoretical framework that postulates the restructuring of the space of possibilities conditional to the occurrence of innovations. The predictions of our theoretical framework are borne out in all the phenomenologies investigated, paving the way to a better understanding and control of innovation processes.

Identifying a set of influential spreaders in complex networks

Identifying a set of influential spreaders in complex networks plays a crucial role in effective information spreading. A simple strategy is to choose top-r ranked nodes as spreaders according to influence ranking method such as PageRank, ClusterRank and k-shell decomposition. Besides, some heuristic methods such as hill-climbing, SPIN, degree discount and independent set based are also proposed. However, these approaches suffer from a possibility that some spreaders are so close together that they overlap sphere of influence or time consuming. In this report, we present a simply yet effectively iterative method named VoteRank to identify a set of decentralized spreaders with the best spreading ability. In this approach, all nodes vote in a spreader in each turn, and the voting ability of neighbors of elected spreader will be decreased in subsequent turn. Experimental results on four real networks show that under Susceptible-Infected-Recovered (SIR) and Susceptible-Infected (SI) models, VoteRank outperforms the traditional benchmark methods on both spreading rate and final affected scale. What’s more, VoteRank has superior computational efficiency.

Locating influential nodes via dynamics-sensitive centrality

With great theoretical and practical significance, locating influential nodes of complex networks is a promising issue. In this paper, we present a dynamics-sensitive (DS) centrality by integrating topological features and dynamical properties. The DS centrality can be directly applied in locating influential spreaders. According to the empirical results on four real networks for both susceptible-infected-recovered (SIR) and susceptible-infected (SI) spreading models, the DS centrality is more accurate than degree, k-shell index and eigenvector centrality.

Reconstructing propagation networks with temporal similarity

Node similarity significantly contributes to the growth of real networks. In this paper, based on the observed epidemic spreading results we apply the node similarity metrics to reconstruct the underlying networks hosting the propagation. We find that the reconstruction accuracy of the similarity metrics is strongly influenced by the infection rate of the spreading process. Moreover, there is a range of infection rate in which the reconstruction accuracy of some similarity metrics drops nearly to zero. To improve the similarity-based reconstruction method, we propose a temporal similarity metric which takes into account the time information of the spreading. The reconstruction results are remarkably improved with the new method.

Detecting the influence of spreading in social networks with excitable sensor networks

Detecting spreading outbreaks in social networks with sensors is of great significance in applications. Inspired by the formation mechanism of humans’ physical sensations to external stimuli, we propose a new method to detect the influence of spreading by constructing excitable sensor networks. Exploiting the amplifying effect of excitable sensor networks, our method can better detect small-scale spreading processes. At the same time, it can also distinguish large-scale diffusion instances due to the self-inhibition effect of excitable elements. Through simulations of diverse spreading dynamics on typical real-world social networks (Facebook, coauthor, and email social networks), we find that the excitable sensor networks are capable of detecting and ranking spreading processes in a much wider range of influence than other commonly used sensor placement methods, such as random, targeted, acquaintance and distance strategies. In addition, we validate the efficacy of our method with diffusion data from a real-world online social system, Twitter. We find that our method can detect more spreading topics in practice. Our approach provides a new direction in spreading detection and should be useful for designing effective detection methods.