Adam Douglas

Dieter Mitsche
email: dmitsche@unice.fr

Pawe

Pra Lat
email: pralat@ryerson.ca

Homophily, influence and the decay of segregation in self-organizing networks

We study the persistence of network segregation in networks characterized by the co-evolution of nodal attributes and link structures, in particular where individual nodes form linkages on the basis of similarity with other network nodes (homophily), and where nodal attributes diffuse across linkages, making connected nodes more similar over time (influence). A general mathematical model of these processes is used to examine the relative influence of homophily and influence in the maintenance and decay of network segregation in self-organizing networks. While prior work has shown that homophily is capable of producing strong network segregation when attributes are fixed, we show that adding even minute levels of influence is sufficient to overcome the tendency towards segregation even in the presence of relatively strong homophily processes. This result is proven mathematically for all large networks, and illustrated through a series of computational simulations that account for additional network evolution processes. This research contributes to a better theoretical understanding of the conditions under which network segregation and related phenomenon-such as community structure-may emerge, which has implications for the design of interventions that may promote more efficient network structures.

1 Introduction: Segregation and community structure in selforganizing networks

Many real-world networks exhibit network segregation, in that linkages are concentrated among nodes with shared or similar attributes [START_REF] Freeman | Segregation in Social Networks[END_REF][START_REF] Henry | Emergence of Segregation in Evolving Social Networks[END_REF]. Related to network segregation, many networked systems also exhibit community structure, where nodes may be naturally partitioned into two or more groups of with many within-group linkages, but relatively few linkages across groups [START_REF] Girvan | Community Structure in Social and Biological Networks[END_REF][START_REF] Newman | The Structure and Function of Complex Networks[END_REF][START_REF] Palla | Uncovering the Overlapping Community Structure of Complex Networks in Nature and Society[END_REF][START_REF] Porter | Communities in Networks[END_REF]. These community boundaries often map onto a natural definition of groups based on clusters of nodal attributes; in this way, community structure is often a strong form of network segregation. 1Network segregation has important consequences for the efficient functioning of networks [START_REF] Jackson | Networks in the Understanding of Economic Behaviors[END_REF]. In some contexts it is advantageous for network nodes to have access, via relatively short paths, to other nodes with heterogeneous attributes or within distinct communities [START_REF] Burt | Structural Holes and Good Ideas[END_REF][START_REF] Granovetter | The Strength of Weak Ties[END_REF]. For example, networks of information exchange among organizations and individuals involved in policy making often cluster around shared values or political positions, making it difficult for actors within these networks to reach negotiated agreements [START_REF] Sabatier | Policy Change and Learning: An Advocacy Coalition Approach[END_REF] or share information necessary to solve complex problems [START_REF] Hong | Groups of Diverse Problem Solvers Can Outperform Groups of High-Ability Problem Solvers[END_REF]. This is one explanation for the mismatch between scientific understanding and political action on complex policy issues such as climate change [START_REF] Dietz | Bringing Values and Deliberation to Science Communication[END_REF][START_REF] Henry | The Challenge of Learning for Sustainability: A Prolegomenon to Theory[END_REF]. Network segregation can also influence the ways in which technologies or behaviors diffuse in a network [START_REF] Banerjee | The Diffusion of Microfinance[END_REF][START_REF] Jackson | Diffusion and Contagion in Networks with Heterogeneous Agents and Homophily[END_REF], and may reinforce inequalities between groups of different socioeconomic status [START_REF] Jackson | Networks in the Understanding of Economic Behaviors[END_REF]. In some other cases, network segregation may be individually advantageous-for example, it may be useful for social actors to exploit fragmentations by occupying brokerage or bottleneck positions between communities [START_REF] Burt | Structural Holes and Good Ideas[END_REF]. Network segregation may even be globally advantageous if, for example, the presence of communities increases the stability and resilience of ecosystems [START_REF] Krause | Compartments Revealed in Food-Web Structure[END_REF] or provides a mechanism that shields "altruistic" or "cooperative" actors from the negative influence of noncooperative nodes [START_REF] Nowak | Five Rules for the Evolution of Cooperation[END_REF]. In any case, better theories of the mechanisms that produce network segregation and community structure can inform the design of interventions to promote more efficient policy processes [START_REF] Sabatier | Theories of the Policy Process[END_REF], increased social learning [START_REF] Henry | The Challenge of Learning for Sustainability: A Prolegomenon to Theory[END_REF][START_REF] Parson | Barriers and Bridges to the Renewal of Ecosystems and Institutions[END_REF], the emergence of cooperation [START_REF] Nowak | Five Rules for the Evolution of Cooperation[END_REF], or any other process emerging from a broad array of network types [START_REF] Newman | The Structure and Function of Complex Networks[END_REF].

Why does network segregation emerge? A large body of research has grown around methods for the efficient and reliable detection of communities in segregated networks [START_REF] Girvan | Community Structure in Social and Biological Networks[END_REF][START_REF] Porter | Communities in Networks[END_REF][START_REF] Newman | Modularity and Community Structure in Networks[END_REF], however relatively few studies have sought to develop theoretical explanations for why these network structures emerge and are maintained over time-but see [START_REF] Palla | Quantifying social group evolution[END_REF][START_REF] Henry | Emergence of Segregation in Evolving Social Networks[END_REF][START_REF] Kumpula | Emergence of Communities in Weighted Networks[END_REF][START_REF] Lambiotte | Majority Model on a Network with Communities[END_REF][START_REF] Durrett | Graph fission in an evolving voter model[END_REF][START_REF] Cooper | Some typical properties of the Spatial Preferred Attachment model[END_REF]. Research in this area often assumes some form of structural or choice-based homophily, in that linkages are more likely to form between similar nodes due to increased opportunities for interaction or systematic biases for homophilous links [START_REF] Boucher | Structural Homophily[END_REF][START_REF] Mcpherson | Birds of a Feather: Homophily in Social Networks[END_REF].

The idea that nodes form connections with each other based on shared or similar traits is a strong and consistent empirical finding in the network science literature, particularly in the study of social networks. For example, research based on the Adolescent Health ("Add Health") dataset [START_REF] Harris | The National Longitudinal Study of Adolescent to Adult Health: Research Design[END_REF] shows a correlation between race and friendship among a sample of high school students, and that this homophily effect tends to be stronger for racial groups that comprise a larger proportion of the student population [START_REF] Currarini | An Economic Model of Friendship: Homophily, Minorities and Segregation[END_REF][START_REF] Currarini | Identifying the Roles of Race-Based Choice and Chance in High School Friendship Network Formation[END_REF]. An analysis of the same dataset also shows that genetic similarity-in addition to social and behavioral characteristicsalso lead to the formation of friendship ties [START_REF] Boardman | How Social and Genetic Factors Predict Friendship Networks[END_REF]. Among new university students in Germany, factors such as race, gender, and propensity for cooperative behavior were found to influence friendship choices [START_REF] Girard | How Individual Characteristics Shape the Structure of Social Networks[END_REF]. In online social networks, homophily drives individuals to "befriend" others with similar tastes [START_REF] Lewis | Social Selection and Peer Influence in an Online Social Network[END_REF]. Within a large corporation, employees were shown to exhibit a preference for communication with others sharing their gender and basic job functions-at least when they had some flexibility to choose their communication partners [START_REF] Kleinbaum | Discretion Within Constraint: Homophily and Structure in a Formal Organization[END_REF]. A tendency toward homophily has also been observed for social aggregates. For example, organizations seeking to influence policy will tend to coordinate with other organziations that share their beliefs about policy problems [START_REF] Henry | Ideology, Power, and the Structure of Policy Networks[END_REF][START_REF] Henry | Belief Systems and Social Capital as Drivers of Policy Network Structure: The Case of California Regional Planning[END_REF], and municipal governments tend to seek out collaborative ties with other governments on the basis of shared political ideology [START_REF] Gerber | Political Homophily and Collaboration in Regional Planning Networks[END_REF].

Within this very large literature on homophily, it should be noted that there is some variation in how the terms "homophily" and "segregation" are used. For our purposes, "homophily" refers to a dynamic process of tie formation or deletion, where the formation or deletion of ties occurs with probability proportional to the similarity or dissimilarity of network nodes. Homophily therefore refers to one of many possible factors that determine network structure. On the other hand, the term "segregation" is descriptive. Following [START_REF] Freeman | Segregation in Social Networks[END_REF], a segregated network is one where linkages are observed to be concentrated among nodes with similar traitsa characteristic that has sometimes been referred to as observed homophily [START_REF] Kossinets | Origins of Homophily in an Evolving Social Network[END_REF]. Homphily is a natural explanation for segregation, and both empirical and theoretical research shows that even very weak forms of homophily can be a powerful force in the emergence of network segregation [START_REF] Bramoullé | Homophily and Long-Run Integration in Social Networks[END_REF][START_REF] Henry | Emergence of Segregation in Evolving Social Networks[END_REF][START_REF] Kossinets | Origins of Homophily in an Evolving Social Network[END_REF].

On the other hand, segregation may be produced through pathways other than homophily. In particular, many segregated networks emerge in the context of attributes that are malleable and shaped in part by the influences of other network nodes. Influence is therefore a potentially important mechanism of network evolution-under influence, a particular node's neighbors will exert a changing force on that node's attribute, making connected nodes more similar over time. Influence processes have been studied in many contexts including social learning and opinion formation [START_REF] Degroot | Reaching a Consensus[END_REF][START_REF] Friedkin | Social Influence Network Theory: A Sociological Examination of Small Group Dynamics[END_REF][START_REF] Golub | Does Homophily Predict Consensus Times? Testing a Model of Network Structure via a Dynamic Process[END_REF], the diffusion of technological or policy innovations [START_REF] Valente | Network Models of the Diffusion of Innovations[END_REF], and the adoption of culture or behaviors among human and non-human animals [START_REF] Danchin | Public Information: From Nosy Neighbors to Cultural Evolution[END_REF].

These mechanisms of network evolution-homophily and influence-are often studied in isolation, however these are often not independent processes. For example, research on social networks suggests that the degree to which two individuals exercise an influence on one another is proportional to the similarity of these individuals [START_REF] Centola | An Experimental Study of Homophily in the Adoption of Health Behavior[END_REF]. Moreover, in many contexts link structures and nodal attributes co-evolve with one another [START_REF] Lazer | The Co-Evolution of Individual and Network[END_REF]. Studies such as [START_REF] Aral | Engineering Social Contagions: Optimal Network Seeding in the Presence of Homophily[END_REF] underscore the importance of considering both processes occurring in tandem; these authors show that homophily in a social network can change the efficiency of interventions meant to promote the spread of new technologies or behaviors.

Co-evolutionary models of homophily and influence are emerging [START_REF] Centola | Homophily, Cultural Drift, and the Co-Evolution of Cultural Groups[END_REF][START_REF] Dandekar | Biased Assimilation, Homophily, and the Dynamics of Polarization[END_REF][START_REF] Henry | Discovery of Nodal Attributes through a Rank-Based Model of Network Structure[END_REF][START_REF] Lewis | Social Selection and Peer Influence in an Online Social Network[END_REF]. We advance work in this area by proposing a general mathematical model of network evolution where linkages are cut and formed through homophily, and where network nodes take on the attributes of others they are connected to. Our results show that even a minimal diffusion of attributes across linkages are sufficient to prevent the emergence of network segregation, even when individual nodes has a strong preference for segregation. We prove this result mathematically for all large network structures.

A mathematical model of network self-organization

The network evolution process analyzed here P(G 0 , ω 0 , , q, r, K) = (G t , ω t ) ∞ t=0 is defined as a Markov chain and generates a stochastic sequence of networks (also referred to here as graphs). At each time step t, the process produces a graph G t = (V t = V, E t ) consisting of n = |V t | nodes (also referred to as vertices) and m = |E t | links (also referred to as edges). 2 The total number of nodes and linkages does not change during the network evolution process; thus, our attention focuses on the changing distribution of links and nodal attributes in the space over time, rather than on the growth of the network as studied in other lines of research [START_REF] Barabási | Emergence of Scaling in Random Networks[END_REF][START_REF] Souza | Emergence of Tempered Preferential Attachment from Optimization[END_REF][START_REF] Aiello | A spatial web graph model with local influence regions[END_REF][START_REF] Cooper | Scale-free graphs of increasing degree[END_REF].

Measuring network segregation

During the network evolution process, individual nodes use their attributes to assess their similarity to or difference from other nodes, and nodal attributes also change as a result of influences exercised within network connections. Nodal attributes at time t are represented by the function ω t : V → [0, 1] r , where r ∈ N represents the fixed dimensionality of attributes. The assumption that nodal attributes are multidimensional allows for more flexibility in modeling real-world processes where several unique attributes may exercise parallel influences on network structure. The similarity between any two network nodes is captured by a normalized measure of attribute distance, defined as d : [0, 1] r × [0, 1] r → [0, 1]. For x ∈ R, x and x are defined as the smallest integer being greater than or or equal to x and the largest integer being smaller than or equal to x, respectively. Following [START_REF] Henry | Emergence of Segregation in Evolving Social Networks[END_REF], attribute distances are converted into a discrete measure d K (•, •) by fixing K ∈ N and partitioning all distances into K bins such that

d K (x, y) = Kd(x,y) K ifd(x, y) > 0, 1 K otherwise.
The purpose of discretizing distances by introducing K bins is only to simplify calculations in this paper; our results do not depend on this approach. It should also be noted here that the actual distances d(x, y) are assued to fall in the interval [0, 1], which ensures that any discretized distance d K is no more than 1 and no less than 1/K. Using this distance function, the case where K = 1 puts all attribute distances in the same bin, therefore "erasing" the effect of attributes on network structures.

The term edge length refers to the attribute distance of nodes that are connected by a particular network link-thus, actors with very similar attributes are connected by "short edges" whereas actors who are very different are connected by "long edges."

Networks comprised primarily of short edges are indicative of network segregation, which coupled with a multimodal distribution of attributes, also implies the existence of a community structure. Two additional variables help to track the emergence or suppression of network segregation. The global center of mass M t is unique to each network G t and is defined as the mean attribute across all nodes at time t,

M t = 1 n v∈Vt ω t (v).
The local center of mass M t (v) is unique to each network node v at a particular time step, and is defined as the mean attribute of that particular node's neighbors in the network:

M t (v) = 1 |N t (v)| u∈Nt(v) ω t (u), provided that |N t (v)| ≥ 1. N t (v) = {u ∈ V t : vu ∈ E t } denotes the set of v's neighbors at time t.

Dynamics of the evolutionary process: Homophily and influence

The evolutionary process begins at t = 0, with an initial network G 0 = (V 0 = V, E 0 ) on n = |V | vertices, m = |E| edges, and with initial vertex attributes ω 0 : V → [0, 1] r . The network G 0 may have any structure and vertices might be distributed in any way in the attribute space. Time-step t, for t ≥ 1, is defined to be the transition between G t-1 and G t .

At time t, and independently of the history of the process prior to t, the network undergoes one of two processes: a rewiring process, where a random link is rewired via homophily, and an influence process, where attributes are transmitted through network ties. At each time step, influence occurs with probability ∈ (0, 1); otherwise (that is, with probability 1 -) the rewiring process is performed. The parameter is important because in most networks there will be far fewer nodes than linkages, and allows us to adjust the relative speed of influence and rewiring processes in terms of the proportion of all nodes and links that have been updated by these processes at least once. More information about the behavior of with respect to the relative speed of influence and rewiring is provided in the Supplemental Information.

When influence occurs, a random node v ∈ V t-1 is chosen. Since influence is interpreted as a process of adopting the attributes of one's network neighbors, we assume that v's neighbors exert a force that pulls v towards its own local center of mass (that is, the average attribute of v's neighbors). The degree to which node v fully adopts the attributes of its neighbors may vary, and is captured by an additional parameter q ∈ (0, 1]. If q = 1, then v jumps immediately to its local center of mass; for q < 1, on the other hand, v will move only part way. Thus, the parameter q represents the degree to which attributes are resistant to change. More precisely, if N t-1 (v) is non-empty, then

ω t (v) = (1 -q) • ω t-1 (v) + q • M t-1 (v);
otherwise (that is, when N t-1 (v) = ∅), ω t (v) = ω t-1 (v). Attributes of other nodes do not change. A schematic of the influence process is depicted in the top panel of Figure 1.

Figure 1: Network evolution process at time t. The figure depicts a schematic of the process for parameters q = 0.5 and K = 8. Nodal attributes are represented in the horizontal position of nodes. At time t, either a single node is selected for influence (probability ) or a single edge is selected for rewiring (probability 1 -). Under influence, the node selected for influence (A in the figure) is pulled to its local center of mass M t (A), or the average attribute of all neighbors. The attribute of A then shifts q(M t (A) -ω(A)), or from ω(A) = 0.5 to ω(A) = 0.604 in this example. Under rewiring, an edge (AD) is selected uniformly at random and is deleted with probability d K (ω(A), ω(D)) = 0.375 (proportional to its edge length). A and D are then chosen with equal probability to rewire the link. The selected node (A in this case) assesses all possible edge lengths in the network and, under homophily, is more likely to create a link with a node having similar attributes than with a dissimilar node.

Homophily is modeled in the network rewiring process. When rewiring occurs, a random edge uv ∈ E t-1 is chosen uniformly at random. The nodes u and v assess their attribute distance d K (ω t-1 (u), ω t-1 (v)), and make a choice to rewire the linkage or to leave it in place. Due to homophily, nodes are assumed to prefer linkages with other nodes holding shared or similar attributes-thus, we assume that ties are rewired with probability proportional to their edge length (meaning that linkages between nodes with dissimilar attributes are more likely to be rewired). Specifically, the probability of tie deletion between u and v is d K (ω t-1 (u), ω t-1 (v)). 3 When a tie is deleted, it is then rewired by selecting one of its endpoints with equal probability (set w := u or w := v according to the choice made), removing uv, choosing a vertex x ∈ V t-1 at random, and then finally adding wx. The vertex x is selected so that creating short edges is more probable than creating long ones. Formally, the vertex x ∈ V t-1 is chosen with probability proportional to 1/d K (ω t-1 (w), ω t-1 (x)); that is, with probability equal to

1/d K (ω t-1 (w), ω t-1 (x)) v∈Vt-1 1/d K (ω t-1 (w), ω t-1 (v)) ≥ 1 v∈Vt-1 K = 1 Kn .
In order to get an upper bound, note that

1/d K (ω t-1 (w), ω t-1 (x)) v∈Vt-1 1/d K (ω t-1 (w), ω t-1 (v)) ≤ K v∈Vt-1 1 = K n .
Thus, when a link is deleted, it is randomly assigned to one of the actors in the dyad, who then creates a new link with another network node chosen on the basis of attribute similarity. 4 This rewiring process is depicted in the bottom panel of Figure 1.

Results

As typical in random graph theory [START_REF] Janson | Random Graphs[END_REF], all results are asymptotic, that is, for m tending to infinity, and thus for n tending to infinity as well. We say that an event holds asymptotically almost surely (a.a.s.) if it holds with probability tending to one as m → ∞. Throughout, we will use the stronger notion of with extreme probability (w.e.p.) in favor of the more commonly used a.a.s., since it simplifies some of the proofs. We say that an event holds w.e.p. if it holds with probability at least 1 -exp(ω(m) ln m) as m → 1 (ω(m) is any function tending to infinity together with m). Thus, if we consider a polynomial number of events of which each holds w.e.p., then w.e.p. all events hold. For technical reasons, we will assume in our theorems that ln 7 n m/n n/ ln 3 n. This basic model framework allows for a rigorous analysis of systems characterized by varying levels of homophily and influence operating in tandem. Before moving to the technical arguments needed to analyze this model, it is useful to provide a brief synopsis of the main results.

Synopsis of findings

We show that even minute levels of influence are ultimately sufficient to cause vertex attributes to converge to a single point, even in the presence of strong homophily processes. This will happen more or less quickly under different scenarios, and in some cases it is possible to predict with greater precision the process by which vertex attributes converge.

When the process begins at t = 0, vertex attributes may follow any distribution and the network G 0 may take on any initial structure. As the network undergoes subsequent rewirings, eventually each endpoint of each link has been rewired at least once-we call this time T . At this point, a sufficient amount of randomness has been introduced into the process, and we are able to predict the behavior of the model with high probability. We are able to establish an upper bound for T that is of order m log m (see Lemma 1).

After time T , it is useful to split the analysis of the network evolution process into two cases: first, where network rewirings do not take into account vertex attributes (the "zero homophily" case where K = 1, in which all edges are assigned the same distance, and thus independently of the underlying network, a rewiring is chosen uniformly at random), and second, where vertices cut and form ties on the basis of attribute similarity (the "homophily" case where K ≥ 2; in which a rewiring is more likely to appear between close vertices). Analyzing the zero homophily case is useful as results from this more specific model may be applied to the analysis of models with either weak or strong homophily processes (K ≥ 2 with K small or large, respectively).

In the zero homophily case, we can predict the specific process by which attributes converge. After time T , the local center of mass of each vertex is equal to the global center of mass in expectation, and in fact with high probability all local centers of mass are well concentrated around the global center of mass (see Lemma 2(i)). This means that the attributes of any given node's neighbor are similar to a random sample of vertex attributes drawn from the entire network. At this point in time, network structures will be similar to binomial random graphs. While vertex attributes have not necessarily converged at this point, these results imply that by time T any segregation seen in initial network conditions will have been destroyed by the influence processes without homophily supporting cross-group partitions. After at most T = Θ( -1 n ln n) more steps, all vertex attributes have then finally converged to the global center of mass. This result is given in Theorem 3.

In the homophily case, Lemma 2(ii) demonstrates that by time T , the local centers of mass are being pushed away from their boundaries towards the global center of mass. This means that the local centers of mass will typically be some fraction of the distance between that vertex's attribute and the global center of mass. We can specify an upper bound on this distance, which increases as the tendency towards homophily increases (that is, as K gets larger). Networks at this point exhibit network segregation as studied in [START_REF] Henry | Emergence of Segregation in Evolving Social Networks[END_REF] in that linkages in the network tend to be "short," that is, connecting vertices with similar attributes. If vertex attributes ω t (v) maintain a multi-modal distribution at this point, then a clear community structure will emerge.

In both cases (that is, for any value of K), vertex attributes begin to converge after time T up to some time T + T . In the absence of homophily, all vertex attributes at time T + T will be very close (within o(ln -2 n) = o(1)) of the global center of mass (see Theorem 3). 5 The bigger n is, the closer all vertex attributes will be. This is because, for large n, the concentration results are stronger and the behavior of the whole network is even more predictable. An upper bound for T + T is identified in Theorem 3. Moreover, we are able to predict precisely the process by which this convergence to the global center of mass takes place, in terms of how the average distance between each individual vertex and the global center of mass changes over time. The behavior of this random variable is predicted using the differential equation method and is specified in Theorem 12.

In the presence of homophily, we determine an upper bound for the time when all vertex attributes are within 1/K of each other (see Theorem 5). At this point, the attributes of nodes are within a small enough interval that the distinctions between vertex attributes begin to disappear, meaning that homophily no longer exercises a noticeable influence on the network structure. From this point on, findings from the K = 1 case may be applied to show that, after another T time steps, the local centers of mass are well concentrated around the global center of mass as shown in Lemma 2(i).

The following sections analyze the model in more depth by asking (and answering!) a series of questions about the model's behavior with some constraints placed on parameters. Ultimately, these answers allow us to make precise predictions about how the model behaves without any parameter constraints. Much of the mathematical logic underlying these results is contained in the proofs, which are included in the Supplemental Information for interested readers.

How long does it take to rewire each edge endpoint at least once?

Each time a rewiring occurs, an edge is selected uniformly at random (that is, a given edge is selected with probability 1/m), and then one of the endpoints of this edge is selected uniformly at random (that is, with probability 1/2). So in each rewiring step, one of the 2m edge endpoints is selected uniformly at random and is associated with a random vertex. Although vertices that are more similar to the selected endpoint have a higher probability of being chosen, a given vertex is always selected with probability at least 1/(Kn). These steps occur independently of the history of the process.

Based on the following lemma, we know that the time at which each edge endpoint has been rewired at least once is no later than T , which is of order m ln m. A proof of Lemma 1 is provided in the Supplemental Information.

Lemma 1. Consider the evolutionary process P(G 0 , ω 0 , , q, r, K) = (G t , ω t ) ∞ t=0 . Let ω(m) be any function that tends to infinity as m → ∞, and let T be the first time every edge has both endpoints rewired at least once. Then, a.a.s.

T ≤ 2Km 1 - (ln m + ω(m)) = Θ(m ln m). (1)
It should be noted that this upper bound is a function of both K and . This is because, in addition to linkages being rewired, vertex attributes are also being updated as a result of the influence process. If the only process occurring were the rewiring of links, then from the well-known coupon collector problem it would be sufficient to wait (1 + o(1))2m log m time steps to rewire all 2m edge endpoints. 6 But since some time steps are used for influence rather than rewiring, it is necessary to wait (1 + o( 1))(2m/(1 -)) log m rounds to ensure enough endpoints are rewired. Finally, since edge endpoints are not selected uniformly at random (i.e., endpoints associated with long edges have a higher chance of being selected), it is necessary to wait even slightly longer (a multiplicative factor of K is sufficient) to make sure that the endpoints of short edges are rewired as well.

Where are local centers of mass relative to the global center of mass?

After the rewiring of every edge endpoint at time T , we can begin to estimate the distance between the global center of mass at time t (M t ) and the average attribute of vertex v's neighbors (v's local center of mass, denoted M t (v)).

Suppose first that K = 1. In this situation, attributes' differences are irrelevant and edges are rewired without any tendency towards homophily; that is, regardless of whether the selected edge is long (connecting vertices with very different attributes) or short (connecting vertices with very similar attributes). The random graph at time T is relatively easy to study. In particular, for a given edge e ∈ E 0 from the initial network G 0 , t ≥ T , and any two vertices x and y, the probability that e connects x and y at time t is 2/n 2 . Indeed, with probability 1/n 2 the first endpoint was associated with x and the second one with y, at the last time they were rewired. The same property holds when x is swapped with y. It follows that

P(xy ∈ E t ) = 1 -1 - 2 n 2 m = 1 -exp - 2m n 2 + O m n 4 = 2m n 2 + O m 2 n 4 = 2m n 2 1 + O m n 2 = (1 + o(ln -3 n)) 2m n 2 , (2)
provided that m = o(n 2 / ln 3 n).

In this situation, the expected degree of vertices in the network is (1 + o(1))2m/n, and networks exhibit properties similar to those observed in binomial random graphs G(n, p) with p = 2m/n 2 . In particular, the local centers of mass will be very close to the global one, provided that the network is dense enough to ensure that a given vertex's neighbors are representative of the entire set of network nodes.

Suppose now that K ≥ 2. In this case, network rewiring is driven by some degree of homophily where long edges (connecting dissimilar vertices) are terminated with higher probability than short edges, and where short edges are formed with higher probability than long edges. This process tends to generate segregated, "attribute-close" networks where most edges are short, connecting vertices with similar or shared attributes; see [START_REF] Henry | Emergence of Segregation in Evolving Social Networks[END_REF] for more details. Therefore, it is expected that the local center of mass of a vertex v lies between v and the global center of mass.

Indeed, we are able to specify more precisely the distance between the local centers of mass and the global center of mass, in both the K = 1 and K ≥ 2 cases. Since each dimension may be treated independently, we assume without loss of generality that r = 1. These distances are specified in Lemma 2.

Lemma 2. Consider the social process

P(G 0 , ω 0 , , q, 1, K) = (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n). Let C > 0.
Then, w.e.p. for every T ≤ t ≤ n C and every v ∈ V t , the following holds

(i) If K = 1, then M t (v) = (1 + o(ln -3 n))M t . (ii) If K ≥ 2, then M t (v) ≥ (1 + o(1))K -6 M t + o(ln -5 n) and M t (v) ≤ 1 -(1 + o(1))K -6 (1 -M t ) + o(ln -5 n).
At this point it is possible to have local centers of mass that are outliers, in the sense that vertices are closer to the global center of mass than their neighbors. In this case, local centers of mass can be pulled away from the global center because of the influence of their neighbors, but this does not substantially affect the global dynamics. However, once all vertex attributes are trapped in a particular interval, they will always remain within that interval. This observation-which we elaborate on in the following sections-tells us that local centers of mass that are outliers and close to the boundaries will tend to be pushed towards the global center of mass, causing the length of this interval in which all vertex attributes are "trapped" to shrink over time.

How quickly do vertex attributes converge in the absence of homophily?

We now consider the model's behavior in the absence of homophily-that is, when K = 1 and edge rewirings are independent of vertex attributes. These results may then be applied with some modifications to the unconstrained case where K ≥ 1. For the sake of brevity, we state the final result for the K = 1 case here as Theorem 3. The Supplemental Information contains a formal proof of Theorem 3 as well as a full explanation of the logic of how this result is obtained through the analysis of a series of more simple models. Theorem 3. Consider the evolutionary process P(G 0 , ω 0 , , q, r,

1) = (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n) and ≥ n -C for some C ≥ 1,
and recall the definition of T in (1). Then, a.a.s.

ω T + T (v) -M T = o(ln -2 n) = o(1)
for every v ∈ V T + T , where T = -1 (2 + ε)n ln n for some ε > 0.

Note that a.a.s.

T + T = Θ(m ln m) + Θ( -1 n ln n) = O(n C+1 ln n).
Theorem 3 says that, at time T + T and for K = 1, the distance between each vertex's attribute and the global center of mass is o(ln -2 n); in words, the bigger n, the closer all vertex attributes are. The intuition behind this is that as the value of n grows, the process becomes more predictable (since the variance decreases by the law of large numbers). More precisely, all vertex attributes are in some interval (a, b) of length o(ln -2 n) and, once all attributes are in this interval, they will always remain there.

What is the process by which attributes converge in the absence of homophily?

Above, we demonstrated that vertex attributes will converge when K = 1. Additionally, it is possible to predict the convergence process between time T and T + T . This is done using the differential equation (DE) method [START_REF] Wormald | The differential equation method for random graph processes and greedy algorithms[END_REF], which allows us to show that a.a.s. the average distance between vertex attributes and the global center of mass at a given time period decreases in a predictable way. An introduction to the DE method is provided in the Supplemental Information. Formally, let

W t = v∈Vt |ω t (v) -M t |.
The random variable W t represents the overall deviations between the global center of mass and all individual local centers of mass at time t. Corollary 4 specifies how this random variable behaves over time.

Corollary 4. Consider the evolutionary process P(G 0 , ω 0 , , q, r, 1) = (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n) and ≥ n -C for some C ≥ 1. Then, a.a.s.

W t = (1 + o(1))W T exp - q (t -T ) n
for every t such that T ≤ t ≤ T + t f , where T is defined in (1) and

t f = n q ln ln n -ln n W T .
This result is a corollary to Theorem 12, which is explained in further detail (and proven) in the Supplemental Information.

Model behavior with homophily, K ≥ 2

In a homophilous network, there is a bias for the termination of long edges and the creation of short edges. Suppose that all vertex attributes lie in the interval [a, b] (as usual, we may treat all dimensions independently and so it is enough to focus on one dimension). It follows from Lemma 2(ii) that when vertex v is selected for influence at time t ≥ T , it is moved away from at least one border of the attribute space (i.e., the value a or b). While the exact updated attribute of each vertex selected for influence cannot be predicted, it is known that the global center of mass is positioned far enough from one end of the interval such that all vertices selected for influence are pushed away from that end. Unfortunately, the global center of mass might be shifting during this process, and it is likely impossible to precisely predict how the global center of mass moves over time. This is in contrast to the result for the K = 1 case (see Theorem 3), which says that the global center of mass does not drift substantially between times T and T + T .

Fortunately, it is possible to show that after at most 3 -1 n ln n steps, w.e.p. the maximum distance between any pair of nodes shrinks (in each dimension) by a multiplicative factor of at least ε := q(13K 12 n ln n) -1 . That is, if the distance is D at some time t, at time t + 3 -1 n ln n it is w.e.p. at most D(1 -ε). This is an upper bound only, and it is expected that the convergence process is in fact more rapid. A proof of Theorem 5 is provided in the Supplemental Information: Theorem 5. Consider the evolutionary process P(G 0 , ω 0 , , q, r, K)

= (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n) and ≥ n -C for some C ≥ 1.
Then, a.a.s. for every pair u, v ∈ V t we have

|ω t (u) -ω t (v)| ≤ √ r 1 - q 13K 12 n ln n (t-T )/(3n ln n) ≤ √ r exp - q (t -T )/(3n ln n) 13K 12 n ln n
for every t such that T ≤ t = O( -1 n 2 ln 2 n) (the random variable T is defined in (1)). In particular, if t = cq -1 -1 n 2 ln 2 n for some constant c > 0, then a.a.s. for every pair u, v ∈ V t we have

|ω t (u) -ω t (v)| ≤ (1 + o(1)) √ r exp - c 39K 12 .
This result implies that at some time

T ≤ 1 2 ln r + ln K + 1 39K 12 (q -1 -1 n 2 ln 2 n) = O( -1 n 2 ln 2 n)
a.a.s. all vertex attributes are within distance 1/K of each other. At this point, the attributes of nodes are within a small enough interval that the distinctions between vertex attributes begin to disappear, meaning that homophily no longer exercises a noticeable influence on the network structure. From this point on, findings from the K = 1 case may be applied to show that, after another T time steps, the local centers of mass are well concentrated around the global center of mass as shown in Lemma 2(i). With this result in hand, the behavior of the process can be predicted quite easily, and a.a.s. all the vertex attributes converge to a single point.

Corollary 6. Consider the evolutionary process P(G 0 , ω 0 , , q, r, K) = (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n) and ≥ n -C for some C ≥ 1. Let T be the first time all pairs of vertices are within distance 1/K (or T = ∞ if this never happens). Then, a.a.s.

T ≤ 1 2 ln r + ln K + 1 39K 12 (q -1 -1 n 2 ln 2 n) = O( -1 n 2 ln 2 n)
Moreover,

W t = (1 + o(1))W T +T exp - q (t -T -T ) n
for every t such that T + T ≤ t ≤ T + T + t f , where T is defined in (1) and

t f = n q ln ln n -ln n W T +T .
In particular, at time T + T + t f = O( -1 n 2 ln 2 n) the average distance between vertices is o(1).

Examining dynamics through computational simulation

This analysis shows that, for all network structures, very small amounts of influence will lead to a convergence in attributes over time even when homophily (a polarizing force) is very strong. Thus, in theory, even small amounts of influence are sufficient to overcome even strong patterns of network segregation. The speed of convergence in attributes will of course depend on the relative strength of the homophily and influence processes. The preceding results allow us to predict with more precision the behavior of the system over time, in terms of how quickly the local centers of mass converge to the global center of mass for a given network. These dynamics are illustrated in Figure 2, which plots the maximum distance between local and global centers of mass over time, for 1) varying strengths of influence for a given level of homophily (left panel), and 2) varying levels of homophily for a given influence parameter (right panel).

The mathematical model developed here allows for a strong, generalized prediction about the behavior of networked systems over time. At the same time, the methods used here require limiting our attention to relatively simple network evolution processes, meaning that we face a fundamental trade-off between Figure 2: Upper bounds on attribute convergence speeds for varying levels of influence and homophily model complexity and strength of predictions. Computational simulations are one way to introduce more complexity into these models, and also illustrate the evolutionary dynamics discussed in this paper. Thus, to complement the main mathematical model, we conducted a series of computational simulations of the influence and network rewiring process in small, random networks. 7

Computational model setup

Our computational simulations begin with small, undirected random networks on 30 vertices and 44 edges (yielding a fixed network density of about 0.1). At initialization agents are assigned, uniformly and at random, an attribute value of 0 or 1. Links are then assigned with probability proportional to attribute similarity, so that initial networks exhibit high degrees of segregation and community structure (see, for example, the top panel of Figure 4). By starting with highly segregated initial network structures, we create conditions that are most favorable for the maintenance of network segregation over time.

With the initial networks in place, at each time step the system undergoes an influence process (where randomly selected vertices update their attributes based on network position), followed by an edge rewiring process (where randomly selected edges are deleted and reallocated to non-adjacent vertices). 8 When a vertex i is selected for influence, it moves a fraction of the distance between its own attribute and i's local center of mass (i.e., the average attribute of vertex i's neighbors). This fraction is governed by a model parameter q ∈ [0, 1] as defined above.

Edge rewiring, on the other hand, progresses in a slightly different manner from the mathematical model presented in this paper. When an edge is selected for rewiring, it is randomly rewired by choosing a pair of non-adjacent vertices with probability proportional to the attractiveness of that pair. In order to account for more drivers of network formation, attractiveness of a potential link between two nodes i and j is allowed to be a function of three factors, including the similarity of nodal attributes (representing the tendency towards homophily), the number of paths of length 2 between i and j (representing the tendency towards transitivity, or so called triadic closure), and the degree of nodes i and j (representing the tendency towards forming linkages with high-degree actors, as in a preferential attachment model). In general, the attractiveness of a link between non-adjacent vertices i to j is assumed to be

a i→j = 1 d K (i, j) + p closure T (i, j) + p degree d(j),
where K is a simulation parameter representing the strength of the homophily effect, d K (i, j) is the discretized distance between vertices i and j (as described earlier), p closure is a simulation parameter representing the strength of triadic closure, T (i, j) is the number of paths of length 2 between vertices i and j, p degree is a simulation parameter representing the strength of vertex degree, and d(j) is the degree of j, that is, the number of vertices adjacent to j. Thus, the attractiveness of two non-adjacent vertices depends on their distance, the degree of the incoming vertex, and the number of common neighbors of i and j. When an edge is selected for rewiring, the attractiveness scores of non-adjacent vertices are calculated. The resultant set of attractiveness scores is then converted into a probability distribution from which a particular dyad is selected-the edge selected for rewiring is then relocated to this randomly-chosen dyad.

The attractiveness of pairs of vertices based on these effects is illustrated in Figure 3. From the perspective of a particular vertex (labeled Ego in Figure 3), different potential linkages (non-adjacent vertices in the far left panel) have varying levels of attractiveness. Potential links are depicted as dashed red lines, and their attractiveness depends on the three simulation parameters triadic closure, degree, and homophily (K). 9 With higher triadic closure parameters, Ego will tend to view linkages that create triangles as more attractive, and therefore Ego will want to form a link with A in this schematic. With higher degree parameters, Ego will tend to view linkages with high degree vertices (e.g., vertex B) as more attractive. With higher homophily parameters, Ego will tend to view links as more attractive when the linkage reduces the difference between Ego's attribute and Ego's local center of mass (e.g., a link with vertex C). The right side of the figure displays the distribution of the local centers of mass of each vertex, relative to the global center of mass (the global center of mass is indicated by the vertical reference line in the distribution plot). In this particular example, the local centers of mass collapse around the global center of mass after 65 time steps. This is also seen in the network diagrams, which show the decay of segregation around shared attributes early in the process to a well-mixed network where linkages are independent of starting attributes (node color) in the final time step.

Simulation results

Approximately 1,800 simulations were run with three model parameters-homophily, transitivity, and degree-assigned uniformly at random from [0, 100] and q assigned uniformly at random from [0.15, 1] at each Figure 3: How simulation parameters change the relative attractiveness of pairs of vertices simulation run. Consistent with our findings reported earlier, these simulations show that in all cases-even when additional network evolution dynamics are taken into account-vertex attributes always converge such that local centers of mass eventually collapse to the global center of mass. These dynamics are summarized in Figure 5. This figure plots the distribution of maximum distance between all local centers of mass and the global center of mass, for each simulation, and at different stages of the process. In order to visualize all simulations on a common scale, the distributions are represented at the initial time step in the far left, and subsequent distributions are for one-tenth of the final time step, two-tenths of the final time step, and so on. In the final time step, the maximum distance between the global and local centers of mass is no more than 0.05.

Figure 5 shows a large amount of variation in convergence patterns, however in aggregate we see a clear trend towards attribute convergence. But while attributes tend towards a single point, it is useful to examine how variation in the simulation parameters explain the speed of attribute convergence. Figure 6 summarizes these patterns by fitting an OLS linear regression model with time to convergence as the dependent variable, and simulation parameters as independent variables. Specifically, we model time to convergence as a linear combination of simulation parameters using the individual simulation run as the unit of analysis:

Y = b 0 + b 1 • p closure + b 2 • p degree + b 3 • K + b 4 • q + e,
where Y is a simulation's time to convergence, b 0 , b 1 , b 2 , b 3 , and b 4 are constant coefficients, e is an error term, and p closure , p degree , K, and q represent (respectively) the model parameters described above: the tendency towards triadic closure, the tendency to form ties with high-degree actors, homophily, and influence.

These results indicate that triadic closure and homophily have complementary effects on convergence speeds; both are positive, with roughly the same magnitude. This means that homophily and closure both tend to increase convergence times-that is, network segregation will take longer to disappear when tie formation is driven by homophily and triadic closure. This does make intuitive sense. If a network exhibits segregation, then triadic closure will tend to amplify the formation of ties among similar vertices because neighbors of neighbors will also tend to have similar attributes. On the other hand, introducing triadic closure does not prevent attributes from converging any more than homophily does.

Seeking out vertices with high degree appears to speed the process of convergence. This also makes intuitive sense, since this is a process that allows ties to be formed independently of attributes. So while 6: Ordinary least squares regression model of effect of computational simulation parameters on time to attribute convergence triadic closure will tend to create more short edges in the presence of network segregation, forming links on the basis of degree has nothing to do with attributes and provides a way for vertices to "escape" from homogenous network neighborhoods. The overall effect of degree-seeking is larger than both the homophily and triadic closure effects, meaning that degree-seeking behavior will tend to decay network segregation much faster than homophily or closure can maintain it.

Conclusion

This paper shows that influence processes are able to overcome the polarizing effect of homophily in creating segregated networks, even when strong forms of homophily are coupled with a relatively weak influence process. We prove mathematically that asymptotically almost surely, the size of the interval containing all vertex attributes tends to zero as t approaches infinity. In other words, the distinctions between vertices based on malleable attributes eventually disappear, which in turn prevents homophily from influencing emergent network structures.

Network segregation and related concepts, such as community structure, are well-studied phenomena in self-organizing networks. But why does network segregation emerge, and how is it maintained over time? Developing better models of these dynamics is important because they can suggest ways to manage the problems that arise from segregated networks-such as conflict or mistrust between social groups, or difficulties in searching for diverse sources of information.

While small amounts of homophily are sufficient to produce segregated networks when attributes are fixed, once malleability of attributes is introduced it becomes difficult to model the persistence of network segregation over time. We show mathematically that an important class of models, those where attributes move (potentially very slowly) towards one another, cannot maintain network segregation indefinitely. While our definition of influence represents one of many possibilities of how attributes change dynamically, these results are more powerful than those inferred from simulations that can only investigate a finite number of possible scenarios (and yet, the results are also supported by computational simulations that include more complex network evolution processes). With this research, we hope to provide a baseline for more investigations into the micro-level processes that generate and maintain the network segregation that is observed empirically across a wide range of self-organizing networks.

6 Supplemental Information

Introduction to the Differential Equation method

The general setting that is used in the DEs method [START_REF] Wormald | The differential equation method for random graph processes and greedy algorithms[END_REF] is a sequence of random processes indexed by n (which in our case is the number of objects in any set V t ). The aim is to find properties of the random process in the limit as n → ∞. The conclusion we aim for is that variables defined on a random process are well concentrated, which informally means that with high probability they are very close to certain deterministic functions. These functions arise as the solution to a system of ordinary first-order differential equations. One of the important features of this approach is that the computation of the approximate behavior of processes is clearly separated from the proof that the approximation is correct.

To show that the random variables in a process usually approximate the solution of differential equations, we need to use large deviation inequalities. These inequalities are often used to give an upper bound on the probability that a random variable deviates very far from its expected value. In a typical situation with a random process, the aim is to show that the random variable Y t of interest is sharply concentrated. In fact,

Y t -Y 0 = t i=1 (Y i -Y i-1 ).
If the differences Y i -Y i-1 are independent, then the Chernoff bound is very useful, see for example Theorem 2.8 [START_REF] Janson | Random Graphs[END_REF].

Theorem 7. Let X be a random variable that can be expressed as a sum X = n i=1 X i of independent random indicator variables where X i ∈ Bernoulli(p i ) with (possibly) different p i = P(X i = 1) = E[X i ]. Then the following holds for t ≥ 0:

P(X ≥ E[X] + t) ≤ exp - t 2 2(E[X] + t/3) , P(X ≤ E[X] -t) ≤ exp - t 2 2E[X]
.

In particular, if ε ≤ 3/2, then

P(|X -E[X]| ≥ εE[X]) ≤ 2 exp - ε 2 E[X] 3 . (3)
Strong concentration results of a sequence of not necessarily independent random variables can also be obtained if two consecutive random variables do not differ by too much and have the same (or similar) expectations. This is formalized using the concept of martingales, introduced next. Definition 8. A martingale is a sequence X 0 , X 1 , . . . of random variables defined on the random process such that E

[X n+1 | X 0 , X 1 , . . . , X n ] = X n .
In most applications, the martingale satisfies the property that

E[X n+1 | X 0 , X 1 , . . . , X n ] = E[X n+1 | X n ] = X n .
As a simple example, consider the following "random walk." Toss a coin n times. Let S n be the difference between the number of heads and the number of tails after n tosses. S n is a martingale. Indeed,

E[S n+1 | S n ] = S n + 1 2 • 1 + 1 2 • (-1) = S n .
Clearly, the expected value of S n is zero. Thus, it is natural to expect that S n stays relatively close to zero. The following well-known Hoeffding-Azuma inequality serves as a tool to investigate this, see for example Theorem 2.25 [START_REF] Janson | Random Graphs[END_REF].

Lemma 9. Let X 0 , X 1 , . . . be a martingale. Suppose that there exist constants c k > 0 such that

|X k -X k-1 | ≤ c k for each k ≤ n. Then, for every t > 0, P(X n ≥ E[X n ] + t) ≤ exp - t 2 2 n k=1 c 2 k , P(X n ≤ E[X n ] -t) ≤ exp - t 2 2 n k=1 c 2 k .
This is often applied with t growing much faster than √ n and the c k all small non-zero integers. In the martingale discussed above c k = 1 for all k. Hence,

P(|S n | ≥ α √ n) ≤ 2 exp (α √ n) 2 2n = 2 exp α 2 /2 ,
which is arbitrarily small for α large enough. Finally, let us mention that the Hoeffding-Azuma inequality can be generalized in many ways: an analogous inequality holds for supermartingales (E[X n+1 |X n ] ≤ X n ) as well as submartingales (E[X n+1 |X n ] ≥ X n ). Our proofs use the supermartingale method as described in Corollary 4.1 of [START_REF] Wormald | The differential equation method for random graph processes and greedy algorithms[END_REF]. We will use the following lemma, that follows from the generalized Hoeffding-Azuma inequality.

Lemma 10. Let G 0 , G 1 , . . . , G L be a random process and X t a random variable determined by G 0 , G 1 , . . . , G t , 0 ≤ t ≤ L. Suppose that for some real β and γ,

E(X t -X t-1 | G 0 , G 1 , . . . , G t-1 ) < β and |X t -X t-1 -β| ≤ γ for 1 ≤ t ≤ L. Then for all ε > 0, P For some t with 0 ≤ t ≤ L : X t -X 0 ≥ tβ + ε ≤ exp - ε 2 2Lγ 2 .

The role of the parameter

The parameter controls the relative speed of the influence and rewiring process in the network. Note that setting = 0.5 (such that influence and rewiring occurs with equal probability at each time step) will cause attribute updating (via influence) to occur for a given node far more frequently than link rewiring (via homophily) for a given edge. This is a result of most networks having far more links than nodes.

To allow for the direct specification of the relative speed of rewiring versus influence, let = (n, m) to be a function of the number of nodes and edges, and let tend to zero as n → ∞. Let 0 be such that

0 1 -0 = n m ,
and consider the evolutionary process run with parameter 0 . Note that when t = cn/ 0 steps are performed (for some c ∈ (0, ∞)), we expect 0 t = cn influence steps and so an 1 -e -c fraction of vertices should be hit.

On the other hand, after t steps, the number of rewirings is expected to be (1 -0 )t = cn(1 -0 )/ 0 = cm and so we expect to hit an 1 -e -c fraction of edges as well. Note also that 0 = (1 + o(1))n/m = o(1), provided that n = o(m) which is usually the case. For n = cm for some c ∈ (0, 1) we have 0 = c/(1 + c) > 0.

There are three possible behaviors that might be desired for different scenarios:

• the two processes are of the same speed: = 0 ,

• there are more influence steps than rewiring ones: > 0 ,

• there are more rewiring steps than influence steps: < 0 .

Proof of Lemma 1

Lemma 1 specifies the maximum length of time that is required to rewire each edge endpoint at least one time, and is stated in the main paper. In particular, Lemma 1 says that the time at which each edge endpoint has been rewired at least once is no later than T , which is of order m ln m.

Lemma. Consider the evolutionary process P(G 0 , ω 0 , , q, r, K) = (G t , ω t ) ∞ t=0 . Let ω(m) be any function that tends to infinity arbitrarily slowly as m → ∞, and let T be the first time every edge has both endpoints rewired at least once. Then, a.a.s.

T ≤ 2Km 1 - (ln m + ω(m)) = Θ(m ln m). (4)
Proof. Define T * = 2Km 1-(ln m + ω(m)) for some function ω(m) tending to infinity arbitrarily slowly. Fix a permutation of length 2m of all edge endpoints in the initial network G 0 . For i ∈ {1, 2, . . . , 2m}, let A i be the event that the ith endpoint is not rewired after T * steps. Note that at every step of the process, a given endpoint is rewired with probability at least (1 -)/(2Km). Therefore, independently of the previous steps, we have that for every i ∈ {1, 2, . . . , 2m}, and denoting by ω(m) any function tending to infinity with m arbitrarily slowly,

P(A i ) ≤ 1 - 1 - 2Km T * = exp - ( 1
-)T * 2Km + O T * m 2 = (1 + o(1)) exp (-ln m -ω(m)) = o(m -1 ).
In order to prove part (ii), it is convenient to think about the rewiring process as before (see the discussion right before (2)). Since each endpoint is rewired at least once at a given time t ≥ T , we can fix an endpoint of some edge and then focus on the last attempt to rewire this endpoint. With probability at least 1/K (and clearly at most 1) the rewiring is performed and a given vertex is chosen with probability at least 1/(Kn) (at most K/n, respectively). This implies that for any endpoint and any vertex x with probability at least 1/(K 2 n) (at most K/n, respectively) this endpoint is associated with x. Note that these bounds hold independently of the previous steps already performed. Performing the same calculations as in [START_REF] Aral | Engineering Social Contagions: Optimal Network Seeding in the Presence of Homophily[END_REF] we get

P(xy ∈ E t ) ≥ 1 -1 - 2 K 4 n 2 m = (1 + o(ln -3 n))
2m K 4 n 2 , and

P(xy ∈ E t ) ≤ 1 -1 - 2K 2 n 2 m = (1 + o(ln -3 n)) 2K 2 m n 2 .
Since M t (v) ≥ 0 for every v (deterministically), the statement trivially holds when M t = o(ln -5 n). Hence, we may assume that M t = Ω(ln -5 n). Using the notation as in part (i), we have

E[X] ≥ (1 + o(1)) 2mM t K 4 n = (1 + o(1)) dM t K 4 ln 2 n.
It follows from (3), applied with ε = ln 1))M t /K 6 . The second statement of part (ii) is analogous, since there is no difference whether we measure the distance from the beginning of the interval [0, 1] or from the end. The proof of part (ii) is complete. 3

Explanation and proof of Theorem 3

To prepare for the slightly technical argument that is required to analyze the original model, a few simple processes are investigated first in the absence of homophily-that is, when K = 1 and edge rewirings are independent of vertex attributes. These results may then be applied with some modifications to the unconstrained case where K ≥ 1.

We begin with a modified influence process (Model α) in which a vertex selected for attribute updating is moved to the global center of mass instead of the local center of mass. A second model (Model β) investigates a process in which there is no bias towards short edges (K = 1) and vertex attributes shift rapidly (q = 1) before generalizing the process (Model γ) to a slower version where attributes are more resistant to change (q < 1).

Since the first steps of the process are strongly influenced by the initial network and the initial vertex attributes, the beginning of the process is unpredictable. In the following analyses we wait T steps for every edge endpoint to be refreshed at least once (a.a.s. T = Θ(m ln m) by Lemma 1). As noted above, each attribute dimension may be treated independently and so, without loss of generality, we assume that r = 1 and all attributes are in the interval [0, 1]. All of the following results may be generalized to any dimensionality of vertex attributes r ∈ N.

Model α. For t ≥ T , let X t be the random variable equal to n times the global center of mass at time t; that is,

X t = nM t = v∈Vt ω t (v).
We may assume that X T = cn for some c = c(n) ≥ 1/2, since there is no difference whether we measure the distance from the beginning of the interval [0, 1] or from the end. At any time t > T of the process, if an influence step is performed then we assume that a vertex is selected uniformly at random and is moved to the global center of mass (that is, to X t-1 /n). Network rewiring does not influence the value of X t , so it is sufficient to concentrate on influence steps only. It follows from the well-known phenomenon of the coupon collector that a.a.s. after T = (n(ln

n + ω(n)))/ = Θ( -1 n ln n) (5)
steps there are n(ln n + ω(n) + o(1)) influence steps and so a.a.s. every vertex's attribute has been updated at least once. At this point of the process every vertex is very close to the center of mass. In fact, we want to show that a.a.s.

ω T + T (v) = c + o(ln -2 n) = c + o(1) for every v ∈ V T + T .
It is easy to see that {X t } t≥T is a martingale. Indeed, by defining L v (t) as the event that vertex v was selected for influence at time t, we have

E[X t -X t-1 |X t-1 ] = v∈Vt-1 X t-1 n -ω t-1 (v) P(L v (t)) =   X t-1 - v∈Vt-1 ω t-1 (v)   1 n = 0,
provided that an influence step occurs at time t. Moreover, since only one vertex is affected at this step, |X t -X t-1 | ≤ 1. It follows from Hoeffding-Azuma's inequality (see Lemma 9) that w.e.p. during a period of n(ln n + ω(n) + o(1)) influence steps, X t moves from the original value of X T by at most ω(n) √ n ln n. We get that w.e.p. the center of mass at any time t (T ≤ t ≤ T + T ) is at most

ω(n) √ n ln n n = ω(n) ln n √ n = o(ln -2 n)
away from the starting point. The claim holds, since a.a.s. the attribute of every vertex has been updated in the meantime.

Model β. We now consider the process where homophily is not at work (that is, K = 1) and vertices selected for influence automatically adopt the average attribute of their neighbors (q = 1). The behavior of this model is very similar to the behavior observed in Model α. The only difference is that instead of moving to the global center of mass, vertices selected for influence processes are moved to their respective centers of mass. It follows from Lemma 2(i), however, that these local centers of mass are very close to the global center of mass.

In order to obtain a comparable ratio between influence and rewiring steps, we take = Θ( 0 ) = Θ(n/m) ( 0 is the threshold defined earlier) and assume that ≥ n -C for some C ≥ 1 to cover a reasonable set of . 10 A result for this model is given in Theorem 11.

Theorem 11. Consider the social process P(G 0 , ω 0 , , 1, r, 1) = (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n) and ≥ n -C for some C ≥ 1, and recall the definition of T in (1). Then, a.a.s.

ω T + T (v) -M T = o(ln -2 n) = o(1)
for every v ∈ V T + T , where T is defined in [START_REF] Boardman | How Social and Genetic Factors Predict Friendship Networks[END_REF].

L v (t) be the event that v is selected for influence at time t. For any t, provided that an influence step occurs at that time,

E[X t -X t-1 |X t-1 ] = v∈Vt-1 qM t-1 (v) + (1 -q)ω t-1 (v) -ω t-1 (v) P(L v (t)) = q n v∈Vt-1 M t-1 (v) -ω t-1 (v) = q n v∈Vt-1 (1 + o(ln -3 n))M t-1 -ω t-1 (v) = q n (1 + o(ln -3 n))nM t-1 - v∈Vt-1 ω t-1 (v) = q n (1 + o(ln -3 n))X t-1 -X t-1 = o(ln -3 n).
Arguing as before, we obtain that a.a.s. for every T ≤ t ≤ T + T ,

X t = (1 + o(ln -2 n))X T
and so the global center of mass does not change much during this time.

Let us focus on some vertex v for now. Let d t = ω t (v) -c be the distance measured at time t between v and the global center of mass at time T ; in particular, d T ≤ 1. Note that every time a vertex v is selected during the influence step, the distance between this vertex and c shrinks by a constant factor. Formally, we know that

d t+1 = d t (1 -q) + o(ln -2 n) = d t (1 -q + o(1)) ≤ d t 1 - q 2 ,
provided that d t = Ω(ln -3 n). Let ω(n) = Θ(ln ln n) = o(ln n) be a function tending to infinity as n → ∞ such that (1 -q/2) ω(n) = ln -5/2 n. Since after ω(n) influence steps d t = o(ln -2 n), it remains to show that a.a.s. every vertex was selected to update its attributes ω(n) times in this time interval. Let Y = Y (v) be a random variable counting how many times vertex v was selected. We have

E[Y ] = T n = (2 + ε) ln n.
It follows from the Chernoff bound (Theorem 7) that

P(Y ≤ ω(n)) = P(Y ≤ E[Y ] -(E[Y ] -ω(n))) ≤ exp - (E[Y ] -ω(n)) 2 2E[Y ] = exp - (2 + ε -o(1)) 2 2(2 + ε) ln n = exp -1 + ε 2 -o(1) ln n = o(n -1 ).
Hence, the expected number of vertices that have updated their attributes at most ω(n) times is o(1). It follows from Markov's inequality that a.a.s. every vertex has updated its attributes at least ω(n) times. The proof is complete. 3

Derivation and proof of Corollary 4

At time T , that is, when every endpoint is rewired at least once, vertex attributes might still be distributed across the whole space [0, 1] r . On the other hand, Theorem 3 implies that at time T + T a.a.s. all vertices are in a ball of radius o(ln -2 n). Theorem 12, stated below, investigates the convergence process-that is, how the process behaves between time T and T + T . For T ≤ t ≤ T + T , let Z t /n be the average distance between vertices and the global center of mass at time T ; that is,

Z t = v∈Vt |ω t (v) -M T |. (6)
It is clear that Z T ≤ n. (In fact, Z t ≤ n for all t ≥ 0.) Suppose that at time t a vertex v is selected for influence. It follows from the proof of Theorem 3 that the global center of mass does not move much during the process. Moreover, from Lemma 2(i) we have that the local centers of mass are close to the global center of mass. Combining these two results, we get that the distance between the global center located at M t and v decreases from its original value of |ω t-1 (v) -M T | in a predictable way. Namely,

Z t -Z t-1 = -|ω t-1 (v) -M T |q + o(ln -2 n).
Hence,

E[Z t -Z t-1 |Z t-1 ] = v∈Vt-1 -|ω t-1 (v) -M T |q + o(ln -2 n) P(L v (t)) = - Z t-1 n q + o(ln -2 n).
This random variable is analyzed using the differential equation (DE) method [START_REF] Wormald | The differential equation method for random graph processes and greedy algorithms[END_REF]. Defining a real function z(x) to model the behavior of Z T +xn /n, the above relation implies the following differential equation z (x) = -q z(x), with the initial condition z(0) = Z T /n. The general solution is

z(x) = exp(-q x + C), C ∈ R,
and the particular solution is z(x) = (Z t /n) exp(-q x). This suggests that the random variable Z t should be close to the deterministic function Z T exp(-q (t -T )/n).

Theorem 12 below states precisely the conditions under which this holds.

Theorem 12. Consider the social process P(G 0 , ω 0 , , q, r, 1) = (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n) and ≥ n -C for some C ≥ 1. Then, a.a.s.

Z t = (1 + o(1))Z T exp - q (t -T ) n
for every t such that T ≤ t ≤ T + t f , where T is defined in (1) and

t f = n q ln ln n -ln n Z T .
Since Z T +t f = n/ ln n, this theorem tells us that, a.a.s., the random variable Z t is well concentrated around the solution of the differential equation until it reaches the value of n/ ln n. Note that t f ≤ T . It should be noted that Corollary 4, stated in the main paper, holds under this Theorem with Z t replaced by W t .

Before moving to a proof of Theorem 12, one more useful tool is needed: the "stopping time." A stopping time with respect to a random process is a random variable S with values in {0, 1, . . . }∪{∞} for which it can be determined whether S = t, for any time t, from knowledge of the process up to and including time t. The name can be misleading, since a process does not necessarily stop when it reaches a stopping time. The key result says that if a supermartingale (X i ) is stopped at a stopping time (that is, (X i ) becomes static for all time after the stopping time), then the result is a supermartingale; see, for example, [START_REF] Wormald | The differential equation method for random graph processes and greedy algorithms[END_REF] for more details.

Theorem 13. If, with respect to some process, (X i ) is a supermartingale and S is a stopping time, then (X min{i,S} ) is also a supermartingale with respect to the same process. Now, we are ready to prove Theorem 12:

Proof. Since the random variable Z t does not change during rewiring steps, we focus on influence steps only. Suppose that the influence process occurs at times T ≤ s 1 ≤ s 2 ≤ . . . ≤ s t ≤ . . .. Put X 0 = Z T and for t > 0, let X t = Z st . We need to transform X t into something close to a martingale. Consider the following random variable H t = ln X t + qt n and the stopping time S = min t ≥ 0 : X t < n 2 ln n ∨ t = t f .

(Note that H t is chosen so that it is close to a constant along every trajectory of the differential equation z (x) = -qz(x).) Consider the sequence of random variables (H t : 0 ≤ t ≤ t f ). In order to use the generalized Hoeffding-Azuma inequality (see Lemma 10), we need to estimate the expected change:

E[H t -H t-1 | X t-1 , t -1] = v∈Vs t-1 ln Z st-1 -|ω st-1 (v) -M T |q + o(ln -2 n) -ln Z st-1 + q n • P   L v (s t ) v∈Vs t-1 L v (s t )   = q n + 1 n v∈Vs t-1 ln 1 - |ω st-1 (v) -M T |q + o(ln -2 n) Z st-1 .
which implies that S = t f a.a.s., and so a.a.s. ( 7) holds for 0 ≤ t ≤ t f . To complete the proof, it is enough to show that the concentration for the random variable X t implies the concentration for the original random variable Z t . Fix t such that T ≤ t ≤ T + t f . It follows easily from the Chernoff bound (3) that w.e.p. from time T until time t there are (t -T ) + O(n 2/3 ) time steps at which influence processes are performed. As a result w.e.p. Theorem. Consider the evolutionary process P(G 0 , ω 0 , , q, r, K) = (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n) and ≥ n -C for some C ≥ 1. Then, a.a.s. for every pair u, v ∈ V t we have |ω t (u) -ω t (v)| ≤ √ r 1 -q 13K 12 n ln n (t-T )/(3n ln n) ≤ √ r exp -q (t -T )/(3n ln n) 13K 12 n ln n for every t such that T ≤ t = O( -1 n 2 ln 2 n) (the random variable T is defined in (1)). In particular, if t = cq -1 -1 n 2 ln 2 n for some constant c > 0, then a.a.s. for every pair u, v ∈ V t we have

|ω t (u) -ω t (v)| ≤ (1 + o(1)) √ r exp - c 39K 12 .
Proof. As always, we assume that r = 1 and that at some time t 0 ≥ T all vertices lie in the interval [0, 1]. (Note that if the maximum distance in each dimension is at most x, then the maximum distance is at most √ rx.) Let ε = (12K 12 n ln n) -1 . The proof strategy is to show that during at most 3 -1 n ln n steps the interval shrinks by a factor of at least (1 + o(1))qε (that is, the length of the interval will be at most 1 -(1 + o(1))qε). Since the time intervals can be treated independently, the result follows.

Let us consider the following two cases. Case 1: for every t 0 ≤ t ≤ t 2 := t 0 + 1.5 -1 n ln n, we have M t ≥ K 6 ε. It follows from Lemma 2(ii) that w.e.p. for every t in the range under consideration and v ∈ V t , M t (v) ≥ (1 + o(1))K -6 M t ≥ (1 + o(1))ε.

Hence, all vertices selected (during the influence process) between time t 0 and t 2 are moved away from 0; in fact, the distance from 0 is at least (1 + o(1))qε. Since during this time interval there are (1.5 + o(1))n ln n influence steps w.e.p., all vertices are selected at least once w.e.p. After that, all vertices are in the interval [(1 + o(1))qε, 1] and the result holds.

Case 2: for some t 1 such that t 0 ≤ t 1 ≤ t 2 := t 0 + 1.5 -1 n ln n, we have M t1 < K 6 ε. Our goal is to show that the global center of mass cannot drift too fast to the other end of the interval during another 1.5 -1 n ln n steps. Since M t1 < K 6 ε, at time t 1 there are at most 2K 6 εn vertices at distance at most 1/2 from 1, the other end of the interval. We will call these vertices red ; the remaining ones are blue. We will couple the original process with the one in which all red vertices are moved (at time t 1 ) to 1/2. This is the only difference between the two processes; everything else remains the same, including the rewiring process on the (random) graph G t . Let ω t (v) denote the position of vertex v at time t in the coupled process; similarly, M t (v) is the corresponding local center of mass of v at time t. We have ω t1 (v) = ω t1 (v) for all blue vertices; and ω t1 (v) = 1/2 ≤ ω t1 (v) for all red ones.

We consider both processes starting from time t 1 . First, we will show (by induction on i) that after i < 1.6n log n influence steps we have the following two properties w.e.p.: i) for every blue vertex we have |ω t (v) -ω t (v)| ≤ 2K 12 εi, ii) for every red vertex we have |ω t (v) -ω t (v)| ≤ 1/2. The property trivially holds for i = 0. Suppose that the property holds for some i and vertex v is selected for the influence process at time t. All remaining vertices do not move (in both processes) and so one needs to show the desired property for v only. It follows that w.e.p.

M t-1 (v) -M t-1 (v) ≤ 1 |N t-1 (v)| u∈Nt-1(v) ω t-1 (u) -ω t-1 (u) ≤ 1 |N t-1 (v)| (2K
|ω t (v) -ω t (v)| ≤ q|M t-1 (v) -M t-1 (v)| + (1 -q)|ω t-1 (v) -ω t-1 (v)|
≤ q2K 12 ε(i + 1) + (1 -q)2K 12 εi ≤ 2K 12 ε(i + 1).

Similarly, w.e.p. for each red vertex we have

|ω t (v) -ω t (v)| ≤ q|M t-1 (v) -M t-1 (v)| + (1 -q)|ω t-1 (v) -ω t-1 (v)| ≤ q2K 12 ε(i + 1) + (1 -q)(1/2) ≤ 1/2,
where the last inequality follows by our assumption on i. The claim holds by induction. We consider 1.5 -1 n ln n steps of the process which selects all vertices w.e.p. Clearly, in the coupled process the global center of mass is always in the interval [0, 1/2] (deterministically). Since (2K 12 ε)(1.5n ln n) <

Figure 4

 4 Figure 4 displays one typical simulation run. On the left side of the figure are depictions of the network realized at each time step. In this diagram, the color of vertices indicate their starting attribute (0 or 1), and vertex sizes are proportional to the vertex's local center of mass and the network's global center of mass. The right side of the figure displays the distribution of the local centers of mass of each vertex, relative to the global center of mass (the global center of mass is indicated by the vertical reference line in the distribution plot). In this particular example, the local centers of mass collapse around the global center of mass after 65 time steps. This is also seen in the network diagrams, which show the decay of segregation around shared attributes early in the process to a well-mixed network where linkages are independent of starting attributes (node color) in the final time step.Approximately 1,800 simulations were run with three model parameters-homophily, transitivity, and degree-assigned uniformly at random from [0, 100] and q assigned uniformly at random from [0.15, 1] at each

Figure 4 :

 4 Figure 4: Evolution dynamics for a typical simulation run: the depicted simulation has parameters homophily (K) = 10; triadic closure (p closure ) = 30; degree (p degree ) = 30

Figure 5 :

 5 Figure 5: Aggregate simulation behavior over time

Figure

  Figure 6: Ordinary least squares regression model of effect of computational simulation parameters on time to attribute convergence

Z 3 6. 7

 37 t = X (t-T ) +O(n 2/3 ) = (1 + o(1))X 0 exp -q(t -T ) n + o(1) = (1 + o(1))Z T exp -q(t -T ) n ,and the proof is finished. Proof of Theorem 5

  -1/2 n, that w.e.p. X = (1 + o(1))E[X]. Similarly, we get that w.e.p. |N t (v)| ≤ (1 + o(1))K 2 d and so w.e.p. M t (v) ≥ (1 + o(

  12 εi)(# of blue neighbors) e.p. there are at most 2K 12 ε|N t-1 (v)| red neighbors of v. Indeed, by the upper and lower bounds for the probability of an edge, there are at most 4K 8 mε/n red neighbors, and the size of the neighborhood in total is at least d/K 4 = (2m)/(nK 4 ). Hence the fraction of red neighbors is at most 2K 12 ε. It follows that w.e.p. for each blue vertex we have

		+(1/2)(# of red neighbors)
	≤	1 |N t-1 (v)|	(2K 12 εi|N

t-1 (v)|) + (1/2)(2K 12 ε|N t-1 (v)|) ≤ 2K 12 ε(i + 1), since w.

Community structure and network segregation are complementary but distinct concepts in network science. Community structure refers to a concentration of linkages among certain groups of nodes, whereas network segregation refers to a situation where the existence of links is correlated with the similarity of nodal attributes. It is possible to have networks that exhibit both segregation and community structure, but community structure is also possible without network segregation and network segregation is possible without community structure.

It should be noted that the set of vertices does not change over time.

Note that d K (ω t-1 (u), ω t-1 (v)) ∈ [1/K, 1]so the probability distribution is well-defined.

This model allows loops and multiple edges, however there will typically be very few of these and their exclusion will not greatly affect the conclusions.

We use the following standard asymptotic notation:f (n) = o(g(n)), if limn→∞ f (n)/g(n) = 0, and f (n) = O(g(n)) if there exists some n 0 so that for all n ≥ n 0 , f (n) ≤ Cg(n) for some absolute constant C > 0. Similarly, if f (n) = O(g(n)), then g(n) = Ω(f (n)), and if both f (n) = O(g(n)) and g(n) = O(f (n)) hold, then f (n) = Θ(g(n)).

Let c ∈ R. From the coupon collector problem, it follows that after 2m(ln(2m) + c) rewirings, with probability tending to e -e -c , every endpoint is rewired at least once. From this it follows that if c → ∞, then after 2m(ln(2m) + c) rewirings, a.a.s. every endpoint is rewired at least once.

Agent-based models were programmed in R[START_REF] Core | R: A language and environment for statistical computing[END_REF]. Visualizations presented here made use of the R sna package[START_REF] Butts | sna: Tools for Social Network Analysis. R package version 2[END_REF].

At each time step, 3 vertices are selected uniformly at random for influence and

edges are selected uniformly at random for rewiring. Among the selected vertices and edges, the influence and rewiring processes occur simultaneously. This setup was chosen to speed computation times.

The homophily parameter is analogous to the parameter K in the main mathematical model.

As noted previously, for a comparable ratio of influence versus rewiring steps, we require = Θ(n/m) = Ω(n -1 ). In such a situation, we may take any C > 1. Larger values of C might be used to model processes in which influence steps are rare.

* A. D. Henry gratefully acknowledges support from the U.S. National Science Foundation (NSF) under grant #1124172, and the University of Arizonas Institute of the Environment.

† P. Pra lat gratefully acknowledges support from NSERC and Ryerson University.

1

Therefore, the expected number of endpoints not rewired is 2m • o(m -1 ) = o(1) and so a.a.s. every endpoint is rewired at least once by Markov's inequality. 3

Proof of Lemma 2

After time T , it is possible to make certain inferences about the distance of local centers of mass from the global center of mass. These results are specified in Lemma 2.

Lemma. Consider the social process P(G 0 , ω 0 , , q, 1, K) = (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n). Let C > 0. Then, w.e.p. for every T ≤ t ≤ n C and every v ∈ V t , the following holds

Proof. As noted above, each dimension may be treated independently. Thus, without loss of generality we may assume that r = 1 and ω t :

Since we consider a polynomial number of events only, it is enough to show that each of them holds w.e.p. The proof of part (i) is a simple application of the Chernoff bound. Let

that is, X is the sum of distances from the beginning of the interval [0, 1] to all the neighbors of v. As we already noticed, M t (v) = X/|N t (v)|, so it remains to estimate the random variable X and the degree of v independently. Note that, without loss of generality, we may assume that M t = M t (n) ≥ 1/2, since there is no difference whether we measure the distance from the beginning of the interval [0, 1] or from the end. For any fixed value of M t , it follows from (2) that Note that a.a.s.

Proof. It follows from Lemma 2(i) that w.e.p. for every

Hence, we may assume that this property holds deterministically in the time range we are interested in. The difference between the global center and the one of a vertex that is updating its attribute is at most

As in the previous model, we try to investigate the behavior of the random variable X t = nM t (t ≥ T ) with X T = cn. Without loss of generality, we may assume that c = c(n) ≥ 1/2. This time, we need to use the generalized version of Hoeffding-Azuma inequality (see Lemma 10) that works for random variables that are not necessarily martingales. Since there are O(n ln n) influence processes, we can apply the lemma with

√ n ln n (note that there is a lot of room for argument here; in fact, ε could be any function that is o(n ln -2 n)) to get that a.a.s. for every T ≤ t ≤ T + T ,

The claim holds, since a.a.s. every vertex was selected for influence in this time interval.

3

Model γ. This model continues investigating a process without homophily (K = 1), but this time we relax the condition of rapid attribute updating through influence. We now consider cases where q < 1. In this case, the global center of mass still does not change much during the process. While in Model β it was enough for a vertex attribute to be updated at least once to arrive close to the global center of mass, this time the influence process is rather slow, and so each vertex must be selected many times in order to arrive very close to the global center of mass. The result is stated in the main paper, as Theorem 3.

To summarize, Theorem 3 tells us that, at time T + T and for K = 1, the distance between each vertex's attribute and the global center of mass is of order less than o(ln -2 n). At this point, all vertex attributes are in some interval (a, b) of length o(ln -2 n) and, once all attributes are in this interval, they will always remain there.

Theorem. Consider the evolutionary process P(G 0 , ω 0 , , q, r, 1) = (G t , ω t ) ∞ t=0 . Suppose that d = 2m/n is such that ln 7 n d = o(n/ ln 3 n) and ≥ n -C for some C ≥ 1, and recall the definition of T in (1). Then, a.a.s.

for every v ∈ V T + T , where T = -1 (2 + ε)n ln n for some ε > 0.

Note that a.a.s.

Proof. The proof is very similar to the proof of Theorem 11. We use Lemma 2(a) again to get that w.e.p. for every T ≤ t ≤ T + T and every v ∈ V t , we have

We focus on the random variable X t = nM t (t ≥ T ) with X T = cn. As usual, we may assume (without loss of generality) that c = c(n) ≥ 1/2. We need to show first that {X t } t≥T is close to a martingale. Let By Taylor expansion,

provided S > t, since then X t-1 ≥ n 2 ln n . Similarly, we get that (Note that there are L ≤ t f ≤ T = O(n ln n) steps and so Lβ = o(1).) As H 0 = ln X 0 , it follows from the definition of H t , that a.a.s. ln(X t /X 0 ) = -qt/n + o(1) for 0 ≤ t ≤ S, and thus

Now, we will show that a.a.s. S = t f . The events asserted by the equation hold a.a.s. up until time S, as shown above. Thus, in particular, a.a.s.

) n ln n 1/3, w.e.p. blue vertices in the original process are close to their counterparts in the coupled one: Indeed, since the difference of the global center of mass coming from the contribution of red vertices is at most 2K 6 ε, and the contribution coming from blue vertices at most 1/3, the global center of mass in the original process must be smaller than 5/6+2K 6 ε w.e.p. But this implies that once all vertices are selected for the influence process, all of them must be far away from 1: By Lemma 2(ii) we then have that M t (v) ≤ 1 -(1 + o(1)) 1 6 K -6 + o(1). Hence, the distance of M t (v) from the right border of the interval is at least 1 6 K -6 + o(1), and once the vertex undergoes the influence process, its distance from the right border is thus at least q 1 6 K -6 + o(1). The proof is finished.

3