1
|
Jankowski J. Habituation effect in social networks as a potential factor silently crushing influence maximisation efforts. Sci Rep 2021; 11:19055. [PMID: 34561501 PMCID: PMC8463708 DOI: 10.1038/s41598-021-98493-9] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/29/2021] [Accepted: 09/09/2021] [Indexed: 02/08/2023] Open
Abstract
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.
Collapse
Affiliation(s)
- Jarosław Jankowski
- Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, 71-210, Szczecin, Poland.
| |
Collapse
|
2
|
Bródka P, Jankowski J, Michalski R. Sequential seeding in multilayer networks. CHAOS (WOODBURY, N.Y.) 2021; 31:033130. [PMID: 33810708 DOI: 10.1063/5.0023427] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 07/29/2020] [Accepted: 02/26/2021] [Indexed: 06/12/2023]
Abstract
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.
Collapse
Affiliation(s)
- Piotr Bródka
- Department of Computational Intelligence, Wrocław University of Science and Technology, Wybrzeże Wyspiańskiego 27, Wrocław 50-370, Poland
| | - Jarosław Jankowski
- Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, Zolnierska 49, Szczecin 71-210, Poland
| | - Radosław Michalski
- Department of Computational Intelligence, Wrocław University of Science and Technology, Wybrzeże Wyspiańskiego 27, Wrocław 50-370, Poland
| |
Collapse
|
3
|
Lev T, Shmueli E. State-based targeted vaccination. APPLIED NETWORK SCIENCE 2021; 6:6. [PMID: 33501371 PMCID: PMC7820107 DOI: 10.1007/s41109-021-00352-z] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 10/06/2020] [Accepted: 01/07/2021] [Indexed: 06/12/2023]
Abstract
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.
Collapse
Affiliation(s)
- Tomer Lev
- Department of Industrial Engineering, Tel-Aviv University, Ramat Aviv, 69978 Tel-Aviv, Israel
| | - Erez Shmueli
- Department of Industrial Engineering, Tel-Aviv University, Ramat Aviv, 69978 Tel-Aviv, Israel
| |
Collapse
|
4
|
Ran Y, Deng X, Wang X, Jia T. A generalized linear threshold model for an improved description of the spreading dynamics. CHAOS (WOODBURY, N.Y.) 2020; 30:083127. [PMID: 32872812 DOI: 10.1063/5.0011658] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 04/23/2020] [Accepted: 07/27/2020] [Indexed: 06/11/2023]
Abstract
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.
Collapse
Affiliation(s)
- Yijun Ran
- College of Computer and Information Science, Southwest University, Beibei, Chongqing 400715, People's Republic of China
| | - Xiaomin Deng
- College of Computer and Information Science, Southwest University, Beibei, Chongqing 400715, People's Republic of China
| | - Xiaomeng Wang
- College of Computer and Information Science, Southwest University, Beibei, Chongqing 400715, People's Republic of China
| | - Tao Jia
- College of Computer and Information Science, Southwest University, Beibei, Chongqing 400715, People's Republic of China
| |
Collapse
|
5
|
Karampourniotis PD, Szymanski BK, Korniss G. Influence Maximization for Fixed Heterogeneous Thresholds. Sci Rep 2019; 9:5573. [PMID: 30944359 PMCID: PMC6447584 DOI: 10.1038/s41598-019-41822-w] [Citation(s) in RCA: 5] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/13/2018] [Accepted: 03/19/2019] [Indexed: 11/10/2022] Open
Abstract
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.
Collapse
Affiliation(s)
- P D Karampourniotis
- Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590, USA. .,Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590, USA.
| | - B K Szymanski
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590, USA.,Department of Computer Science, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590, USA.,Faculty of Computer Science and Management, Wroclaw University of Science and Technology, Wrocław, Poland
| | - G Korniss
- Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590, USA.,Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590, USA
| |
Collapse
|
6
|
Karczmarczyk A, Jankowski J, Wątróbski J. Multi-criteria decision support for planning and evaluation of performance of viral marketing campaigns in social networks. PLoS One 2018; 13:e0209372. [PMID: 30589859 PMCID: PMC6307867 DOI: 10.1371/journal.pone.0209372] [Citation(s) in RCA: 36] [Impact Index Per Article: 6.0] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/27/2018] [Accepted: 12/04/2018] [Indexed: 11/18/2022] Open
Abstract
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.
Collapse
Affiliation(s)
- Artur Karczmarczyk
- Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, ul. Żołnierska 49, 71-210 Szczecin, Poland
| | - Jarosław Jankowski
- Faculty of Computer Science and Information Technology, West Pomeranian University of Technology in Szczecin, ul. Żołnierska 49, 71-210 Szczecin, Poland
| | - Jarosław Wątróbski
- Faculty of Economics and Management, University of Szczecin, Mickiewicza 64, 71-101, Szczecin, Poland
| |
Collapse
|
7
|
Jankowski J, Waniek M, Alshamsi A, Bródka P, Michalski R. Strategic distribution of seeds to support diffusion in complex networks. PLoS One 2018; 13:e0205130. [PMID: 30325936 PMCID: PMC6191084 DOI: 10.1371/journal.pone.0205130] [Citation(s) in RCA: 7] [Impact Index Per Article: 1.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/07/2018] [Accepted: 09/17/2018] [Indexed: 12/03/2022] Open
Abstract
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.
Collapse
Affiliation(s)
- Jarosław Jankowski
- Department of Computer Science and Information Technology, West Pomeranian University of Technology, Szczecin, Poland
- * E-mail:
| | - Marcin Waniek
- Masdar Institute, Khalifa University of Science and Technology, Abu Dhabi, United Arab Emirates
| | - Aamena Alshamsi
- Masdar Institute, Khalifa University of Science and Technology, Abu Dhabi, United Arab Emirates
- The MIT Media Lab, Massachusetts Institute of Technology, Cambridge, MA, United States of America
| | - Piotr Bródka
- Department of Computer Science and Information Technology, West Pomeranian University of Technology, Szczecin, Poland
- Department of Computational Intelligence, Faculty of Computer Science and Management, Wrocław University of Science and Technology, Wrocław, Poland
| | - Radosław Michalski
- Department of Computer Science and Information Technology, West Pomeranian University of Technology, Szczecin, Poland
- Department of Computational Intelligence, Faculty of Computer Science and Management, Wrocław University of Science and Technology, Wrocław, Poland
| |
Collapse
|
8
|
Jankowski J, Szymanski BK, Kazienko P, Michalski R, Bródka P. Probing Limits of Information Spread with Sequential Seeding. Sci Rep 2018; 8:13996. [PMID: 30228338 PMCID: PMC6143613 DOI: 10.1038/s41598-018-32081-2] [Citation(s) in RCA: 14] [Impact Index Per Article: 2.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/12/2018] [Accepted: 08/28/2018] [Indexed: 11/22/2022] Open
Abstract
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.
Collapse
Affiliation(s)
- Jarosław Jankowski
- Faculty of Computer Science and Information Technology, West Pomeranian University of Technology, 70-310, Szczecin, Poland.
| | - Boleslaw K Szymanski
- Social and Cognitive Networks Academic Research Center and Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, 12180, USA.,Społeczna Akademia Nauk, Łódź, Poland
| | - Przemysław Kazienko
- Faculty of Computer Science and Management, Wroclaw University of Science and Technology, 50-370, Wroclaw, Poland
| | - Radosław Michalski
- Faculty of Computer Science and Management, Wroclaw University of Science and Technology, 50-370, Wroclaw, Poland
| | - Piotr Bródka
- Faculty of Computer Science and Management, Wroclaw University of Science and Technology, 50-370, Wroclaw, Poland
| |
Collapse
|
9
|
Paluch R, Lu X, Suchecki K, Szymański BK, Hołyst JA. Fast and accurate detection of spread source in large complex networks. Sci Rep 2018; 8:2508. [PMID: 29410504 PMCID: PMC5802743 DOI: 10.1038/s41598-018-20546-3] [Citation(s) in RCA: 38] [Impact Index Per Article: 6.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/23/2017] [Accepted: 01/15/2018] [Indexed: 11/29/2022] Open
Abstract
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.
Collapse
Affiliation(s)
- Robert Paluch
- Center of Excellence for Complex Systems Research, Faculty of Physics, Warsaw University of Technology, Koszykowa 75, 00662, Warsaw, Poland.
| | - Xiaoyan Lu
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590, USA
| | - Krzysztof Suchecki
- Center of Excellence for Complex Systems Research, Faculty of Physics, Warsaw University of Technology, Koszykowa 75, 00662, Warsaw, Poland
| | - Bolesław K Szymański
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8th Street, Troy, NY, 12180-3590, USA
- The ENGINE Centre, Wroclaw University of Science and Technology, Wyb. Wyspianskiego 27, 50-370, Wroclaw, Poland
| | - Janusz A Hołyst
- Center of Excellence for Complex Systems Research, Faculty of Physics, Warsaw University of Technology, Koszykowa 75, 00662, Warsaw, Poland
- ITMO University, 49 Kronverkskiy av., 197101, Saint Petersburg, Russia
| |
Collapse
|
10
|
Towards Sustainability in Viral Marketing with User Engaging Supporting Campaigns. SUSTAINABILITY 2017. [DOI: 10.3390/su10010015] [Citation(s) in RCA: 14] [Impact Index Per Article: 2.0] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
|
11
|
Dynamic Rankings for Seed Selection in Complex Networks: Balancing Costs and Coverage. ENTROPY 2017. [DOI: 10.3390/e19040170] [Citation(s) in RCA: 11] [Impact Index Per Article: 1.6] [Reference Citation Analysis] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/16/2022]
|