Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Video

Updated: Oct 13, 2025

Quantifying Branching Density in Rat Mammary Gland Whole-mounts Using the Sholl Analysis Method
11:02

Quantifying Branching Density in Rat Mammary Gland Whole-mounts Using the Sholl Analysis Method

Published on: July 12, 2017

14.6K

Robust subgraph counting with distribution-free random graph analysis.

Johan S H van Leeuwaarden1, Clara Stegehuis2

  • 1Tilburg University, Tilburg, The Netherlands.

Physical Review. E
|November 16, 2021
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

Probability Distributions01:32

Probability Distributions

9.5K
 The probability of a random variable x  is the likelihood of its occurrence. A probability distribution represents the probabilities of a random variable using a formula, graph, or table. There are two types of probability distribution– discrete probability distribution and continuous probability distribution.
A discrete probability distribution is a probability distribution of discrete random variables. It can be categorized into binomial probability distribution and Poisson...
9.5K
Quantifying and Rejecting Outliers: The Grubbs Test01:02

Quantifying and Rejecting Outliers: The Grubbs Test

2.6K
Sometimes, a data set can have a recorded numerical observation that greatly  deviates from the rest of the data. Assuming that the data is normally distributed, a statistical method called the Grubbs test can be used to determine whether the observation is truly an outlier.  To perform a two-tailed Grubbs test, first, calculate the absolute difference between the outlier and the mean. Then, calculate the ratio between this difference and the standard deviation of the sample. This...
2.6K
Uniform Distribution01:19

Uniform Distribution

5.3K
The uniform distribution is a continuous probability distribution of events with an equal probability of occurrence. This distribution is rectangular.
Two essential properties of this distribution are
5.3K
Probability Histograms01:17

Probability Histograms

12.4K
A probability histogram is a visual representation of a probability distribution. Similar a typical histogram, the probability histogram consists of contiguous (adjoining) boxes. It has both a horizontal axis and a vertical axis. The horizontal axis is labeled with what the data represents. The vertical axis is labeled with probability. Each rectangular bar in the histogram is 1 unit wide, which suggests that the area under each bar equals the probability, P(x), where x is 1, 2, 3, and so on.
12.4K
Distributions to Estimate Population Parameter01:26

Distributions to Estimate Population Parameter

4.4K
The accurate values of population parameters such as population proportion, population mean, and population standard deviation (or variance) are usually unknown. These are fixed values that can only be estimated from the data collected from the samples. The estimates of each of these parameters are sample proportion, the sample mean, and sample standard deviation (or variance). To obtain the values of these sample statistics, data are required that have particular distribution and central...
4.4K
Binomial Probability Distribution01:15

Binomial Probability Distribution

13.0K
A binomial distribution is a probability distribution for a procedure with a fixed number of trials, where each trial can have only two outcomes.
The outcomes of a binomial experiment fit a binomial probability distribution. A statistical experiment can be classified as a binomial experiment if the following conditions are met:
There are a fixed number of trials. Think of trials as repetitions of an experiment. The letter n denotes the number of trials.
There are only two possible outcomes,...
13.0K

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

Homophily within and across groups.

Nature communications·2025
Same author

Identify structures underlying out-of-equilibrium reaction networks with random graph analysis.

Chemical science·2025
Same author

Resource and location sharing in wireless networks.

PloS one·2024
Same author

Sharpest possible clustering bounds using robust random graph analysis.

Physical review. E·2023
Same author

Detecting hyperbolic geometry in networks: Why triangles are not enough.

Physical review. E·2022
Same author

Cluster Tails for Critical Power-Law Inhomogeneous Random Graphs.

Journal of statistical physics·2019
Same journal

Erratum: Low-dimensional model for adaptive networks of spiking neurons [Phys. Rev. E 111, 014422 (2025)].

Physical review. E·2026
Same journal

Disentangling the effects of many-body forces on depletion interactions.

Physical review. E·2026
Same journal

Charge transport and mode transition in dual-energy electron beam diodes.

Physical review. E·2026
Same journal

Optimization of multisite reactions in complex compartmentalized media.

Physical review. E·2026
Same journal

Origin of geometric cohesion in nonconvex granular materials: Interplay between interdigitation and rotational constraints enhancing frictional stability.

Physical review. E·2026
Same journal

Interaction of walkers with a standing Faraday wave.

Physical review. E·2026
See all related articles

This study introduces robust subgraph counting methods for complex networks, using only mean and mean absolute deviation (MAD) of degree distributions. These new bounds accurately predict subgraph counts in real-world networks, including dense power-law networks.

Area of Science:

  • Network Science
  • Graph Theory
  • Statistical Physics

Background:

  • Subgraphs like cliques and stars are vital in real-world networks.
  • Estimating subgraph counts relies on degree distributions, which are difficult to fit for scale-free networks.
  • Existing methods are sensitive to the full degree distribution, limiting their applicability.

Purpose of the Study:

  • To develop robust subgraph count estimations independent of the full degree distribution.
  • To provide tight bounds for subgraph counts using only mean and mean absolute deviation (MAD).
  • To establish robust scaling laws for subgraph counts in various network types.

Main Methods:

  • Formulated an optimization problem to derive tight bounds for subgraph counts.
  • Identified the extremal random graph with a three-point degree distribution achieving these bounds.

More Related Videos

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis
06:56

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis

Published on: September 22, 2023

1.3K
Novel Sequence Discovery by Subtractive Genomics
09:40

Novel Sequence Discovery by Subtractive Genomics

Published on: January 25, 2019

8.9K

Related Experiment Videos

Last Updated: Oct 13, 2025

Quantifying Branching Density in Rat Mammary Gland Whole-mounts Using the Sholl Analysis Method
11:02

Quantifying Branching Density in Rat Mammary Gland Whole-mounts Using the Sholl Analysis Method

Published on: July 12, 2017

14.6K
Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis
06:56

Author Spotlight: Advancements in X-ray CT Tool Chain for Tree Core Analysis

Published on: September 22, 2023

1.3K
Novel Sequence Discovery by Subtractive Genomics
09:40

Novel Sequence Discovery by Subtractive Genomics

Published on: January 25, 2019

8.9K
  • Applied bounds to derive robust scaling laws for subgraph counts as a function of network size.

    • Main Results:

    • Developed subgraph counts robust to variations in degree distribution, relying only on mean and MAD.
    • Established sharp bounds for subgraph counts applicable to all networks with identical mean and MAD.
    • Demonstrated that dense power-law networks, not sparse ones, exhibit extreme subgraph counts.
    • Validated the robust bounds against real-world network datasets.

    Conclusions:

    • The developed method offers a robust and practical approach to subgraph counting in complex networks.
    • The findings challenge assumptions about extreme subgraph counts in sparse power-law networks.
    • The robust bounds and scaling laws are applicable across diverse real-world network structures.