Degree-preserving randomization

Degree Preserving Randomization is a technique used in Network Science that aims to assess whether or not variations observed in a given graph could simply be an artifact of the graph's inherent structural properties rather than properties unique to the nodes, in an observed network.

Background

Cataloged as early as 1996 , the most simple implementation of degree preserving randomization relies on a Monte Carlo algorithm that rearranges, or "rewires" the network at random such that, with a sufficient number of rewires, the network's degree distribution is identical to the initial degree distribution of the network, though the topological structure of the network has become completely distinct from the original network.

File:Rewire.png

A demonstration of a single iteration of the Degree Preserving Randomization algorithm.

Degree preserving randomization, while it has many different forms, typically takes on the form of a relatively simple approach: for any network consisting of $N$ nodes with $E$ edges, select two dyadically tied nodes. For each of these dyadic pairs, switch the edges such that the new dyadic pairs are mismatched. After a sufficient number of these mismatches, the network increasingly loses its original observed topography.

As is common with algorithms based on Markov Chains, the number of iterations, or individual rewires, must occur on a given graph such that the graph is sufficiently random and distinct from the original graph is unknown, though Espinoza asserts that a safe minimum threshold is $Q*E$, where $Q$ "is at least 100" (Espinoza). Others have provided input for this issue, including one author who states that a safe minimum may instead be at least ${\frac {E}{2}}*ln(1/\epsilon )$, where epsilon lies in a range between $10^{-6}$ and $10^{-7}$, though ultimately the correct number is not presently known .

Uses

There are several cases in which published research have explicitly employed degree preserving randomization in order to analyze network properties. Dekker used rewiring in order to more accurately model observed social networks by adding a secondary variable, $\pi$, which introduces a high-degree attachment bias. Liu et al. have additionally employed degree preserving randomization to assert that the Control Centrality, a metric they identify, alters little when compared to the Control Centrality of an Erdős–Rényi model containing the same number of $N$ nodes in their simulations.