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 Videos

The average distances in random graphs with given expected degrees.

Fan Chung1, Linyuan Lu

  • 1Department of Mathematics, University of California at San Diego, La Jolla, CA 92093-0112, USA. fan@ucsd.edu

Proceedings of the National Academy of Sciences of the United States of America
|December 6, 2002
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

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

Sort by
Same author

A Multi-Branch Training Strategy for Enhancing Neighborhood Signals in GNNs for Community Detection.

Entropy (Basel, Switzerland)·2026
Same author

Stochastically evolving graphs via edit semigroups.

Proceedings of the National Academy of Sciences of the United States of America·2025
Same author

Discontinuation of glacial meltwater input reshapes the diversity and stability of eukaryotic planktonic microbial communities in glacial lakes.

Environmental research·2025
Same author

The Synergistic Effects of Structural Evolution and Attack Strategies on Network Matching Robustness.

Entropy (Basel, Switzerland)·2025
Same author

RIVA: Efficient relational inference with variate attention.

Neural networks : the official journal of the International Neural Network Society·2025
Same author

Comprehensive analysis of greenhouse gases emissions and microbial dynamics in glacier-fed lakes across various ablation stages.

Water research·2025
Same journal

The TaMYB55-TaSnRK1α1-TabZIP9 module confers heat stress tolerance in wheat.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Superstatistics approach to turbulent circulation fluctuations.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

A molecular timescale for evolution of cobamide biosynthesis.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Pierre Chambon, a pioneer of molecular biology and gene regulation in eukaryotes.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Granulosa cell glycogen fuels the avascular corpus luteum.

Proceedings of the National Academy of Sciences of the United States of America·2026
Same journal

Synthetic essentiality of TRAIL/TNFSF10 in VHL-deficient renal cell carcinoma.

Proceedings of the National Academy of Sciences of the United States of America·2026
See all related articles

Random graph theory reveals the small-world phenomenon, where most people are connected via short acquaintance chains. This study analyzes average distances in power law graphs, finding logarithmic distances for exponents greater than 3 and log-log distances for exponents between 2 and 3.

Area of Science:

  • Network Science
  • Graph Theory
  • Statistical Physics

Background:

  • The small-world phenomenon describes the property of many real-world networks where any two individuals are connected by a short chain of acquaintances.
  • Random graph theory provides a mathematical framework for understanding network structures and their emergent properties.

Purpose of the Study:

  • To analyze the average distance and diameter of power law random graphs.
  • To investigate how different exponent values (beta) in power law distributions affect network properties.
  • To characterize the structure of dense subgraphs (cores) within these networks.

Main Methods:

  • Application of random graph theory to analyze network structures.
  • Derivation of average distance formulas based on expected degrees and power law exponents.

Related Experiment Videos

  • Identification and analysis of dense subgraphs within the studied networks.

    • Main Results:

    • For power law graphs with beta > 3, the average distance is of the order log n / log d.
    • For power law graphs with 2 < beta < 3, the average distance is of the order log log n, while the diameter is of the order log n.
    • These networks feature a dense core subgraph, with most vertices closely connected to it.

    Conclusions:

    • The structure of power law random graphs significantly influences their small-world properties.
    • Network characteristics vary substantially based on the exponent of the power law degree distribution.
    • Understanding these graph properties is crucial for analyzing real-world networks like the Internet and social networks.