Related Experiment Video
Updated: May 21, 2026
05:55
Modeling the Functional Network for Spatial Navigation in the Human Brain
Published on: October 13, 2023
Unbiased degree-preserving randomization of directed binary networks.
1Department of Mathematics, King's College London, The Strand, London, United Kingdom.
Summary
Generating random directed graphs is challenging due to biases in naive methods. This study introduces a novel Markov chain approach using edge swaps to create unbiased, uniform random networks and specialized graph structures.
Area of Science:
- Network science
- Graph theory
- Computational mathematics
Background:
- Naive randomization algorithms for networks often introduce biases.
- Existing methods for directed graphs lack unbiased sampling.
- Generating networks with specific topological features remains a challenge.
Purpose of the Study:
- To develop an unbiased method for randomizing directed graphs.
- To construct a Markov chain that converges to a uniform distribution over directed graphs.
- To enable the generation of directed graphs with tailored topological properties, such as specific degree correlations.
Main Methods:
- Constructed an ergodic detailed balance Markov chain for directed graphs.
- Utilized edge swaps with nontrivial acceptance probabilities that conserve in-degrees and out-degrees.
- Generalized acceptance probabilities to target arbitrary measures on the space of directed graphs.
- Developed a process for generating directed graphs with specified degree-degree correlation functions.
Main Results:
- The proposed Markov chain converges to a strictly uniform measure on directed graphs.
- The method successfully generates random directed graphs without the biases of naive approaches.
- Demonstrated the ability to produce directed graphs with specified degree-degree correlation functions.
- Validated the theory through numerical implementation and testing on synthetic and biological networks.
Conclusions:
- The novel Markov chain provides an unbiased method for generating random directed graphs.
- This approach allows for the creation of directed networks with desired topological characteristics.
- The framework is applicable to both theoretical network generation and the analysis of real-world networks.
Related Concept Videos
01:13Randomized Experiments
The randomization process involves assigning study participants randomly to experimental or control groups based on their probability of being equally assigned. Randomization is meant to eliminate selection bias and balance known and unknown confounding factors so that the control group is similar to the treatment group as much as possible. A computer program and a random number generator can be used to assign participants to groups in a way that minimizes bias.
Simple randomization
Simple...
Simple randomization
Simple...
01:22Bias
Bias refers to any tendency that prevents a question from being considered unprejudiced. In research, bias occurs when one outcome or answer is selected or encouraged over others in sampling or testing. Bias can occur during any research phase, including study design, data collection, analysis, and publication.
In statistics, a sampling bias is created when a sample is collected from a population, and some members of the population are not as likely to be chosen as others (remember, each member...
In statistics, a sampling bias is created when a sample is collected from a population, and some members of the population are not as likely to be chosen as others (remember, each member...
01:17Wald-Wolfowitz Runs Test I
The Wald-Wolfowitz test, also known as the runs test, is a nonparametric statistical test used to assess the randomness of a sequence of two different types of elements (e.g., positive/negative values, successes/failures). It examines whether the order of the elements in a sequence is random or if there is a pattern or trend present. This nonparametric test applies to any ordered data despite the population and sample data distribution, even if a higher sample size is available.
The test works...
The test works...
01:34Woodward–Hoffmann Selection Rules and Microscopic Reversibility
Electrocyclic reactions, cycloadditions, and sigmatropic rearrangements are concerted pericyclic reactions that proceed via a cyclic transition state. These reactions are stereospecific and regioselective. The stereochemistry of the products depends on the symmetry characteristics of the interacting orbitals and the reaction conditions. Accordingly, pericyclic reactions are classified as either symmetry-allowed or symmetry-forbidden. Woodward and Hoffmann presented the selection criteria for...
01:24Sequence Networks of Rotating Machines
A Y-connected synchronous generator, grounded through a neutral impedance, is designed to produce balanced internal phase voltages with only positive-sequence components. The generator's sequence networks include a source voltage that is exclusively in the positive-sequence network. The sequence components of line-to-ground voltages at the generator terminals illustrate this configuration.
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
Zero-sequence current induces a voltage drop across the generator's neutral impedance and other...
01:09Random Variables
A random variable is a single numerical value that indicates the outcome of a procedure. The concept of random variables is fundamental to the probability theory and was introduced by a Russian mathematician, Pafnuty Chebyshev, in the mid-nineteenth century.
Uppercase letters such as X or Y denote a random variable. Lowercase letters like x or y denote the value of a random variable. If X is a random variable, then X is written in words, and x is given as a number.
For example, let X = the...
Uppercase letters such as X or Y denote a random variable. Lowercase letters like x or y denote the value of a random variable. If X is a random variable, then X is written in words, and x is given as a number.
For example, let X = the...