Structural cut-off

The structural cut-off is a concept in network science which imposes a degree cut-off in the degree distribution of a finite size network due to structural limitations (such as the simple graph property). Networks with vertices with degree higher than the structural cut-off will display structural disassortativity.

Definition

The structural cut-off is a maximum degree cut-off that arises from the structure of a finite size network.

Let E_{kk'} be the number of edges between all vertices of degree k and k' if k \neq k', and twice the number if k=k'. Given that multiple edges between two vertices are not allowed, E_{kk'} is bounded by the maximum number of edges between two degree classes  m_{kk'} .

Then, the ratio can be written

 r_{kk'} \equiv \frac{E_{kk'}}{m_{kk'}} = \frac{\langle k \rangle P(k,k')}{\min\{kP(k),k'P(k'), NP(k)P(k')\}} ,

where \langle k \rangle is the average degree of the network, N is the total number of vertices, P(k) is the probability a randomly chosen vertex will have degree k, and P(k,k') = E_{kk'}/\langle k \rangle N is the probability that a randomly picked edge will connect on one side a vertex with degree k with a vertex of degree k'.

To be in the physical region, r_{kk'} \leq 1 must be satisfied.

The structural cut-off  k_s is then defined by  r_{k_sk_s} = 1 . [1]

Structural cut-off for neutral networks

The structural cut-off plays an important role in neutral (or uncorrelated) networks, which do not display any assortativity. The cut-off takes the form

 k_s \sim (\langle k \rangle N )^{1/2}

which is finite in any real network.

Thus, if vertices of degree k \geq k_s exist, it is physically impossible to attach enough edges between them to maintain the neutrality of the network.

Structural disassortativity in scale-free networks

In a scale-free network the degree distribution is described by a power law with characteristic exponent \gamma, P(k) \sim k^{-\gamma}. In a finite scale free network, the maximum degree of any vertex (also called the natural cut-off), scales as

 k_{\text{max}} \sim N^{\frac{1}{\gamma-1}} .

Then, networks with \gamma < 3, which is the regime of most real networks, will have k_\text{max} diverging faster than k_s\sim N^{1/2} in a neutral network. This has the important implication that an otherwise neutral network may show disassortative degree correlations if k_\text{max} > k_s . This disassortativity is not a result of any microscopic property of the network, but is purely due to the structural limitations of the network. In the analysis of networks, for a degree correlation to be meaningful, it must be checked that the correlations are not of structural origin.

Impact of the structural cut-off

Generated networks

A network generated randomly by a network generation algorithm is in general not free of structural disassortativity. If a neutral network is required, then structural disassortativity must be avoided. There are a few methods by which this can be done: [2]

  1. Allow multiple edges between the same two vertices. While this means that the network is no longer a simple network, it allows for sufficient edges to maintain neutrality.
  2. Simply remove all vertices with degree k>k_s. This guarantees that no vertex is subject to structural limitations in its edges, and the network is free of structural disassortativity.

Real networks

In some real networks, the same methods as for generated networks can also be used. In many cases, however, it may not make sense to consider multiple edges between two vertices, or such information is not available. The high degree vertices (hubs) may also be an important part of the network that cannot be removed without changing other fundamental properties.

To determine whether the assortativity or disassortativity of a network is of structural origin, the network can be compared with a degree-preserving randomized version of itself (without multiple edges). Then any assortativity measure of the randomized version will be a result of the structural cut-off. If the real network displays any additional assortativity or disassortativity beyond the structural disassortativity, then it is a meaningful property of the real network.

Other quantities that depend on the degree correlations, such as some definitions of the rich-club coefficient, will also be impacted by the structural cut-off. [3]

See also

References

  1. Boguna, M.; Pastor-Satorras, R.; Vespignani, A. (1 March 2004). "Cut-offs and finite size effects in scale-free networks". The European Physical Journal B - Condensed Matter 38 (2): 205–209. doi:10.1140/epjb/e2004-00038-8.
  2. Catanzaro, Michele; Boguñá, Marián; Pastor-Satorras, Romualdo (February 2005). "Generation of uncorrelated random scale-free networks". Physical Review E 71 (2). doi:10.1103/PhysRevE.71.027103.
  3. Zhou, S; Mondragón, R J (28 June 2007). "Structural constraints in complex networks". New Journal of Physics 9 (6): 173–173. doi:10.1088/1367-2630/9/6/173.
This article is issued from Wikipedia - version of the Sunday, January 31, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.