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

Spectra of random graphs with given expected degrees.

Fan Chung1, Linyuan Lu, Van Vu

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

Proceedings of the National Academy of Sciences of the United States of America
|May 14, 2003
PubMed
Summary

This study reconciles two theories on power-law graph spectra. It demonstrates that eigenvalue distributions follow the semicircle law for normalized Laplacians and the power law for adjacency matrices, clarifying spectral analysis in random graphs.

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

Promoting adolescent mental health in Tanzania and Vietnam through a co-created universal school-based initiative: Findings from a mixed method study.

Global mental health (Cambridge, England)·2025
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

Area of Science:

  • Graph theory
  • Spectral analysis
  • Network science

Background:

  • Two competing theories exist for the spectra of power-law graphs: Wigner's semicircle law and power-law distribution.
  • These theories appear contradictory but may apply to different graph representations.

Purpose of the Study:

  • To reconcile the semicircle law and power-law distribution for power-law graph spectra.
  • To demonstrate that both spectral distribution theories are valid under specific conditions and for appropriate matrices.

Main Methods:

  • Analysis of random graphs with specified expected degrees.
  • Examination of the eigenvalues of both the normalized Laplacian and the adjacency matrix.
  • Investigation of key invariants and their relation to spectral properties.

Related Experiment Videos

Main Results:

  • The eigenvalues of the normalized Laplacian of random power-law graphs follow the semicircle law.
  • The spectrum of the adjacency matrix of power-law graphs adheres to the power-law distribution.
  • Identified new values for the exponent beta, indicating phase transitions in eigenvalue distributions.

Conclusions:

  • Both the semicircle law and power-law distribution are valid descriptions of power-law graph spectra, depending on the matrix considered.
  • The findings have direct implications for graph algorithms, particularly those involving rapidly mixing Markov chains and randomized algorithms.