# Emergence of segregation in evolving social networks

See allHide authors and affiliations

Edited by William A. V. Clark, University of California, Los Angeles, CA, and approved March 16, 2011 (received for review October 7, 2010)

## Abstract

In many social networks, there is a high correlation between the similarity of actors and the existence of relationships between them. This paper introduces a model of network evolution where actors are assumed to have a small aversion from being connected to others who are dissimilar to themselves, and yet no actor strictly prefers a segregated network. This model is motivated by Schelling’s [Schelling TC (1969) Models of segregation. *Am Econ Rev* 59:488–493] classic model of residential segregation, and we show that Schelling’s results also apply to the structure of networks; namely, segregated networks always emerge regardless of the level of aversion. In addition, we prove analytically that attribute similarity among connected network actors always reaches a stationary distribution, and this distribution is independent of network topology and the level of aversion bias. This research provides a basis for more complex models of social interaction that are driven in part by the underlying attributes of network actors and helps advance our understanding of why dysfunctional social network structures may emerge.

## The Problem of Segregation in Social Networks

Cooperation and conflict in social networks are central features of many contemporary social and policy issues, including commons governance, climate change policy, and economic development. Of particular importance is the well-known tendency for network linkages to concentrate between actors who are similar to one another in terms of certain key attributes—a phenomenon we refer to as “attribute closeness.” Attribute closeness is one important indicator of segregation within a social network, as it signals tightly knit communities of homogenous actors and may reinforce divisions between disparate groups. These types of networks have been observed in a wide variety of contexts (1–3), including diverse examples such as race- and gender-oriented segregation in high school friendship networks and value- and belief-oriented segregation in environmental policy networks. Thus, the literature provides many empirical examples of segregation in terms of the structure of relationships, in addition to the geographically explicit residential segregation studied in Schelling’s classic model of this phenomenon (4, 5).

Network segregation is problematic when actors are faced with the need to collectively address complex social, environmental, or economic dilemmas. For example, social and policy networks are an important part of the machinery of collective action (6, 7). If the networks that form around social dilemmas are heavily fragmented, then it may be difficult for actors to develop the social capital necessary for the emergence of cooperative behavior (8). These fragmentations are observed in real-world policy networks, such as in regional planning networks where segregation is often observed between actors working in different functional domains (e.g., when transportation planners fail to coordinate with land-use planners), levels of government (e.g., when federal agencies do not coordinate with state agencies), or ideologies (e.g., when environmental groups do not coordinate with prodevelopment groups). Moreover, these types of fragmented, segregated networks work against the diversity that is central to social learning, innovation, and successful problem solving (9, 10).

In order to overcome network segregation, it is necessary to develop a better understanding of the factors that shape social networks. Given the similarity between residential and network segregation patterns, it is natural to look toward Schelling’s model of residential segregation (4, 5) for insights into why such networks emerge and persist. Schelling’s model focused on the role of individual preferences in shaping emergent segregation patterns and demonstrated that seemingly mild preferences against being a local minority can produce stark and counterintuitive patterns of global segregation. This model challenged the common view that discrimination—defined as a strict preference for homogenous communities, potentially coupled with formal regulations that inhibit integration—is a necessary condition for segregation to emerge. Even though the point is still hotly debated, research using agent-based models (such as Fossett’s SimSeg model; see ref. 11) convincingly demonstrate the theoretical point that individual preferences can produce segregation even in the absence of discrimination (11, 12). Moreover, empirical tests of Schelling’s model, beginning with Clark (13), have demonstrated the existence of segregation-promoting preferences that are stronger than the preferences assumed by the Schelling segregation model (12, 13).

Like residential segregation patterns, social network structures are potentially influenced by both exogenous constraints (such as “discriminatory” rules that create attribute-close linkages with higher probability) and endogenous drivers, such as individual preferences for certain relationships. Just as residential segregation scholars have sometimes assumed strict individual preferences for homogenous communities, the networks literature has similarly focused on the role of “homophily,” or agents’ attraction to others similar to themselves, in driving endogenous networking choices.* However, despite the influence of homophily-based models, the Schelling model suggests that the attraction aspect of homophily may not be a necessary condition for the emergence of network segregation. Rather, a mild aversion from dissimilar network partners, coupled with a random selection of new partners, may be sufficient to produce segregated networks.

In this paper, we introduce a mathematical, Markov-chain model of network segregation based on the assumption that actors have no strict preference for forming ties with similar network partners, but are subject to a (potentially very small) bias for cutting ties with dissimilar actors. This model is an effort to analytically prove the emergence of segregated network structures under this process, given any initial network topology. As with Schelling’s original model, we show that aversion processes are sufficient to explain the emergence of segregated, attribute-close network structures. Our results not only complement a long line of analytical proofs and simulations of the Schelling model (11, 12, 15–18) with some network analysis applications (19, 20), but we also contribute to the emergent literature on the dynamics of network evolution where structure is influenced by the attributes of individual network actors.

This paper makes four key contributions to the literature on segregation and network evolution. First, we show that the distribution of attribute similarity among connected actors always converges to a stationary distribution over time, where linkages are predominately concentrated between pairs of similar actors. Second, the stationary distribution does not depend on the initial network structure or the level of aversion bias, which may be infinitesimally small. Third, we are able to predict the distribution of attribute similarity among connected actors at any point in the Markov process, meaning that we not only predict convergence states but also the convergence process. Finally, all of the results presented here allow for actor attributes that may be multidimensional and may take on any number of discrete, ordinal values. This allows for great flexibility in modeling the complex, multifaceted nature of aversion processes within social networks, because aversion processes may be a function of multiple interacting attributes (such as race and religion and age) rather than just single categorical attributes (such as race only). This generalization is motivated also by work in the residential segregation literature, where it is noted that segregation occurs in a “multicultural landscape” where preferences are affected by many different factors including ethnicity, status, and housing quality (11, 12).

## A General Model of Network Segregation

We begin by outlining a general Markov-chain model of network evolution that operationalizes the aversion aspect of the Schelling segregation model. Although we define a general model, a majority of this paper is committed to the analysis of a more specific case for the sake of tractability. Major components to the model include the initial network conditions, including the assignment of attributes to network actors, as well as the basic process of aversion-driven network rewiring.

### Initial Conditions.

Our model begins with an *initial network*, denoted *G* = (*V*,*E*), on *n* = |*V*| vertices and *m* = |*E*| links (also known as “edges”). Vertices are referred to interchangeably as “agents” or “actors” in the network. The initial network *G* may have any structure and may include any number of agents. In addition, each vertex is assigned a fixed attribute that will be used to assess their similarity to other network actors. Vertex attributes are represented by the function *ω*: *V* → [-1,1]^{r}, where represents the dimensionality of attributes. In this paper we focus on the case of unidimensional attributes (e.g., agents make networking decisions based on similarities and differences in only one trait, such as ethnicity or gender); however, the general approach is applicable to multidimensional attributes where *r*≥2 (e.g., agents make their networking decisions based on differences in both ethnicity and gender).^{†}

The attribute distance between any two vertices in the network is defined generally as *d*: [-1,1]^{r} × [-1,1]^{r} → [0,1]. We refer to large attribute distances as “long edges,” and small attribute distances as “short edges,” because one may imagine that agents occupy fixed positions within their attribute space. Distance within this attribute space is congruent to the concept of social distance described by Fossett (11); relationships between actors with small social distances are “short;” whereas relationships between actors with large social distances are “long.”

Agents’ propensity to cut ties with dissimilar network actors is represented by a single parameter that we call *aversion bias*, represented by *p*∈(0,1]. Larger values of *p* indicate that agents have a strong aversion to maintaining linkages with actors who are very different from themselves (e.g., when the attribute distance *d* is large). This aversion parameter models the strength of agents’ preferences and is congruent to the residential preferences originally measured by Clark (13).

### The Network Evolution Process.

The *social process* analyzed here [] is defined as a Markov chain and generates a stochastic sequence of graphs. The process begins at *t* = 0, with *G*_{0} = *G*. Time step *t*, for *t*≥1, is defined to be the transition between *G*_{t-1} and *G*_{t}.

Network evolution occurs through a stochastic process of link termination, followed by random rewiring of terminated links. This is modeled by choosing, at each time step, a random edge *uv*∈*E*(*G*_{t-1}). The agents *u* and *v* then assess their attribute distance *d*(*ω*(*u*),*ω*(*v*)) and make a choice to delete or keep the relationship between them based on their attribute distance and *p*. Specifically, the probability of tie deletion between *u* and *v* is *d*(*ω*(*u*),*ω*(*v*))·*p*.^{‡} When a tie is deleted, it is then *rewired* by removing *uv*, choosing a vertex *x*∈*V* uniformly at random, then finally adding either *ux* or *vx* with equal probability. Thus, when a tie is deleted, it is randomly allocated to one of the actors in the dyad, who then forms a relationship at random with another actor in the network. A schematic of this process is provided in *SI Text* (Fig. S2). The total number of edges in the network stays the same throughout the process, that is, is equal to *m* = |*E*|.^{§} Note that this assumption does not imply that actors maintain the same number of relationships—degree distributions are allowed to change dynamically. We assume only that the overall density of the network remains constant throughout the process.

Note that if by the times *t*_{1}, *t*_{2} each edge of the initial network *G* have both neighbors rewired at some point of the process, the networks *G*_{t1} and *G*_{t2} are random objects, identical in distribution, whose properties depend on *m*, *r*, *ω*, and *d* only (*p* and properties of the initial network *G* other than *m* = |*E*| do not affect the distribution). We call the graph generated in this process the *social network* and denote it as .^{¶}

All our 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* (*aas*) if it holds with probability tending to one as *m* → ∞. Finally, we will make frequent use of the *Chernoff bound*; this is a standard result about the sum of independent random variables and is included in *SI Text* (section 2).

## Predicting the Convergence Process: A Specific Case

Our analysis of the general model begins by assuming more specific functional forms for the distribution of attributes in the population of network actors (*ω*), and the attribute distance between pairs of actors (*d*). These assumptions will allow us to predict the process by which the initial network *G* is transformed into the stationary social network .

### The Distribution of Attributes.

Suppose that actors are assigned, uniformly and at random, attributes drawn from an *r*-dimensional space.^{∥} Distances between attributes are defined by the function *d*(·,·), which ranges from 0 (when two vertices were assigned the same attributes) and 1 (when two vertices were assigned attributes as far from each other as possible).

Although the distance metric *d*(·,·) is continuous, it is useful to think of attribute distance as a discrete variable. This is done by fixing and partitioning all possible distances *d*(·,·) into *K* discrete bins. In particular, the attribute distance *d*_{K}(·,·) between two vertices with attributes *x* and *y* is defined as , if *d*(*x*,*y*) > 0, and , otherwise.**

This operationalization fixes a lower bound on attribute distance and therefore ensures that all edges have some nonzero probability of being cut. For large values of *K*, the attribute distance function *d*_{K}(·,·) approximates *d*(·,·), and so this technique allows us to imagine attribute distances that are nearly continuous.

### Measuring Network Segregation.

We track the emergence of network segregation by defining several special-use measures of attribute closeness.^{††} At this point we simplify the analysis by assuming unidimensional attributes (that is, *r* = 1), although the same approach is applicable for *r*≥2 as well; proofs for the case of multidimensional attributes are provided in *SI Text* (section 6).

Let *E*_{i}(*t*) (where *i*∈{1,2,…,*K*}) denote the total number of edges in *G*_{t} that have attribute distance (or “length”) equal to , that is, . Then because the number of edges stays unchanged during the social process.

Next, let *F*(*t*) represent the total length of all the edges in the graph; the probability of rewiring an edge at any time step will depend on this quantity. We have

This result is derived in *SI Text* (section 4).

### Expected Changes in Attribute Distance.

Now we run the process and focus on the random variable *E*_{i}(*t*) for a given *i*∈{1,2,…,*K* - 1}. *E*_{i}(*t*) will decrease if we rewire an edge *vu* that has attribute distance . The probability that this happens is equal to the probability that an edge with attribute distance is chosen, times the probability that the edge, if chosen, is rewired. This probability is Conversely, *E*_{i}(*t*) may also be increased if we terminate an edge *vu* and create a new edge *vw* with length . Using the Chernoff inequality, it can be shown that this happens with probability (1 + *o*(1))/*K* provided that an edge is rewired.^{‡‡} Because the expected number of edges that we rewire at time step *t* is the expected change in the number of edges of a given length at a given time step is [1]

It turns out that as we run this process, over time most of the edges become short in that they are concentrated between pairs of agents with small attribute distances. In other words, this process yields networks that are attribute-close and consistent with the emergent behavior seen in the Schelling segregation model. Although it is important to highlight this result, the main focus of this research is to show how we may predict the process by which these networks emerge. Before we take a rigorous look at the convergence process, however, let us consider heuristically why the end result makes sense.

#### A heuristic argument.

We investigate the limit of the process, that is, the social network , when a stationary distribution of the Markov chain is obtained. For the moment, let us assume that the expected change in edge lengths is zero (this will be proven below). In this case, we have that for *i*∈{1,2,…,*K* - 1}. It follows from Eq. **1** that . Thus, hence Finally, we get that the number of edges of length at least is [2]This summation can be approximated by the integral, yielding[3]Indeed, the ratio between the number of edges of length at least *ε* (for a given *ε* > 0) to the total number of edges is well approximated by , which is very close to zero for large values of *K*.

#### A closer look at the convergence process.

Let us return to the social process that gives rise to these attribute-close social networks. It helps to define real functions *e*_{i}(*x*) to model the behavior of the scaled random variables , *i*∈{1,2,…,*K* - 1}. Presuming that the changes in the function correspond to the expected changes of the random variable (see Eq. **1**), we obtain the following system of differential equations (DEs): for *i*∈{1,2,…,*K* - 1}, where Noting that the total number of edges is |*E*| (and therefore *E*_{K} can be calculated based on all other values), we have *K* - 1 functions to discover, and *K* - 1 equations in the DEs system.

The initial condition to the system depends on the initial graph. For example, when *G* is generated at random, then we expect *E*_{i}(0) = |*E*|/*K* for *i*∈{1,2,…,*K* - 1}, so we should use *e*_{i}(0) = 1/*K*.^{§§} When *G* contains short edges only, we should set *e*_{1}(0) = 1 and *e*_{i}(0) = 0 for 2 ≤ *i* ≤ *K*. Similarly, if *G* contains long edges only, then the initial conditions are *e*_{K}(0) = 1 and *e*_{i}(0) = 0 for 1 ≤ *i* ≤ *K* - 1.

Before turning to a general case, let us consider carefully the case for *K* = 4. We get the following system of differential equations [recall that *e*_{4}(*x*) = 1 - *e*_{1}(*x*) - *e*_{2}(*x*) - *e*_{3}(*x*) so it can be removed from the consideration]:

The general solution is where , , , and the constants *C*_{i}’s depend on the initial values. For instance, for the random graph as a starting point (*e*_{i}(0) = 1/*K*, *i*∈{1,2,…,*K*}), we get , , .

Note first that *p* plays an important role in the convergence process, even though it does not (as noted above) influence the stationary distribution of edge lengths in ). The smaller the value of *p*, the slower the rate of convergence (although the rate of convergence is always exponential). In Fig. 1 *A* and *B*, we compare convergence rates for large and small values of *p* (*p* = 1 and *p* = 0.05, respectively) using a random graph as a starting point. The diagrams track the proportion of total edges of a given length (vertical axis) over time (horizontal axis). Because *k* = 4 in these scenarios, there are four possible edge lengths, each represented by a curve in the graph. In a random graph, we expect a uniform distribution of edge lengths—that is, roughly 25% of edges will have any given edge length, meaning that all curves begin at the same point (0.25) on the vertical axis. As the network evolves, the distribution of edge lengths changes as well and eventually reaches a stationary distribution where most edges are short (far right side of each graph). Large values of *p* (Fig. 1*A*) converge more quickly than small values of *p* (Fig. 1*B*). Similar behavior may be observed for other scenarios.

Another noteworthy result, also illustrated in Fig. 1, is that the initial graph does not matter. The stationary distribution depends only on the number of edges in the initial graph; other structural parameters (such as network centrality, clustering, or diameter) do not influence the final distribution of edge lengths. However, the dynamic behavior of the social process (i.e., the path taken toward segregation) varies depending on the initial scenario. Fig. 1 *B*–*D* presents three illustrative cases for *p* = 0.05. As noted above, Fig. 1*B* depicts an initial network that is a random graph [i.e., *e*_{i}(0)’s are uniformly distributed]. Fig. 1*C* depicts an initial network with high attribute closeness (where all edges are short), whereas Fig. 1*D* depicts an initial network with low attribute closeness (where all edges are long). Note that the path taken toward convergence differs; however, each respective curve always converges to the same position on the vertical axis at the end of the process.

Let us return to the general case (that is, for any ). The system of DEs we consider can be rewritten as [4]where *A* = (*a*_{ij}) is a matrix defined as follows: *a*_{ij} = *K* - *j* if *i* ≠ *j* and *a*_{ii} = (*K* - *i*) + *iK*; otherwise, *E*(*x*) = (*e*_{1}(*x*),*e*_{2}(*x*),…,*e*_{K-1}(*x*))^{T} and *B* = (*K*,*K*,…,*K*)^{T} are vectors.

This is a linear, ordinary, first-order system of differential equations with constant coefficients. These have been well-studied in the literature. It follows from the previous section that one particular solution is given by One can solve the characteristic equation to find the eigenvalues *λ*_{1},*λ*_{2},…,*λ*_{K-1} of the matrix *A*. Then, the general solution is of the formwhere constants *C*_{i,j} depend on the initial values to the system of DEs (that is, the initial graph *G*). Because the social process ensures that *e*_{i}(*x*) ≤ 1, we get that real parts of all eigenvalues are positive.^{¶¶} Therefore, where is the smallest absolute value of an eigenvalue.^{∥∥}

Finally, the DEs method (introduced and developed by Wormald et al. (22)) can be used to show that our random variables are well-concentrated around their expectations. Using the general purpose theorem (Theorem 5.1 in ref. 22), we get the following result:

Let *p*∈(0,1], , and *C* > 0. Let *G* = (*V*,*E*) be any graph on *n* = |*V*| vertices distributed uniformly at random on [-1,1] (*r* = 1), *m* = |*E*| tends to infinity with *n*. Let *e*_{i}(*x*), *i*∈{1,2,…,*K* - 1}, be the particular solution to the system of differential equations **4** with the initial conditions based on the initial graph *G*, and . Let *λ*_{min} be the smallest absolute value of an eigenvalue of *A*.

Then, *aas* during the social process for *i*∈{1,2,…,*K*} and 0 ≤ *t* ≤ *Cm*.

In particular, for the social graph , *aas* we have that for *i*∈{1,2,…,*K*}.

Although a typical application of Markov chains would reveal information only about the stationary distribution of edge lengths, this theorem and the DEs method allows us to predict what the evolving network will look like at any point during the process. As noted above, the stationary distribution of edge lengths is reached after *O*(*m* log *m*) steps. On the other hand, it is sufficient to study the behavior of the process up to time *Cm* for *C* large enough. The reason is that, at time *Cm*, *aas* there are still a few edges that are not rewired, but this does not significantly affect the total number of edges of a given length because the error term is arbitrarily small for large values of *C*.

## Model Implications

In the model presented here, actors make choices about networking strictly on the basis of attribute similarity with others they share a direct linkage with; relationships are terminated with probability proportional to attribute distance, and new partners are selected uniformly at random when a link is terminated. Although this is a relatively simple view on network evolution, it lends itself to a rigorous analytic proof showing that segregation will always emerge in the absence of additional endogenous or exogenous drivers of network structure. Of course, the trade-off for mathematical tractability is a relatively limited view on how networking decisions are made by real actors in real social networks. Thus, it is useful to consider how this model may inform the empirical study of network segregation, both by illustrating the model’s behavior when attributes are polarized in the population, and through a discussion of how segregation is still likely to emerge when additional network effects are taken into account.

## The Distribution of Attributes and Clustering in Segregated Networks

A large literature has grown around the identification of community structure and clustering within networks, which provides at least one natural way to think about segregation patterns—in a clustered network, there exist natural groups of agents with a high density of interaction within groups, and relatively sparse interactions across groups. However, attribute closeness does not necessarily imply clustering within a network. Indeed, if attributes are distributed uniformly (as in the specific case investigated here), then the emergent social networks are lattice-like structures where any given network actor tends to be surrounded by very similar partners, but there is no global partitioning of actors into clear communities. This is because the uniform distribution has no natural centroids around which network clusters may form. Of course, assuming a uniform distribution of attributes is also unrealistic for many empirical applications, especially in the residential segregation literature where choices are driven by categorical variables such as race, or highly nonuniform variables such as social status (11).

Applications of this model may build upon the specific case presented here to incorporate multimodal distributions of attributes where populations may be partitioned into two or more natural groups based on their traits. This is a relatively minor change and would not alter the model’s behavior in terms of the stationary distribution of edge lengths.

Fig. 2 illustrates the model’s behavior if one assumes that network actors have unidimensional attributes that follow a bimodal distribution in the population, as will be the case in at least some potential empirical applications.^{***} In this illustration, 100 actors are connected in a network with 300 edges (*n* = 100 and *m* = 300, thus network density is approximately 0.03). Attributes are represented by the shape and size of network vertices; actors with attributes less than the population mean are represented as triangles, whereas actors with attributes greater than the population mean are represented as circles. Vertex size represents the distance of the actor’s attribute from the mean attribute. In the initial condition, actors are connected with one another in a random graph. As the network evolves, eventually the long edges connecting actors with very dissimilar attributes become short as the distribution of edge lengths reaches the stationary distribution. In the final condition (depicted in Fig. 2, *Far Right*), most edges are short, connecting actors with small attribute distances.

## Integrating Other Network Effects

Although this model assumes dyadic independence in actors’ networking choices, it is well known in the social networks literature that dyadic decisions (i.e., terminate or form a relationship with a particular partner) are often correlated across dyads. Of particular interest are “closure” effects where actors have a bias toward forming relationships with others they are already linked to through one or more indirect relationships. In the statistical modeling of networks we are now able to account for such complex dependencies using tools such as exponential random graph models (23) or the stochastic actor-oriented models proposed by Snijders et al. (24). Integrating more realistic views of networking behavior into mathematical models such as the one presented here is an important area for future research. On the other hand, our model also presents a conservative view on the emergence of segregation, which is likely to be accelerated if one integrates effects such as transitive or cyclic closure.

Transitive closure refers to actors’ tendency to choose relationships in a way that emulates the networking behavior of others they share a direct linkage with. Thus, new friends may be chosen because they are already “friends of friends,” and this effect may be even stronger when two disconnected actors share multiple friends. These tendencies are reflected in the existence of transitive triads (triangles), or higher-order transitive configurations such as *k* triangles that link a pair of actors through *k* indirect two-step paths. Cyclic closure refers to actors’ tendency to form relationships in a way that creates cycles (paths originating and ending at the same vertex), which is thought to reflect a bias against hierarchical structures or the spread of positive reputations throughout the network.

Transitive closure and cyclic closure would both accelerate the emergence of segregation in the model outlined here. This is because both closure effects would result in the formation of new edges with lengths that are correlated with existing edges—for example, if actors *A* and *B* share short edges with five common friends (i.e., both *A* and *B* are similar to their common friends), then the transitive edge between *A* and *B* will also be short because these two actors are similar to each other. Indeed, because the distribution of edge lengths in our model tends to include more short edges over time, then new edges formed through transitivity or cyclic closure will also tend to be short edges as well. The result would be a stationary distribution with even fewer long edges that connect very dissimilar actors, and even more pronounced patterns of network segregation.

## Conclusion

This model provides a network analogue to the Schelling segregation model: Actors embedded within a social network may not strictly prefer forming homogeneous networks, but such structures can emerge if actors are subject to a small bias against interaction with partners who are dissimilar from themselves. Furthermore, the model allows us to predict the process by which these segregated social networks emerge (see Theorem 1). We provide a mathematical operationalization of this model and prove the results asymptotically.

Like all models, this model does not capture the full complexity of social interaction and network dynamics. However, this model has useful theoretical and methodological implications for research on social networks. In terms of theoretical contributions, this research widens our understanding of the candidate processes that may give rise to segregated networks. Our application of the Schelling model underscores that homophily processes (or a deliberate bias for forming attribute-close relationships) are not a necessary condition for the emergence of network segregation. Given sufficient iterations, a very slight bias toward cutting ties with dissimilar partners will eventually lead to polarized networks given *any* initial network structure. Because in many real-world networks we may expect to see realignments occurring frequently (e.g., as a result of daily conversations), segregation may emerge quite quickly even for very slight aversion tendencies.

On the methodological side, our model contributes to the enterprise of moving from descriptions of observed social networks to models of the evolution of these complex, evolving structures (25). Of particular interest are network models that account for the interdependencies between relationship choices and actor attributes (conceptualized as positions within, for example, a geographic or cultural space) (26). We also demonstrate the utility of the DEs method (22) in proving the convergence processes, which yields a more detailed and nuanced view of network evolution (27, 28).

Network segregation has been observed empirically across many types of social and policy networks and has important implications for actors’ collective ability to address shared problems. This research illustrates the importance of mild individual preferences in driving network segregation, which in turn suggests that institutional designs to overcome network segregation must take seriously the important role that individual preferences play in shaping networks. Thus, future work will need to focus on empirical tests of models such as the one presented here, with a particular emphasis on the measurement of core theoretical variables such as actors’ varying levels of aversion bias, as well as the dimensionality and distribution of attributes that are thought to drive individual networking behavior.

## Acknowledgments

The authors gratefully acknowledge the support of an Awards for Research Team Scholarship research grant from West Virginia University’s Eberly College of Arts and Sciences.

## Footnotes

- ↵
^{1}To whom correspondence should be addressed. E-mail: adam.henry{at}mail.wvu.edu.

Author contributions: A.D.H., P.P., and C.-Q.Z. performed research; A.D.H. and P.P. wrote the paper.

The authors declare no conflict of interest.

This article is a PNAS Direct Submission.

This article contains supporting information online at www.pnas.org/lookup/suppl/doi:10.1073/pnas.1014486108/-/DCSupplemental.

↵

^{*}A large literature has also focused on contagion processes, whereby actors become more similar over time through social influence (14). Contagion processes are beyond the scope of this paper, however, because we consider attributes that may be assumed to be static (e.g., gender or race) or highly stable over time (e.g., cultural traits or value systems).↵

^{†}A proof of the convergence process for multidimensional attributes (*r*≥2) is sketched in*SI Text*(section 6).↵

^{‡}Note that*d*(*ω*(*u*),*ω*(*v*))∈[0,1] and*p*∈(0,1], so the probability distribution is well-defined.↵

^{§}Note that this model allows loops and multiple edges. However, there generally will not be very many of these, and it can be shown that excluding them will not significantly affect the conclusions.↵

^{¶}It can be shown that the stationary state will be reached after*O*(*m*log*m*) steps. This result will become important later and is explained in more detail in*SI Text*(section 1).↵

^{∥}More details on how the distance functions are created are available in*SI Text*(section 3).↵

^{**}⌈*x*⌉ denotes the ceiling of*x*, that is, the smallest integer not smaller than*x*.↵

^{††}These measures complement other formal measures that have been proposed in the social networks literature; see, for example, refs. 2 and 21.↵

^{‡‡}More details are provided in*SI Text*(section 5); note that this claim follows from Eq.**S2**.↵

^{§§}In fact,*aas**E*_{i}(0) = (1 +*o*(1))*m*/*K*for all*i*∈{1,2,…,*K*}.↵

^{¶¶}Alternatively, one should be able to derive this using linear algebra.↵

^{∥∥}Although it is difficult to find any general lower bound for*λ*_{min}, exact values may be obtained computationally. Lower bounds for select values of*K*are given in*SI Text*(section 7).↵

^{***}In this illustration, half of the vertices have attributes distributed uniformly at random in the interval [0,1/4], and the other half have attributes distributed uniformly at random in the interval [3/4,1]. Note also that the torus metric is not used to calculate edge lengths. Thus, 0 and 1 represent “extreme” attribute values.

Freely available online through the PNAS open access option.

## References

- ↵
- Girvan M,
- Newman MEJ

- ↵
- ↵
- Henry AD,
- Lubell M,
- McCoy M

- ↵
- Schelling TC

- ↵
- ↵
- Nowak MA

- ↵
- Dietz T,
- Henry AD

- ↵
- ↵
- Hong L,
- Page SE

- ↵
- Rendell L,
- et al.

- ↵
- ↵
- Clark WAV,
- Fossett M

- ↵
- ↵
- ↵
- ↵
- Laurie AJ,
- Jaggi NK

- ↵
- ↵
- ↵
- Singh A,
- Haahr M

- ↵
- ↵
- ↵
- Karoński M,
- Prömel HJ

- Wormald N

- ↵
- ↵
- Carrington PJ,
- Scott J,
- Wasserman S

- Snijders TAB

- ↵
- Barabási AL

- ↵
- Aiello W,
- Bonato A,
- Cooper C,
- Janssen J,
- Prałat P

- ↵
- Prałat P,
- Wormald N

- ↵

## Citation Manager Formats

## Article Classifications

- Social Sciences
- Social Sciences

- Physical Sciences
- Mathematics

## Sign up for Article Alerts

## Jump to section

- Article
- Abstract
- The Problem of Segregation in Social Networks
- A General Model of Network Segregation
- Predicting the Convergence Process: A Specific Case
- Model Implications
- The Distribution of Attributes and Clustering in Segregated Networks
- Integrating Other Network Effects
- Conclusion
- Acknowledgments
- Footnotes
- References

- Figures & SI
- Info & Metrics