Draft:Degree–degree distance

  • Comment: Not enough independent, significant coverage. WikiOriginal-9 (talk) 14:12, 7 November 2023 (UTC)

In the study of graphs and networks, the degree–degree distance[1] [2] (or degree ratio) refers to the measure of how different the degrees are between two connected nodes in a network. It captures the similarity or dissimilarity in the number of connections that two linked nodes have, providing insights into the network's structural properties.

In any given network, denoted as , each node is inherently associated with a scale, known as its degree . This scale corresponds to the number of other nodes that connect to node . Notably, this intrinsic scale is solely determined by the network's topology, and is not influenced by any external attributes. On the flip side, each link is essentially a 2-tuple without a comparable intrinsic scale, unless additional characteristics like weight or capacity are assigned to it. This absence of a common scale often renders links to a secondary role in most statistical analyses of complex networks.

One of the goals of introducing the concept of degree–degree distance is to reestablish the statistical relevance of links within the network. This makes degree–degree distance a "link-oriented" metric, putting it on a comparable footing with the well-established node's degree metric.

Definition

edit

The degree ratio, denoted as  , is defined by the formula

 

representing the ratio of the degrees of the connected nodes (larger degree over smaller degree). Here,   denotes a link that connects nodes   and  . It can also be reformulated as (hence bearing the name degree–degree distance)

 

This measure is purely topological, meaning it's determined solely by the network's structure.

The value of   ranges between 1 and the maximum degree ( ) in the network, which coincidentally matches the range of   if the minimum degree  .

Indeed, it is more fitting to designate   as the "distance".[2] Although both   and   qualify as "semi-distances" in a formal mathematical sense, only   meets the criteria for a semi-metric.[3]

Scale-free property

edit

When fitting to power laws, approximately 60 percent of real-world networks exhibit a statistically significant power-law degree–degree distance distribution across the full range  .[2] In contrast, only a third of real-world networks have a statistically significant power-law degree distribution across the full range  . This difference in statistical significance suggests that many real-world networks can genuinely be classified as scale-free, specifically through the lens of degree–degree distance rather than just degree distribution.

The above empirical observation has been rigorously proven by the following theorem: every network with a power-law distribution of   also has a power-law distribution of  , but not vice versa.[1] This result can be formulated as

 

where   denotes the set of all network models that have a power-law degree distribution (DD) in the asymptotic limit  , and   for power-law degree–degree distance distribution (DDDD) in the asymptotic limit  .

Proof

The proof contains two parts: (i) inclusion and (ii) strict inequality:

(i) To demonstrate this, the copula theory is used. Let   be the conditional joint probability of sequentially selecting two nodes   and   that have degrees  , respectively, conditioned on   and   being connected. This implies that   can be understood as half the probability of selecting a link (from all links) that connects two nodes of degrees  ​ and   (half because of the symmetry between   and  ​).

The marginal distribution focused on  ​ is proportional to  , since a node with a degree  ​ is   times more likely to be selected. For a degree distribution following  , this leads to a marginal distribution of  .

Invoking Sklar's theorem, the conditional joint probability can be expressed through:

 

By incorporating this equation into

 

which outlines the degree–degree distance distribution  ,[1] we derive

 

Therefore, the degree–degree distance distribution also contains a positive power-law term  , provided that the copula density function is smooth. This confirms its intrinsic relationship to the degree distribution in terms of their power-law exponents:  .

(ii) To prove this, it suffices to provide a counterexample with a power-law degree–degree distance distribution but not a power-law degree distribution. Such counterexamples have been found.[1]

Generalization

edit

The properties of   have been extended to cover wider aspects in the study of networks.[4][5] For example, it has been associated with network assortativity[6] and closeness.[3] Moreover, several node-specific metrics, initially formulated in terms of   like centrality and the clustering coefficient, can be revisited or expanded using   as well.

References

edit
  1. ^ a b c d Xiangyi Meng, Bin Zhou (2023). "Scale-Free Networks beyond Power-Law Degree Distribution". Chaos, Solitons & Fractals. 176: 114173. arXiv:2310.08110. doi:10.1016/j.chaos.2023.114173.
  2. ^ a b c Bin Zhou, Xiangyi Meng, H. Eugene Stanley (2020). "Power-Law Distribution of Degree–Degree Distance: A Better Representation of the Scale-Free Property of Complex Networks". Proc. Natl. Acad. Sci. 117 (26): 14812–14818. doi:10.1073/pnas.1918901117. PMC 7334507. PMID 32541015.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  3. ^ a b Tim S. Evans, Bingsheng Chen (2022). "Linking the Network Centrality Measures Closeness and Degree". Commun. Phys. 5 (1): 1–11.
  4. ^ Bing Wang, Jia Zhu, Daijun Wei (2021). "The self-similarity of complex networks: From the view of degree–degree distance". Mod. Phys. Lett. B. 35 (18). World Scientific: 2150331. doi:10.1142/S0217984921503310.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  5. ^ Alianna J Maren (2021). "The 2-D cluster variation method: Topography illustrations and their enthalpy parameter correlations". Entropy. 23 (3). MDPI: 319. doi:10.3390/e23030319. PMC 7999889. PMID 33800360.
  6. ^ Amirhossein Farzam, Areejit Samal, Jürgen Jost (2020). "Degree difference: a simple measure to characterize structural heterogeneity in complex networks". Sci. Rep. 10 (1). Nature Publishing Group: 1–12.{{cite journal}}: CS1 maint: multiple names: authors list (link)