Section 7.1
Introduction

Angelina Jolie and Brad Pitt, Ben Affleck and Jennifer Garner, Harrison Ford and Calista Flockhart, Michael Douglas and Catherine Zeta-Jones, Tom Cruise and Katie Holmes, Richard Gere and Cindy Crawford (Image 7.1). An odd list, yet instantly recognizable to those immersed in the headline-driven world of celebrity couples. They are Hollywood stars that are or were married. Their weddings (and breakups) has drawn countless hours of media coverage and sold millions of gossip magazines. Thanks to them we take for granted that celebrities marry each other. We rarely pause to ask: Is this normal? In other words, what is the true chance that a celebrity marries another celebrity?

Assuming that a celebrity could date anyone from a pool of about a hundred million (10⁸) eligible individuals worldwide, the chances that their mate would be another celebrity from a generous list of 1,000 other celebrities is only 10^-5. Therefore, if dating were driven by random encounters, celebrities would never marry each other.

Even if we do not care about the dating habits of celebrities, we must pause and explore what this phenomenon tells us about the structure of the social network. Celebrities, political leaders, and CEOs of major corporations tend to know an exceptionally large number of individuals and are known by even more. They are hubs. Hence celebrity dating (Image 7.1) and joint board memberships are manifestations of an interesting property of social network: hubs tend to have ties to other hubs.

As obvious this may sound, this property is not present in all networks. Consider for example the protein-interaction network of yeast, shown in Image 7.2. A quick inspection of the network reveals its scale-free nature: numerous one- and two-degree proteins coexist with a few highly connected hubs. These hubs, however, tend to avoid linking to each other. They link instead to many small-degree nodes, generating a hub-and-spoke pattern. This is particularly obvious for the two hubs highlighted in Image 7.2: they almost exclusively interact with small-degree proteins.

A brief calculation illustrates how unusual this pattern is. Let us assume that each node chooses randomly the nodes it connects to. Therefore the probability that nodes with degrees k and k′ link to each other is

Equation (7.1) tells us that hubs, by the virtue of the many links they have, are much more likely to connect to each other than to small degree nodes. Indeed, if k and k′ are large, so is p_k,k’ . Consequently, the likelihood that hubs with degrees k=56 and k’ = 13 have a direct link between them is p_k,k’ = 0.16, which is 400 times larger than p_1,2 = 0.0004, the likelihood that a degree-two node links to a degree-one node. Yet, there are no direct links between the hubs in Image 7.2, but we observe numerous direct links between small degree nodes.

Instead of linking to each other, the hubs highlighted in Image 7.2 almost exclusively connect to degree one nodes. By itself this is not unexpected: We expect that a hub with degree k = 56 should link to N₁p_{1, 56} ≈ 12 nodes with k = 1. The problem is that this hub connects to 46 degree one neighbors, i.e. four times the expected number.

In summary, while in social networks hubs tend to “date” each other, in the protein interaction network the opposite is true: The hubs avoid linking to other hubs, connecting instead to many small degree nodes. While it is dangerous to derive generic principles from two examples, the purpose of this chapter is to show that these patterns are manifestations of a general property of real networks: they exhibit a phenomena called degree correlations. We discuss how to measure degree correlations and explore their impact on the network topology.

Section 7.2
Assortativity and Disassortativity

Just by the virtue of the many links they have, hubs are expected to link to each other. In some networks they do, in others they don’t. This is illustrated in Image 7.3, that shows three networks with identical degree sequences but different topologies:

• Neutral Network
  Image 7.3b shows a network whose wiring is random. We call this network neutral, meaning that the number of links between the hubs coincides with what we expect by chance, as predicted by (7.1).
• Assortative Network
  The network of Image 7.3a has precisely the same degree sequence as the one in Image 7.3b. Yet, the hubs in Image 7.3a tend to link to each other and avoid linking to small-degree nodes. At the same time the small-degree nodes tend to connect to other small-degree nodes. Networks displaying such trends are assortative. An extreme manifestation of this pattern is a perfectly assortative network, in which each degree-k node connects only to other degree-k nodes (Image 7.4).
• Disassortative Network
  In Image 7.3c the hubs avoid each other, linking instead to small-degree nodes. Consequently the network displays a hub and-spoke character, making it disassortative.

In general a network displays degree correlations if the number of links between the high and low-degree nodes is systematically different from what is expected by chance. In other words, the number of links between nodes of degrees k and k′ deviates from (7.1).

The information about potential degree correlations is captured by the degree correlation matrix, e_ij, which is the probability of finding a node with degrees i and j at the two ends of a randomly selected link. As e_ij is a probability, it is normalized, i.e.

In (5.27) we derived the probability q_k that there is a degree-k node at the end of the randomly selected link, obtaining

We can connect q_k to e_ij via

In neutral networks, we expect

A network displays degree correlations if e_ij deviates from the random expectation (7.5). Note that (7.2) - (7.5) are valid for networks with an arbitrary degree distribution, hence they apply to both random and scale-free networks.

Given that e_ij encodes all information about potential degree correlations, we start with its visual inspection. Figures 7.3d,e,f show e_ij for an assortative, a neutral and a disassortative network. In a neutral network small and high-degree nodes connect to each other randomly, hence e_ij lacks any trend (Image 7.3e). In contrast, assortative networks show high correlations along the main diagonal, indicating that nodes predominantly connect to nodes with comparable degree. Therefore low-degree nodes tend to link to other low-degree nodes and hubs to hubs (Image 7.3d). In disassortative networks e_ij displays the opposite trend: it has high correlations along the secondary diagonal. Therefore high-degree nodes tend to connect to low-degree nodes (Image 7.3f).

In summary information about degree correlations is carried by the degree correlation matrix e_ij. Yet, the study of degree correlations through the inspection of e_ij has numerous disadvantages:

• It is difficult to extract information from the visual inspection of a matrix.
• Unable to infer the magnitude of the correlations, it is difficult to compare networks with different correlations.
• e_jk contains approximately k_max²/2 independent variables, representing a huge amount of information that is difficult to model in analytical calculations and simulations.

We therefore need to develop a more compact way to detect degree correlations. This is the goal of the subsequent sections.

Section 7.3
Measuring Degree Correlations

While e_ij contains the complete information about the degree correlations characterizing a particular network, it is difficult to interpret its content. In this section is to introduce the degree correlation function that offers a simpler way to quantify degree correlations.

Degree correlations capture the relationship between the degrees of nodes that link to each other. One way to quantify their magnitude is to measure for each node i the average degree of its neighbors (Image 7.5)

The degree correlation function calculates (7.6) for all nodes with degree k [4, 5]

where P(k’|k) is the conditional probability that following a link of a k-degree node we reach a degree-k' node. Therefore k_nn(k) is the average degree of the neighbors of all degree-k nodes.To quantify degree correlations we inspect the dependence of k_nn(k) on k.

• Neutral Network
  For a neutral network (7.3)-(7.5) predict $P(k'|k) = \frac{{e_{kk'} }}{{\sum\limits_{k'} {e_{kk'} } }} = \frac{{e_{kk'} }}{{q_k }} = \frac{{q_{k'} q_k }}{{q_k }} = q_{k'} \ hspace{20 mm} (7 . 8)$ This allows us to express k_nn(k) as $k_{nn} (k) = \sum\limits_{k'} {k'q_{k'} = \sum\limits_{k'} {k'\frac{{k'p(k')}}{{\left\langle k \right\rangle }} = \frac{{\left\langle {k^2 } \right\rangle }}{k}} } \hspace{20 mm} (7 . 9)$ Therefore, in a neutral network the average degree of a node’s neighbors is independent of the node’s degree k and depends only on the global network characteristics 〈k〉 and 〈k²〉. So plotting k_nn(k) in function of k should result in a horizontal line at 〈k²〉 / 〈k〉, as observed for the power grid (Image 7.6b). Equation (7.9) also captures an intriguing property of real networks: our friends are more popular than we are, a phenomenon called the friendship paradox (BOX 7.1).
• Assortative Network
  In assortative networks hubs tend to connect to other hubs, hence the higher is the degree k of a node, the higher is the average degree of its nearest neighbors. Consequently for assortative networks k_nn(k) increases with k, as observed for scientific collaboration networks (Image 7.6a).
• Disassortative Network
  In disassortative network hubs prefer to link to low-degree nodes. Consequently k_nn(k) decreases with k, as observed for the metabolic network (Image 7.6c).

The behavior observed in Image 7.6 prompts us to approximate the degree correlation function with [4]

If the scaling (7.10) holds, then the nature of degree correlations is determined by the sign of the correlation exponent μ:

• Assortative Networks: μ > 0
  A fit to k_nn(k) for the science collaboration network provides μ = 0.37 ± 0.11 (Image 7.6a).
• Neutral Networks: μ = 0
  According to (7.9) k_nn(k) is independent of k. Indeed, for the power grid we obtain μ = 0.04 ± 0.05, which is indistinguishable from zero (Image 7.6b).
• Disassortative Networks: μ < 0
  For the metabolic network we obtain μ = − 0.76 ± 0.04 (Image 7.6c).

In summary, the degree correlation function helps us capture the presence or absence of correlations in real networks. The k_nn(k) function also plays an important role in analytical calculations, allowing us to predict the impact of degree correlations on various network characteristics (SECTION 7.6). Yet, it is often convenient to use a single number to capture the magnitude of correlations present in a network. This can be achieved either through the correlation exponent μ defined in (7.10), or using the degree correlation coefficient introduced in BOX 7.2.

Section 7.4
Structural Cutoffs

Throughout this book we assumed that networks are simple, meaning that there is at most one link between two nodes (Figure 2.17). For example, in the email network we place a single link between two individuals that are in email contact, despite the fact that they may have exchanged multiple messages. Similarly, in the actor network we connect two actors with a single link if they acted in the same movie, independent of the number of joint movies. All datasets discussed in Table 4.1 are simple networks.

In simple networks there is a puzzling conflict between the scale-free property and degree correlations [10, 11]. Consider for example the scalefree network of Image 7.7a, whose two largest hubs have degrees k = 55 and k' = 46. In a network with degree correlations e_kk' the expected number of links between k and k' is

For a neutral network e_kk' is given by (7.5), which, using (7.3), predicts

Therefore, given the size of these two hubs, they should be connected to each other by two to three links to comply with the network’s neutral nature. Yet, in a simple network we can have only one link between them, causing a conflict between degree correlations and the scale-free property. The goal of this section is to understand the origin and the consequences of this conflict.

For small k and k' (7.14) predicts that E_kk’ is also small, i.e. we expect less than one link between the two nodes. Only for nodes whose degree exceeds some threshold k_s does (7.14) predict multiple links. As we show in ADVANCED TOPICS 7.B, k_s, called structural cutoff, scales as

In other words, nodes whose degree exceeds (7.15) have E_kk’ > 1, a conflict that as we show below gives rise to degree correlations.

In other words, nodes whose degree exceeds (7.15) have E_kk’ > 1, a conflict that as we show below gives rise to degree correlations.

To understand the consequences of the structural cutoff we must first ask if a network has nodes whose degrees exceeds (7.15). For this we compare the structural cutoff, k_s, with the natural cutoff, k_max, which is the expected largest degree in a network. According to (4.18), for a scale-free network k_max ~ N^1/γ-1 . Comparing k_max to k_s allows us to distinguish two regimes:

• No Stuctural Cutoff
  For random networks and scale-free networks with γ ≥ 3 the exponent of k_max is smaller than 1/2, hence k_max is always smaller than k_s. In other words the node size at which the structural cutoff turns on exceeds the size of the biggest hub. Consequently we have no nodes for which E_kk’ > 1. For these networks we do not have a conflict between degree correlations and the simple network requirement.
• Stuctural Disassortativity
  For scale-fee networks with γ < 3 we have 1/(γ-1) > 1/2, i.e. k_s can be smaller than k_max. Consequently nodes whose degree is between k_s and k_max can violate E_kk’ > 1. In other words the network has fewer links between its hubs than (7.14) would predict. These networks will therefore become disassortative, a phenomenon we call structural disassortativity. This is illustrated in Image 7.8a,b that show a simple scale-free network generated by the configuration model. The network shows disassortative scaling, despite the fact that we did not impose degree correlations during its construction.

We have two avenues to generate networks that are free of structural disassortativity:

1. We can relax the simple network requirement, allowing multiple links between the nodes. The conflict disappears and the network will be neutral (Image 7.8c,d).
2. If we insist having a simple scale-free network that is neutral or assortative, we must remove all hubs with degrees larger than k_s. This is illustrated in Image 7.8e,f: a network that lacks nodes with k ≥ 100 is neutral.

Finally, how can we decide whether the correlations observed in a particular network are a consequence of structural disassortativity, or are generated by some unknown process that leads to degree correlations? Degree-preserving randomization (Image 4.17) helps us distinguish these two possibilities:

1. Degree Preserving Randomization with Simple Links (R-S)
   We apply degree-preserving randomization to the original network and at each step we make sure that we do not permit more than one link between a pair of nodes. On the algorithmic side this means that each rewiring that generates multi-links is discarded. If the real k_nn(k) and the randomized k_nn^R−S(k) are indistinguishable, then the correlations observed in a real system are all structural, fully explained by the degree distribution. If the randomized knn k_nn^R−S(k) does not show degree correlations while k_nn(k) does, there is some unknown process that generates the observed degree correlations.
2. Degree Preserving Randomization with Multiple Links (R-M)
   For a self-consistency check it is sometimes useful to perform degree-preserving randomization that allows for multiple links between the nodes. On the algorithmic side this means that we allow each random rewiring, even if it leads to multi-links. This process eliminates all degree correlations.

We performed the randomizations discussed above for three real networks. As Image 7.9a shows, the assortative nature of the scientific collaboration network disappears under both randomizations. This indicates that the assortative correlations of the collaboration network is not linked to its scale-free nature. In contrast, for the metabolic network the observed disassortativity remains unchanged under R-S (Image 7.9c). Consequently the disassortativity of the metabolic network is structural, being induced by its degree distribution.

In summary, the scale-free property can induce disassortativity in simple networks. Indeed, in neutral or assortative networks we expect multiple links between the hubs. If multiple links are forbidden (simple graph), the network will display disassortative tendencies. This conflict vanishes for scale-free networks with γ ≥ 3 and for random networks. It also vanishes if we allow multiple links between the nodes.

Section 7.5
Correlations in Real Networks

To understand the prevalence of degree correlations we need to inspect the correlations characterizing real networks. In Image 7.10 we show the k_nn(k) function for the ten reference networks, observing several patterns:

• Power Grid
  For the power grid k_nn(k) is flat and indistinguishable from its randomized version, indicating a lack of degree correlations (Image 7.10a). Hence the power grid is neutral.
• Internet
  For small degrees (k ≤ 30) k_nn(k) shows a clear assortative trend, an effect that levels off for high degrees (Image 7.10b). The degree correlations vanish in the randomized version of the Internet map. Hence the Internet is assortative, but structural cutoffs eliminate the effect for high k.
• Social Networks
  The three networks capturing social interactions, the mobile phone network, the science collaboration network and the actor network, all have an increasing knn(k), indicating that they are assortative (Image 7.10c-e). Hence in these networks hubs tend to link to other hubs and low-degree nodes tend to link to low-degree nodes. The fact that the observed k_nn(k) differs from the k_nn^R-S(k), indicates that the assortative nature of social networks is not due to their scale-free the degree distribution.
• Email Network
  While the email network is often seen as a social network, its k_nn(k) decreases with k, documenting a clear disassortative behavior (Imag 7.10f). The randomized k_nn^R-S(k) also decays, indicating that we are observing structural disassortativity, a consequence of the network’s scale-free nature.
• Biological Networks
  The protein interaction and the metabolic network both have a negative μ, suggesting that these networks are disassortative. Yet, the scaling of k_nn^R-S(k) is indistinguishable from k_nn(k), indicating that we are observing structural disassortativity, rooted in the scale-free nature of these networks (Image 7.10 g,h).
• WWW
  The decaying k_nn(k) implies disassortative correlations (Image 7.10i). The randomized k_nn^R-S(k) also decays, but not as rapidly as k_nn(k). Hence the disassortative nature of the WWW is not fully explained by its degree distribution.
• Citation Network
  This network displays a puzzling behavior: for k ≤ 20 the degree correlation function k_nn(k) shows a clear assortative trend; for k > 20, however, we observe disassortative scaling (Image 7.10j). Such mixed behavior can emerge in networks that display extreme assortativity (Image 7.13b). This suggests that the citation network is strongly assortative, but its scale-free nature induces structural disassortativity, changing the slope of k_nn(k) for k ≫ k_s.

In summary, Image 7.10 indicates that to understand degree correlations, we must always compare k_nn(k) to the degree randomized k_nn^R-S(k). It also allows us to draw some interesting conclusions:

1. Of the ten reference networks the power grid is the only truly neutral network. Hence most real networks display degree correlations.
2. All networks that display disassortative tendencies (email, protein, metabolic) do so thanks to their scale-free property. Hence, these are all structurally disassortative. Only the WWW shows disassortative correlations that are only partially explained by its degree distribution.
3. The degree correlations characterizing assortative networks are not explained by their degree distribution. Most social networks (mobile phone calls, scientific collaboration, actor network) are in this class and so is the Internet and the citation network

A number of mechanisms have been proposed to explain the origin of the observed assortativity. For example, the tendency of individuals to form communities, the topic of CHAPTER 9, can induce assortative correlations [12]. Similarly, the society has endless mechanisms, from professional committees to TV shows, to bring hubs together, enhancing the assortative nature of social and professional networks. Finally, homophily, a well documented social phenomena [13], indicates that individuals tend to associate with other individuals of similar background and characteristics, hence individuals with comparable degree tend to know each other. This degree-homophily may be responsible for the celebrity marriages as well (Image 7.1).

Section 7.6
Generating Correlated Networks

To explore the impact of degree correlations on various network characteristics we must first understand the correlations characterizing the network models discussed thus far. It is equally important to develop algorithm that can generate networks with tunable correlations. As we show in this section, given the conflict between the scale-free property and degree correlations, this is not a trivial task.

Degree Correlations in Static Models

Erdős-Rényi Model
The random network model is neutral by definition. As it lacks hubs, it does not develop structural correlations either. Hence for the Erdős-Rényi network k_nn(k) is given by (7.9), predicting μ = 0 for any 〈k〉 and N.

Configuration Model
The configuration model (Image 4.15) is also neutral, independent of the choice of the degree distribution p_k. This is because the model allows for both multi-links and self-loops. Consequently, any conflicts caused by the hubs are resolved by the multiple links between them. If, however, we force the network to be simple, then the generated network will develop structural disassortativity (Image 7.8).

Hidden Parameter Model
In the model e_jk is proportional to the product of the randomly chosen hidden variables η_j and η_k (Image 4.18). Consequently the network is technically uncorrelated. However, if we do not allow multi-links, for scalefree networks we again observe structural disassortativity. Analytical calculations indicate that in this case [18]

i.e. the degree correlation function follows (7.10) with μ = − 1.

Taken together, the static models explored so far generate either neutral networks, or networks characterized by structural disassortativity following (7.16).

Degree Correlations in Evolving Networks

To understand the emergence (or the absence) of degree correlations in growing networks, we start with the initial attractiveness model (SECTION 6.5), which includes as a special case the Barabási-Albert model

Initial Attractiveness Model
Consider a growing network in which preferential attachment follows (6.23), i.e. Π(k) ~ A + k, where A is the initial attractiveness. Depending on the value of A, we observe three distinct scaling regimes [15]:

1. Disassortative Regime: γ < 3
   If − m < A < 0 we have $k_{nn} (k) \sim m\frac{{(m + A)^{1 - \frac{A}{m}} }}{{2m + A}}\zeta \left( {\frac{{2m}}{{2m + A}}} \right)N^{\frac{A}{{2m + A}}} k^{\frac{A}{m}} \hspace{20 mm} (7 . 17)$ Hence the resulting network is disassortative, k_nn(k) decaying following the power-law [15, 16] $k_{nn} (k) \sim k^{\frac{{|A|}}{m}} \hspace{20 mm} (7 . 18)$
2. Neutral Regime: γ = 3
   If A = 0 the initial attractiveness model reduces to the Barabási-Albert model. In this case $k_{nn} (k) \sim \frac{m}{2}\ln N \hspace{20 mm} (7 . 19)$ Consequently k_nn(k) is independent of k, hence the network is neutral.
3. Weak Assortativity: γ > 3
   If A > 0 the calculations predict $k_{nn} (k) \approx (m + A)\ln \left( {\frac{k}{{m + A}}} \right) \hspace{20 mm} (7 . 20)$ As k_nn(k) increases logarithmically with k, the resulting network displays a weak assortative tendency, but does not follow (7.10).

In summary, (7.17) - (7.20) indicate that the initial attractiveness model generates rather complex degree correlations, from disassortativity to weak assortativity. Equation (7.19) also shows that the network generated by the Barabási-Albert model is neutral. Finally, (7.17) predicts a power law k-dependence for k_nn(k), offering analytical support for the empirical scaling (7.10).

Bianconi-Barabási Model
With a uniform fitness distribution the Bianconi-Barabási model generates a disassortative network [5] (Image 7.12). The fact that the randomized version of the network is also disassortative indicates that the model's disassortativity is structural. Note, however, that the real k_nn(k) and the randomized k_nn^R-S(k) do not overlap, indicating that the disassortativity of the model is not fully explained by its scale-free nature.

Tuning Degree Correlations

Several algorithms can generate networks with desired degree correlations [8, 17, 18]. Next we discuss a simplified version of the algorithm proposed by Xalvi-Brunet and Sokolov that aims to generate maximally correlated networks with a predefined degree sequence [19, 20, 21]. It consists of the following steps (Image 7.13a):

• Step 1: Link Selection
  Choose at random two links. Label the four nodes at the end of these two links with a, b, c, and d such that their degrees are ordered as $k_a \ge k_b \ge k_c \ge k_d$
• Step 2: Rewiring
  Break the selected links and rewire them to form new pairs. Depending on the desired degree correlations the rewiring is done in two ways:
  • Step 2A: Assortative
    By pairing the two highest degree nodes (a with b) and the two lowest degree nodes (c/ with d), we connect nodes with comparable degrees, enhancing the network’s assortative nature.
  • Step 2B: Disassortative
    By pairing the highest and the lowest degree nodes (a with d and b with c), we connect nodes with different degrees, enhancing the network’s disassortative nature.

By iterating these steps we gradually enhance the network’s assortative (Step 2A) or disassortative (Step 2B) features. If we aim to generate a simple network (free of multi-links), after Step 2 we check whether the particular rewiring leads to multi-links. If it does, we reject it, returning to Step 1.

The correlations characterizing the networks generated by this algorithm converge to the maximal (assortative) or minimal (disassortative) value that we can reach for the given degree sequence (Image 7.13b). The model has no difficulty creating disassortative correlations (Image 7.13e,f). In the assortative limit simple networks display a mixed k_nn(k): assortative for small k and disassortative for high k (Image 7.13b). This is a consequence of structural cutoffs: For scale-free networks the system is unable to sustain assortativity for high k. The observed behavior is reminiscent of the k_nn(k) function of citation networks (Image 7.10j).

The version of the Xalvi-Brunet & Sokolov algorithm introduced in Image 7.13 generates maximally assortative or disassortative networks. We can tune the magnitude of the generated degree correlations if we use the algorithm discussed in Image 7.14.

In summary, static models, like the configuration or hidden parameter model, are neutral if we allow multi-links, and develop structural disassortativity if we force them to generate simple networks. To generate networks with tunable correlations, we can use for example the Xalve-Brunet & Sokolov algorithm. An important result of this section is (7.16) and (7.18), offering the analytical form of the degree correlation function for the hidden paramenter model and for a growing network, in both case predicting a power-law k-dependence. These results offer analytical backing for the scaling hypothesis (7.10), indicating that both structural and dynamical effects can result in a degree correlation function that follows a power law.

Section 7.7
The Impact of Degree Correlations

As we have seen in Image 7.10, most real networks are characterized by some degree correlations. Social networks are assortative; biological networks display structural disassortativity. These correlations raise an important question: Why do we care? In other words, do degree correlations alter the properties of a network? And which network properties do they influence? This section addresses these important questions.

An important property of a random network is the emergence of a phase transition at 〈k〉 = 1, marking the appearance of the giant component (SECTION 3.6). Image 7.15 shows the relative size of the giant component for networks with different degree correlations, documenting several patterns [8, 19, 20]:

• Assortative Networks
  For assortative networks the phase transition point moves to a lower 〈k〉, hence a giant component emerges for 〈k〉 < 1. The reason is that it is easier to start a giant component if the high-degree nodes seek out each other.
• Disassortative Networks
  The phase transition is delayed in disassortative networks, as in these the hubs tend to connect to small degree nodes. Consequently, disassortative networks have difficulty forming a giant component.
• Giant Component
  For large 〈k〉 the giant component is smaller in assortative networks than in neutral or disassortative networks. Indeed, assortativity forces the hubs to link to each other, hence they fail to attract to the giant component the numerous small degree nodes.

These changes in the size and the structure of the giant component have implications to the spread of diseases [22, 23, 24], the topic of CHAPTER 10. Indeed, as we have seen in Image 7.10, social networks tend to be assortative. The high degree nodes therefore form a giant component that acts as a “reservoir” for the disease, sustaining an epidemic even when on average the network is not sufficiently dense for the virus to persist.

The altered giant component has implications for network robustness as well [25]. As we discuss in CHAPTER 8, the removal of a network's hubs fragments a network. In assortative networks hub removal makes less damage because the hubs form a core group, hence many of them are redundant. Hub removal is more damaging in disassortative networks, as in these the hubs connect to many small-degree nodes, which fall off the network once a hub is deleted.

Let us mention a few additional consequences of degree correlations:

• Image 7.16 shows the path-length distribution of a random network rewired to display different degree correlations. It indicates that in assortative networks the average path length is shorter than in neutral networks. The most dramatic difference is in the network diameter, d_max, which is significantly higher for assortative networks. Indeed, assortativity favors links between nodes with similar degree, resulting in long chains of k = 2 nodes, enhancing d_max (Image 7.13c).
• Degree correlations influence a system’s stability against stimuli and perturbations [26] as well as the synchronization of oscillators placed on a network [27, 28].
• Degree correlations have a fundamental impact on the vertex cover problem [29], a much-studied problem in graph theory that requires us to find the minimal set of nodes (cover) such that each link is connected to at least one node in the cover (BOX 7.4).
• Degree correlations impact our ability to control a network, altering the number of input signals one needs to achieve full control [30].

In summary, degree correlations are not only of academic interest, but they influence numerous network characteristics and have a discernable impact on many processes that take place on a network.

Section 7.8
Summary

Degree correlations were first discovered in 2001 in the context of the Internet by Romualdo Pastor-Satorras, Alexei Vazquez, and Alessandro Vespignani [4, 5], who also introduced the degree correlation function k_nn(k) and the scaling (7.10). A year later Kim Sneppen and Sergey Maslov used the full p(k_i,k_j), related to the e_ij matrix, to characterize the degree correlations of protein interaction networks [32]. In 2003 Mark Newman introduced the degree correlation coefficient [8, 9] together with the assortative, neutral, and disassortative distinction. These terms have their roots in social sciences [13]:

Assortative mating reflects the tendency of individuals to date or marry individuals that are similar to them. For example, low-income individuals marry low-income individuals and college graduates marry college graduates. Network theory uses assortativity in the same spirit, capturing the degree-based similarities between nodes: In assortative networks hubs tend to connect to other hubs and small-degree nodes to other small-degree nodes. In a network environment we can also encounter the traditional assortativity, when nodes of similar properties link to each other (Image 7.18).

Disassortative mixing, when individuals link to individuals wo are unlike them, is also common in some social and economic systems. Sexual networks are perhaps the best example, as most sexual relationships are between individuals of different gender. In economic settings trade typically takes place between individuals of different skills: the baker does not sell bread to other bakers, and the shoemaker rarely fixes other shoemaker's shoes.

Taken together, there are several reasons why we care about degree correlations in networks (BOX 7.5):

• Degree correlations are present in most real networks (SECTION 7.5).
• Once present, degree correlations change a network’s behavior (SECTION 7.7).
• Degree correlations force us to move beyond the degree distribution, representing quantifiable patters that govern the way nodes link to each other that are not captured by p_k alone.

Despite the considerable effort devoted to characterizing degree correlations, our understanding of the phenomena remains incomplete. For example, while in SECTION 7.6 we offered an algorithm to tune degree correlations, the problem is far from being fully resolved. Indeed, the most accurate description of a network's degree correlations is contained in the e_ij matrix. Generating networks with an arbitrary e_ij remains a difficult task.

Finally, in this chapter we focused on the k_nn(k) function, which captures two-point correlations. In principle higher order correlations are also present in some networks (BOX 7.6). The impact of such three or four point correlations remains to be understood.

Section 7.9
Homework

1. Detailed Balance for Degree Correlations

   Express the joint probability e_kk', the conditional probability P(k'|k) and the probability q_k, discussed in this chapter, in terms of number of nodes N, average degree 〈k〉, number of nodes with degree k, N_k, and the number of links connecting nodes of degree k and k', E_kk' (note that E_kk' is twice the number of links when k = k'). Based on these expressions, show that for any network we have

   $e_{kk'} = q_k P(k'|k)$
2. Star Network

   Consider a star network, where a single node is connected to N – 1 degree one nodes. Assume that N≫1.

   1. What is the degree distribution p_k of this network?
   2. What is the probability q_k that moving along a randomly chosen link we find at its end a node with degree k?
   3. Calculate the degree correlation coefficient r for this network. Use the expressions of e_kk' and P(k'|k) calculated in HOMEWORK 7.1.
   4. Is this network assortative or disassortative? Explain why.
   
   
3. Structural Cutoffs

   Calculate the structural cutoff k_s for the undirected networks listed in Table 4.1. Based on the plots in Image 7.10, predict for each network whether k_s is larger or smaller than the maximum expected degree k_max. Confirm your prediction by calculating k_max.

4. Degree Correlations in Erdős-Rényi Networks

   Consider the Erdős-Rényi G(N,L) model of random networks, introduced in CHAPTER 2 (BOX 3.1 and SECTION 3.2), where N labeled nodes are connected with L randomly placed links. In this model, the probability that there is a link connecting nodes i and j depends on the existence of a link between nodes l and s.

   1. Write the probability that there is a link between i and j, e_ij and the probability that there is a link between i and j conditional on the existence of a link between l and s.
   2. What is the ratio of such two probabilities for small networks? And for large networks?
   3. What do you obtain for the quantities discussed in (a) and (b) if you use the Erdős-Rényi G(N,p) model?

   Based on the results found for (a)-(c) discuss the implications of using the G(N,L) model instead of the G(N,p) model for generating random networks with small number of nodes.

Section 7.10
Advanced Topic 7.A
Degree Correlation Coefficient

In BOX 7.2 we defined the degree correlation coefficient r as an alternative measure of degree correlations [8, 9]. The use of a single number to characterize degree correlations is attractive, as it offers a way to compare the correlations observed in networks of different nature and size. Yet, to effectively use r we must be aware of its origin.

The hypothesis behind the correlation coefficient r implies that the k_nn(k) function can be approximated by the linear function

This is different from the scaling (7.10), which assumes a power law dependence on k. Equation (7.21) raises several issues:

• The initial attractiveness model predicts a power law (7.18) or a logarithmic k-dependence (7.20) for the degree correlation function. A similar power law is derived in (7.16) for the hidden parameter model. Consequently, r forces a linear fit to an inherently nonlinear function. This linear dependence is not supported by numerical simulations or analytical calculations. Indeed, as we show in Image 7.19, (7.21) offers a poor fit to the data for both assortative and disassortative networks.
• As we have seen in Image 7.10, the dependence of k_nn(k) on k is complex, often changing trends for large k thanks to the structural cutoff. A linear fit ignores this inherent complexity.
• The maximally correlated model has a vanishing r for large N, despitethe fact that the network maintains its degree correlations (BOX 7.7).This suggests that the degree correlation coefficient has difficulty detectingcorrelations characterizing large networks.

Relationship Between μ and r

On the positive side, r and μ are not independent of each other. To show this we calculated r and μ for the ten reference networks (TABLE 7.1). The results are plotted in Image 7.20, indicating that μ and r correlate for positive r. Note, however, that this correlation breaks down for negative r. To understand the origin of this behavior, next we derive a direct relationship between μ and r. To be specific we assume the validity of (7.10) and determine the value of r for a network with correlation exponent μ.

We start by determining a from (7.10). We can write the second moment of the degree distribution as

which leads to

We now calculate r for a network with a given μ:

For μ = 0 the term in the last parenthesis vanishes, obtaining r = 0. Hence if μ = 0 (neutral network), the network will be neutral based on r as well. For k > 1 (7.22) suggests that for μ > 0 the parenthesis is positive, hence r > 0, and for μ < 0 the parenthesis is negative, hence r < 0. Therefore r and μ predict degree correlations of similar kind.

In summary, if the degree correlation function follows (7.10), then the sign of the degree correlation exponent μ will determine the sign of the coefficient r:

Directed Networks

To measure correlations in directed networks we must take into account that each node i is characterized by an incoming k_iⁱⁿ and an outgoing em>k_i^out degree. We therefore define four degree correlation coefficients, r_in,in, r_in,out, r_out,in, r_out,out, capturing all possible combinations between the incoming and outgoing degrees of two connected nodes (Image 7.21a-d). Formally we have [14]

where α and β refer to the in and out indices and q_←j^α in the probability of finding a node with α-degree j by following a random link backward and q_→k^β in the probability of finding a β-link with degree k by following a random link forward. σ_←^α and σ_→^β are the corresponding standard deviations. To illustrate the use of (7.23), in Image 7.21e we show the four correlation coefficients for the five directed reference networks (TABLE 7.1). Note, however, that for a complete characterization of degree correlations it is desirable to measure the four k_nn(k) functions as well (BOX 7.3)

In summary, the degree correlation coefficient assumes that k_nn(k) scales linearly with k, a hypothesis that lacks numerical and analytical support. Analytical calculations predict the power-law form (7.10) or the weaker logarithmic dependence (7.20). Yet, in general the sign of r and μ do agree. Consequently, we can use r to get a quick sense of the nature of the potential correlations present in a network. Yet, the accurate characterization of the underlying degree correlations requires us to measure k_nn(k).

Section 7.11
Advanced Topic 7.B
Structural Cutoffs

As discussed in SECTION 7.4, the fundamental conflict between the scalefree property and degree correlations leads to a structural cutoff in simple networks. In this section we derive (7.15), calculating how the structural cutoff depends on the system size N [11].

We start by defining

where E_kk′ is the number of links between nodes of degrees k and k’ for k≠k’ and twice the number of connecting links for k=k’, and

is the largest possible value of E_kk′. The origin of (7.25) is explained in Image 7.22. Consequently, we can write r_kk’ as

As m_kk’ is the maximum of E_kk’, we must have r_kk’ ≤ 1 for any k and k’. Strictly speaking, in simple networks degree pairs for which r_kk’ > 1 cannot exist. Yet, for some networks and for some k, k’ pairs r_kk’ is larger than one. This is clearly non-physical and signals some conflict in the network configuration. Hence, we define the structural cutoff k_s as the solution of the equation

Note that as soon as k > Np_k’ and k’ > Np_k , the effects of the restriction on the multiple links are felt, turning the expression for r_kk′ into

For scale-free networks these conditions are fulfilled in the region k, k’ > (aN)^1/(γ+1), where a is a constant that depends on p_k. Note that this value is below the natural cutoff. Consequently this scaling provides a lower bound for the structural cutoff, in the sense that whenever the cutoff of the degree distribution falls below this limit, the condition r_kk’ < 1 is always satisfied.

For neutral networks the joint distribution factorizes as

Hence, the ratio (7.28) becomes

Therefore, the structural cutoff needed to preserve the condition r_kk’ ≤ 1 has the form [11, 34, 35, 36]

which is (7.15). Note that (7.31) is independent of the degree distribution of the underlying network. Consequently, for a scale-free network ks(N) is independent of the degree exponent γ.

Section 7.12
Bibliography

[1] P. Uetz, L. Giot, G. Cagney, T. A. Mansfield, RS Judson, JR Knight, D. Lockshon, V. Narayan, M. Srinivasan, P. Pochart, A. Qureshi-Emili, Y. Li, B. Godwin, D. Conover, T. Kalbfleisch, G. Vijayadamodar, M. Yang, M. Johnston, S. Fields, J. M. Rothberg. A comprehensive analysis of protein-protein interactions in Saccharomyces cerevisiae. Nature, 403: 623–627, 2000.

[2] I. Xenarios, D. W. Rice, L. Salwinski, M. K. Baron, E. M. Marcotte, D. Eisenberg. DIP: the database of interacting proteins. Nucleic Acids Res., 28: 289–29, 2000.

[3] H. Jeong, S.P. Mason, A.-L. Barabási, and Z.N. Oltvai. Lethality and centrality in protein networks. Nature, 411: 41-42, 2001.

[4] R. Pastor-Satorras, A. Vázquez, and A. Vespignani. Dynamical and correlation properties of the Internet. Phys. Rev. Lett., 87: 258701, 2001.

[5] A. Vazquez, R. Pastor-Satorras, and A. Vespignani. Large-scale topological and dynamical properties of Internet. Phys. Rev., E 65: 066130, 2002.

[6] S.L. Feld. Why your friends have more friends than you do. American Journal of Sociology, 96: 1464–1477, 1991.

[7] E.W. Zuckerman and J.T. Jost. What makes you think you’re so popular? Self evaluation maintenance and the subjective side of the “friendship paradox”. Social Psychology Quarterly, 64: 207–223, 2001.

[8] M. E. J. Newman. Assortative mixing in networks. Phys. Rev. Lett., 89: 208701, 2002.

[9] M. E. J. Newman. Mixing patterns in networks. Phys. Rev. E, 67: 026126, 2003.

[10] S. Maslov, K. Sneppen, and A. Zaliznyak. Detection of topological pattern in complex networks: Correlation profile of the Internet. Physica A, 333: 529-540, 2004.

[11] M. Boguna, R. Pastor-Satorras, and A. Vespignani. Cut-offs and finite size effects in scale-free networks. Eur. Phys. J. B, 38: 205, 2004.

[12] M. E. J. Newman and Juyong Park. Why social networks are different from other types of networks. Phys. Rev. E, 68: 036122, 2003.

[13] M. McPherson, L. Smith-Lovin, and J. M. Cook. Birds of a feather: homophily in social networks. Annual Review of Sociology, 27:415-444, 2001.

[14] J. G. Foster, D. V. Foster, P. Grassberger, and M. Paczuski. Edge direction and the structure of networks. PNAS, 107: 10815, 2010.

[15] A. Barrat and R. Pastor-Satorras. Rate equation approach for correlations in growing network models. Phys. Rev. E, 71: 036127, 2005.

[16] S. N. Dorogovtsev and J. F. F. Mendes. Evolution of networks. Adv. Phys., 51: 1079, 2002.

[17] J. Berg and M. Lässig. Correlated random networks. Phys. Rev. Lett., 89: 228701, 2002.

[18] M. Boguñá and R. Pastor-Satorras. Class of correlated random networks with hidden variables. Phys. Rev. E, 68: 036112, 2003.

[19] R. Xulvi-Brunet and I. M. Sokolov. Reshuffling scale-free networks: From random to assortative. Phys. Rev. E, 70: 066102, 2004.

[20] R. Xulvi-Brunet and I. M. Sokolov. Changing correlations in networks: assortativity and dissortativity. Acta Phys. Pol. B, 36: 1431, 2005.

[21] J. Menche, A. Valleriani, and R. Lipowsky. Asymptotic properties of degree-correlated scale-free networks. Phys. Rev. E, 81: 046103, 2010.

[22] V. M. Eguíluz and K. Klemm. Epidemic threshold in structured scale-free networks. Phys. Rev. Lett., 89:108701, 2002.

[23] M. Boguñá and R. Pastor-Satorras. Epidemic spreading in correlate complex networks. Phys. Rev. E, 66: 047104, 2002.

[24] M. Boguñá, R. Pastor-Satorras, and A. Vespignani. Absence of epidemic threshold in scale-free networks with degree correlations. Phys. Rev. Lett., 90: 028701, 2003.

[25] A. Vázquez and Y. Moreno. Resilience to damage of graphs with degree correlations. Phys. Rev. E, 67: 015101R, 2003.

[26] S.J. Wang, A.C. Wu, Z.X. Wu, X.J. Xu, and Y.H. Wang. Response of degree-correlated scale-free networks to stimuli. Phys. Rev. E, 75: 046113, 2007.

[27] F. Sorrentino, M. Di Bernardo, G. Cuellar, and S. Boccaletti. Synchronization in weighted scale-free networks with degree–degree correlation. Physica D, 224: 123, 2006.

[28] M. Di Bernardo, F. Garofalo, and F. Sorrentino. Effects of degree correlation on the synchronization of networks of oscillators. Int. J. Bifurcation Chaos Appl. Sci. Eng., 17: 3499, 2007.

[29] A. Vazquez and M. Weigt. Computational complexity arising from degree correlations in networks. Phys. Rev. E, 67: 027101, 2003.

[30] M. Posfai, Y Y. Liu, J-J Slotine, and A.-L. Barabási. Effect of correlations on network controllability. Scientific Reports, 3: 1067, 2013.

[31] M. Weigt and A. K. Hartmann. The number of guards needed by a museum: A phase transition in vertex covering of random graphs. Phys. Rev. Lett., 84: 6118, 2000.

[32] S. Maslov and K. Sneppen. Specificity and stability in topology of protein networks. Science, 296: 910–913, 2002.

[33] L. Adamic and N. Glance. The political blogosphere and the 2004 U.S. election: Divided they blog (2005).

[34] J. Park and M. E. J. Newman. The origin of degree correlations in the Internet and other networks. Phys. Rev. E, 66: 026112, 2003.

[35] F. Chung and L. Lu. Connected components in random graphs with given expected degree sequences. Annals of Combinatorics, 6: 125, 2002.

[36] Z. Burda and Z. Krzywicki. Uncorrelated random networks. Phys. Rev. E, 67: 046118, 2003.