Network Degree Correlation

• The degree correlation is a measure of the probability of finding a node with degrees and at the two ends of a randomly selected link.

  Let be the probability that there is a -degree node at the end of a randomly selected link

  Then

  is a marginal probability

  • For directed networks we can define variants based on pairings of the in and out degree.

• The degree correlation function calculates, for all nodes with degree

  • This can be approximated using the following

• The degree correlation coefficient is a constant defined as

  Where

  • It is the Pearson correlation between the degrees found at the two ends of the same link under the assumption of a linear relationship between the degree correlation function and the degree.

Classes of Networks §

• An assortative network is one where the hubs tend to link to each other and avoid linking to small degree nodes.

  • For assortative networks, nodes of comparable degrees tend to link to each other.

• A dissassortative network is a network where hubs avoid linking with each other. Instead, they link to small degree nodes.

  • For disassortative networks, there is a hub and spoke character

• A neutral network is a network whose wiring is similar to random.

  • An indicator of this is that the number of links between hubs coincides with what is expected by chance. That is
    Where
    denotes the probability that a degree and node link up.
  • The degree correlation function is given by
  • The average degree of a node’s neighbor is dependent only on the global network characteristics

• A perfectly assortative network is an extreme case of an assortative network where each degree only connects with other degree nodes.

Correlations of Various Models §

Static Models §

• Models in this category tend to be neutral, and if forced to be simple, exhibit structural disassortativity.

• The Erdos Renyi Model is neutral by definition

• The Configuration model is neutral independent of the choice of degree distribution since we allow for multi-edges and loops.

  Any conflict caused by hubs are resolved by the multiple links between them. However, if the network is forced to be simple, then we will encounter structural disassortativity.

• For a hidden parameter model, the degree correlation is proportional follows

  • Here the network is neutral, but forcing it to be simple means encountering structural disassortativity. In such a case, the degree correlation function is

Evolving Networks §

• Initial attractiveness - depending on the value of we observe different scaling regimes.

  • If We have a disassortative phase transition where

  It follows a Power Law where

  • If , we have theBarabasi-Albert model where the network is neutral. We have that
  • If , we have weak assortativity and

• For the Bianconi-Barabasi model with uniform fitness distribution, the network is disassortative due to structural disassortativity.

  • Analysis shows that the real and the randomized degree correlation functions do not overlap, which means the disassortativity is not fully explained by the network being scale free.

Empirical Measurement §

• The use of empirical measurements is useful because analytical methods have their limitations
  • It is difficult to extract information from correlation matrices
  • It is difficult to compare networks with different correlations since magnitude is hard to infer.
  • contains a huge amount of information that is difficult to model.

Degree Correlation Function §

• For a neutral network we have

  Thus, the average degree of a node only depends on its global characteristics

• For an assortative network, the value of increases with .

• For a disassortative network, the value of decreases with

Approximate Degree Correlation §

• For assortative networks, the parameter
• For neutral networks, the parameter
• For disassortative networks

Degree Correlation Coefficient. §

• For assortative networks,
• For neutral networks,
• For disassortative networks .

Structural Disassortativity §

• Structural Disassortativity is a phenomenon wherein a network appears disassortative even though no degree correlation was imposed

• Because scale free networks have large hubs, there is a natural cutoff for given by

  If we have that diverges faster than a neutral network. Thus, an otherwise neutral network may show disassortativity as a result of the structural limitations of the network

• For a neutral network, the structural cutoff takes the form

  If vertices of degree exist, it is physically impossible to attach enough edges between them to maintain neutrality.

  • This is apparent in random networks and scale-free networks with

  • This follows because the correlation is given by

    And the ratio becomes

• There are two ways we can prevent strucctural disassortativity

  • Allow multiple edges
  • Remove hubs that have a degree larger than the structural cutoff.

• We can detect if a degree correlation was a consequence of structural disassortativity as follows:

  • Use degree preserving randomization on the original network and check if the generated network exhibits any degree correlations.
  • If it does, then we have structural disassortativity induced by the degree correlation.
  • Otherwise, if the real network exhibits correlations beyond the correlations in the generated network, then we have a meaningful property of the network.

Xalvi-Brunet-Sokolov Algorithm §

• The Xalvi-Brunet-Sokolov Algorithm generates maximally correlated networks with a predefined degree sequence

• The procedure is as follows

  • Link selection. Choose two links at random. Label the four nodes at the end of these two links such that their degrees are ordered

  • Rewiring. Break the selected links and rewire them to form new pairs depending on which is desired

    • For assortative networks, pair the two highest degree nodes and the two lowest degree nodes.
    • For disassortative networks, the new pairs are and

  • Iteration: We iterate over these steps to enhance the assortativity or disassortativity of the network.

• When generating an assortative network, the degree correlation function is assortative for small but disassortative for large due to the structural cutoff.

• For scale free networks, the system cannot sustain assortativity for high .

Impact §

• The more disassortative the network, the harder it is for the giant component to emerge.
  • By the Erdos-Renyi theorem on giant components and how giant components emerge within random networks, *a giant component emerges in a neutral network when . *
  • For assortative networks, the phase moves to a lower (i.e., ).
    • However, because hubs tend to link to each other, assortative networks tend to have smaller giant components compared to neutral networks.
  • For disassortative networks, the phase transition moves to higher .

So the giant component emerges at .

• Hub removal becomes more impactful the more disassortative the network since hubs are connected to more nodes.
  • In assortative networks, because the giant component mainly consists of hubs linking with each other, the impact of removing any single hub is low.
  • In disassortative networks, the impact of removing hubs is much higher since each hub tends to connect to many small-degree nodes, which fall off when a hub is deleted
• Assortative networks have shorter paths on average but larger diameters.
  • This arises from the fact we connect mostly to nodes with the same degree, so we favor long chains of nodes, each of with have similar degree to their neighbors.
• Degree correlation can influence the properties that a network has.
  • Degree correlations influence the system’s stability against stimuli and perturbations.
  • Degree correlations have an impact on the Vertex Cover Problem
  • Degree correlations impact the ability to control the network.

Links §

• Barabasi
• Fundamental Constructs of Network Science