Fitting In and Breaking Up: A Nonlinear Version of Coevolving Voter Models
Yacoub H. Kureh Mason A. Porter
physics.soc-ph cond-mat.stat-mech cs.SI math.DS nlin.AO



APS/???-???








Department of Mathematics, University of California Los Angeles, Los Angeles, California 90095, USA






We investigate a nonlinear version of coevolving voter models, in which node states and network structure update as a coupled stochastic dynamical process. Most prior work on coevolving voter models has focused on linear update rules with fixed and homogeneous rewiring and adopting probabilities. By contrast, in our nonlinear version, the probability that a node rewires or adopts is a function of how well it “fits in” within its neighborhood. To explore this idea, we incorporate a parameter σ that represents the fraction of neighbors of an updating node that share its opinion state. In an update, with probability σ^q (for some nonlinearity parameter q), the updating node rewires; with complementary probability 1-σ^q, the updating node adopts a new opinion state. We study this mechanism using three rewiring schemes: after an updating node deletes a discordant edge, it then either (1) “rewires-to-random" by choosing a new neighbor in a random process; (2) “rewires-to-same" by choosing a new neighbor in a random process from nodes that share its state; or (3) “rewires-to-none" by not rewiring at all (akin to “unfriending” on social media). We compare our nonlinear coevolving model to several existing linear models, and we find in our model that initial network topology plays a larger role in the dynamics and the choice of rewiring mechanism plays a smaller role. A particularly interesting feature of our model is that, under certain conditions, the opinion state that is held initially by a minority of the nodes can effectively spread to almost every node in a network if the minority nodes view themselves as the majority. In light of this observation, we relate our results to recent work on the majority illusion in social networks.



Valid PACS appear here



 Fitting In and Breaking Up: A Nonlinear Version of Coevolving Voter Models
    Mason A. Porter
    December 30, 2023
===========================================================================













§ INTRODUCTION
 

The spread of opinions and the competition between different opinions is a vital aspect of societal discourse, and analysis of such phenomena has become increasingly prominent amidst the ubiquity of social media and intensifying political polarization <cit.>. Such topics have been studied using a variety of lenses from numerous disciplines <cit.>, including longstanding efforts to develop mathematical frameworks for modeling opinion dynamics by employing ideas from subjects such as statistical physics and nonlinear dynamics <cit.>. There has also been much cross-fertilization with research in the modeling of disease spreading <cit.>. For example, one can examine the “virality” of memes or seemingly contagious behaviors <cit.>. 

In developing mathematical frameworks for studying opinion dynamics, accounting for social network structure can significantly improve both the accuracy of mathematical models and the understanding of spreading processes <cit.>. 
For example, research on the severe acute respiratory syndrome (SARS) outbreaks by L. A. Meyers et al. illustrated the utility of accounting for social networks for assessing public-health strategies <cit.>. This stems from a network's influence on the properties of dynamical processes that take place on them <cit.>. Additionally, networks themselves are typically not time-independent, as they often evolve in response to a dynamical process and in turn influence that process <cit.>. For instance, in the spread of diseases, networks of interactions can change as a result of quarantines or different daily habits when somebody is ill. Similarly, in social media, individuals can choose to “follow” or “unfollow” other individuals (or other types of accounts) in response to posted content. The interplay of dynamics on networks and dynamics of networks [See <cit.> for reviews of research on time-dependent networks.] is a rapidly growing area of study in many disciplines <cit.>. Although much of the prior work on such “adaptive” (also known as “coevolving”) network models has focused on studying the complex behavior of simple models in abstract settings, there have also been efforts at incorporating further realism into the models <cit.> and at applying such models to study empirical data in situations — such as vote shares in historical United States elections <cit.> and the swarming dynamics of locusts <cit.> — that can involve notions of “opinions” and consensus. 

A popular family of adaptive network models are coevolving voter models (CVMs), in which node opinions (the node states) coevolve with network structure <cit.>. (These models are also sometimes called “adaptive voter models”.) Coevolving voter models combine the classical framework of voter models <cit.>, in which individuals update their opinions based on their neighbors' opinions, with an evolving network structure (in which individuals change their relationships with other individuals in response to their opinions <cit.>). A coevolving voter model consists of a network of individuals, two or more opinion states, and a rule (e.g., in the form of a stochastic process) for updating both the network and the states of its nodes or edges. We restrict our attention to a binary set of opinions, but one can also study models with more than two opinions <cit.> or with continuous opinions (e.g., using a bounded-confidence mechanism <cit.>). There is also an interesting coevolving opinion model that includes states both on the nodes and on the edges <cit.>.


One of the motivations for studying coevolving voter models is their fascinating dynamics, and scholars have analyzed them using approaches from subjects like dynamical systems, statistical physics, partial differential equations, and probability theory <cit.>. A particularly interesting aspect of the dynamics of CVMs is the apparent phase transition that can occur in “linear” CVMs. In this context, “linear” refers to the linearity of the rewiring probability function f_r(x) and adoption probability function f_a(x): A vertex with a fraction x of disagreeing neighbors has a probability f_r(x) = α x (for some parameter α) to rewire and a probability f_r(x) = (1-α) x to adopt. The parameter α is sometimes called the “rewiring rate”, and (1-α) is sometimes called the “adoption rate”. 
In some variants of linear CVMs (such as those in <cit.>), there appears to be a phase transition as one increases the adoption rate (and thus decreases the rewiring rate) from a regime of “rapid disintegration” to a regime of “prolonged persistence of the dynamics”. In the former regime, a network separates into components so quickly that the densities of the opinion states are unable to change significantly. 
In the latter regime, the system progresses slowly towards a steady state in which almost every node has the same opinion state. Basu and Sly recently presented a mathematically rigorous proof of the existence of phase transitions for two variants of linear CVMs on dense Erdős–Rényi (ER) networks (using the G(N,p) model with p = 1/2) <cit.>. However, it has not yet been proven that a phase transition occurs for sparse networks or other classes of dense networks. In appsec:Linear_CVM_Simulations, we review some of the existing computational results for linear CVMs on sparse ER networks and present computational results for these models on sparse networks that we construct from a stochastic block model (SBM). We demonstrate that, although these linear CVMs modify the structure of their associated network, their steady-state behavior appears to be insensitive to the examined initial network structures in a sense that we make precise in appsec:Linear_CVM_Simulations. For over a decade, linear CVMs have been a challenging, popular, and fruitful topic to study. From a practical perspective, however, nonlinearity appears to be a critical ingredient for coevolving voter models. For example, Couzin et al. <cit.> successfully predicted the existence of novel collective behaviors of schooling fish using nonlinear adaptive-network models.

A key contribution of the present paper is the introduction of a nonlinear coevolving voter model. In our setting, individuals seek to achieve social harmony (i.e., having the same opinion state as all of their neighbors) by rewiring and adopting at rates that depend on the states of their neighbors in a nonlinear way. Each node is in one of two states, and neighboring nodes “agree” if they are in the same state and “disagree” if they are in different states. We refer to edges between agreeing neighbors as concordant and edges between disagreeing neighbors as discordant. When updating, a node that is not in a local consensus (i.e., it disagrees with at least one neighbor) performs one of two actions with respect to a disagreeing neighbor: (1) it adopts the opinion of the disagreeing neighbor, causing other neighbors who had been in agreement to now disagree; or (2) it abandons the edge that connects it to the disagreeing neighbor and possibly forms a new connection. Similar to the CVM in <cit.>, a node makes a random choice between options (1) and (2). However, unlike in their model, the probability to choose a given option is not homogeneous; instead, it depends nonlinearly on the states of the node's neighbors. In our model, nodes conduct a local survey of all of their neighbors. Those who agree with a large fraction of their neighbors (i.e., those who “fit in”) are more likely to choose to remove the edge and possibly rewire, rather than adopting their disagreeing neighbor's opinion (which could place them in a local minority). Conversely, nodes that are in a local minority among their neighbors are more likely to adopt a neighbor's opinion (which could place them in a local majority), rather than remove the edge and possibly rewire. 


A node's local survey provides it with a sample view of a population. The sample is susceptible to bias, as the nodes survey only their neighbors in a network. Under certain conditions, the local surveys can accurately estimate global statistics, such as an opinion's popularity, which is equal to the fraction of nodes that hold that opinion. However, it is possible to configure systems such that the sampling bias leads nodes to construe globally popular opinions as locally unpopular, and vice versa. Under certain conditions, we find in our nonlinear CVM that when a node's local surveys are so distorted that it perceives the minority opinion to instead be the majority opinion, almost every node eventually adopts the opinion that was initially unpopular. Consequently, such distorted sampling in local surveys, which we relate to recent work by Lerman et al. <cit.> on what they called the “majority illusion”, has important implications for the dynamics of our nonlinear CVM.

In our paper, we examine three different rewiring schemes, which we illustrate in fig:rewiring_schemes. In [plain]sec:RTR, we explore a “rewire-to-random" (RTR) scheme, in which nodes sever connections (i.e., discordant edges) with disagreeing neighbors and replace them with new connections to nodes in a way that is agnostic to opinion states. In [plain]sec:RTS, we explore a “rewire-to-same" (RTS) scheme, in which nodes sever connections with disagreeing neighbors and replace them with new connections to nodes who share their opinion state. Finally, in [plain]sec:RTN, we explore a “rewire-to-none" (RTN) scheme, in which nodes sever connections with disagreeing neighbors without forming any new connections to other nodes. This third type of rewiring models behavior on social media in which individuals “unfriend" (or “unfollow”) someone after a disagreement <cit.>. A fascinating feature of linear CVMs is that the choice of rewiring scheme has a dramatic impact on their steady-state properties <cit.>. However, for our nonlinear CVM, the choice between the above rewiring schemes does not seem to have major qualitative effects on their steady-state behavior. 

In sec:Conclusion, we summarize our results and discuss possibilities for future work. We find that our nonlinear CVM has several features, such as a strong dependency on network structure, that distinguish it from previously-studied linear CVMs.
We give additional details, computations, and analysis in appendices. We provide details for our mean-field calculations in appsec:MFA_Sigma. In appsec:RTS_RTN_Algos, we give complete algorithms for our nonlinear CVM with rewire-to-same and rewire-to-none schemes. In appsec:Linear_CVM_Simulations, we examine a linear CVM with the RTR, RTS, and RTN rewiring schemes to facilitate comparisons with our nonlinear CVM. We simulate our nonlinear CVM for a wider range of parameter values in appsec:RTR_big_q_appendix.











§ REWIRE-TO-RANDOM
 





 §.§ Model


We now formally introduce our nonlinear coevolving voter model (CVM), starting with the version with a “rewire-to-random" scheme.  In all versions of our nonlinear CVM, we consider a space of binary opinion states O={A,B} and networks with finitely many nodes (i.e., vertices) and edges. The space of states for the system itself, which we will call “system states” to distinguish from the opinion states, is given by the space of triples (V,E,S), where V is the set of nodes (which represent individuals), N := |V| denotes the number of nodes, E is the set of edges (which represent undirected and unweighted ties between individuals), and S: V→ O is a function that records the opinion state (or simply the “state”) of each node. 

The systems that we study evolve between system states in a stochastic, memoryless fashion, so we can construe each such system as a first-order Markov chain. The set V of nodes remains fixed as a system evolves, but the set E of edges and the function S can update. When we refer to the edge set or the state function at a certain time, we use the notation E(t) and S^t to explicitly indicate time-dependence, but otherwise we suppress the notation for time. When evaluating the function S for a specific node, we use square brackets, so S[i] indicates the state of node i and S^t[i] indicates the state of node i at time t. We use E_D (and E_D(t) when specifying the time t explicitly) to denote the set 

    E_D = {(u,v)∈ E: S[u] ≠ S[v]}
 
of discordant edges, which are edges between disagreeing nodes, in E (and E(t)).
The closed neighborhood of node i is 

    Γ(i,E)={j∈ V: (i,j)∈ E}∪{i} .
 
It consists of the set of nodes that are adjacent to i, as well as node i itself. 

An important choice to make when defining the update rules for a voter model is the use of synchronous versus asynchronous updating. Synchronous updating entails updating all of the nodes in unison at each time step. By contrast, in asynchronous updating, one chooses a node (at random using a specified random process) at each step to interact with one of its neighbors, while the state of the rest of the system is constant. If the random process for choosing which node to update has a uniform distribution over the nodes, then after N steps in an asynchronous voter model, one updates each node once on average in an N-node network. This corresponds to one time step in synchronous voter models <cit.>. Therefore, when comparing asynchronous models that use a uniform random distribution to synchronous models, an asynchronous voter model evolves at a rate that is scaled by 1/N relative to synchronous models. The choice between synchronous and asynchronous updating is an important one, as it can have significant effects on the dynamics of voter models (beyond the time scaling), including differences in the number of absorbing states <cit.>. See <cit.> for discussions of the effects of synchronous versus asynchronous updating in voter models and in evolutionary games. In our analysis of coevolving voter models, we find that it is simpler to define update rules in an asynchronous manner [We are not aware of any studies of coevolving voter models with synchronous updating. One challenge in defining such a model is establishing a protocol for the situation when two adjacent nodes select each other for updating and both simultaneously attempt to rewire the same edge.]. 

After choosing to do asynchronous updating, one then chooses between “node-based” versus “edge-based” updating. In “node-based” voter models, in each step, one first selects a node i (at random following some distribution over the set of nodes) and then chooses one of its neighbors j (at random following some distribution over the set of neighbors of node i). If node i is isolated, the system does not change in that step. Another model choice is that ones needs to choose whether to update node i or node j. Under “direct node-based” rules, one updates the state of node i by copying the state of node j; under “reverse node-based” (which is also called “invasion process”) rules, the roles are switched, so one updates the state of node j by copying the state of node i <cit.>. The two “node-based” rules contrasts with “edge-based”  (i.e., “link-based”) rules. Under “edge-based” rules, in each step, one first selects an edge (i,j) at random following some distribution over the set of edges and then uniformly randomly selects one of the edge's incident nodes to update. That is, with equal probability, one updates node i by copying the state of node j or one updates node j by copying the state of node i. The seemingly minor choice between “direct node-based”, “reverse node-based”, and “edge-based” rules can have very substantial effects on the dynamics of a voter model, including convergence time and steady-state behavior <cit.>. One can observe an immediate difference between the three rules based on how they bias the relationship between the degrees of nodes i and j. In the “node-based” rules, we observe that expected degree of node j is larger than the expected degree of node i. By contrast, in the “edge-based” rules, it follows from symmetry that nodes i and j have identical expected degrees.

In our CVMs, we use asynchronous “edge-based” updates, and we perform one update for each elementary time step t={1, 2, …}. During an elementary time step, we select a discordant edge (i,j) uniformly at random from E_D. Alternatively, one can think of choosing the edges from E according to the probability mass function 

    f_E((i,j)) = 
    	1/|E_D| ,     (i,j) ∈ E_D , 
     0 ,     (i,j) ∉ E_D .

The only effect on the dynamics by choosing directly from E_D instead of E is that we can skip steps in which nodes i and j already share the same state, as such steps do not affect the state of the system. This leads to a logarithmic speedup in the time to reach a steady state (compare this to the coupon-collector problem <cit.>) and was called an “efficient version” of CVMs in <cit.>. We then select one of the two nodes (which we can take to be the one with the label i without loss of generality) at random with equal probabilities to be the primary node; we take the other node (j) to be the secondary node. After selecting the primary node i, it takes a local survey of it neighbors. We measure the result of the local survey by calculating σ_i := s_i/k_i, where s_i=|{j: (i,j)∈ E , S[i]=S[j]}| and k_i is the degree of node i. We also define s̅_̅i̅ := k_i-s_i, which counts the number of discordant edges that are incident to node i. Therefore, σ_i is the fraction of neighbors of node i that agree with i. For node i to be selected for updating, it needs to have at least one disagreeing neighbor (i.e., at least one discordant incident edge), so σ_i∈ [0,1). Note that σ_i is not defined for isolated nodes; however, because our CVM is edge-based, it is not possible to select an isolated node for updating.

Our nonlinear CVM has a parameter q that is akin to a parameter in nonlinear q-voter models <cit.>.  With probability σ_i^q, node i performs a rewiring action, in which it deletes its edge to the chosen secondary node and then randomly forms a new edge to a node that is not currently one of its neighbors. One needs to choose a probability distribution for this random process. In the first version of our CVM, we suppose that the primary node picks a node from a network uniformly at random. (The original node j from which i just deleted an edge is available for selection.) This type of rewiring scheme, which yields an edge between node i and any node (irrespective of its opinion state), is known as a “rewire-to-random” (RTR) strategy <cit.>. With complementary probability 1-σ_i^q, node i takes an adopting action, in which it adopts the opinion state of the chosen secondary node. We then repeat this process until there are no discordant edges in a network. If the system reaches a system state with no discordant edges at time t^*, then the dynamics reach a steady state, and we say that the system “terminates” at that system state, such that the system remains in that system state for all t≥ t^*. Both the rewiring and adoption actions conserve the number of edges, so |E(t)| is constant in time. 
Recently, Min and San Miguel <cit.> introduced a nonlinear CVM that also incorporates such a parameter q. Under their “direct node-based” rules, once one selects a node i, it is with probability (1-σ_i)^q that node i performs any update at all, and then a separate parameter p determines the relative probabilities of rewiring and adoption updates. This differs from our “edge-based” rules, in which once we select a node i to update, σ^q determines the relative probabilities of rewiring and adoption updates.

When q is a positive integer, one can interpret our rewiring process above as the primary node randomly selecting a panel of q of its neighbors (with repetition allowed). If any member of the panel is in a different state from the primary node, the latter undertakes an adopting action. Therefore, only when the panel and the primary node are all in the same state does the primary node perform a rewiring action. We summarize the rewiring process in Algorithm <ref> and give a schematic representation of the process during one elementary time step in fig:RTRschema. 

Because σ_i∈ [0,1) for nodes that can update, it follows that in the limit as q→∞, we recover a voter model with only adoption (and no rewiring). However, as q→ 0^+, we do not recover a model with only rewiring, because for some nodes i, it can be the case that σ_i = 0 if all of node i's incident edges are discordant; in that case, node i performs an adoption action for all q>0. In the present paper, we also perform simulations with q=0; for these simulations, we take 0^0 to be 1 to recover a pure rewiring model.

The nonlinear CVM that we just described is an absorbing Markov chain. The absorbing system states are those in which a network has no discordant edges. Such a situation occurs when each connected component of the network is in a consensus, but it does not necessarily require all components to achieve a consensus with the same opinion state. There has been significant prior work on noisy voter models <cit.>, and some recent work has studied noisy CVMs with random opinion-state mutations <cit.>. In these systems, in addition to the rewiring and adoption updates, there is also a mechanism that alters the opinion states of nodes according to some random process. Incorporating such noise yields a Markov chain that no longer is absorbing, because the system can exit the systems states with component-wise consensus through random creation of discordant edges. 
The resulting models are ergodic, so one can approximate the non-Markovian second-order (and higher-order) moment terms (see eq:momentdefs) using Markovian terms <cit.>.








A complete description of the system state is given by (V,E,S). Even for small networks, this amount of information is difficult to study, so we seek a coarse-grained description of our CVM's dynamics <cit.>. One type of summary is a count of “state-specified motifs”,
which are subgraphs H in which the nodes of H are in specified states. Relevant counts of state-specified motifs include

    
  * N_X(t) = |{i∈ V: S^t[i]=X}|, the number of nodes i at time t that are in state X∈ O={A,B} ;
        
  * N_X,Y(t) = |{(i,j)∈ V× V: (i,j)∈ E(t) , S^t[i]=X , S^t[j]=Y }|, the number of node pairs (i,j) at time t in which i and j are adjacent, node i is in state X ∈ O={A,B}, and node j is in state Y∈ O ;
    
  * N_X,Y,Z(t) = |{(i,j,k)∈ V× V× V: (i,j), (j,k)∈ E(t) , S^t[i]=X , S^t[j]=Y , S^t[k]=Z}|, the number of node triples (i,j,k) at time t in which i and j are adjacent, j and k are adjacent, node i is in state X∈ O={A,B}, node j is in state Y∈ O,
    and node k is in state Z∈ O .

 Note that 

    N_A(t)+N_B(t)    = N , 
    
    	N_AA(t)+N_AB(t)+N_BA(t)+N_BB(t)    = 2|E|  , 
    
    	N_AB(t) = N_BA(t)    = |E_D(t)| .


We refer to an instance of a triple among the N_XYZ triples as an XYZ-triple. One can also compute counts for state-specified motifs with more than three nodes, but we will not need them. Because the node set V is fixed, it is convenient to examine state densities N_X(t)/N, which give the fraction of nodes in a state X. We are also interested in the expected values (i.e., “moments”) of these quantities <cit.>. Three examples of moments are

    [X]     = [X](t) = ⟨ N_X(t)⟩  = 𝔼[N_X(t)]  , 
    
    	[XY]     = [XY](t) = ⟨ N_X,Y(t)⟩  = 𝔼[N_X,Y(t)] , 
    
    	[XYZ]     = [XYZ](t)  = ⟨ N_X,Y,Z(t)⟩  =𝔼[N_X,Y,Z(t)]  .



We compare our rewire-to-random model (see Algorithm <ref>) to the “rewire-to-random” (RTR) CVM that was described in <cit.>. Although there are many variants, we henceforth write “the linear RTR-CVM” when referring to this specific model. In the linear RTR-CVM, the system updates in a way that is similar to our nonlinear RTR-CVM, except that the probability for which action to take is given by a parameter α∈[0,1]. With probability α, a node performs a rewiring action; with probability 1-α, it adopts a neighbor's opinion. Therefore, in the linear RTR-CVM, until E_D = ∅, the count N_A(t) increases by 1 with probability 1-α2, decreases by 1 with probability 1-α2, and does not change with probability α during each elementary time step. If we take α=0 (entailing that the network topology never changes) and begin with a finite, connected network (V,E), then N_A(t) behaves equivalently to a simple, symmetric, one-dimensional (1D) random walk [In a 1D random walk, “simple” refers to the rule that, at each time step, the walker must move by either +1 or -1; and “symmetric” refers to these outcomes being equally probable. In a symmetric random walk with possible moves +1, -1, and 0, one requires only that the first two possibilities are equiprobable to each other.] (i.e., the two possibilities both have a probability of 1/2) <cit.> on the integers with boundary {0,N}. This implies that for any finite, connected network, the probability at time t that opinion state A eventually becomes the consensus opinion state is N_A(t)/N. For α>0, the quantity N_A(t) behaves like a symmetric, 1D random walk with step sizes +1 and -1 that each occur with equal probability 1-α2 and a no-move (“null”) step that occurs with probability α.

In the linear RTR-CVM, it is equivalent to take the view that one is choosing the type of action (rewire or adoption) before choosing which node of the selected edge is the primary one. This makes it clearer that even when the number of nodes in state A is not equal to the number of nodes in state B (i.e., when N_A(t) ≠ N_B(t)), a rewiring action causes the number N_AB(t) of discordant edges to decrease by 1/2 in expectation, regardless of the system state. By contrast, the effect of an adoption on the number N_AB(t) of discordant edges does depend on the system state, and it is possible for an adoption to increase N_AB(t) in expectation. As an extreme case, consider a star network S_k with a hub node in state A and k leaf nodes, and suppose that one node is in state B but all others are in state A. An updating step is guaranteed to select the network's single discordant edge; if an adoption occurs, N_AB(t) increases by k-3/2 in expectation. However, for a system on a regular network that satisfies the conditions

    σ_i    ≈ N_A(t)/N   for all nodes   i  in state   A , 
    σ_j    ≈ N_B(t)/N   for all nodes  j  in state   B ,

an adoption causes N_AB(t) to decreases by 1 in expectation. We use the term locally well-mixed for a system on any network that satisfies the conditions in eq:wellmixed, which entails that there are no correlations between the opinion states of nodes and the network topology. In a recent paper, Lee et al. <cit.> defined a related quantity called social perception bias that measures the ratio of a node's perception of the fraction of the minority to the true fraction of the minority, where a value of exactly 1 implies perfect perception of the frequency of the minority state in a network. 
Using this terminology, one can alternatively characterize a system as locally well-mixed using the condition that all nodes have a social perception bias that is close to 1. One can give a mathematically precise definition in the limit that the number N of nodes becomes infinite. Specifically, a system is locally well-mixed if almost all nodes have a social perception bias of 1-o(1) as N→∞.

In our nonlinear CVM, there is no longer a symmetry between the two nodes that are incident to the same discordant edge (i,j). The local survey σ_i of node i and the local survey σ_j of node j can differ, so the probabilities for which action (rewiring or adoption) occurs depend on which node is the primary one. That is, during an elementary time step that involves node i in state A and node j in state B (i.e., after one selects the discordant edge (i,j), but before selecting which node is the primary one), N_A(t) either (1) increases by 1 with probability (1-σ_j^q)2, corresponding to node j adopting node i's state; (2) decreases by 1 with probability (1-σ_i^q)2, corresponding to node i adopting node j's state; or (3) remains the same with probability σ_i^q+σ_j^q2, corresponding to either node i rewiring or node j rewiring. Therefore, although we can still view N_A(t) as a 1D random walk, it is no longer symmetric, because the step probabilities can differ from each other.

The effect of this asymmetry on N_AB(t) is more subtle. Consider a locally well-mixed system on a connected network. We also assume that one of the states, which we take to be B without loss of generality, is the majority (so N_B(t)>N_A(t)). During an elementary time step, suppose that we select the discordant edge (i,j) with node i in state A and node j in state B. The local surveys then satisfy σ_i<1/2<σ_j. When q=1, this implies that if i is the primary node, it is more likely to adopt than to rewire. If node i adopts state B, then N_AB(t) decreases by more than 1 in expectation, because more of i's neighbors are in state B than in state A. If node j is the primary node, it is more likely to rewire than to adopt. If node j rewires to a node that we choose uniformly at random, then N_AB(t) decreases by N_B(t)/N > 1/2 in expectation. Overall, we observe that the number N_AB(t) of discordant edges decreases more rapidly in our nonlinear CVM than it does in the linear RTR-CVM under locally well-mixed conditions. Our nonlinear CVM has rather different dynamics when it is locally well-mixed than when it is not locally well-mixed. In sec:RTR_SBM, we explore how to construct systems with correlations between nodes' opinion states and network topology, and we investigate how their dynamics differ from the situation in which the system is locally well-mixed. 





 §.§ Simulations on Erdos–Renyi Networks
  






We begin exploring our nonlinear RTR-CVM by simulating it on Erdős–Rényi (ER) G(N,p) networks. We seed each realization with an ER network with N=50,000 nodes, half of which begin in state A and the other half of which begin in state B. The edge probability p is 4/N-1, so the mean degree is ⟨ k ⟩≈ 4. Here and throughout our paper, when we simulate a voter model, we let the system evolve until it terminates in an absorbing steady state (i.e., until there are no discordant edges). This yields a “terminal” state. We focus on studying properties of terminal states, so we are interested in the t→∞ regime. For example, we examine the terminal state densities N_A(t)/N and N_B(t)/N and the terminal minority-state density min{N_A(t)/N,N_B(t)/N}.

In [plain]fig:RTR_ER_Terminal_Minority, we plot the terminal minority-state density from simulations for a range of values of q with discretization Δ q=0.02. When q<1, we observe that the minority-state density is approximately 0.5. This implies that the network is fragmented, in the sense that it is separated into multiple components that are disconnected from one another, such that all nodes of a component are in the same opinion state. This behavior is similar to the fragmentation observed in <cit.> for the linear RTR-CVM with sufficiently large rewiring rates. We interpret such fragmentation as individuals segregating into isolated communities, such that no pair of disagreeing individuals are neighbors of each other. This typically occurs when rewiring actions dominate the system, such that the state densities N_X(t)/N do not change significantly. As we consider progressively larger values of q between 1 and 3.5, we observe a smooth transition of an inverted `S' shape in the terminal minority-state density from approximately 0.5 to approximately 0.03. The small terminal minority-state densities for larger values of q suggest that adoption actions dominate the system, leading to a large change in the state densities. For expository convenience, we will say that “almost every” node ends up in state X if 90 % or more of the nodes are in state X when a system terminates by reaching an absorbing state. Initially, N_A(0)/N=N_B(0)/N=1/2. However, by the end of a simulation, one of the opinion states dominates, such that max{N_A(t)/N,N_B(t)/N}≈ 1. The other nearly vanishes, so min{N_A(t)/N,N_B(t)/N}≈ 0, as one can see in [plain]fig:RTR_ER_Terminal_Minority.

In fig:RTR_ER_Terminal_A, we plot the terminal density of state A from simulations for a range of values of q. In this plot, each of the small blue dots is the terminal value of N_A(t)/N for one of the 20 realizations that we simulate for each value of q. The crosses (×) give the mean of the terminal quantity of N_A(t)/N for each value of q. In the “branching” of the data points in this figure, we observe what appears to be a transition between a fragmentation regime (with no significant changes to state densities) and a regime with competition between the adoption and rewiring mechanisms. Because our initial state densities are N_A(0)/N=N_B(0)/N=1/2 in these simulations, it is equally likely for almost every node to terminate in state A as it is for almost every node to terminate in state B. We confirm this result in the means of terminal state-A densities that we plot in fig:RTR_ER_Terminal_A.

With respect to coarse qualitative behavior, both our nonlinear RTR-CVM and the linear RTR-CVM of <cit.> have a regime — when q<1 for our model, and for 1-α<0.2 for the linear RTR-CVM — in which rewiring dominates the system, as indicated by terminal minority-state densities that are close to the starting densities of 0.5. However, outside this regime, the two models differ significantly, as one can see by comparing fig:RTR_ER_Terminal_A with fig:LIN_RTR_ER_Term_A. The linear RTR-CVM appears to have a continuous (but non-smooth) phase transition from the rewiring-dominated regime to a regime in which rewiring and adoption are competitive <cit.>. In our nonlinear RTR-CVM, there seems to be a smooth transition between a regime in which rewiring dominates and a regime in which adoption dominates.





 §.§ Approximations


Although mean-field approximations have been unable thus far to produce precise quantitative results in previous work on CVMs, they have been useful for exploring some of their qualitative behavior <cit.>. Writing a mean-field approximation of our model will require developing a mean-field analog of σ_i. We consider a state-heterogeneous mean, so we separately average the local surveys of nodes in state A and average
the local surveys of nodes in state B. First, we consider the unweighted mean

    σ_A = ∑_i:S[i]=A,  k_i ≠ 0σ_i/∑_i:S[i]=A,  k_i ≠ 0 1 .

The unweighted mean σ_A is useful, because it has a simple interpretation and it is well-approximated [This approximation is exact for non-empty, degree-regular networks with at least one node in state A.] by N_AA(t)/N_AA(t)+N_AB(t). We will use the unweighted mean σ_A in sec:Illusion, but it is not well-suited as a mean-field approximation of our nonlinear RTR-CVM. In edge-based models such as ours and the linear RTR-CVM of <cit.>, nodes are not equally likely to be selected for an update. Instead, one is more likely to select nodes that have several neighbors of the opposing state, as they contribute more edges to the set E_D of discordant edges (from which we sample uniformly). Therefore, a suitable mean-field analog of σ should weight nodes based on their probability of being selected. The probability that we select a particular node i to be the primary node in an update is 

    1/2k_i-s_i/N_AB(t)=1/2s̅_̅i̅/N_AB(t) ,

where s̅_̅i̅ is the number of discordant edges that are incident to node i and the 1/2 accounts for the random choice between primary and secondary node. Therefore, our mean-field analogs of σ, which we denote by σ_X for X ∈{A,B}, are

    σ_A    = ∑_{i:S[i]=A ,  k_i ≠ 0}σ_i1/2k_i-s_i/N_AB(t)
       = 1/2N_AB(t)( N_AA(t)- ∑_{i:S[i]=A ,  k_i ≠ 0}s_i^2/k_i) , 
    σ_B    = 1/2N_AB(t)( N_BB(t)- ∑_{i:S[i]=B ,  k_i ≠ 0}s_i^2/k_i) .


The equation for the first moment, which we express in terms of state A, is

    d [A]/dt = ([AB]+[BA])(σ_A^q -σ_B^q) .

Equation (<ref>) arises from taking the difference of the “incoming rate”  (i.e., nodes that change their state to A) minus the “outgoing rate” (i.e., nodes that change their state from A) to determine the net rate of change of nodes in state A. Nodes in state B that are adjacent to a node in state A adopt state A at rate 1-σ_B^q. Nodes in state A that are adjacent to a node in state B adopt state B at rate 1-σ_A^q. Summing these rates over all nodes gives ([AB]+[BA])(1-σ_A^q). Similarly, the rate at which nodes in state B adopt state A is ([AB]+[BA])(1-σ_B^q).

[plain]eq:moment_equation indicates that the local surveys, which we capture in our mean-field approximation by σ_A and σ_B, have a global effect on the drift of opinion states, as they control the sign of d [A]/dt. (By contrast, d [A]/dt = 0 in the linear RTR-CVM of <cit.>.) This suggests that network structure plays a more prominent role in how [A] and [B] evolve in our nonlinear RTR-CVM than in the linear RTR-CVM. For example, consider a network with two communities, where one community is densely connected and consists of C_A nodes in state A and the other community is sparsely connected and consists of C_B nodes in state B. We suppose that the second community is larger than the first (i.e., C_B>C_A). We also suppose that the two communities are linked to each other (in a way that we will make more precise in sec:RTR_SBM). When we select a discordant edge (i,j) with node i in state A and node j in state B, the local surveys satisfy σ_i > σ_j. On average, at least initially, we expect that more nodes in state B convert to state A than the reverse. However, the values of σ_A and σ_B can change rapidly in non-obvious ways as the system evolves, potentially reversing the sign of d [A]/dt. Therefore, it is not guaranteed that such a two-community network will terminate in a state with a large fraction of nodes in state A. In fact, as we will see in sec:RTR_SBM, whether this occurs depends on the nonlinearity parameter q. 





 §.§ Simulations on Stochastic Block Models
 

To explore how community structure impacts the dynamics of our nonlinear RTR-CVM, we simulate it on a network that we seed with communities using a stochastic block model (SBM) <cit.>. We assign the N nodes into two communities, which we call community a and community b. Community a consists of cN nodes and community b consists of (1-c)N nodes, with c<1/2. That is, community b has more nodes than community a. In our discussion, we often refer to an SBM with two seeded communities as a “two-community structure”. We seed all nodes in community a with state A and all nodes in community b with state B. 





  §.§.§ Two-Community SBM
 

To create a two-community network in which the smaller community (i.e., community a) is denser than than the the larger community (i.e., community b), the edge-probability matrix 

    P = [ P_aa P_ab; P_ba P_bb ]

has probabilities that satisfy P_aa>P_bb>P_ab=P_ba. We initialize our simulations with networks with c=1/4, and we set the SBM parameters to be P_aa=12/cN-1, P_bb=4/(1-c)N-1 (so that N_AA(0)≈ N_BB(0)), and P_ab=1/N. In our simulations, we check that the expectations of σ_A and σ_B satisfy the inequality 𝔼[σ_A(0)]  > 𝔼[σ_B(0)]. See [plain]appsec:MFA_Sigma for details. Accordingly, we expect that, at least initially, the density N_A(t)/N of state A increases as the system evolves. In [plain]fig:RTR_SBM_Steps_Vs_A, we plot N_A(t)/N during the first 10,000 elementary time steps of simulations for nine different values of q. In this plot, we show the initial (and transient) dynamics, rather than the full temporal evolution of our simulation to termination. The plot confirms the initial increase in N_A(t)/N. However, in fig:RTR_SBM_TWO_COM_TERMINAL_A, we observe that, despite this initial increase, the terminal value of N_A(t)/N depends on the nonlinearity parameter q.





In [plain]fig:RTR_SBM_TWO_COM_TERMINAL_A, we plot the terminal state-A density from 20 simulations for each q.
For q ∈ [0,3.8), between approximately 25 % and 60 % of the nodes terminate in state A, implying that the network fragments into multiple components. We observe what appears to be a hybrid phase transition <cit.> at q^c ≈ 3.8, where there is a higher-order transition (i.e., at least second order) for q≤  q^c and a first-order transition q> q^c because the terminal density is nearly constant (wiyh N_A/N ≈ 1) for q ∈ (q^c,6.2). This implies that almost every node terminates in state A in all of our realizations, suggesting that rewiring dynamics are not fragmenting the system into multiple components.  For q ∈ (6.2,7), either almost every node terminates in state A or almost every node terminates in state B, and the latter occurs in progressively more realizations as we increase q. Although we do not show this in [plain]fig:RTR_SBM_TWO_COM_TERMINAL_A, the system has an additional regime for sufficiently large q. In this regime, the adoption action dominates and the system behaves like a voter model that does not coevolve with network structure (see appsec:RTR_big_q_appendix). In this situation, 
state A becomes the consensus opinion with probability N_A(0)/N=c=1/4.

In fig:LIN_RTR_SBM_TWO_COM_Term_A, we repeat our experiment using the linear RTR-CVM seeded with a two-community SBM network with the same parameter values. We observe that [plain]fig:LIN_RTR_SBM_TWO_COM_Term_A resembles the outcome of initializing the linear RTR-CVM with an ER network (see fig:LIN_RTR_ER_Term_A_1-3). This suggests that, with respect to terminal state densities, the linear RTR-CVM may be less sensitive than our nonlinear RTR-CVM to initial community structure in a network.

As we show in appsec:MFA_Sigma, we are able to numerically approximate the quantity 𝔼[σ_A(0)^q-σ_B(0)^q] for two-community SBM networks. We find that it depends on the parameters q, c, P_aa, P_ab, and P_ba. As the system evolves, however, it becomes more challenging to track 𝔼[σ_A(t)^q-σ_B(t)^q] over time t. Nevertheless, from fig:RTR_SBM_TWO_COM_TERMINAL_A, we know that the temporal evolution is affected by the value of the nonlinearity parameter q.









  §.§.§ Core–Periphery Structure
 

We now investigate the dynamics of our nonlinear RTR-CVM with σ_A(0) ≫σ_B(0) and N_A(0)≪ N_B(0) using a core–periphery configuration of the SBM <cit.>. Instead of having two communities, our initial network has a small, densely-connected core of nodes in state A and a large periphery of sparsely-connected nodes in state B. We label the core as block a and the periphery as block b.  In this core–periphery network, the SBM probabilities in eq:SBM_edge_prob_matrix satisfy P_aa>P_ab>P_bb. In this scenario, a node i's local survey σ_i differs from the true global densities. For core nodes, σ_i>1/2, so such nodes believe that their state (namely, state A) is the majority state, even though it is not. Conversely, for the peripheral nodes, σ_j<1/2, so such nodes believe that their state (i.e., state B) is the minority state, even though it is not. When q=1, if we select a core node as the primary node in an update, it is more likely to rewire than to adopt, at least initially. However, as most nodes are in state B initially, the core node is likely to rewire to another node in state B. If we select a peripheral node as the primary node for an update, it is more likely to adopt than to rewire. At least initially, such adoptions convert peripheral nodes from the majority state B to the minority state A. 

In our simulations of our nonlinear RTR-CVM on SBM networks with core–periphery structure, we take 3 N_A(0)=N_B(0), and we set the probabilities to be P_aa=20/N_A(0)-1, P_bb=1/N_B(0)-1, and P_ab=5/N. In fig:RTR_SBM_Terminal_A_CP, we plot the terminal density of state A for various values of q from simulations on networks with N=50,000 nodes. We observe a transition in the qualitative dynamics in the range q ∈ [4,4.5]. As we increase q from 0 to 4, there are progressively more nodes that terminate in state A before the network fragments, with approximately 90 % the nodes terminating in state A when q=4. For q∈ (4,4.5), the system appears to exhibit a phase transition that is similar to that of the ostensible hybrid phase transition of fig:RTR_SBM_Terminal_A_CP.

In this case, however, the hybrid transition is discontinuous. In appsec:RTR_big_q_appendix, we explore q∈[0,100]. For q∈(4.5,39), we find that almost every node terminates in state B (see fig:RTR_SBM_Terminal_A_CP_big_q). 





  §.§.§ Majority and Minority Illusions
 

Recent work by Lerman et al. <cit.> on the “majority illusion” in social networks examined the phenomenon of distorted local observations when a state that is globally rare in a network may be dramatically overrepresented in the local neighborhoods of many individuals. Using a model of threshold opinion dynamics, Lerman et al. illustrated that majority illusions can accelerate the spread of states that are initially rare. For our work with binary opinion states, we find it useful to distinguish between two different types of “illusions”. By a majority illusion, we mean the phenomenon of nodes in a minority state perceiving their state to be in the majority. Analogously, by a minority illusion, we mean the phenomenon of nodes in the majority state perceiving their state to be in a minority. For binary opinion states, the minority illusion implies that nodes in the majority state incorrectly perceive that the minority state is held by the majority of nodes.

In our nonlinear CVM, a node's local survey σ is based on a sample of the global population. In a locally well-mixed system (see eq:wellmixed), the sample leads to good estimates of the global densities N_A(t)/N and N_B(t)/N. However, when seeding the system as in sec:RTR_SBM_two_communities and sec:RTR_SBM_CP, the samples are biased initially. In [plain]fig:RTR_SBM_Terminal_Steps_Sigma_Proportions_TWO_COM and [plain]fig:RTR_SBM_Terminal_Steps_Sigma_Proportions_CP, we plot the mean of the local surveys σ_A (solid blue curves) and σ_B (solid red curves) versus elementary time steps and compare them to the true global densities, N_A(t)/N (dashed blue curves) and N_B(t)/N (dashed red curves), for simulations on systems that we seed with two-community structure and core–periphery structure, respectively. We calculate the unweighted means σ_A and σ_B from eq:arithemticmeansigma, so we are treating all local surveys equally. In mathematical language, assuming that state A is in the minority (i.e., N_A(t)/N < 1/2), the majority illusion occurs when σ_A>1/2. Analogously, assuming that state B is in the majority (i.e., N_B(t)/N > 1/2), the minority illusion occurs when σ_B<1/2. In Table <ref>, we summarize how we seed networks with different types of “illusions” using an SBM network with N_A(0)=cN and c<1/2.











In [plain]fig:RTR_SBM_Terminal_Steps_Sigma_Proportions_TWO_COM, we seed a network using the SBM two-community structure that we described in sec:RTR_SBM_two_communities. Initially, the larger community (which has 3/4 of the nodes) consists of nodes in state B, and the smaller community (which has the remaining 1/4 of the nodes) consists of nodes in state A. However, the local surveys of the nodes in the smaller community lead them to perceive state A as the majority state and thus state B as the minority. Similarly, the local surveys of the nodes in the larger community lead them to perceive state B as the majority state and thus state A as the minority. In other words, the larger community of nodes (which are in the majority state) correctly believe that their state is in the majority. However, the smaller community of nodes (which are in the minority state) experience a majority illusion, as they incorrectly believe that their state is in the majority. 





As we noted in fig:RTR_SBM_TWO_COM_TERMINAL_A, the effect on the terminal densities of initializing the system with a majority illusion depends on the value of the nonlinearity parameter q. For q=0, in which only rewiring occurs, the state densities do not change, but the system fragments, such that each node only has neighbors that share its state. Therefore, σ_A and σ_B increase towards 1, and the majority illusion of state A increases in severity. For q=4, the illusion becomes a reality, in the sense that N_A/N increases to match σ_A. The network ultimately reaches an absorbing state with most nodes in state A, but there are still small clusters of nodes in state B, so σ_B increases to 1 towards the end of the simulation (because we take the mean over only these nodes). For q=8 and q=12, the nodes “wise up” in the sense that σ_A decreases to match N_A/N. The network ultimately reaches an absorbing state with most nodes in state B, but there are still small clusters of nodes in state A that cause σ_A to increase to 1 towards the end of our simulations. 

In [plain]fig:RTR_SBM_Terminal_Steps_Sigma_Proportions_CP, we seed the system using the SBM core–periphery structure that we described in sec:RTR_SBM_CP. Initially, all peripheral nodes (which constitute 3/4 of the nodes) are in state B, and the core nodes (which constitute the remaining 1/4 of the nodes) are in state A. The local surveys of the peripheral nodes lead them to perceive state B as the minority state and thus state A as the majority. Similarly, the local surveys of the core nodes lead them to perceive state A as the majority state and thus state B as the minority. In other words, the core nodes (which are in the minority state) experience a majority illusion, incorrectly believing that their state is in the majority. Conversely, the peripheral nodes (which are in the majority state) experience a minority illusion, incorrectly believing that their state is in the minority. 





As we saw for two-community structure, the effect of the majority and minority illusions depends on the value of the nonlinearity parameter q in our networks with core–periphery structure. For q=0, in which only rewiring occurs, state densities do not change, but the network fragments, such that each node only has neighbors that share its state. Therefore, σ_A and σ_B increase towards 1, and the majority illusion for state A increases in severity, but the minority illusion for state B dissipates. For q=4, the majority illusion for state A becomes a reality, in the sense that N_A/N increases to match σ_A. The minority illusion for state B also becomes a reality, in the sense that N_B/N decreases to match σ_B initially. However, towards the end of a simulation, σ_B increases because there are still small clusters of nodes in state B and σ_B is a mean over only these nodes. For q=8 and q=12, the nodes wise up to both illusions, as σ_A decreases to match N_A/N and σ_B increases to match N_B/N. The system ultimately reaches an absorbing state with most nodes in state B, but there are still small clusters of nodes in state A that cause σ_A to increase to 1 towards the end of our simulations. 

These examples demonstrate that, under certain conditions, seeding our nonlinear RTR-CVM with illusions can lead to the spreading of initially rare states. For instance, when we seed the system with an SBM two-community network such that there is a majority illusion but not a minority illusion and take the value of the nonlinearity parameter to be q=4, almost every node adopts the initially rare state in all realizations of our simulations. However, under other conditions, seeding the system with illusions can also stifle the spread of initially rare states. For example, when we seed the system with core–periphery structure such that there is both a majority illusion and a minority illusion and take the value of the nonlinearity parameter to be q=8, the rare state vanishes almost entirely in all realizations of our simulations. This behavior contrasts strongly with what we observe in the linear RTR-CVM, in which the probability that an initially rare state spreads, conditioned on the event that a state does indeed spread, is equal to the initial fraction of nodes in the rare state. In other words, the adoption rate parameter α in the linear RTR-CVM affects whether some opinion state spreads to almost every node, but the initial state densities determine the probability of which state it will be. By contrast, the nonlinearity parameter q in our nonlinear RTR-CVM affects not only whether some opinion state spreads to almost every node but also the probabilities for which state it will be.  See appsec:Linear_CVM_Simulations for details.







§ REWIRE-TO-SAME







 §.§ Model


In this section, we explore our nonlinear CVM with a “rewire-to-same" (RTS) scheme. We give a formal description of it in Algorithm <ref> in appsec:RTSAlgo. The key difference from the RTR scheme is that when rewiring occurs in the RTS scheme, the primary node deletes its discordant edge to the secondary node and then forms an edge with a node that we choose uniformly at random from the set of nodes in the same state as the primary node. In appsec:Linear_CVM_Simulations_RTS, we compare our nonlinear RTS-CVM of Algorithm <ref> to the linear RTS-CVM of <cit.>. Based on previous work <cit.>, it seems that RTS schemes have been more difficult to analyze quantitatively than RTR schemes in linear CVMs.

To fully specify the RTS scheme, we start by examining a peculiarity of the RTS scheme: What happens when a rewiring action cannot take place, because the primary node is already adjacent to all nodes in its state (including the trivial case in which there are no other nodes in its state)? This situation is likely to arise if a system approaches consensus or if a network is densely connected (specifically, if the mean degree satisfies ⟨ k ⟩≥N/2) <cit.>. There are several possible rules to employ, and the choice of rule may affect both the outcome and the analysis. Possible specifications include the following: 

    
  (i) stipulate that there is no replacement edge;
    
  (ii) stipulate that we instead perform an RTR operation;
    
  (iii) stipulate that the recently deleted discordant edge reforms;
    
  (iv) stipulate that the recently deleted discordant edge reforms and that the primary node instead performs an adoption action; and
    
  (v) stipulate that we allow multi-edges, self-edges, or both.


Each of these choices either introduces a new mechanism, such as an edge deletion, or it changes the class of allowed networks. (Previously, we demanded that networks have neither self-edges nor multi-edges.) We choose to use option (i) of letting no replacement edge form, such that |E(t)| is no longer a conserved quantity. By contrast, recent work on CVMs on dense random graphs allowed the formation of multi-edges <cit.>. 






 §.§ Simulations






We first simulate our nonlinear RTS-CVM on ER networks. In fig:RTS_ER_Final_A, we observe similar qualitative behavior as we did in our nonlinear RTR-CVM (see fig:RTR_ER_Terminal_A). Specifically, there seems to be a continuous transition between fragmentation and consensus regimes. One difference is that the transition occurs at about q≈4.5 in the RTS version of the model. The similarity of these two models contrasts starkly with results for the linear CVM, whose behavior differs significantly under the two rewiring schemes (see fig:LIN_RTR_ER_Term_A and fig:lin_rts_terminal_A_ER). Prior research on linear CVMs suggests that the rewiring scheme affects linear CVMs significantly because of strong correlations between network structure and node states that arise from RTS actions, but not from RTR actions <cit.>. By contrast, the similarity of results between the RTR and RTS variants for our nonlinear CVM suggests that such correlations play a less prominent role in our model than they do in previously studied linear CVMs.

The sketch in fig:Dem_near_end represents what Demirel et al.  <cit.> reported as a “typical” configuration that is near fragmentation for a linear RTS-CVM. As the system evolves, nodes group into communities, which are connected to each other by only a few edges. Occasionally, there is an adoption that creates many discordant edges that are concentrated at one node. This leads to a disproportionately large number of ABA-triples that are concentrated on one node and constitutes a strong three-node correlation. However, in our nonlinear RTS-CVM, such situations occur much less frequently than they do in the linear RTS-CVM of <cit.>. In fact, in our nonlinear CVM, the more ABA-triples that a node in state A creates by adopting state B, the less likely it is to adopt state B. To illustrate this observation, suppose that node i is in state A and has at least two neighbors in state A. If we select node i for an update, it adopts state B with probability 1-σ_i^q, where σ_i is the fraction of nodes that are adjacent to node i and are also in state A. Consequently, the probability of node i creating ABA-triples by adopting state B decreases as the number of concordant edges that are incident to node i (i.e. the edges that would form part of the ABA-triples) increases.








In fig:RTS_ER_Sigma, we plot the evolution of unweighted means, σ_A and σ_B, of local surveys and compare them to global state densities (as in sec:Illusion). We observe fragmentation in our simulations with q=0, q=2, and q=4. Fragmentation causes the local surveys of nodes to become distorted, because nodes are in clusters and have no neighbors in a different state. This leads to a weak form of a majority illusion for nodes in each state: although roughly half of the nodes are in state A and roughly half are in state B, almost every node perceives its own state to be in the majority. In our simulations with q=6, we again initially observe a weak majority illusion for nodes in both states. As the system evolves, the density of state A decreases and σ_A decreases commensurately, but nodes in state A still exhibit a majority illusion. The system ultimately reaches an absorbing state with most nodes in state B, but there are still small clusters of nodes in state A that cause σ_A to increase to 1 towards the end of our simulations. 





We conclude this section on our nonlinear RTS-CVM by conducting simulations that we seed with (1) two-community structure and (2) core–periphery structure using SBM networks (see sec:RTR_SBM). In fig:RTS_SBM_Final_A_Two_Com, we observe that our nonlinear RTS-CVM initialized with two-community structure exhibits qualitatively similar long-time behavior as our nonlinear RTR-CVM initialized with the same two-community structure  (see fig:RTR_SBM_TWO_COM_TERMINAL_A). Nevertheless, simulations using these two rewiring schemes do exhibit quantitative differences, such as in the locations of the transitions between regimes with qualitatively different terminal statistics. In fig:RTS_SBM_Final_A_CP, we also observe qualitatively similar results for simulations seeded with core–periphery structure for both the RTS and RTR versions of our nonlinear CVM (see fig:RTR_SBM_Terminal_A_CP). 








§ REWIRE-TO-NONE
 





 §.§ Model


We now examine our nonlinear CVM with edge deletion, which we call “rewire-to-none” (RTN) to parallel the rewire-to-random and rewire-to-same terminology. In this RTN-CVM, adoption occurs with probability 1-σ_i^q, and edge deletion occurs with probability σ_i^q; there are no replacement edges. We give a precise description of this model in appsec:RTNAlgo. 

To the best of our knowledge, a RTN scheme has not been studied previously using linear CVMs, although a bounded-confidence opinion model with edge deletion (to model unfollowing on social media) was examined very recently in <cit.>. In appsec:LINRTNCVM, we investigate a linear CVM with our RTN scheme both analytically and computationally. There are many reasons to study an RTN mechanism in opinion models. In some sense, the edge-deletion mechanism is simpler than mechanisms that require additional parameters and specification of a rewiring rule [However, edge deletion can pose a mathematical challenge, because the number of edges and the mean degree are no longer constant <cit.>.]. Moreover, edge deletion may also more accurately model internet social dynamics than rewiring, because individuals perform actions such as “unfriending” or “unfollowing” without necessarily “friending” or “following” another account <cit.>. Edge deletion is also an important network mechanism in the structural evolution of social networks <cit.>.








 §.§ Simulations






We seed our nonlinear RTN-CVM with ER G(N,p) networks with N=25,000 nodes and an edge probability of p=4/N-1, and we initialize half of the nodes in state A and the other half of the nodes in state B. We plot the terminal state density of A in fig:RTN_ER_Terminal_A. When q=0, no adoption occurs, so state densities do not change before the network fragments. We find that with edge deletion (i.e., the RTN mechanism), fragmentation of a network into disconnected components can occur for a wide range of q values up to at least q=20. This is a larger range than what we observed for the RTR and RTS schemes for our nonlinear CVM. For the RTR scheme, we did not observation fragmentation for q⪆3; for the RTS scheme, we did not observe fragmentation for q⪆5.5.





We conduct simulations using two-community SBM networks (see sec:RTR_SBM_two_communities) to seed the system. We plot the terminal density of state A in fig:RTN_Two_Com_A; for q ∈ (0,8.5), we observe that the two communities separate from each other and that there are no signficant changes to the densities of opinion states. In contrast to the RTR scheme that we illustrated in fig:RTR_SBM_TWO_COM_TERMINAL_A and the RTS scheme in fig:RTS_SBM_Final_A_Two_Com, for the nonlinear RTN-CVM, we do not observe any values of q in which almost every node terminates in state A for every realization of a simulation. For q≈ 9.52, state A spreads to most nodes in most realizations, with a mean terminal density of approximately 0.75 over the 20 realizations. However, in some realizations for q≈ 9.52, almost every node terminates in state B. 

Finally, we simulate our nonlinear RTN-CVM model using SBM core–periphery networks (see sec:RTR_SBM_CP) to seed the system. In fig:RTN_SBM_cp_A, we observe that the RTN scheme produces terminal behavior that is qualitatively very similar to what we observed with the RTR (see fig:RTR_SBM_Terminal_A_CP) and RTS (see fig:RTS_SBM_Final_A_CP) schemes. 










§ CONCLUSIONS AND DISCUSSION
 

We explored a novel nonlinear coevolving voter model in which nodes take local information into consideration for their update actions, and we examined variants of our model with three different rewiring schemes: rewire-to-same, rewire-to-random, and rewire-to-none (i.e., “unfriending”). In our nonlinear CVM, updates are edge-based and occur asynchronously. An updating node surveys its neighbor and records the fraction σ that share its state. With probability σ^q, for a nonlinearity parameter q, the node rewires its discordant connection; otherwise, with complementary probability 1 - σ^q, the node adopts a new state. 

By conducting extensive numerical simulations, we observed that our nonlinear CVM exhibits qualitatively similar characteristics as the linear CVM of <cit.> with respect to terminal state densities when both models are initialized on ER networks with equal state densities N_A(0)/N=N_B(0)/N=1/2. For example, both types of models possess a regime with rapid fragmentation into communities of different opinion states and a regime in which the system reaches a consensus. However, when we seed our nonlinear CVM with more complicated network structures, such as ones with community structure or core–periphery structure, we observed striking differences between our nonlinear CVM and the aforementioned linear CVM. In these scenarios, when the nodes have distorted views of local densities — such that they believe that they are in the majority or minority when the opposite is true — the value of the nonlinearity parameter q has a major effect on terminal state densities. For certain values of q and initial network topologies, the initially minority state consistently became the consensus in our simulations; for other values of q, the initially majority state consistently became the consensus. Although further analysis is necessary (especially of finite-size effects), our work suggests that on certain networks, our nonlinear CVM exhibits a rich assortment of phase transitions. The impact of initial network topology on terminal state densities distinguishes our nonlinear CVM from the linear CVM of <cit.>. We also demonstrated that unlike the linear CVM of <cit.>, which is very sensitive to the choice of rewiring mechanism, our nonlinear CVM yields qualitatively similar behavior with both the RTR and RTS mechanisms.

Our nonlinear CVM also exhibits fascinating manifestations of both majority and minority illusions. For example, we observed that majority illusions can arise as a system evolves, and we also found that such illusions can resolve in different ways (e.g., by becoming true or by nodes wising up) for different values of the nonlinearity parameter q.

Our investigation of our nonlinear CVM raises several interesting questions. For example, we noted in sec:RTS and sec:RTN that the differences in model behavior from rewiring schemes in our nonlinear CVM are far less pronounced than they are in the examined linear CVM, and it is desirable to develop a mechanistic understanding of this qualitative difference between these families of models. It will also be interesting to develop precise conditions that determine when majority and minority illusions arise in our nonlinear CVM. Such illusions can either accelerate or stifle the spread of rare states, so it is important to develop an understanding of the mechanisms that lead to these effects. To examine these ideas further, it will be interesting to explore the dynamics of our models on a larger variety of networks, such as those that were developed recently by Stewart et al.  <cit.>. It is also desirable to extend tools for approximating the dynamics of linear CVMs (such as approximate master equations <cit.> and pair approximations <cit.>) to nonlinear CVMs.

There are also many fascinating ways to extend our nonlinear CVM. We anticipate that it will be particularly interesting to incorporate ideas from recent efforts that have examined the effects of noise (e.g., random state mutations) <cit.>, hipsters (in the form of nodes that try to be in a minority) <cit.>, and zealots (in the form of nodes that do not change states) <cit.>. Another worthwhile direction is to study adaptive opinion models with continuous opinions (e.g., using a bounded-confidence mechanism) <cit.>. 

Opinions and social networks are coupled to each other intimately in a complex way. Developing and refining models for coevolving opinions and social networks can help improve understanding of not only their relationships with each other but also their impact on political and social polarization, echo chambers, and other social phenomena.








§ ACKNOWLEDGEMENTS


We thank Andrea Baronchelli, Heather Zinn Brooks, Michelle Feng, James Gleeson, Thilo Gross, Istvan Kiss, Yi Ming Lai, Michael Lindstrom, Joel Miller, William Oakley, Alice Schwarze, Samuel Scarpino, and Bill Shi for helpful discussions and comments. We also thank two anonymous referees for helpful comments. YHK was supported by MURI N00014-17-S-F006. YHK and MAP acknowledge support from the National Science Foundation (grant number 1922952) through the Algorithms for Threat Detection (ATD) program.

















§  MEAN-FIELD APPROXIMATION FOR LOCAL SURVEYS



figuresection

In sec:approx_rtr, we explored a mean-field approximation of our nonlinear CVM with an RTR scheme. 
This necessitated finding a suitable mean-field analog of the local surveys σ_i. We considered a state-heterogeneous approximation, in which we separately average over nodes in state A and state B. Denoting these approximations as σ_A and σ_B, we found in eq:sigma_equation_1 that

    σ_A = 1/2N_AB( N_AA- ∑_i:S[i]=A,  k_i ≠ 0s_i^2/k_i)

and

    σ_B=1/2N_AB( N_BB- ∑_i:S[i]=B,  k_i ≠ 0s_i^2/k_i) .

Equivalently, we can write

    σ_A=∑_i:S[i]=A,  s̅_̅i̅≠ 0s_is̅_̅i̅(s_i+s̅_̅i̅)∑_j:S[j]=As̅_̅j̅

and 

    σ_B=∑_i:S[i]=B, s̅_̅i̅≠ 0s_is̅_̅i̅(s_i+s̅_̅i̅)∑_j:S[j]=Bs̅_̅j̅ .


We seek to compute 𝔼[σ_A(0)] for systems that we seed with two-community SBM networks. (If we take all edge probabilities in the SBM to be equal, we obtain ER networks.) We calculate

    𝔼[σ_A(0)]     = 𝔼[∑_i:S[i]=A, s̅_̅i̅≠ 0s_is̅_̅i̅(s_i+s̅_̅i̅)∑_j:S[j]=As̅_̅j̅] 
        = ∑_i:S[i]=A, s̅_̅i̅≠ 0𝔼[ s_is̅_̅i̅(s_i+s̅_̅i̅)∑_j:S[j]=As̅_̅j̅] 
       ≈(N_A(0) (1-exp(P_abN_B(0)))) 
           ×𝔼.[ s_is̅_̅i̅(s_i+s̅_̅i̅)∑_j:S[j]=As̅_̅j̅|s̅_̅i̅ > 0] 
        = (N_A(0) (1-exp(P_abN_B(0)))) 
           ×𝔼.[ s_is̅_̅i̅(s_i+s̅_̅i̅)(s̅_̅i̅+∑_j:S[j]=A,  j≠ is̅_̅j̅)|s̅_̅i̅ > 0] .

The quantity s_i is the random number of neighbors of node i that have the same opinion as i;
it is distributed binomially with parameters n=N_A(0)-1 and p=P_aa. The quantity s̅_̅i̅ is the random number of neighbors of node i that have a different opinion from i; it is distributed binomially with parameters n=N_B(0) and p=P_ab. 
There are N_A(0) nodes in state A; with probability (1-(1-P_ab)^N_B(0)), each such node has at least one discordant edge. In the limit N →∞, there are (N_A(0) [1-exp(P_abN_B(0)]) nodes in state A with at least one discordant neighbor. We use this expression as a large-N approximation in the third line of Eq. <ref>; in this line, we replace summing over nodes that are in state A and are incident to at least one discordant edge by multiplying by the expected number of such nodes.

Edges in our SBM networks are independent of each other, so s_i, s̅_̅i̅, and s̅_̅j̅ are all independent random variables. For convenience, we define the notation z := ∑_j:S[j]=A,  j≠ is̅_̅j̅. The sum of independent and identically distributed
binomial random variables is another binomial random variable, so z is distributed binomially with parameter values n=(N_A(0)-1)N_B(0) and p=P_ab. Using the law of the unconscious statistician, we obtain

    E[. s_is̅_̅i̅(s_i+s̅_̅i̅)(s̅_̅i̅+z)|s̅_̅i̅ > 0]  
       =∑_t_i, t̅_̅i̅≥ 1,  t(t_it̅_̅i̅(t_i+t̅_̅i̅)(t̅_̅i̅+z)P(s_i=t_i)P(s̅_̅i̅=t̅_̅i̅)P(z=t))/1-P(s̅_̅i̅=0) .

With eq:expected_sigma_2, we can numerically approximate 𝔼[σ_A(0)] for both ER and two-community SBM networks. 








§ ALGORITHMS FOR NONLINEAR COEVOLVING VOTER MODELS
  
figuresection





 §.§ Rewire-To-Same (RTS) Model
  

In Algorithm <ref>, we present the precise rules for our nonlinear CVM with a rewire-to-same scheme (i.e., for the nonlinear RTS-CVM). Specifically, we use an RTS scheme that stipulates that there is no replacement edge when a primary node attempts to rewire, but is unable to do so (see sec:RTS). We use the notation V_X to denote the set of nodes that are in state X.











 §.§ Rewire-To-None (RTN) Model
  

In Algorithm <ref>, we present the precise rules for our nonlinear CVM with a rewire-to-none (i.e., edge-deletion) scheme. We use the acronym RTN-CVM for this model. 













§ LINEAR COEVOLVING VOTER MODELS
 
figuresection





 §.§ Linear Rewire-to-Random (RTR) CVM
  

We compare the simulation results for our nonlinear CVM with a rewire-to-random scheme to the linear rewire-to-random CVM that was studied in <cit.>. We seed the system using ER G(N,p) networks with N=20,000 nodes and an edge probability of p=4/N-1. In fig:LIN_RTR_ER_Term_A, we initialize half of the nodes in state A and the other half in state B. In fig:LIN_RTR_ER_Term_A_1-3, we initialize 1/4 of the nodes in state A and the other 3/4 of nodes in state B. In fig:LIN_RTR_ER_Term_A_both, we plot the terminal density of state A for 20 realizations of the simulations for each value of q. In this figure, we also show the means of terminal densities for each q.

In fig:LIN_RTR_ER_Term_A, when 1-α⪅  0.25, rewiring actions dominate; the fraction of nodes that terminate in state A is approximately constant, with a value of 0.5. For progressively larger values of 1-α (i.e., as we consider a progressively smaller rewiring rate α and hence a progressively larger adoption rate), rewiring and adoption actions begin competing and the plot appears to branch, with one branch decreasing to 0 and the other increasing to 1 as 1-α→ 1. This illustrates that, by the time the system terminates, there are larger changes to the state densities of the system for progressively larger 1-α. Because the system begins with N_A(0)/N=N_B(0)/N=1/2, terminating along either branch (i.e., whether there is a positive or negative change for N_A(t)/N or N_B(t)/N) is equally probable, as indicated by the values of the means of the terminal state-A densities. 





When 1-α = 1, no rewiring occurs, so isolated nodes do not change their opinion state. In our simulations in fig:LIN_RTR_ER_Term_A, the seed ER networks have an expected mean degree of 4. In our realizations, the seed networks have a largest connected component (LCC) that consists of approximately 98.2% of the nodes on average, and most of the remaining approximately 1.8% of the nodes have degree 0. When the system terminates and the nodes in the LCC settle in either state A or state B, approximately 0.9 % of nodes are in the other opinion state, because we initialize half of the nodes in each state and those nodes never update their states.

In fig:LIN_RTR_ER_Term_A_1-3, we observe behavior that is qualitatively similar to that in fig:LIN_RTR_ER_Term_A. For 1-α⪅  0.35, rewiring actions dominate; the fraction of nodes that terminate in state A is approximately constant, with a value of 0.25. For progressively larger values of 1-α, rewiring and adoption actions begin competing and the plot appears to branch, with one branch decreasing to 0 (indicating a negative change to N_A(t)/N) and the other increasing to 1 (indicating a positive change to N_A(t)/N) as 1-α→ 1. Unlike in fig:LIN_RTR_ER_Term_A, we begin with N_A(0)/N=1/4, so we expect only 1/4 of the realizations to terminate along the upper branch (i.e., with a positive change to N_A(t)/N), which is what we observe by examining the means of the terminal state-A densities. 

We also consider a linear RTR-CVM in which we seed the system with two-community structure using SBMs. We use the same parameter values as in sec:RTR_SBM_two_communities, so N_A(0)/N=1/4 of the nodes are in state A. In fig:LIN_RTR_SBM_TWO_COM_Term_A, we plot the terminal density of state A from our simulations. The plot has roughly the same shape as when we seeded the linear CVM with an ER network (see fig:LIN_RTR_ER_Term_A_1-3). When 1-α⪅ 0.2, rewiring actions dominate; the terminal minority-state densities are constant, with a value of 0.25. Adoption actions compete with rewiring actions when 1-α⪆0.2, and the plot appears to branch, with one branch decreasing to 0 and the other increasing to 1 as 1-α→ 1. This illustrates that, by the time the system terminates, there are progressively larger changes to the state densities of the system for progressively larger values of 1-α. Because the system begins with N_A(0)/N=1/4, terminating along the upper branch (i.e., there is a positive change for N_A(t)/N) occurs in approximately 1/4 of the realizations, as indicated by the values of the means of the terminal state-A densities.

Finally, in fig:LIN_RTR_CP_Term_A, we plot simulations of the linear RTR-CVM in which we seed the system with core–periphery structure.  We use the same parameter values as in sec:RTR_SBM_CP. The plot's similarity to fig:LIN_RTR_SBM_TWO_COM_Term_A illustrates an insensitivity of this linear RTR-CVM to some types of initial network structure.  With the parameter values of our seed core–periphery networks, approximately 10 % of the nodes begin in state B and are isolated. When 1-α=1, there is no rewiring, so these nodes remain isolated and thus do not change state. This explains why in the realizations in which state A spreads to almost every node, it only reaches approximately 90%̇ of nodes in the system.

There are values of α in fig:LIN_RTR_ER_Term_A_1-3 and fig:LIN_RTR_SBM_Term_A for which none of our realizations terminate with almost all nodes in state A. The probability that a realization terminates along the top branch (signifying a net positive change in the density of state A) is N_A(0)/N=1/4, so we expect on rare occasions (specifically, with probability (3/4)^20≈0.0032) that all 20 realizations for a particular value of α terminate along the bottom branch (i.e., with a net negative change in the density of state A).










 §.§ Linear Rewire-to-Same CVM
  





We compare the results of simulations of our nonlinear RTS-CVM to simulations of the linear RTS-CVM from <cit.>. In fig:lin_rts_terminal_A_ER, we observe what appears to be a discontinuous phase transition for a critical value of α. For 1-α⪅ 0.57, rewiring dominates and state densities do not change significantly. However, when 1-α⪆ 0.57, almost every node terminates in the same state. The system begins with N_A(0)/N=N_B(0)/N=1/2, so it is equally probable for almost every node to terminate in state A or almost every node to terminate in state B. As we noted in appsec:Linear_CVM_Simulations_RTR, when 1-α = 1, there are no rewiring actions, so isolated nodes do not change their opinion state.


In fig:LIN_RTS_SBM_Term_A, we plot the terminal state-A densities from simulations of the linear RTS-CVM from <cit.> on networks that we seed with two-community structure (see sec:RTR_SBM_two_communities) and on networks that we seed with core–periphery structure (see sec:RTR_SBM_two_communities). In both cases, we observe qualitatively similar results as in fig:lin_rts_terminal_A_ER, which again suggests that this linear CVM is less sensitive than our nonlinear CVM to some initial network structures. It also suggests that this linear CVM is more sensitive than our nonlinear CVM to the choice of rewiring mechanism. 










 §.§ Linear Rewire-to-None CVM

 

We briefly discuss some results from our simulations of linear CVMs with edge deletion (i.e., a rewire-to-none scheme). As in the linear RTR-CVM (see Appendix <ref>), this rule involves picking a discordant edge uniformly at random from the set of discordant edges, choosing one of the nodes to be the primary node uniformly at random, and then either deleting the discordant edge with probability α or having the primary node change states with probability 1-α. As in the RTS scheme (see sec:RTS), |E(t)| is not conserved. However, in the linear RTN-CVM, edge deletions occur at a fixed rate α, so the expected number of edges is 𝔼[|E(t)|]=|E(0)|-α t, which is valid until the system terminates, after which the number of edges is constant. 





In fig:lin_rtn_terminal_minority_ER, we plot the terminal minority-state density of our simulations. We seed the system with an ER G(N,p) network with N=20,000 nodes and an edge probability of p=4/N-1.
Initially, there are approximately 20,000 discordant edges. We compute an estimate for the terminal minority-state density in terms of α by assuming that the adoption mechanism does not significantly increase or decrease the number N_AB(t) of discordant edges. Because we delete discordant edges at a constant rate α, we expect the system to terminate in approximately E_D(0)/α elementary time steps. During this time, the expected number of adoption actions is (1-α)E_D(0)/α. Each adoption action increases the number N_A(t) of nodes in state A by 1 with probability 1/2 and decreases it by 1 with probability 1/2. We can thus think of N_A(t) as a simple, symmetric random walk during the steps when adoption occurs. For a simple, symmetric random walk that starts at the origin, the expected distance of the walker to the origin after n steps is √(2nπ) <cit.>. Therefore, after (1-α)E_D(0)/α steps, we expect that N_A(t) has either increased or decreased by 1/N√(2(1-α)E_D(0)/πα). 
 
In fig:lin_rtn_terminal_minority_ER, we include a plot of our estimate 

    1/2-1/N√(2(1-α)E_D(0)/πα)
 
for the terminal minority-state density, where the 1/2 term comes from the initial densities of 1/2 and we subtract from this value because we are 
calculating the minority-state density. The plot illustrates that our estimate captures the behavior of the linear RTN-CVM accurately, with a coefficient of determination of R^2 ≈ 0.959.









§ SIMULATIONS OF OUR NONLINEAR COEVOLVING VOTER MODEL FOR LARGE VALUES OF Q

 





In our simulations of nonlinear CVMs on SBM networks with two-community structure and core–periphery structure, we observed regimes of q values in which almost every node terminates in state B, which initially has density 3/4, for all 20 realizations. See fig:RTR_SBM_TWO_COM_TERMINAL_A and fig:RTR_SBM_Terminal_A_CP for two examples. This regime extends past q=12, but we know that as q→∞, we must recover a voter model that does not coevolve with network structure. In this appendix, we repeat one of our simulations for large values of q to improve our understanding of this behavior.

We repeat our experiment from sec:RTR_SBM_CP of our nonlinear RTR-CVM seeded with core–periphery structure, but now we consider q∈ [0,100] and take our network to have N=20,000 nodes. In fig:RTR_SBM_Terminal_A_CP_big_q, we plot the terminal density of state A. In this case, we see that when q⪆38, the adoption mechanism begins to dominate and state A becomes competitive with state B. In some trials, state A spreads to almost every node. For sufficiently large values of q, adoption actions should completely dominate and the system should behave like a voter model that does not coevolve with network structure; in such a scenario, almost every node terminates in the same state. Specifically, we expect that almost every node terminates in state A in N_A(0)/N=1/4 of the realizations. In our computations, we observe this scenario for q⪆ 80.

As we noted for fig:LIN_RTR_CP_Term_A, due to our initial networks, approximately 10 % of the nodes start in state B and are isolated. Therefore, in the regimes that are dominated by adoption actions, the system terminates with these nodes still in state B, even when state A has spread to almost every node in the LCC.



















81
fxundefined [1]
 ifx#1

fnum [1]
 #1firstoftwo
 secondoftwo
 
fx [1]
 #1firstoftwo
 secondoftwo
 





noop [0]secondoftwo

ref[1]@startlink#1@href
href[1]#1@endlink
anitize@url [0]`
12`$12`&12`#12`1̂2`_12`%12
startlink[1]
endlink[0]

rl [1]href #1












@bib@innerbibempty

[Sunstein(2018)]sunstein2018republic
  author author C. R. Sunstein, @noop  title #Republic: Divided
  Democracy in the Age of Social Media (publisher Princeton
  University Press, address Princeton, NJ, USA, year
  2018)NoStop
[Del Vicario et al.(2016)Del Vicario, Vivaldo, Bessi, Zollo, Scala, Caldarelli, and  Quattrociocchi]del2016echo
  author author M. Del Vicario, author G. Vivaldo, author A. Bessi,
  author F. Zollo, author A. Scala, author
  G. Caldarelli, and author
  W. Quattrociocchi, @noop 
  journal journal Scientific Reports volume 6, pages 37825 (year
  2016)NoStop
[John and Dvir-Gvirsman(2015)]john2015don
  author author N. A. John and author S. Dvir-Gvirsman, @noop  journal journal
  Journal of Communication volume 65, pages 953 (year 2015)NoStop
[Skoric et al.(2018)Skoric,
  Zhu, and Lin]skoric2018predicts
  author author M. M. Skoric, author Q. Zhu, and  author J.-H. T. Lin,  @noop  journal journal American
  Behavioral Scientist volume 62, pages
  1097 (year 2018)NoStop
[Geschke et al.(2019)Geschke, Lorenz, and Holtz]geschke2019triple
  author author D. Geschke, author J. Lorenz,  and author P. Holtz,  @noop  journal journal British Journal of
  Social Psychology volume 58, pages
  129 (year 2019)NoStop
[Castellano et al.(2009a)Castellano, Fortunato, and Loreto]castellano2009statistical
  author author C. Castellano, author S. Fortunato, and author V. Loreto, @noop  journal journal
  Reviews of Modern Physics volume 81, pages 591 (year 2009a)NoStop
[Kiss et al.(2017)Kiss,
  Miller, and Simon]kiss2017mathematics
  author author I. Z. Kiss, author J. C. Miller,  and author P. L. Simon,  @noop  title Mathematics of Epidemics on
  Networks (publisher Springer International Publishing,  address Cham, Switzerland, year 2017)NoStop
[Lehmann and Ahn(2018)]lehmann2018complex
  author author S. Lehmann and author Y.-Y. Ahn, @noop  title Complex Spreading Phenomena
  in Social Systems: Influence and Contagion in Real-World Social Networks  (publisher Springer International Publishing, address Cham, Switzerland, year 2018)NoStop
[Noorazar et al.(2019)Noorazar, Vixie, Talebanpour, and  Hu]opinion-review
  author author H. Noorazar, author K. R. Vixie,
  author A. Talebanpour, and  author Y. Hu, @noop 
  journal journal arXiv preprint arXiv:1909.12089   (year 2019)NoStop
[Pastor-Satorras et al.(2015)Pastor-Satorras, Castellano, Van Mieghem,  and Vespignani]pastor-satorras2015
  author author R. Pastor-Satorras, author C. Castellano, author P. Van Mieghem, and author A. Vespignani, @noop  journal journal
  Reviews of Modern Physics volume 87, pages 925 (year 2015)NoStop
[Meyers et al.(2005)Meyers,
  Pourbohloul, Newman, Skowronski, and Brunham]meyers2005network
  author author L. A. Meyers, author B. Pourbohloul,
  author M. E. J. Newman, author D. M. Skowronski, and author R. C. Brunham, @noop 
  journal journal Journal of Theoretical Biology  volume 232, pages 71 (year
  2005)NoStop
[Porter and Gleeson(2016)]porter2016dynamical
  author author M. A. Porter and author J. P. Gleeson, @noop  title Dynamical Systems on
  Networks: A Tutorial, Vol. volume 4 (publisher
  Springer International Publishing, address Cham,
  Switzerland, year 2016)NoStop
[Sayama et al.(2013)Sayama,
  Pestov, Schmidt, Bush,
  Wong, Yamanoi, and Gross]sayama2013modeling
  author author H. Sayama, author I. Pestov,
  author J. Schmidt, author B. J. Bush, author
  C. Wong, author J. Yamanoi, and author T. Gross, @noop  journal journal Computers & Mathematics with Applications volume 65, pages 1645 (year
  2013)NoStop
[Demirel et al.(2014)Demirel, Vazquez, Böhme, and  Gross]demirel2014moment
  author author G. Demirel, author F. Vazquez,
  author G. A. Böhme, and  author T. Gross, @noop 
  journal journal Physica D volume 267, pages 68 (year 2014)NoStop
[Note1()]Note1
  note See <cit.> for
  reviews of research on time-dependent networks.Stop
[Redner(2019)]redner2018reality
  author author S. Redner, @noop  journal journal
  Comptes Rendus Physique volume 20, pages 275 (year 2019)NoStop
[Fernández-Gracia et al.(2014)Fernández-Gracia, Suchecki,
  Ramasco, San Miguel, and Eguíluz]Fernandez-Gracia2014Voter
  author author J. Fernández-Gracia, author K. Suchecki, author J. J. Ramasco, author M. San
  Miguel, and author V. M. Eguíluz, @noop  journal journal
  Physical Review Letters volume 112, pages 158701 (year 2014)NoStop
[Huepe et al.(2011)Huepe,
  Zschaler, Do, and Gross]huepe2011adaptive
  author author C. Huepe, author G. Zschaler,
  author A.-L. Do, and author T. Gross, @noop 
  journal journal New Journal of Physics volume 13, pages 073022 (year
  2011)NoStop
[Clifford and Sudbury(1973)]clifford1973model
  author author P. Clifford and author A. Sudbury, @noop  journal journal
  Biometrika volume 60, pages 581
  (year 1973)NoStop
[Holley and Liggett(1975)]holley1975ergodic
  author author R. A. Holley and author T. M. Liggett, @noop  journal journal The
  Annals of Probability volume 3, pages
  643 (year 1975)NoStop
[Cox(1989)]cox1989coalescing
  author author J. T. Cox, @noop  journal journal The
  Annals of Probability volume 17, pages
  1333 (year 1989)NoStop
[Ebel and Bornholdt(2002)]ebel2002evolutionary
  author author H. Ebel and author S. Bornholdt, @noop  journal journal
  arXiv preprint cond-mat/0211666  (year 2002)NoStop
[Bornholdt and Rohlf(2000)]bornholdt2000topological
  author author S. Bornholdt and author T. Rohlf, @noop  journal journal
  Physical Review Letters volume 84, pages 6114 (year 2000)NoStop
[Gross et al.(2006)Gross,
  D'Lima, and Blasius]gross2006epidemic
  author author T. Gross, author C. J. D. D'Lima, and author B. Blasius, @noop  journal journal
  Physical Review Letters volume 96, pages 208701 (year 2006)NoStop
[Gross and Blasius(2007)]gross2007adaptive
  author author T. Gross and author B. Blasius, @noop  journal journal
  Journal of the Royal Society Interface volume 5,  pages 259 (year 2007)NoStop
[Holme and Newman(2006)]Holme2006Nonequilibrium
  author author P. Holme and author M. E. J. Newman, @noop  journal journal
  Physical Review E volume 74, pages
  056108 (year 2006)NoStop
[Shi et al.(2013)Shi,
  Mucha, and Durrett]shi2013multiopinion
  author author F. Shi, author P. J. Mucha,  and author R. Durrett,  @noop  journal journal Physical Review
  E volume 88, pages 062818 (year 2013)NoStop
[Brede(2019)]brede2019
  author author M. Brede, @noop  journal journal
  Complexity volume 2019, pages
  1486909 (year 2019)NoStop
[Saeedian et al.(2019)Saeedian, San Miguel, and Toral]saeedian2019absorbing
  author author M. Saeedian, author M. San Miguel, and author R. Toral, @noop  journal journal
  Scientific Reports volume 9, pages
  9726 (year 2019)NoStop
[Durrett et al.(2012)Durrett, Gleeson, Lloyd, Mucha, Shi, Sivakoff, Socolar, and Varghese]durrett2012graph
  author author R. Durrett, author J. P. Gleeson, author A. L. Lloyd,
  author P. J. Mucha, author F. Shi, author
  D. Sivakoff, author
  J. E. S. Socolar, and author
  C. Varghese, @noop  journal journal Proceedings of the National Academy of
  Sciences of the United States of America volume
  109, pages 3682 (year 2012)NoStop
[Silk et al.(2014)Silk,
  Demirel, Homer, and Gross]Silk2014Exploring
  author author H. Silk, author G. Demirel,
  author M. Homer, and author T. Gross, @noop 
  journal journal New Journal of Physics volume 16, pages 093051 (year
  2014)NoStop
[Chodrow and Mucha(2018)]chodrow2018local
  author author P. S. Chodrow and author P. J. Mucha, @noop  journal journal arXiv
  preprint arXiv:1812.05464  (year 2018)NoStop
[Basu and Sly(2017)]basu2017evolving
  author author R. Basu and author A. Sly,  @noop  journal journal The Annals of
  Applied Probability volume 27, pages
  1235 (year 2017)NoStop
[Couzin et al.(2011)Couzin,
  Ioannou, Demirel, Gross,
  Torney, Hartnett, Conradt,
  Levin, and Leonard]couzin2011uninformed
  author author I. D. Couzin, author C. C. Ioannou,
  author G. Demirel, author T. Gross, author
  C. J. Torney, author
  A. Hartnett, author
  L. Conradt, author S. A. Levin, and author N. E. Leonard, @noop  journal
  journal Science volume 334, pages 1578 (year 2011)NoStop
[Lerman et al.(2016)Lerman,
  Yan, and Wu]lerman2016majority
  author author K. Lerman, author X. Yan, and  author X.-Z. Wu, @noop 
  journal journal PloS ONE volume 11, pages e0147617 (year
  2016)NoStop
[Bode(2016)]bode2016pruning
  author author L. Bode, @noop  journal journal Research
  & Politics volume 3, pages 1
  (year 2016)NoStop
[Yang et al.(2017)Yang,
  Barnidge, and Rojas]yang2017politics
  author author J. H. Yang, author M. Barnidge,  and author H. Rojas,  @noop  journal journal Computers in Human
  Behavior volume 70, pages 22
  (year 2017)NoStop
[Zhu et al.(2017)Zhu,
  Skoric, and Shen]zhu2017shield
  author author Q. Zhu, author M. Skoric, and  author F. Shen, @noop 
  journal journal Political Communication  volume 34, pages 112 (year
  2017)NoStop
[Sood et al.(2008)Sood,
  Antal, and Redner]sood2008voter
  author author V. Sood, author T. Antal, and  author S. Redner, @noop 
  journal journal Physical Review E volume 77, pages 041121 (year
  2008)NoStop
[Gastner(2015)]gastner2015ising
  author author M. T. Gastner, @noop  journal journal
  Journal of Statistical Mechanics: Theory and Experiment volume 2015, pages P03004 (year
  2015)NoStop
[Huberman and Glance(1993)]huberman1993evolutionary
  author author B. A. Huberman and author N. S. Glance, @noop  journal journal
  Proceedings of the National Academy of Sciences of the United States of
  America volume 90, pages 7716
  (year 1993)NoStop
[Roca et al.(2009)Roca,
  Cuesta, and Sánchez]roca2009evolutionary
  author author C. P. Roca, author J. A. Cuesta,  and author A. Sánchez,  @noop  journal journal Physics of Life
  Reviews volume 6, pages 208 (year 2009)NoStop
[Fernández-Gracia et al.(2011)Fernández-Gracia, Eguíluz, and San Miguel]fernandez2011update
  author author J. Fernández-Gracia, author V. M.  Eguíluz, and author M. San Miguel, @noop  journal
  journal Physical Review E volume 84,  pages 015103 (year 2011)NoStop
[Note2()]Note2
  note We are not aware of any studies of coevolving voter models
  with synchronous updating. One challenge in defining such a model is
  establishing a protocol for the situation when two adjacent nodes select each
  other for updating and both simultaneously attempt to rewire the same
  edge.Stop
[Nardini et al.(2008)Nardini, Kozma, and Barrat]nardini2008whos
  author author C. Nardini, author B. Kozma,  and author A. Barrat,  @noop  journal journal Physical Review
  Letters volume 100, pages 158701
  (year 2008)NoStop
[Sood and Redner(2005)]sood2005voter
  author author V. Sood and author S. Redner,  @noop  journal journal Physical Review
  Letters volume 94, pages 178701
  (year 2005)NoStop
[Feller(1957)]feller1957probability
  author author W. Feller, @noop  title An Introduction to
  Probability Theory and Its Applications, Vol. volume 1  (publisher John Wiley and Sons, year
  1957)NoStop
[Basak et al.(2015)Basak,
  Durrett, and Zhang]basak2015evolving
  author author A. Basak, author R. Durrett,  and author Y. Zhang,  @noop  journal journal arXiv preprint
  arXiv:1512.07871  (year 2015)NoStop
[Castellano et al.(2009b)Castellano, Muñoz, and Pastor-Satorras]castellano2009nonlinear
  author author C. Castellano, author M. A. Muñoz, and author R. Pastor-Satorras, @noop  journal journal Physical Review E volume 80, pages 041129 (year 2009b)NoStop
[Min and San Miguel(2017)]min2017fragmentation
  author author B. Min and author M. San Miguel, @noop  journal journal
  Scientific Reports volume 7, pages
  12864 (year 2017)NoStop
[Granovsky and Madras(1995)]granovsky1995noisy
  author author B. L. Granovsky and author N. Madras, @noop  journal journal
  Stochastic Processes and Their Applications volume
  55, pages 23 (year 1995)NoStop
[Carro et al.(2016)Carro,
  Toral, and San Miguel]carro2016noisy
  author author A. Carro, author R. Toral, and  author M. San Miguel,  @noop  journal journal Scientific
  Reports volume 6, pages 24775
  (year 2016)NoStop
[Ji et al.(2013)Ji,
  Xu, Choi, and Hui]ji2013correlations
  author author M. Ji, author C. Xu, author C. W. Choi, and author P. M. Hui, @noop 
  journal journal New Journal of Physics volume 15, pages 113024 (year
  2013)NoStop
[Kuehn(2016)]kuehn2016moment
  author author C. Kuehn, in @noop  booktitle Control of
  Self-Organizing Nonlinear Systems, editor edited by editor E. Schöll, editor
  S. H. L. Klapp, and editor
  P. Hövel (publisher
  Springer, year 2016) pp. pages
  253–271NoStop
[Note3()]Note3
  note In a 1D random walk, “simple” refers to the rule that, at
  each time step, the walker must move by either +1 or -1; and
  “symmetric” refers to these outcomes being equally probable. In a symmetric
  random walk with possible moves +1, -1, and 0, one requires only that
  the first two possibilities are equiprobable to each other.Stop
[Masuda et al.(2017)Masuda,
  Porter, and Lambiotte]masuda2017
  author author N. Masuda, author M. A. Porter,  and author R. Lambiotte,  @noop  journal journal Physics Reports  volume 716–717, pages 1 (year 2017)NoStop
[Lee et al.(2019)Lee,
  Karimi, Wagner, Jo,
  Strohmaier, and Galesic]Lee2019Homophily
  author author E. Lee, author F. Karimi,
  author C. Wagner, author H.-H. Jo, author
  M. Strohmaier, and author
  M. Galesic, https://doi.org/10.1038/s41562-019-0677-4 journal journal Nature Human Behaviour volume 3,  pages 1078 (year 2019)NoStop
[Kimura and Hayakawa(2008)]Kimura2008Coevolutionary
  author author D. Kimura and author Y. Hayakawa, https://doi.org/10.1103/PhysRevE.78.016103 journal journal Physical Review E volume 78, pages 016103 (year
  2008)NoStop
[Pugliese and Castellano(2009)]pugliese2009heterogeneous
  author author E. Pugliese and author C. Castellano, @noop  journal journal
  EPL (Europhysics Letters) volume 88, pages 58004 (year 2009)NoStop
[Böhme and Gross(2011)]bohme2011analytical
  author author G. A. Böhme and author T. Gross, @noop  journal journal
  Physical Review E volume 83, pages
  035101 (year 2011)NoStop
[Gleeson et al.(2012)Gleeson, Melnik, Ward, Porter, and Mucha]gleeson2012accuracy
  author author J. P. Gleeson, author S. Melnik,
  author J. A. Ward, author M. A. Porter, and author P. J. Mucha, @noop 
  journal journal Physical Review E volume 85, pages 026106 (year
  2012)NoStop
[Note4()]Note4
  note This approximation is exact for non-empty, degree-regular
  networks with at least one node in state A.Stop
[Fortunato and Hric(2016)]fortunato2016community
  author author S. Fortunato and author D. Hric, @noop  journal journal Physics
  Reports volume 659, pages 1 (year 2016)NoStop
[Newman(2018)]newman2018book
  author author M. E. J.  Newman, @noop  title
  Networks, edition 2nd ed. (publisher Oxford
  University Press, address Oxford, UK, year
  2018)NoStop
[Vazquez et al.(2008)Vazquez, Eguíluz, and San Miguel]vazquez2008generic
  author author F. Vazquez, author V. M. Eguíluz, and author M. San Miguel, @noop  journal journal
  Physical review letters volume 100, pages 108702 (year 2008)NoStop
[Lee et al.(2016)Lee,
  Choi, Stippinger, Kertész, and Kahng]lee2016hybrid
  author author D. Lee, author S. Choi, author M. Stippinger, author
  J. Kertész, and author
  B. Kahng, @noop  journal journal Physical Review E volume 93, pages 042109 (year
  2016)NoStop
[Csermely et al.(2013)Csermely, London, Wu, and Uzzi]csermely2013structure
  author author P. Csermely, author A. London,
  author L.-Y. Wu, and author B. Uzzi, @noop  journal journal Journal of Complex Networks volume 1, pages 93 (year
  2013)NoStop
[Rombach et al.(2017)Rombach, Porter, Fowler, and  Mucha]rombach2017core
  author author P. Rombach, author M. A. Porter,
  author J. H. Fowler, and  author P. J. Mucha, @noop
   journal journal SIAM Review volume 59, pages 619 (year
  2017)NoStop
[Sasahara et al.(2019)Sasahara, Chen, Peng, Ciampaglia, Flammini, and Menczer]sasahara2019inevitability
  author author K. Sasahara, author W. Chen,
  author H. Peng, author
  G. L. Ciampaglia, author
  A. Flammini, and author
  F. Menczer, @noop  journal journal arXiv preprint arXiv:1905.03919  (year 2019)NoStop
[Note5()]Note5
  note However, edge deletion can pose a mathematical challenge,
  because the number of edges and the mean degree are no longer constant <cit.>.Stop
[Farajtabar et al.(2015)Farajtabar, Wang, Rodriguez, Li, Zha, and Song]farajtabar2015coevolve
  author author M. Farajtabar, author Y. Wang,
  author M. G. Rodriguez, author S. Li, author
  H. Zha, and author
  L. Song, in @noop  booktitle Advances in Neural Information Processing Systems  (year 2015) pp. pages 1954–1962NoStop
[Saavedra et al.(2008)Saavedra, Reed-Tsochas, and Uzzi]saavedra2008asymmetric
  author author S. Saavedra, author F. Reed-Tsochas, and author B. Uzzi, @noop  journal journal
  Proceedings of the National Academy of Sciences of the United States of
  America volume 105, pages 16466
  (year 2008)NoStop
[Stewart et al.(2019)Stewart, Mosleh, Diakonova, Arechar, Rand, and Plotkin]stewart2019information
  author author A. J. Stewart, author M. Mosleh,
  author M. Diakonova, author A. A. Arechar, author
  D. G. Rand, and author
  J. B. Plotkin, @noop  journal journal Nature volume 573,  pages 117 (year 2019)NoStop
[Gleeson(2013)]gleeson2013binary
  author author J. P. Gleeson, @noop  journal journal
  Physical Review X volume 3, pages
  021004 (year 2013)NoStop
[Jedrzejewski(2017)]jedrzejewski2017pair
  author author A. Jedrzejewski, @noop  journal journal
  Physical Review E volume 95, pages
  012307 (year 2017)NoStop
[Juul and Porter(2019)]juul2019hipsters
  author author J. S. Juul and author M. A. Porter, @noop  journal journal
  Physical Review E volume 99, pages
  022313 (year 2019)NoStop
[Klamser et al.(2017)Klamser, Wiedermann, Donges, and  Donner]klamser2017zealotry
  author author P. P. Klamser, author M. Wiedermann,
  author J. F. Donges, and  author R. V. Donner,  @noop  journal journal Physical Review
  E volume 96, pages 052315 (year 2017)NoStop
[Kozma and Barrat(2008)]kozma2008consensus
  author author B. Kozma and author A. Barrat,  @noop  journal journal Physical Review
  E volume 77, pages 016102 (year 2008)NoStop
[Holme and Saramäki(2012)]holme2012temporal
  author author P. Holme and author J. Saramäki, @noop  journal journal
  Physics Reports volume 519, pages 97
  (year 2012)NoStop
[Holme(2015)]holme2015
  author author P. Holme, @noop  journal journal
  European Physical Journal B volume 88, pages 234 (year 2015)NoStop
[Holme and Saramäki(2019)]holme2019
  editor P. Holme and editor J. Saramäki, eds., @noop
   title Temporal Network Theory (publisher Springer International Publishing, address Cham,
  Switzerland, year 2019)NoStop










