1
|
Abella D, San Miguel M, Ramasco JJ. Aging in binary-state models: The Threshold model for complex contagion. Phys Rev E 2023; 107:024101. [PMID: 36932591 DOI: 10.1103/physreve.107.024101] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 09/13/2022] [Accepted: 12/08/2022] [Indexed: 02/04/2023]
Abstract
We study the non-Markovian effects associated with aging for binary-state dynamics in complex networks. Aging is considered as the property of the agents to be less prone to change their state the longer they have been in the current state, which gives rise to heterogeneous activity patterns. In particular, we analyze aging in the Threshold model, which has been proposed to explain the process of adoption of new technologies. Our analytical approximations give a good description of extensive Monte Carlo simulations in Erdős-Rényi, random-regular and Barabási-Albert networks. While aging does not modify the cascade condition, it slows down the cascade dynamics towards the full-adoption state: the exponential increase of adopters in time from the original model is replaced by a stretched exponential or power law, depending on the aging mechanism. Under several approximations, we give analytical expressions for the cascade condition and for the exponents of the adopters' density growth laws. Beyond random networks, we also describe by Monte Carlo simulations the effects of aging for the Threshold model in a two-dimensional lattice.
Collapse
Affiliation(s)
- David Abella
- Instituto de Física Interdisciplinar y Sistemas Complejos IFISC (CSIC-UIB), Campus Universitat Illes Balears, 07122 Palma de Mallorca, Spain
| | - Maxi San Miguel
- Instituto de Física Interdisciplinar y Sistemas Complejos IFISC (CSIC-UIB), Campus Universitat Illes Balears, 07122 Palma de Mallorca, Spain
| | - José J Ramasco
- Instituto de Física Interdisciplinar y Sistemas Complejos IFISC (CSIC-UIB), Campus Universitat Illes Balears, 07122 Palma de Mallorca, Spain
| |
Collapse
|
2
|
Ruan Z, Yu B, Zhang X, Xuan Q. Role of lurkers in threshold-driven information spreading dynamics. Phys Rev E 2021; 104:034308. [PMID: 34654143 DOI: 10.1103/physreve.104.034308] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/23/2020] [Accepted: 09/09/2021] [Indexed: 11/07/2022]
Abstract
The threshold model as a classical paradigm for studying information spreading processes has been well studied. The main focuses are on how the underlying social network structure or the size of initial seeds can affect the cascading dynamics. However, the influence of node characteristics has been largely ignored. Here, inspired by empirical observations, we extend the threshold model by taking into account lurking nodes, who rarely interact with their neighbors. In particular, we consider two different scenarios: (i) Lurkers are absolutely silent and never interact with others and (ii) lurkers intermittently interact with their neighborhood with an activity rate p. In the first case, we demonstrate that lurkers may reduce the effective average degree of the underlying network, playing a dual role in spreading dynamics. In the latter case, we find that the stochastic dynamic behavior of lurkers could significantly promote the spread of information. Concretely, slightly raising the activity rate p of lurkers may result in a remarkable increase in the final cascade size. Further increasing p could make nodes become more stable on average, while it is still easy to observe global cascades due to the fluctuations of the effective degree of nodes.
Collapse
Affiliation(s)
- Zhongyuan Ruan
- Institute of Cyberspace Security, Zhejiang University of Technology, Hangzhou 310023, China
| | - Bin Yu
- Institute of Cyberspace Security, Zhejiang University of Technology, Hangzhou 310023, China
| | - Xiyun Zhang
- Department of Physics, Jinan University, Guangzhou, Guangdong 510632, China
| | - Qi Xuan
- Institute of Cyberspace Security, Zhejiang University of Technology, Hangzhou 310023, China
| |
Collapse
|
3
|
Peng H, Nematzadeh A, Romero DM, Ferrara E. Network modularity controls the speed of information diffusion. Phys Rev E 2020; 102:052316. [PMID: 33327110 DOI: 10.1103/physreve.102.052316] [Citation(s) in RCA: 4] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 08/12/2020] [Accepted: 11/08/2020] [Indexed: 11/07/2022]
Abstract
The rapid diffusion of information and the adoption of social behaviors are of critical importance in situations as diverse as collective actions, pandemic prevention, or advertising and marketing. Although the dynamics of large cascades have been extensively studied in various contexts, few have systematically examined the impact of network topology on the efficiency of information diffusion. Here, by employing the linear threshold model on networks with communities, we demonstrate that a prominent network feature-the modular structure-strongly affects the speed of information diffusion in complex contagion. Our simulations show that there always exists an optimal network modularity for the most efficient spreading process. Beyond this critical value, either a stronger or a weaker modular structure actually hinders the diffusion speed. These results are confirmed by an analytical approximation. We further demonstrate that the optimal modularity varies with both the seed size and the target cascade size and is ultimately dependent on the network under investigation. We underscore the importance of our findings in applications from marketing to epidemiology, from neuroscience to engineering, where the understanding of the structural design of complex systems focuses on the efficiency of information propagation.
Collapse
Affiliation(s)
- Hao Peng
- School of Information, University of Michigan, Ann Arbor, Michigan 48109, USA
| | | | - Daniel M Romero
- School of Information, University of Michigan, Ann Arbor, Michigan 48109, USA
| | - Emilio Ferrara
- Information Sciences Institute, University of Southern California, Los Angeles, California 90292, USA
| |
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
|
Mazumder O, Gavas R, Sinha A. Mediolateral stability index as a biomarker for Parkinson's disease progression: A graph connectivity based approach. ANNUAL INTERNATIONAL CONFERENCE OF THE IEEE ENGINEERING IN MEDICINE AND BIOLOGY SOCIETY. IEEE ENGINEERING IN MEDICINE AND BIOLOGY SOCIETY. ANNUAL INTERNATIONAL CONFERENCE 2020; 2019:5063-5067. [PMID: 31946997 DOI: 10.1109/embc.2019.8857224] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.5] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Indexed: 11/06/2022]
Abstract
This paper presents a novel metric to serve as a bio-marker for understanding and detecting progression of Parkinson's disease (PD). Proposed metric, termed as `Mediolateral Stability (MLS) index' has been derived from processing insole gait data using graph connectivity analysis. The proposed metric focuses on variability of mediolateral pressure in foot during gait progression. Vertical Ground Reaction Force (VGRF) and stride time information derived from a wearable insole for PD subjects as well as healthy controls are processed to create a connectivity graph. The insole contains eight pressure sensitive sensors for each foot and these sensors serve as the nodes of the connectivity graph. The proposed MLS index shows significant difference (p <; 0.05) in between control and PD groups and also in between progressive stages of PD, such as mild and moderate PD groups with p <; 0.05. Proposed graph connectivity based feature can act as a bio marker to correctly classify PD, identify early onset of PD and trace changes due to disease progression and can also provide information about dynamic pressure distribution during gait.
Collapse
|
6
|
Pond T, Magsarjav S, South T, Mitchell L, Bagrow JP. Complex Contagion Features without Social Reinforcement in a Model of Social Information Flow. ENTROPY 2020; 22:e22030265. [PMID: 33286039 PMCID: PMC7516717 DOI: 10.3390/e22030265] [Citation(s) in RCA: 7] [Impact Index Per Article: 1.8] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Download PDF] [Figures] [Subscribe] [Scholar Register] [Received: 02/01/2020] [Revised: 02/21/2020] [Accepted: 02/24/2020] [Indexed: 12/04/2022]
Abstract
Contagion models are a primary lens through which we understand the spread of information over social networks. However, simple contagion models cannot reproduce the complex features observed in real-world data, leading to research on more complicated complex contagion models. A noted feature of complex contagion is social reinforcement that individuals require multiple exposures to information before they begin to spread it themselves. Here we show that the quoter model, a model of the social flow of written information over a network, displays features of complex contagion, including the weakness of long ties and that increased density inhibits rather than promotes information flow. Interestingly, the quoter model exhibits these features despite having no explicit social reinforcement mechanism, unlike complex contagion models. Our results highlight the need to complement contagion models with an information-theoretic view of information spreading to better understand how network properties affect information flow and what are the most necessary ingredients when modeling social behavior.
Collapse
Affiliation(s)
- Tyson Pond
- Department of Mathematics & Statistics, University of Vermont, Burlington, VT 05405, USA;
| | - Saranzaya Magsarjav
- School of Mathematical Sciences, The University of Adelaide, Adelaide, SA 5005, Australia; (S.M.); (T.S.); (L.M.)
| | - Tobin South
- School of Mathematical Sciences, The University of Adelaide, Adelaide, SA 5005, Australia; (S.M.); (T.S.); (L.M.)
| | - Lewis Mitchell
- School of Mathematical Sciences, The University of Adelaide, Adelaide, SA 5005, Australia; (S.M.); (T.S.); (L.M.)
| | - James P. Bagrow
- Department of Mathematics & Statistics, University of Vermont, Burlington, VT 05405, USA;
- Correspondence:
| |
Collapse
|
7
|
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
|
8
|
Milli L, Rossetti G, Pedreschi D, Giannotti F. Active and passive diffusion processes in complex networks. APPLIED NETWORK SCIENCE 2018; 3:42. [PMID: 30460330 PMCID: PMC6214334 DOI: 10.1007/s41109-018-0100-5] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Key Words] [Grants] [Track Full Text] [Figures] [Subscribe] [Scholar Register] [Received: 03/09/2018] [Accepted: 09/11/2018] [Indexed: 06/09/2023]
Abstract
Ideas, information, viruses: all of them, with their mechanisms, spread over the complex social information, viruses: all tissues described by our interpersonal relations. Usually, to simulate and understand the unfolding of such complex phenomena are used general mathematical models; these models act agnostically from the object of which they simulate the diffusion, thus considering spreading of virus, ideas and innovations alike. Indeed, such degree of abstraction makes it easier to define a standard set of tools that can be applied to heterogeneous contexts; however, it can also lead to biased, incorrect, simulation outcomes. In this work we introduce the concepts of active and passive diffusion to discriminate the degree in which individuals choice affect the overall spreading of content over a social graph. Moving from the analysis of a well-known passive diffusion schema, the Threshold model (that can be used to model peer-pressure related processes), we introduce two novel approaches whose aim is to provide active and mixed schemas applicable in the context of innovations/ideas diffusion simulation. Our analysis, performed both in synthetic and real-world data, underline that the adoption of exclusively passive/active models leads to conflicting results, thus highlighting the need of mixed approaches to capture the real complexity of the simulated system better.
Collapse
Affiliation(s)
- Letizia Milli
- University of Pisa, Largo B. Pontecorvo, 2, Pisa, Italy
- KDD Lab. ISTI-CNR, via G. Moruzzi, 1, Pisa, Italy
| | - Giulio Rossetti
- University of Pisa, Largo B. Pontecorvo, 2, Pisa, Italy
- KDD Lab. ISTI-CNR, via G. Moruzzi, 1, Pisa, Italy
| | | | | |
Collapse
|
9
|
Min B, San Miguel M. Competition and dual users in complex contagion processes. Sci Rep 2018; 8:14580. [PMID: 30275519 PMCID: PMC6167365 DOI: 10.1038/s41598-018-32643-4] [Citation(s) in RCA: 4] [Impact Index Per Article: 0.7] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/30/2018] [Accepted: 09/04/2018] [Indexed: 11/13/2022] Open
Abstract
We study the competition of two spreading entities, for example innovations, in complex contagion processes in complex networks. We develop an analytical framework and examine the role of dual users, i.e. agents using both technologies. Searching for the spreading transition of the new innovation and the extinction transition of a preexisting one, we identify different phases depending on network mean degree, prevalence of preexisting technology, and thresholds of the contagion process. Competition with the preexisting technology effectively suppresses the spread of the new innovation, but it also allows for phases of coexistence. The existence of dual users largely modifies the transient dynamics creating new phases that promote the spread of a new innovation and extinction of a preexisting one. It enables the global spread of the new innovation even if the old one has the first-mover advantage.
Collapse
Affiliation(s)
- Byungjoon Min
- Department of Physics, Chungbuk National University, Cheongju, Chungbuk, 28644, Korea. .,IFISC, Instituto de Física Interdisciplinar y Sistemas Complejos (CSIC-UIB), Campus Universitat Illes Balears, E-07122, Palma de Mallorca, Spain.
| | - Maxi San Miguel
- IFISC, Instituto de Física Interdisciplinar y Sistemas Complejos (CSIC-UIB), Campus Universitat Illes Balears, E-07122, Palma de Mallorca, Spain.
| |
Collapse
|
10
|
Ruan Z, Wang J, Xuan Q, Fu C, Chen G. Information filtering by smart nodes in random networks. Phys Rev E 2018; 98:022308. [PMID: 30253588 DOI: 10.1103/physreve.98.022308] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/23/2018] [Indexed: 06/08/2023]
Abstract
Diffusion of information in social networks has drawn extensive attention from various scientific communities, with many contagion models proposed to explain related phenomena. In this paper, we present a simple contagion mechanism, in which a node will change its state immediately if it is exposed to the diffusive information. By considering two types of nodes (smart and normal) and two kinds of information (true and false), we study analytically and numerically how smart nodes influence the spreading of information, which leads to information filtering. We find that for randomly distributed smart nodes, the spreading dynamics over random networks with Poisson degree distribution and power-law degree distribution (with relatively small cutoffs) can both be described by the same approximate mean-field equation. Increasing the heterogeneity of the network may elicit more deviations, but not much. Moreover, we demonstrate that more smart nodes make the filtering effect on a random network better. Finally, we study the efficacy of different strategies of selecting smart nodes for information filtering.
Collapse
Affiliation(s)
- Zhongyuan Ruan
- College of Computer Science, Zhejiang University of Technology, Hangzhou 310023, China
| | - Jinbao Wang
- College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China
| | - Qi Xuan
- College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China
| | - Chenbo Fu
- College of Information Engineering, Zhejiang University of Technology, Hangzhou 310023, China
| | - Guanrong Chen
- Department of Electronic Engineering, City University of Hong Kong, Hongkong, China
| |
Collapse
|
11
|
Abstract
We introduce the threshold q-voter opinion dynamics where an agent, facing a binary choice, can change its mind when at least q_{0} among q neighbors share the opposite opinion. Otherwise, the agent can still change its mind with a certain probability ɛ. This threshold dynamics contemplates the possibility of persuasion by an influence group even when there is not full agreement among its members. In fact, individuals can follow their peers not only when there is unanimity (q_{0}=q) in the lobby group, as assumed in the q-voter model, but also, depending on the circumstances, when there is simple majority (q_{0}>q/2), Byzantine consensus (q_{0}>2q/3), or any minimal number q_{0} among q. This realistic threshold gives place to emerging collective states and phase transitions which are not observed in the standard q voter. The threshold q_{0}, together with the stochasticity introduced by ɛ, yields a phenomenology that mimics as particular cases the q voter with stochastic drivings such as nonconformity and independence. In particular, nonconsensus majority states are possible, as well as mixed phases. Continuous and discontinuous phase transitions can occur, but also transitions from fluctuating phases into absorbing states.
Collapse
Affiliation(s)
- Allan R Vieira
- Department of Physics, PUC-Rio, Rua Marquês de São Vicente, 225, 22451-900, Rio de Janeiro, Brazil
| | - Celia Anteneodo
- Department of Physics, PUC-Rio, Rua Marquês de São Vicente, 225, 22451-900, Rio de Janeiro, Brazil
- National Institute of Science and Technology for Complex Systems, Brazil
| |
Collapse
|
12
|
Xu XJ, Li JY, Fu X, Zhang LJ. Impact of directionality and correlation on contagion. Sci Rep 2018; 8:4814. [PMID: 29556044 PMCID: PMC5859107 DOI: 10.1038/s41598-018-22508-1] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/27/2017] [Accepted: 02/23/2018] [Indexed: 11/09/2022] Open
Abstract
The threshold model has been widely adopted for modelling contagion processes on social networks, where individuals are assumed to be in one of two states: inactive or active. This paper studies the model on directed networks where nodal inand out-degrees may be correlated. To understand how directionality and correlation affect the breakdown of the system, a theoretical framework based on generating function technology is developed. First, the effects of degree and threshold heterogeneities are identified. It is found that both heterogeneities always decrease systematic robustness. Then, the impact of the correlation between nodal in- and out-degrees is investigated. It turns out that the positive correlation increases the systematic robustness in a wide range of the average in-degree, while the negative correlation has an opposite effect. Finally, a comparison between undirected and directed networks shows that the presence of directionality and correlation always make the system more vulnerable.
Collapse
Affiliation(s)
- Xin-Jian Xu
- Department of Mathematics, Shanghai University, Shanghai, 200444, China.,Key Laboratory of Embedded System and Service Computing (Tongji University), Ministry of Education, Shanghai, 201804, China
| | - Jia-Yan Li
- Department of Mathematics, Shanghai University, Shanghai, 200444, China
| | - Xinchu Fu
- Department of Mathematics, Shanghai University, Shanghai, 200444, China
| | - Li-Jie Zhang
- Department of Physics, Shanghai University, Shanghai, 200444, China.
| |
Collapse
|
13
|
Abstract
Weighted networks capture the structure of complex systems where interaction strength is meaningful. This information is essential to a large number of processes, such as threshold dynamics, where link weights reflect the amount of influence that neighbours have in determining a node's behaviour. Despite describing numerous cascading phenomena, such as neural firing or social contagion, the modelling of threshold dynamics on weighted networks has been largely overlooked. We fill this gap by studying a dynamical threshold model over synthetic and real weighted networks with numerical and analytical tools. We show that the time of cascade emergence depends non-monotonously on weight heterogeneities, which accelerate or decelerate the dynamics, and lead to non-trivial parameter spaces for various networks and weight distributions. Our methodology applies to arbitrary binary state processes and link properties, and may prove instrumental in understanding the role of edge heterogeneities in various natural and social phenomena.
Collapse
|
14
|
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
|
15
|
Abstract
Online social networks have increasing influence on our society, they may play decisive roles in politics and can be crucial for the fate of companies. Such services compete with each other and some may even break down rapidly. Using social network datasets we show the main factors leading to such a dramatic collapse. At early stage mostly the loosely bound users disappear, later collective effects play the main role leading to cascading failures. We present a theory based on a generalised threshold model to explain the findings and show how the collapse time can be estimated in advance using the dynamics of the churning users. Our results shed light to possible mechanisms of instabilities in other competing social processes.
Collapse
Affiliation(s)
- János Török
- Center for Network Science, Central European University, Nádor u. 9, H-1051, Budapest, Hungary.
- Department of Theoretical Physics, Budapest University of Technology and Economics, H-1111, Budapest, Hungary.
| | - János Kertész
- Center for Network Science, Central European University, Nádor u. 9, H-1051, Budapest, Hungary
- Department of Theoretical Physics, Budapest University of Technology and Economics, H-1111, Budapest, Hungary
| |
Collapse
|
16
|
Abstract
We investigate opinion spreading by a threshold model in a situation in which the influence of people is heterogeneously distributed. We assume that there is a coupling between the influence of an individual (measured by the out-degree) and the threshold for accepting a new opinion or habit. We find that if the coupling is strongly positive, the final state of the system will be a mix of different opinions. Otherwise, it will converge to a consensus state. This phenomenon cannot simply be explained as a phase transition, but it is a combined effect of mechanisms and their relative dominance in different regions of parameter space.
Collapse
Affiliation(s)
- Eun Lee
- Department of Energy Science, Sungkyunkwan University, Suwon 16419, Korea
| | - Petter Holme
- Institute of Innovative Research, Tokyo Institute of Technology, Yokohama, Japan
| |
Collapse
|
17
|
Balancing Speed and Coverage by Sequential Seeding in Complex Networks. Sci Rep 2017; 7:891. [PMID: 28420880 PMCID: PMC5429852 DOI: 10.1038/s41598-017-00937-8] [Citation(s) in RCA: 35] [Impact Index Per Article: 5.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/14/2016] [Accepted: 03/20/2017] [Indexed: 11/23/2022] Open
Abstract
Information spreading in complex networks is often modeled as diffusing information with certain probability from nodes that possess it to their neighbors that do not. Information cascades are triggered when the activation of a set of initial nodes – seeds – results in diffusion to large number of nodes. Here, several novel approaches for seed initiation that replace the commonly used activation of all seeds at once with a sequence of initiation stages are introduced. Sequential strategies at later stages avoid seeding highly ranked nodes that are already activated by diffusion active between stages. The gain arises when a saved seed is allocated to a node difficult to reach via diffusion. Sequential seeding and a single stage approach are compared using various seed ranking methods and diffusion parameters on real complex networks. The experimental results indicate that, regardless of the seed ranking method used, sequential seeding strategies deliver better coverage than single stage seeding in about 90% of cases. Longer seeding sequences tend to activate more nodes but they also extend the duration of diffusion. Various variants of sequential seeding resolve the trade-off between the coverage and speed of diffusion differently.
Collapse
|
18
|
Assortative Mating: Encounter-Network Topology and the Evolution of Attractiveness. Sci Rep 2017; 7:45107. [PMID: 28345625 PMCID: PMC5366857 DOI: 10.1038/srep45107] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 11/15/2016] [Accepted: 02/17/2017] [Indexed: 11/09/2022] Open
Abstract
We model a social-encounter network where linked nodes match for reproduction in a manner depending probabilistically on each node's attractiveness. The developed model reveals that increasing either the network's mean degree or the "choosiness" exercised during pair formation increases the strength of positive assortative mating. That is, we note that attractiveness is correlated among mated nodes. Their total number also increases with mean degree and selectivity during pair formation. By iterating over the model's mapping of parents onto offspring across generations, we study the evolution of attractiveness. Selection mediated by exclusion from reproduction increases mean attractiveness, but is rapidly balanced by skew in the offspring distribution of highly attractive mated pairs.
Collapse
|
19
|
Wang P, Zhang LJ, Xu XJ, Xiao G. Heuristic Strategies for Persuader Selection in Contagions on Complex Networks. PLoS One 2017; 12:e0169771. [PMID: 28072847 PMCID: PMC5224984 DOI: 10.1371/journal.pone.0169771] [Citation(s) in RCA: 1] [Impact Index Per Article: 0.1] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/11/2016] [Accepted: 12/21/2016] [Indexed: 11/19/2022] Open
Abstract
Individual decision to accept a new idea or product is often driven by both self-adoption and others' persuasion, which has been simulated using a double threshold model [Huang et al., Scientific Reports 6, 23766 (2016)]. We extend the study to consider the case with limited persuasion. That is, a set of individuals is chosen from the population to be equipped with persuasion capabilities, who may succeed in persuading their friends to take the new entity when certain conditions are satisfied. Network node centrality is adopted to characterize each node's influence, based on which three heuristic strategies are applied to pick out persuaders. We compare these strategies for persuader selection on both homogeneous and heterogeneous networks. Two regimes of the underline networks are identified in which the system exhibits distinct behaviors: when networks are sufficiently sparse, selecting persuader nodes in descending order of node centrality achieves the best performance; when networks are sufficiently dense, however, selecting nodes with medium centralities to serve as the persuaders performs the best. Under respective optimal strategies for different types of networks, we further probe which centrality measure is most suitable for persuader selection. It turns out that for the first regime, degree centrality offers the best measure for picking out persuaders from homogeneous networks; while in heterogeneous networks, betweenness centrality takes its place. In the second regime, there is no significant difference caused by centrality measures in persuader selection for homogeneous network; while for heterogeneous networks, closeness centrality offers the best measure.
Collapse
Affiliation(s)
- Peng Wang
- College of Sciences, Shanghai University, Shanghai 200444, China
| | - Li-Jie Zhang
- College of Sciences, Shanghai University, Shanghai 200444, China
| | - Xin-Jian Xu
- College of Sciences, Shanghai University, Shanghai 200444, China
- Key Laboratory of Embedded System and Service Computing (Tongji University), Ministry of Education, Shanghai 201804, China
- * E-mail:
| | - Gaoxi Xiao
- School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore, Singapore
| |
Collapse
|
20
|
Abstract
The understanding and prediction of information diffusion processes on networks is a major challenge in network theory with many implications in social sciences. Many theoretical advances occurred due to stochastic spreading models. Nevertheless, these stochastic models overlooked the influence of rational decisions on the outcome of the process. For instance, different levels of trust in acquaintances do play a role in information spreading, and actors may change their spreading decisions during the information diffusion process accordingly. Here, we study an information-spreading model in which the decision to transmit or not is based on trust. We explore the interplay between the propagation of information and the trust dynamics happening on a two-layer multiplex network. Actors' trustable or untrustable states are defined as accumulated cooperation or defection behaviors, respectively, in a Prisoner's Dilemma setup, and they are controlled by a memory span. The propagation of information is abstracted as a threshold model on the information-spreading layer, where the threshold depends on the trustability of agents. The analysis of the model is performed using a tree approximation and validated on homogeneous and heterogeneous networks. The results show that the memory of previous actions has a significant effect on the spreading of information. For example, the less memory that is considered, the higher is the diffusion. Information is highly promoted by the emergence of trustable acquaintances. These results provide insight into the effect of plausible biases on spreading dynamics in a multilevel networked system.
Collapse
Affiliation(s)
- Hongrun Wu
- State Key Laboratory of Software Engineering, Wuhan University, 430072 Wuhan, China.,Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| | - Alex Arenas
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| | - Sergio Gómez
- Departament d'Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, 43007 Tarragona, Spain
| |
Collapse
|
21
|
Czaplicka A, Toral R, San Miguel M. Competition of simple and complex adoption on interdependent networks. Phys Rev E 2016; 94:062301. [PMID: 28085315 DOI: 10.1103/physreve.94.062301] [Citation(s) in RCA: 29] [Impact Index Per Article: 3.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/12/2016] [Indexed: 11/07/2022]
Abstract
We consider the competition of two mechanisms for adoption processes: a so-called complex threshold dynamics and a simple susceptible-infected-susceptible (SIS) model. Separately, these mechanisms lead, respectively, to first-order and continuous transitions between nonadoption and adoption phases. We consider two interconnected layers. While all nodes on the first layer follow the complex adoption process, all nodes on the second layer follow the simple adoption process. Coupling between the two adoption processes occurs as a result of the inclusion of some additional interconnections between layers. We find that the transition points and also the nature of the transitions are modified in the coupled dynamics. In the complex adoption layer, the critical threshold required for extension of adoption increases with interlayer connectivity whereas in the case of an isolated single network it would decrease with average connectivity. In addition, the transition can become continuous depending on the detailed interlayer and intralayer connectivities. In the SIS layer, any interlayer connectivity leads to the extension of the adopter phase. Besides, a new transition appears as a sudden drop of the fraction of adopters in the SIS layer. The main numerical findings are described by a mean-field type analytical approach appropriately developed for the threshold-SIS coupled system.
Collapse
Affiliation(s)
- Agnieszka Czaplicka
- Instituto de Física Interdisciplinar y Sistemas Complejos, IFISC (CSIC-UIB), Campus UIB, 07122 Palma de Mallorca, Spain
| | - Raul Toral
- Instituto de Física Interdisciplinar y Sistemas Complejos, IFISC (CSIC-UIB), Campus UIB, 07122 Palma de Mallorca, Spain
| | - Maxi San Miguel
- Instituto de Física Interdisciplinar y Sistemas Complejos, IFISC (CSIC-UIB), Campus UIB, 07122 Palma de Mallorca, Spain
| |
Collapse
|
22
|
Al-Garadi MA, Varathan KD, Ravana SD, Ahmed E, Chang V. Identifying the influential spreaders in multilayer interactions of online social networks. JOURNAL OF INTELLIGENT & FUZZY SYSTEMS 2016. [DOI: 10.3233/jifs-169112] [Citation(s) in RCA: 24] [Impact Index Per Article: 3.0] [Reference Citation Analysis] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/15/2022]
Affiliation(s)
- Mohammed Ali Al-Garadi
- Department of Information Systems, Faculty of Computer Science and Information Technology, University of Malaya, Kuala Lumpur, Malaysia
| | - Kasturi Dewi Varathan
- Department of Information Systems, Faculty of Computer Science and Information Technology, University of Malaya, Kuala Lumpur, Malaysia
| | - Sri Devi Ravana
- Department of Information Systems, Faculty of Computer Science and Information Technology, University of Malaya, Kuala Lumpur, Malaysia
| | - Ejaz Ahmed
- Centre for Mobile Cloud Computing Research, Faculty of Computer Science and Information Technology, University of Malaya, Kuala Lumpur, Malaysia
| | - Victor Chang
- International Business School Suzhou, Xi’an Jiaotong Liverpool University, Suzhou, China
| |
Collapse
|
23
|
Curato G, Lillo F. Optimal information diffusion in stochastic block models. Phys Rev E 2016; 94:032310. [PMID: 27739711 DOI: 10.1103/physreve.94.032310] [Citation(s) in RCA: 5] [Impact Index Per Article: 0.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/27/2016] [Indexed: 01/08/2023]
Abstract
We use the linear threshold model to study the diffusion of information on a network generated by the stochastic block model. We focus our analysis on a two-community structure where the initial set of informed nodes lies only in one of the two communities and we look for optimal network structures, i.e., those maximizing the asymptotic extent of the diffusion. We find that, constraining the mean degree and the fraction of initially informed nodes, the optimal structure can be assortative (modular), core-periphery, or even disassortative. We then look for minimal cost structures, i.e., those for which a minimal fraction of initially informed nodes is needed to trigger a global cascade. We find that the optimal networks are assortative but with a structure very close to a core-periphery graph, i.e., a very dense community linked to a much more sparsely connected periphery.
Collapse
Affiliation(s)
| | - Fabrizio Lillo
- Scuola Normale Superiore, Piazza dei Cavalieri 7, 56126 Pisa, Italy
| |
Collapse
|
24
|
Karsai M, Iñiguez G, Kikas R, Kaski K, Kertész J. Local cascades induced global contagion: How heterogeneous thresholds, exogenous effects, and unconcerned behaviour govern online adoption spreading. Sci Rep 2016; 6:27178. [PMID: 27272744 PMCID: PMC4895140 DOI: 10.1038/srep27178] [Citation(s) in RCA: 42] [Impact Index Per Article: 5.3] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 02/03/2016] [Accepted: 05/13/2016] [Indexed: 11/23/2022] Open
Abstract
Adoption of innovations, products or online services is commonly interpreted as a spreading process driven to large extent by social influence and conditioned by the needs and capacities of individuals. To model this process one usually introduces behavioural threshold mechanisms, which can give rise to the evolution of global cascades if the system satisfies a set of conditions. However, these models do not address temporal aspects of the emerging cascades, which in real systems may evolve through various pathways ranging from slow to rapid patterns. Here we fill this gap through the analysis and modelling of product adoption in the world’s largest voice over internet service, the social network of Skype. We provide empirical evidence about the heterogeneous distribution of fractional behavioural thresholds, which appears to be independent of the degree of adopting egos. We show that the structure of real-world adoption clusters is radically different from previous theoretical expectations, since vulnerable adoptions—induced by a single adopting neighbour—appear to be important only locally, while spontaneous adopters arriving at a constant rate and the involvement of unconcerned individuals govern the global emergence of social spreading.
Collapse
Affiliation(s)
- Márton Karsai
- Univ de Lyon, ENS de Lyon, INRIA, CNRS, UMR 5668, IXXI, 69364 Lyon, France
| | - Gerardo Iñiguez
- Department of Computer Science, School of Science, Aalto University, 00076, Finland.,Centro de Investigación y Docencia Económicas, CONACYT, 01210 México D.F., Mexico
| | - Riivo Kikas
- Institute of Computer Science, University of Tartu, 50409 Tartu, Estonia.,Software Technology and Applications Competence Center (STACC), 51003 Tartu, Estonia
| | - Kimmo Kaski
- Department of Computer Science, School of Science, Aalto University, 00076, Finland
| | - János Kertész
- Center for Network Science, Central European University, 1051 Budapest, Hungary.,Institute of Physics, Budapest University of Technology and Economics, 1111 Budapest, Hungary
| |
Collapse
|
25
|
Abstract
The threshold model has been widely adopted as a classic model for studying contagion processes on social networks. We consider asymmetric individual interactions in social networks and introduce a persuasion mechanism into the threshold model. Specifically, we study a combination of adoption and persuasion in cascading processes on complex networks. It is found that with the introduction of the persuasion mechanism, the system may become more vulnerable to global cascades, and the effects of persuasion tend to be more significant in heterogeneous networks than those in homogeneous networks: a comparison between heterogeneous and homogeneous networks shows that under weak persuasion, heterogeneous networks tend to be more robust against random shocks than homogeneous networks; whereas under strong persuasion, homogeneous networks are more stable. Finally, we study the effects of adoption and persuasion threshold heterogeneity on systemic stability. Though both heterogeneities give rise to global cascades, the adoption heterogeneity has an overwhelmingly stronger impact than the persuasion heterogeneity when the network connectivity is sufficiently dense.
Collapse
|
26
|
Ruan Z, Iñiguez G, Karsai M, Kertész J. Kinetics of Social Contagion. PHYSICAL REVIEW LETTERS 2015; 115:218702. [PMID: 26636878 DOI: 10.1103/physrevlett.115.218702] [Citation(s) in RCA: 36] [Impact Index Per Article: 4.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Subscribe] [Scholar Register] [Received: 05/30/2015] [Indexed: 05/25/2023]
Abstract
Diffusion of information, behavioral patterns or innovations follows diverse pathways depending on a number of conditions, including the structure of the underlying social network, the sensitivity to peer pressure and the influence of media. Here we study analytically and by simulations a general model that incorporates threshold mechanism capturing sensitivity to peer pressure, the effect of "immune" nodes who never adopt, and a perpetual flow of external information. While any constant, nonzero rate of dynamically introduced spontaneous adopters leads to global spreading, the kinetics by which the asymptotic state is approached shows rich behavior. In particular, we find that, as a function of the immune node density, there is a transition from fast to slow spreading governed by entirely different mechanisms. This transition happens below the percolation threshold of network fragmentation, and has its origin in the competition between cascading behavior induced by adopters and blocking due to immune nodes. This change is accompanied by a percolation transition of the induced clusters.
Collapse
Affiliation(s)
- Zhongyuan Ruan
- Center for Network Science, Central European University, H-1051 Budapest, Hungary
- Institute of Physics, Budapest University of Technology and Economics, H-1111 Budapest, Hungary
| | - Gerardo Iñiguez
- Centro de Investigación y Docencia Económicas, Consejo Nacional de Ciencia y Tecnología, 01210 México D.F., Mexico
- Department of Computer Science, Aalto University School of Science, FI-00076 AALTO, Finland
| | - Márton Karsai
- Laboratoire de l'Informatique du Parallélisme, INRIA-UMR 5668, IXXI, ENS de Lyon, 69364 Lyon, France
| | - János Kertész
- Center for Network Science, Central European University, H-1051 Budapest, Hungary
- Institute of Physics, Budapest University of Technology and Economics, H-1111 Budapest, Hungary
- Department of Computer Science, Aalto University School of Science, FI-00076 AALTO, Finland
| |
Collapse
|
27
|
Karampourniotis PD, Sreenivasan S, Szymanski BK, Korniss G. The Impact of Heterogeneous Thresholds on Social Contagion with Multiple Initiators. PLoS One 2015; 10:e0143020. [PMID: 26571486 PMCID: PMC4646465 DOI: 10.1371/journal.pone.0143020] [Citation(s) in RCA: 35] [Impact Index Per Article: 3.9] [Reference Citation Analysis] [Abstract] [MESH Headings] [Grants] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 05/04/2015] [Accepted: 10/29/2015] [Indexed: 12/02/2022] Open
Abstract
The threshold model is a simple but classic model of contagion spreading in complex social systems. To capture the complex nature of social influencing we investigate numerically and analytically the transition in the behavior of threshold-limited cascades in the presence of multiple initiators as the distribution of thresholds is varied between the two extreme cases of identical thresholds and a uniform distribution. We accomplish this by employing a truncated normal distribution of the nodes' thresholds and observe a non-monotonic change in the cascade size as we vary the standard deviation. Further, for a sufficiently large spread in the threshold distribution, the tipping-point behavior of the social influencing process disappears and is replaced by a smooth crossover governed by the size of initiator set. We demonstrate that for a given size of the initiator set, there is a specific variance of the threshold distribution for which an opinion spreads optimally. Furthermore, in the case of synthetic graphs we show that the spread asymptotically becomes independent of the system size, and that global cascades can arise just by the addition of a single node to the initiator set.
Collapse
Affiliation(s)
- Panagiotis D. Karampourniotis
- Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8 Street, Troy, NY, 12180-3590, United States of America
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8 Street, Troy, NY, 12180-3590, United States of America
| | - Sameet Sreenivasan
- Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8 Street, Troy, NY, 12180-3590, United States of America
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8 Street, Troy, NY, 12180-3590, United States of America
| | - Boleslaw K. Szymanski
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8 Street, Troy, NY, 12180-3590, United States of America
- Department of Computer Science, Rensselaer Polytechnic Institute, 110 8 Street, Troy, NY, 12180-3590, United States of America
- Społeczna Akademia Nauk, Łódź, Poland
| | - Gyorgy Korniss
- Department of Physics, Applied Physics, and Astronomy, Rensselaer Polytechnic Institute, 110 8 Street, Troy, NY, 12180-3590, United States of America
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, 110 8 Street, Troy, NY, 12180-3590, United States of America
| |
Collapse
|
28
|
Karsai M, Iñiguez G, Kaski K, Kertész J. Complex contagion process in spreading of online innovation. J R Soc Interface 2015; 11:20140694. [PMID: 25339685 DOI: 10.1098/rsif.2014.0694] [Citation(s) in RCA: 76] [Impact Index Per Article: 8.4] [Reference Citation Analysis] [Abstract] [Key Words] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/12/2022] Open
Abstract
Diffusion of innovation can be interpreted as a social spreading phenomenon governed by the impact of media and social interactions. Although these mechanisms have been identified by quantitative theories, their role and relative importance are not entirely understood, as empirical verification has so far been hindered by the lack of appropriate data. Here we analyse a dataset recording the spreading dynamics of the world's largest Voice over Internet Protocol service to empirically support the assumptions behind models of social contagion. We show that the rate of spontaneous service adoption is constant, the probability of adoption via social influence is linearly proportional to the fraction of adopting neighbours, and the rate of service termination is time-invariant and independent of the behaviour of peers. By implementing the detected diffusion mechanisms into a dynamical agent-based model, we are able to emulate the adoption dynamics of the service in several countries worldwide. This approach enables us to make medium-term predictions of service adoption and disclose dependencies between the dynamics of innovation spreading and the socio-economic development of a country.
Collapse
Affiliation(s)
- Márton Karsai
- Laboratory for the Modeling of Biological and Socio-technical Systems, Northeastern University, Boston, MA 02115, USA Department of Biomedical Engineering and Computational Science (BECS), Aalto University School of Science, 00076 Aalto, Finland Software Technology and Applications Competence Center (STACC), 51003 Tartu, Estonia Laboratoire de l'Informatique du Parallélisme, INRIA-UMR 5668, IXXI, ENS de Lyon, 69364 Lyon, France
| | - Gerardo Iñiguez
- Department of Biomedical Engineering and Computational Science (BECS), Aalto University School of Science, 00076 Aalto, Finland
| | - Kimmo Kaski
- Department of Biomedical Engineering and Computational Science (BECS), Aalto University School of Science, 00076 Aalto, Finland CABDyN Complexity Centre, Säid Business School, University of Oxford, Oxford OX1 1HP, UK
| | - János Kertész
- Department of Biomedical Engineering and Computational Science (BECS), Aalto University School of Science, 00076 Aalto, Finland Center for Network Science, Central European University, 1051 Budapest, Hungary Institute of Physics, Budapest University of Technology and Economics, 1111 Budapest, Hungary
| |
Collapse
|
29
|
Jia T, Spivey RF, Szymanski B, Korniss G. An Analysis of the Matching Hypothesis in Networks. PLoS One 2015; 10:e0129804. [PMID: 26083728 PMCID: PMC4470921 DOI: 10.1371/journal.pone.0129804] [Citation(s) in RCA: 7] [Impact Index Per Article: 0.8] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 03/16/2015] [Accepted: 05/13/2015] [Indexed: 11/19/2022] Open
Abstract
The matching hypothesis in social psychology claims that people are more likely to form a committed relationship with someone equally attractive. Previous works on stochastic models of human mate choice process indicate that patterns supporting the matching hypothesis could occur even when similarity is not the primary consideration in seeking partners. Yet, most if not all of these works concentrate on fully-connected systems. Here we extend the analysis to networks. Our results indicate that the correlation of the couple's attractiveness grows monotonically with the increased average degree and decreased degree diversity of the network. This correlation is lower in sparse networks than in fully-connected systems, because in the former less attractive individuals who find partners are likely to be coupled with ones who are more attractive than them. The chance of failing to be matched decreases exponentially with both the attractiveness and the degree. The matching hypothesis may not hold when the degree-attractiveness correlation is present, which can give rise to negative attractiveness correlation. Finally, we find that the ratio between the number of matched couples and the size of the maximum matching varies non-monotonically with the average degree of the network. Our results reveal the role of network topology in the process of human mate choice and bring insights into future investigations of different matching processes in networks.
Collapse
Affiliation(s)
- Tao Jia
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, Troy, NY, 12180 USA
- Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, 12180 USA
- Department of Physics, Applied Physics and Astronomy, Rensselaer Polytechnic Institute, Troy, NY, 12180 USA
- * E-mail:
| | - Robert F. Spivey
- Department of Physics, Applied Physics and Astronomy, Rensselaer Polytechnic Institute, Troy, NY, 12180 USA
- Department of Electrical and Computer Engineering, Duke University, Durham, NC, 27708 USA
| | - Boleslaw Szymanski
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, Troy, NY, 12180 USA
- Department of Computer Science, Rensselaer Polytechnic Institute, Troy, NY, 12180 USA
- Społeczna Akademia Nauk, Łódź, Poland
| | - Gyorgy Korniss
- Social Cognitive Networks Academic Research Center, Rensselaer Polytechnic Institute, Troy, NY, 12180 USA
- Department of Physics, Applied Physics and Astronomy, Rensselaer Polytechnic Institute, Troy, NY, 12180 USA
| |
Collapse
|
30
|
Zhang X, Adamatzky A, Chan FTS, Deng Y, Yang H, Yang XS, Tsompanas MAI, Sirakoulis GC, Mahadevan S. A biologically inspired network design model. Sci Rep 2015; 5:10794. [PMID: 26041508 PMCID: PMC4455180 DOI: 10.1038/srep10794] [Citation(s) in RCA: 23] [Impact Index Per Article: 2.6] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 10/23/2014] [Accepted: 04/28/2015] [Indexed: 11/09/2022] Open
Abstract
A network design problem is to select a subset of links in a transport network that satisfy passengers or cargo transportation demands while minimizing the overall costs of the transportation. We propose a mathematical model of the foraging behaviour of slime mould P. polycephalum to solve the network design problem and construct optimal transport networks. In our algorithm, a traffic flow between any two cities is estimated using a gravity model. The flow is imitated by the model of the slime mould. The algorithm model converges to a steady state, which represents a solution of the problem. We validate our approach on examples of major transport networks in Mexico and China. By comparing networks developed in our approach with the man-made highways, networks developed by the slime mould, and a cellular automata model inspired by slime mould, we demonstrate the flexibility and efficiency of our approach.
Collapse
Affiliation(s)
- Xiaoge Zhang
- 1] School of Computer and Information Science, Southwest University, Chongqing 400715, China [2] School of Engineering, Vanderbilt University, Nashiville, 37235, USA
| | - Andrew Adamatzky
- Unconventional Computing Center, University of the West of England, Bristol BS16 1QY, UK
| | - Felix T S Chan
- Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hung Hum, Kowloon, Hong Kong
| | - Yong Deng
- 1] School of Computer and Information Science, Southwest University, Chongqing 400715, China [2] School of Engineering, Vanderbilt University, Nashiville, 37235, USA
| | - Hai Yang
- Department of Civil and Environmental Engineering, The Hong Kong University of Science and Technology, Clear Water Bay, Kowloon, Hong Kong
| | - Xin-She Yang
- School of Science and Technology, Middlesex University, London NW4 4BT, UK
| | | | - Georgios Ch Sirakoulis
- Department of Electrical and Computer Engineering, Democritus University of Thrace, Xanthi 67100, Greece
| | | |
Collapse
|
31
|
Ramos M, Shao J, Reis SDS, Anteneodo C, Andrade JS, Havlin S, Makse HA. How does public opinion become extreme? Sci Rep 2015; 5:10032. [PMID: 25989484 PMCID: PMC4437297 DOI: 10.1038/srep10032] [Citation(s) in RCA: 61] [Impact Index Per Article: 6.8] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 12/02/2014] [Accepted: 03/10/2015] [Indexed: 11/09/2022] Open
Abstract
We investigate the emergence of extreme opinion trends in society by employing statistical physics modeling and analysis on polls that inquire about a wide range of issues such as religion, economics, politics, abortion, extramarital sex, books, movies, and electoral vote. The surveys lay out a clear indicator of the rise of extreme views. The precursor is a nonlinear relation between the fraction of individuals holding a certain extreme view and the fraction of individuals that includes also moderates, e.g., in politics, those who are "very conservative" versus "moderate to very conservative" ones. We propose an activation model of opinion dynamics with interaction rules based on the existence of individual "stubbornness" that mimics empirical observations. According to our modeling, the onset of nonlinearity can be associated to an abrupt bootstrap-percolation transition with cascades of extreme views through society. Therefore, it represents an early-warning signal to forecast the transition from moderate to extreme views. Moreover, by means of a phase diagram we can classify societies according to the percolative regime they belong to, in terms of critical fractions of extremists and people's ties.
Collapse
Affiliation(s)
- Marlon Ramos
- Levich Institute and Physics Department, City College of New York, New York, NY 10031, USA
- Departamento de Física, PUC-Rio, 22451-900, Rio de Janeiro, Brazil
- CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior, Ministério da Educação, 70040-020, Brasília, Distrito Federal, Brazil
| | - Jia Shao
- Bloomberg LP, New York, NY 10022, USA
| | - Saulo D. S. Reis
- Levich Institute and Physics Department, City College of New York, New York, NY 10031, USA
- Departamento de Física, Universidade Federal do Ceará, 60451-970 Fortaleza, Ceará, Brazil
| | - Celia Anteneodo
- Departamento de Física, PUC-Rio, 22451-900, Rio de Janeiro, Brazil
| | - José S. Andrade
- Departamento de Física, Universidade Federal do Ceará, 60451-970 Fortaleza, Ceará, Brazil
| | - Shlomo Havlin
- Minerva Center and Physics Department, Bar-Ilan University, Ramat Gan 52900, Israel
| | - Hernán A. Makse
- Levich Institute and Physics Department, City College of New York, New York, NY 10031, USA
- Departamento de Física, Universidade Federal do Ceará, 60451-970 Fortaleza, Ceará, Brazil
| |
Collapse
|
32
|
Bidirectional selection between two classes in complex social networks. Sci Rep 2014; 4:7577. [PMID: 25524835 PMCID: PMC4271259 DOI: 10.1038/srep07577] [Citation(s) in RCA: 10] [Impact Index Per Article: 1.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 06/20/2014] [Accepted: 12/02/2014] [Indexed: 11/19/2022] Open
Abstract
The bidirectional selection between two classes widely emerges in various social lives, such as commercial trading and mate choosing. Until now, the discussions on bidirectional selection in structured human society are quite limited. We demonstrated theoretically that the rate of successfully matching is affected greatly by individuals' neighborhoods in social networks, regardless of the type of networks. Furthermore, it is found that the high average degree of networks contributes to increasing rates of successful matches. The matching performance in different types of networks has been quantitatively investigated, revealing that the small-world networks reinforces the matching rate more than scale-free networks at given average degree. In addition, our analysis is consistent with the modeling result, which provides the theoretical understanding of underlying mechanisms of matching in complex networks.
Collapse
|
33
|
Wang LZ, Huang ZG, Rong ZH, Wang XF, Lai YC. Emergence, evolution and scaling of online social networks. PLoS One 2014; 9:e111013. [PMID: 25380140 PMCID: PMC4224376 DOI: 10.1371/journal.pone.0111013] [Citation(s) in RCA: 2] [Impact Index Per Article: 0.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 07/20/2014] [Accepted: 09/22/2014] [Indexed: 11/18/2022] Open
Abstract
Online social networks have become increasingly ubiquitous and understanding their structural, dynamical, and scaling properties not only is of fundamental interest but also has a broad range of applications. Such networks can be extremely dynamic, generated almost instantaneously by, for example, breaking-news items. We investigate a common class of online social networks, the user-user retweeting networks, by analyzing the empirical data collected from Sina Weibo (a massive twitter-like microblogging social network in China) with respect to the topic of the 2011 Japan earthquake. We uncover a number of algebraic scaling relations governing the growth and structure of the network and develop a probabilistic model that captures the basic dynamical features of the system. The model is capable of reproducing all the empirical results. Our analysis not only reveals the basic mechanisms underlying the dynamics of the retweeting networks, but also provides general insights into the control of information spreading on such networks.
Collapse
Affiliation(s)
- Le-Zhi Wang
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona, United States of America
| | - Zi-Gang Huang
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona, United States of America
- School of Physical Science and Technology, Lanzhou University, Lanzhou, China
- * E-mail: (ZGH); (YCL)
| | - Zhi-Hai Rong
- Web Sciences Center, School of Computer Science and Engineering, University of Electronic Science and Technology of China, Sichuan, China
| | - Xiao-Fan Wang
- Department of Automation, Shanghai Jiao Tong University, Shanghai, China
| | - Ying-Cheng Lai
- School of Electrical, Computer and Energy Engineering, Arizona State University, Tempe, Arizona, United States of America
- Department of Physics, Arizona State University, Tempe, Arizona, United States of America
- * E-mail: (ZGH); (YCL)
| |
Collapse
|
34
|
Nematzadeh A, Ferrara E, Flammini A, Ahn YY. Optimal network modularity for information diffusion. PHYSICAL REVIEW LETTERS 2014; 113:088701. [PMID: 25192129 DOI: 10.1103/physrevlett.113.088701] [Citation(s) in RCA: 92] [Impact Index Per Article: 9.2] [Reference Citation Analysis] [Abstract] [MESH Headings] [Track Full Text] [Subscribe] [Scholar Register] [Received: 01/08/2014] [Indexed: 06/03/2023]
Abstract
We investigate the impact of community structure on information diffusion with the linear threshold model. Our results demonstrate that modular structure may have counterintuitive effects on information diffusion when social reinforcement is present. We show that strong communities can facilitate global diffusion by enhancing local, intracommunity spreading. Using both analytic approaches and numerical simulations, we demonstrate the existence of an optimal network modularity, where global diffusion requires the minimal number of early adopters.
Collapse
Affiliation(s)
- Azadeh Nematzadeh
- School of Informatics and Computing, Indiana University, Bloomington, Indiana 47408, USA
| | - Emilio Ferrara
- School of Informatics and Computing, Indiana University, Bloomington, Indiana 47408, USA
| | - Alessandro Flammini
- School of Informatics and Computing, Indiana University, Bloomington, Indiana 47408, USA
| | - Yong-Yeol Ahn
- School of Informatics and Computing, Indiana University, Bloomington, Indiana 47408, USA
| |
Collapse
|
35
|
Chen DB, Xiao R, Zeng A. Predicting the evolution of spreading on complex networks. Sci Rep 2014; 4:6108. [PMID: 25130862 PMCID: PMC4135329 DOI: 10.1038/srep06108] [Citation(s) in RCA: 19] [Impact Index Per Article: 1.9] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 04/22/2014] [Accepted: 07/30/2014] [Indexed: 11/10/2022] Open
Abstract
Due to the wide applications, spreading processes on complex networks have been intensively studied. However, one of the most fundamental problems has not yet been well addressed: predicting the evolution of spreading based on a given snapshot of the propagation on networks. With this problem solved, one can accelerate or slow down the spreading in advance if the predicted propagation result is narrower or wider than expected. In this paper, we propose an iterative algorithm to estimate the infection probability of the spreading process and then apply it to a mean-field approach to predict the spreading coverage. The validation of the method is performed in both artificial and real networks. The results show that our method is accurate in both infection probability estimation and spreading coverage prediction.
Collapse
Affiliation(s)
- Duan-Bing Chen
- 1] Web Sciences Center, University of Electronic Science and Technology of China, Chengdu 611731, P.R. China [2] Department of Physics, University of Fribourg, Fribourg CH1700, Switzerland
| | - Rui Xiao
- Department of Physics, University of Fribourg, Fribourg CH1700, Switzerland
| | - An Zeng
- 1] Department of Physics, University of Fribourg, Fribourg CH1700, Switzerland [2] School of Systems Science, Beijing Normal University - Beijing 100875, P. R. China
| |
Collapse
|
36
|
Searching for superspreaders of information in real-world social media. Sci Rep 2014; 4:5547. [PMID: 24989148 PMCID: PMC4080224 DOI: 10.1038/srep05547] [Citation(s) in RCA: 220] [Impact Index Per Article: 22.0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Download PDF] [Figures] [Journal Information] [Subscribe] [Scholar Register] [Received: 01/08/2014] [Accepted: 06/04/2014] [Indexed: 11/28/2022] Open
Abstract
A number of predictors have been suggested to detect the most influential spreaders of information in online social media across various domains such as Twitter or Facebook. In particular, degree, PageRank, k-core and other centralities have been adopted to rank the spreading capability of users in information dissemination media. So far, validation of the proposed predictors has been done by simulating the spreading dynamics rather than following real information flow in social networks. Consequently, only model-dependent contradictory results have been achieved so far for the best predictor. Here, we address this issue directly. We search for influential spreaders by following the real spreading dynamics in a wide range of networks. We find that the widely-used degree and PageRank fail in ranking users' influence. We find that the best spreaders are consistently located in the k-core across dissimilar social platforms such as Twitter, Facebook, Livejournal and scientific publishing in the American Physical Society. Furthermore, when the complete global network structure is unavailable, we find that the sum of the nearest neighbors' degree is a reliable local proxy for user's influence. Our analysis provides practical instructions for optimal design of strategies for “viral” information dissemination in relevant applications.
Collapse
|