Social influencing and associated random walk models: Asymptotic consensus times on the complete graph

Solution to urn models of pairwise interaction with application to social, physical, and biological sciences

We investigate a family of urn models that correspond to one-dimensional random walks with quadratic transition probabilities that have highly diverse applications. Well-known instances of these two-urn models are the Ehrenfest model of molecular diffusion, the voter model of social influence, and the Moran model of population genetics. We also provide a generating function method for diagonalizing the corresponding transition matrix that is valid if and only if the underlying mean density satisfies a linear differential equation and express the eigenvector components as terms of ordinary hypergeometric functions. The nature of the models lead to a natural extension to interaction between agents in a general network topology. We analyze the dynamics on uncorrelated heterogeneous degree sequence networks and relate the convergence times to the moments of the degree sequences for various pairwise interaction mechanisms.

Effects of communication burstiness on consensus formation and tipping points in social dynamics

Current models for opinion dynamics typically utilize a Poisson process for speaker selection, making the waiting time between events exponentially distributed. Human interaction tends to be bursty though, having higher probabilities of either extremely short waiting times or long periods of silence. To quantify the burstiness effects on the dynamics of social models, we place in competition two groups exhibiting different speakers' waiting-time distributions. These competitions are implemented in the binary naming game and show that the relevant aspect of the waiting-time distribution is the density of the head rather than that of the tail. We show that even with identical mean waiting times, a group with a higher density of short waiting times is favored in competition over the other group. This effect remains in the presence of nodes holding a single opinion that never changes, as the fraction of such committed individuals necessary for achieving consensus decreases dramatically when they have a higher head density than the holders of the competing opinion. Finally, to quantify differences in burstiness, we introduce the expected number of small-time activations and use it to characterize the early-time regime of the system.

The impact of variable commitment in the Naming Game on consensus formation

The Naming Game has proven to be an important model of opinion dynamics in complex networks. It is significantly enriched by the introduction of nodes committed to a single opinion. The resulting model is still simple but captures core concepts of opinion dynamics in networks. This model limitation is rigid commitment which never changes. Here we study the effect that making commitment variable has on the dynamics of the system. Committed nodes are assigned a commitment strength, w, defining their willingness to lose (in waning), gain (for increasing) or both (in variable) commitment to an opinion. Such model has committed nodes that can stick to a single opinion for some time without losing their flexibility to change it in the long run. The traditional Naming Game corresponds to setting w at infinity. A change in commitment strength impacts the critical fraction of population necessary for a minority consensus. Increasing w lowers critical fraction for waning commitment but increases this fraction for increasing commitment. Further, we show that if different nodes have different values of w, higher standard deviation of w increases the critical fraction for waning commitment and decrease this fraction for increasing commitment.

Analysis of the high-dimensional naming game with committed minorities

The naming game has become an archetype for linguistic evolution and mathematical social behavioral analysis. In the model presented here, there are N individuals and K words. Our contribution is developing a robust method that handles the case when K=O(N). The initial condition plays a crucial role in the ordering of the system. We find that the system with high Shannon entropy has a higher consensus time and a lower critical fraction of zealots compared to low-entropy states. We also show that the critical number of committed agents decreases with the number of opinions and grows with the community size for each word. These results complement earlier conclusions that diversity of opinion is essential for evolution; without it, the system stagnates in the status quo [S. A. Marvel et al., Phys. Rev. Lett. 109, 118702 (2012)PRLTAO0031-900710.1103/PhysRevLett.109.118702]. In contrast, our results suggest that committed minorities can more easily conquer highly diverse systems, showing them to be inherently unstable.

Solution of the multistate voter model and application to strong neutrals in the naming game

We consider the voter model with M states initially in the system. Using generating functions, we pose the spectral problem for the Markov transition matrix and solve for all eigenvalues and eigenvectors exactly. With this solution, we can find all future probability probability distributions, the expected time for the system to condense from M states to M-1 states, the moments of consensus time, the expected local times, and the expected number of states over time. Furthermore, when the initial distribution is uniform, such as when M=N, we can find simplified expressions for these quantities. In particular, we show that the mean and variance of consensus time for M=N are 1/N(N-1)(2) and 1/3(π(2)-9)(N-1)(2), respectively. We verify these claims by simulation of the model on complete and Erdős-Rényi graphs and show that the results also hold on these sparse networks.

Committed activists and the reshaping of status-quo social consensus

The role of committed minorities in shaping public opinion has been recently addressed with the help of multiagent models. However, previous studies focused on homogeneous populations where zealots stand out only for their stubbornness. Here we consider the more general case in which individuals are characterized by different propensities to communicate. In particular, we correlate commitment with a higher tendency to push an opinion, acknowledging the fact that individuals with unwavering dedication to a cause are also more active in their attempts to promote their message. We show that these activists are not only more efficient in spreading their message but that their efforts require an order of magnitude fewer individuals than a randomly selected committed minority to bring the population over to a new consensus. Finally, we address the role of communities, showing that partisan divisions in the society can make it harder for committed individuals to flip the status-quo social consensus.

Solution of the voter model by spectral analysis

An exact spectral analysis of the Markov propagator for the voter model is presented for the complete graph and extended to the complete bipartite graph and uncorrelated random networks. Using a well-defined Martingale approximation in diffusion-dominated regions of phase space, which is almost everywhere for the voter model, this method is applied to compute analytically several key quantities such as exact expressions for the m time-step propagator of the voter model, all moments of consensus times, and the local times for each macrostate. This spectral method is motivated by a related method for solving the Ehrenfest urn problem and by formulating the voter model on the complete graph as an urn model. Comparisons of the analytical results from the spectral method and numerical results from Monte Carlo simulations are presented to validate the spectral method.

Evolutionary prisoner's dilemma game on graphs and social networks with external constraint

A game-theoretical model is constructed to capture the effect of external constraint on the evolution of cooperation. External constraint describes the case where individuals are forced to cooperate with a given probability in a society. Mathematical analyses are conducted via pair approximation and diffusion approximation methods. The results show that the condition for cooperation to be favored on graphs with constraint is b¯/c¯>k/A¯ (A¯=1+kp/(1-p)), where b¯ and c¯ represent the altruistic benefit and cost, respectively, k is the average degree of the graph and p is the probability of compulsory cooperation by external enforcement. Moreover, numerical simulations are also performed on a repeated game with three strategies, always defect (ALLD), tit-for-tat (TFT) and always cooperate (ALLC). These simulations demonstrate that a slight enforcement of ALLC can only promote cooperation when there is weak network reciprocity, while the catalyst effect of TFT on cooperation is verified. In addition, the interesting phenomenon of stable coexistence of the three strategies can be observed. Our model can represent evolutionary dynamics on a network structure which is disturbed by a specified external constraint.

Propensity and stickiness in the naming game: tipping fractions of minorities

Agent-based models of the binary naming game are generalized here to represent a family of models parameterized by the introduction of two continuous parameters. These parameters define varying listener-speaker interactions on the individual level with one parameter controlling the speaker and the other controlling the listener of each interaction. The major finding presented here is that the generalized naming game preserves the existence of critical thresholds for the size of committed minorities. Above such threshold, a committed minority causes a fast (in time logarithmic in size of the network) convergence to consensus, even when there are other parameters influencing the system. Below such threshold, reaching consensus requires time exponential in the size of the network. Moreover, the two introduced parameters cause bifurcations in the stabilities of the system's fixed points and may lead to changes in the system's consensus.

Opinion dynamics and influencing on random geometric graphs

We investigate the two-word Naming Game on two-dimensional random geometric graphs. Studying this model advances our understanding of the spatial distribution and propagation of opinions in social dynamics. A main feature of this model is the spontaneous emergence of spatial structures called opinion domains which are geographic regions with clear boundaries within which all individuals share the same opinion. We provide the mean-field equation for the underlying dynamics and discuss several properties of the equation such as the stationary solutions and two-time-scale separation. For the evolution of the opinion domains we find that the opinion domain boundary propagates at a speed proportional to its curvature. Finally we investigate the impact of committed agents on opinion domains and find the scaling of consensus time.

A model for cross-cultural reciprocal interactions through mass media

We investigate the problem of cross-cultural interactions through mass media in a model where two populations of social agents, each with its own internal dynamics, get information about each other through reciprocal global interactions. As the agent dynamics, we employ Axelrod's model for social influence. The global interaction fields correspond to the statistical mode of the states of the agents and represent mass media messages on the cultural trend originating in each population. Several phases are found in the collective behavior of either population depending on parameter values: two homogeneous phases, one having the state of the global field acting on that population, and the other consisting of a state different from that reached by the applied global field; and a disordered phase. In addition, the system displays nontrivial effects: (i) the emergence of a largest minority group of appreciable size sharing a state different from that of the applied global field; (ii) the appearance of localized ordered states for some values of parameters when the entire system is observed, consisting of one population in a homogeneous state and the other in a disordered state. This last situation can be considered as a social analogue to a chimera state arising in globally coupled populations of oscillators.

Analytic treatment of tipping points for social consensus in large random networks

We introduce a homogeneous pair approximation to the naming game (NG) model by deriving a six-dimensional Open Dynamics Engine (ODE) for the two-word naming game. Our ODE reveals the change in dynamical behavior of the naming game as a function of the average degree {k} of an uncorrelated network. This result is in good agreement with the numerical results. We also analyze the extended NG model that allows for presence of committed nodes and show that there is a shift of the tipping point for social consensus in sparse networks.

Accelerating consensus on coevolving networks: the effect of committed individuals

Social networks are not static but, rather, constantly evolve in time. One of the elements thought to drive the evolution of social network structure is homophily-the need for individuals to connect with others who are similar to them. In this paper, we study how the spread of a new opinion, idea, or behavior on such a homophily-driven social network is affected by the changing network structure. In particular, using simulations, we study a variant of the Axelrod model on a network with a homophily-driven rewiring rule imposed. First, we find that the presence of rewiring within the network, in general, impedes the reaching of consensus in opinion, as the time to reach consensus diverges exponentially with network size N. We then investigate whether the introduction of committed individuals who are rigid in their opinion on a particular issue can speed up the convergence to consensus on that issue. We demonstrate that as committed agents are added, beyond a critical value of the committed fraction, the consensus time growth becomes logarithmic in network size N. Furthermore, we show that slight changes in the interaction rule can produce strikingly different results in the scaling behavior of consensus time, T(c). However, the benefit gained by introducing committed agents is qualitatively preserved across all the interaction rules we consider.

Human-centric sensing

The first decade of the century witnessed a proliferation of devices with sensing and communication capabilities in the possession of the average individual. Examples range from camera phones and wireless global positioning system units to sensor-equipped, networked fitness devices and entertainment platforms (such as Wii). Social networking platforms emerged, such as Twitter, that allow sharing information in real time. The unprecedented deployment scale of such sensors and connectivity options ushers in an era of novel data-driven applications that rely on inputs collected by networks of humans or measured by sensors acting on their behalf. These applications will impact domains as diverse as health, transportation, energy, disaster recovery, intelligence and warfare. This paper surveys the important opportunities in human-centric sensing, identifies challenges brought about by such opportunities and describes emerging solutions to these challenges.

Introduction to Focus Issue: synchronization and cascading processes in complex networks

The study of collective dynamics in complex networks has emerged as a next frontier in the science of networks. This Focus Issue presents the latest developments on this exciting front, focusing in particular on synchronous and cascading dynamics, which are ubiquitous forms of network dynamics found in a wide range of physical, biological, social, and technological systems.