Balancing Speed and Coverage by Sequential Seeding in Complex Networks

Habituation effect in social networks as a potential factor silently crushing influence maximisation efforts

Information spreading processes are a key phenomenon observed within real and digital social networks. Network members are often under pressure from incoming information with different sources, such as informative campaigns for increasing awareness, viral marketing, rumours, fake news, or the results of other activities. Messages are often repeated, and such repetition can improve performance in the form of cumulative influence. Repeated messages may also be ignored due to a limited ability to process information. Learning processes are leading to the repeated messages being ignored, as their content has already been absorbed. In such cases, responsiveness decreases with repetition, and the habituation effect can be observed. Here, we analyse spreading processes while considering the habituation effect and performance drop along with an increased number of contacts. The ability to recover when reducing the number of messages is also considered. The results show that even low habituation and a decrease in propagation probability may substantially impact network coverage. This can lead to a significant reduction in the potential for a seed set selected with an influence maximisation method. Apart from the impact of the habituation effect on spreading processes, we show how it can be reduced with the use of the sequential seeding approach. This shows that sequential seeding is less sensitive to the habituation effect than single-stage seeding, and that it can be used to limit the negative impact on users overloaded with incoming messages.

Sequential seeding in multilayer networks

Multilayer networks are the underlying structures of multiple real-world systems where we have more than one type of interaction/relation between nodes: social, biological, computer, or communication, to name only a few. In many cases, they are helpful in modeling processes that happen on top of them, which leads to gaining more knowledge about these phenomena. One example of such a process is the spread of influence. Here, the members of a social system spread the influence across the network by contacting each other, sharing opinions or ideas, or-explicitly-by persuasion. Due to the importance of this process, researchers investigate which members of a social network should be chosen as initiators of influence spread to maximize the effect. In this work, we follow this direction and develop and evaluate the sequential seeding technique for multilayer networks. Until now, such techniques were evaluated only using simple one layer networks. The results show that sequential seeding in multilayer networks outperforms the traditional approach by increasing the coverage and allowing to save the seeding budget. However, it also extends the duration of the spreading process.

State-based targeted vaccination

Vaccination has become one of the most prominent measures for preventing the spread of infectious diseases in modern times. However, mass vaccination of the population may not always be possible due to high costs, severe side effects, or shortage. Therefore, identifying individuals with a high potential of spreading the disease and targeted vaccination of these individuals is of high importance. While various strategies for identifying such individuals have been proposed in the network epidemiology literature, the vast majority of them rely solely on the network topology. In contrast, in this paper, we propose a novel targeted vaccination strategy that considers both the static network topology and the dynamic states of the network nodes over time. This allows our strategy to find the individuals with the highest potential to spread the disease at any given point in time. Extensive evaluation that we conducted over various real-world network topologies, network sizes, vaccination budgets, and parameters of the contagion model, demonstrates that the proposed strategy considerably outperforms existing state-of-the-art targeted vaccination strategies in reducing the spread of the disease. In particular, the proposed vaccination strategy further reduces the number of infected nodes by 23-99%, compared to a vaccination strategy based on Betweenness Centrality.

A generalized linear threshold model for an improved description of the spreading dynamics

Many spreading processes in our real-life can be considered as a complex contagion, and the linear threshold (LT) model is often applied as a very representative model for this mechanism. Despite its intensive usage, the LT model suffers several limitations in describing the time evolution of the spreading. First, the discrete-time step that captures the speed of the spreading is vaguely defined. Second, the synchronous updating rule makes the nodes infected in batches, which cannot take individual differences into account. Finally, the LT model is incompatible with existing models for the simple contagion. Here, we consider a generalized linear threshold (GLT) model for the continuous-time stochastic complex contagion process that can be efficiently implemented by the Gillespie algorithm. The time in this model has a clear mathematical definition, and the updating order is rigidly defined. We find that the traditional LT model systematically underestimates the spreading speed and the randomness in the spreading sequence order. We also show that the GLT model works seamlessly with the susceptible-infected or susceptible-infected-recovered model. One can easily combine them to model a hybrid spreading process in which simple contagion accumulates the critical mass for the complex contagion that leads to the global cascades. Overall, the GLT model we proposed can be a useful tool to study complex contagion, especially when studying the time evolution of the spreading.

Influence Maximization for Fixed Heterogeneous Thresholds

Influence Maximization is a NP-hard problem of selecting the optimal set of influencers in a network. Here, we propose two new approaches to influence maximization based on two very different metrics. The first metric, termed Balanced Index (BI), is fast to compute and assigns top values to two kinds of nodes: those with high resistance to adoption, and those with large out-degree. This is done by linearly combining three properties of a node: its degree, susceptibility to new opinions, and the impact its activation will have on its neighborhood. Controlling the weights between those three terms has a huge impact on performance. The second metric, termed Group Performance Index (GPI), measures performance of each node as an initiator when it is a part of randomly selected initiator set. In each such selection, the score assigned to each teammate is inversely proportional to the number of initiators causing the desired spread. These two metrics are applicable to various cascade models; here we test them on the Linear Threshold Model with fixed and known thresholds. Furthermore, we study the impact of network degree assortativity and threshold distribution on the cascade size for metrics including ours. The results demonstrate our two metrics deliver strong performance for influence maximization.

Multi-criteria decision support for planning and evaluation of performance of viral marketing campaigns in social networks

The current marketing landscape, apart from conventional approaches, consists of campaigns designed especially for launching information diffusion processes within online networks. Associated research is focused on information propagation models, campaign initialization strategies and factors affecting campaign dynamics. In terms of algorithms and performance evaluation, the final coverage represented by the fraction of activated nodes within a target network is usually used. It is not necessarily consistent with the real marketing campaigns using various characteristics and parameters related to coverage, costs, behavioral patterns and time factors for overall evaluation. This paper presents assumptions for a decision support system for multi-criteria campaign planning and evaluation with inputs from agent-based simulations. The results, which are delivered from a simulation model based on synthetic networks in a form of decision scenarios, are verified within a real network. Last, but not least, the study proposes a multi-objective campaign evaluation framework with several campaign evaluation metrics integrated. The results showed that the recommendations generated with the use of synthetic networks applied to real networks delivered results according to the decision makers' expectation in terms of the used evaluation criteria. Apart from practical applications, the proposed multi-objective approach creates new evaluation possibilities for theoretical studies focused on information spreading processes within complex networks.

Strategic distribution of seeds to support diffusion in complex networks

Usually, the launch of the diffusion process is triggered by a few early adopters–i.e., seeds of diffusion. Many studies have assumed that all seeds are activated once to initiate the diffusion process in social networks and therefore are focused on finding optimal ways of choosing these nodes according to a limited budget. Despite the advances in identifying influencing spreaders, the strategy of activating all seeds at the beginning might not be sufficient in accelerating and maximising the coverage of diffusion. Also, it does not capture real scenarios in which marketing campaigns continuously monitor and support the diffusion process by seeding more nodes. More recent studies investigate the possibility of activating additional seeds as the diffusion process goes forward. In this work, we further examine this approach and search for optimal ways of distributing seeds during the diffusion process according to a pre-allocated seeding budget. Theoretically, we show that a universally best solution does not exist, and we prove that finding an optimal distribution of supporting seeds over time for a particular network is an NP-hard problem. Numerically, we evaluate several seeding strategies on different networks regarding maximising the coverage and minimising the spreading time. We find that each network topology has a best strategy given some spreading parameters. Our findings can be crucial in identifying the best strategies for budget allocation in different scenarios such as marketing or political campaigns.

Probing Limits of Information Spread with Sequential Seeding

We consider here information spread which propagates with certain probability from nodes just activated to their not yet activated neighbors. Diffusion cascades can be triggered by activation of even a small set of nodes. Such activation is commonly performed in a single stage. A novel approach based on sequential seeding is analyzed here resulting in three fundamental contributions. First, we propose a coordinated execution of randomized choices to enable precise comparison of different algorithms in general. We apply it here when the newly activated nodes at each stage of spreading attempt to activate their neighbors. Then, we present a formal proof that sequential seeding delivers at least as good spread coverage as the single stage seeding does. Moreover, we also show that, under modest assumptions, sequential seeding performs provably better than the single stage seeding using the same number of seeds and node ranking. Finally, we present experimental results comparing single stage and sequential approaches on directed and undirected graphs to the well-known greedy approach to provide the objective measure of the sequential seeding benefits. Surprisingly, applying sequential seeding to a simple degree-based selection leads to higher coverage than achieved by the computationally expensive greedy approach currently considered to be the best heuristic.

Fast and accurate detection of spread source in large complex networks

Spread over complex networks is a ubiquitous process with increasingly wide applications. Locating spread sources is often important, e.g. finding the patient one in epidemics, or source of rumor spreading in social network. Pinto, Thiran and Vetterli introduced an algorithm (PTVA) to solve the important case of this problem in which a limited set of nodes act as observers and report times at which the spread reached them. PTVA uses all observers to find a solution. Here we propose a new approach in which observers with low quality information (i.e. with large spread encounter times) are ignored and potential sources are selected based on the likelihood gradient from high quality observers. The original complexity of PTVA is O(N α ), where α ∈ (3,4) depends on the network topology and number of observers (N denotes the number of nodes in the network). Our Gradient Maximum Likelihood Algorithm (GMLA) reduces this complexity to O (N2log (N)). Extensive numerical tests performed on synthetic networks and real Gnutella network with limitation that id's of spreaders are unknown to observers demonstrate that for scale-free networks with such limitation GMLA yields higher quality localization results than PTVA does.