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 (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 ${\mathcal {G}}(V,E)$, each node $i\in V$ is inherently associated with a scale, known as its degree $k_{i}$. This scale corresponds to the number of other nodes that connect to node $i$. 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 $(i,j)\in E$ 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

The degree ratio, denoted as $\eta (i,j)$, is defined by the formula

$\eta (i,j)={\frac {\max\{k_{i},k_{j}\}}{\min\{k_{i},k_{j}\}}},$

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

$\log \eta (i,j)=\log \eta (j,i)=|\log k_{i}-\log k_{j}|.$

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

The value of $\eta$ ranges between 1 and the maximum degree ($k_{\max }$) in the network, which coincidentally matches the range of $k$ if the minimum degree $k_{\min }=1$.

Indeed, it is more fitting to designate $\log \eta (i,j)$ as the "distance". Although both $\eta (i,j)$ and $\log \eta (i,j)$ qualify as "semi-distances" in a formal mathematical sense, only $\log \eta (i,j)$ meets the criteria for a semi-metric.

Scale-free property

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 $\eta \in \left[1,k_{\max }\right]$. In contrast, only a third of real-world networks have a statistically significant power-law degree distribution across the full range $k\in \left[k_{\min },k_{\max }\right]$. 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 $k$ also has a power-law distribution of $\eta$, but not vice versa. This result can be formulated as

${\mathcal {D}}^{2}|_{\text{power-law}}\subsetneq {\mathcal {D}}^{4}|_{\text{power-law}},$

where ${\mathcal {D}}^{2}|_{\text{power-law}}$ denotes the set of all network models that have a power-law degree distribution (DD) in the asymptotic limit $k\to \infty$, and ${\mathcal {D}}^{4}|_{\text{power-law}}$ for power-law degree–degree distance distribution (DDDD) in the asymptotic limit $\eta \to \infty$.

Proof

The proof contains two parts: (i) inclusion and (ii) strict inequality: (i) To demonstrate this, the copula theory is used. Let ${\mathcal {P}}({k_{i},k_{j}}|i\leftrightarrow j)$ be the conditional joint probability of sequentially selecting two nodes $i$ and $j$ that have degrees $k_{i},k_{j}\in [k_{\min },\infty )$, respectively, conditioned on $i$ and $j$ being connected. This implies that ${\mathcal {P}}({k_{i},k_{j}}|i\leftrightarrow j)$ can be understood as half the probability of selecting a link (from all links) that connects two nodes of degrees $k_{i}$​ and $k_{j}$ (half because of the symmetry between $k_{i}$ and $k_{j}$​). The marginal distribution focused on $k_{i}$​ is proportional to $f(k_{i})\times k_{i}$, since a node with a degree $k_{i}$​ is $k_{i}$ times more likely to be selected. For a degree distribution following $f(k_{i})\propto k_{i}^{-\alpha }$, this leads to a marginal distribution of $k_{i}^{-\alpha +1}$. Invoking Sklar's theorem, the conditional joint probability can be expressed through: ${\mathcal {P}}\left(\{k_{i},k_{j}\}|i\leftrightarrow j\right)\sim k_{i}^{-\alpha +1}k_{j}^{-\alpha +1}c({\frac {k_{i}^{-\alpha +2}}{k_{\min }^{-\alpha +2}}},{\frac {k_{j}^{-\alpha +2}}{k_{\min }^{-\alpha +2}}}).$ By incorporating this equation into $g(\eta )=\int _{k_{\min }}^{\infty }2{\mathcal {P}}\left(\{k_{i},\eta k_{i}\}|i\leftrightarrow j\right)k_{i}dk_{i},$ which outlines the degree–degree distance distribution $g(\eta )$, we derive $g(\eta )\sim \int _{k_{\min }}^{\infty }k_{i}^{-2\alpha +2}\eta ^{-\alpha +1}\left(c({\frac {k_{i}^{-\alpha +2}}{k_{\min }^{-\alpha +2}}},0)+O(\eta ^{-\alpha +2})\right)k_{i}dk_{i}.$ Therefore, the degree–degree distance distribution also contains a positive power-law term $\eta ^{-\alpha +1}$, provided that the copula density function is smooth. This confirms its intrinsic relationship to the degree distribution in terms of their power-law exponents: $\beta =\alpha -1$. (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.

Generalization

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