Structural cut-off
| Network science | ||||
|---|---|---|---|---|
| Network types | ||||
| Graphs | ||||
|
||||
| Models | ||||
|
||||
| ||||
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 [math]\displaystyle{ E_{kk'} }[/math] be the number of edges between all vertices of degree [math]\displaystyle{ k }[/math] and [math]\displaystyle{ k' }[/math] if [math]\displaystyle{ k \neq k' }[/math], and twice the number if [math]\displaystyle{ k=k' }[/math]. Given that multiple edges between two vertices are not allowed, [math]\displaystyle{ E_{kk'} }[/math] is bounded by the maximum number of edges between two degree classes [math]\displaystyle{ m_{kk'} }[/math].
Then, the ratio can be written
- [math]\displaystyle{ 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')\}} }[/math],
where [math]\displaystyle{ \langle k \rangle }[/math] is the average degree of the network, [math]\displaystyle{ N }[/math] is the total number of vertices, [math]\displaystyle{ P(k) }[/math] is the probability a randomly chosen vertex will have degree [math]\displaystyle{ k }[/math], and [math]\displaystyle{ P(k,k') = E_{kk'}/\langle k \rangle N }[/math] is the probability that a randomly picked edge will connect on one side a vertex with degree [math]\displaystyle{ k }[/math] with a vertex of degree [math]\displaystyle{ k' }[/math].
To be in the physical region, [math]\displaystyle{ r_{kk'} \leq 1 }[/math] must be satisfied.
The structural cut-off [math]\displaystyle{ k_s }[/math] is then defined by [math]\displaystyle{ r_{k_sk_s} = 1 }[/math]. [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
- [math]\displaystyle{ k_s \sim (\langle k \rangle N )^{1/2} }[/math]
which is finite in any real network.
Thus, if vertices of degree [math]\displaystyle{ k \geq k_s }[/math] 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 [math]\displaystyle{ \gamma }[/math], [math]\displaystyle{ P(k) \sim k^{-\gamma} }[/math]. In a finite scale free network, the maximum degree of any vertex (also called the natural cut-off), scales as
- [math]\displaystyle{ k_{\text{max}} \sim N^{\frac{1}{\gamma-1}} }[/math].
Then, networks with [math]\displaystyle{ \gamma \lt 3 }[/math], which is the regime of most real networks, will have [math]\displaystyle{ k_\text{max} }[/math] diverging faster than [math]\displaystyle{ k_s\sim N^{1/2} }[/math] in a neutral network. This has the important implication that an otherwise neutral network may show disassortative degree correlations if [math]\displaystyle{ k_\text{max} \gt k_s }[/math]. 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]
- 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.
- Simply remove all vertices with degree [math]\displaystyle{ k\gt k_s }[/math]. 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
- ↑ 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 38 (2): 205–209. doi:10.1140/epjb/e2004-00038-8. Bibcode: 2004EPJB...38..205B.
- ↑ 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. Bibcode: 2005PhRvE..71b7103C.
- ↑ 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. Bibcode: 2007NJPh....9..173Z.
 |  |
