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

Graph partitioning induced phase transitions.

Gerald Paul1, Reuven Cohen, Sameet Sreenivasan

  • 1Center for Polymer Studies and Department of Physics, Boston University, Boston, Massachusetts 02215, USA.

Physical Review Letters
|October 13, 2007
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

Comparative effectiveness of CDK4/6 inhibitors in metastatic breast cancer: using the target trial emulation framework to investigate overall survival in routine care.

Breast cancer research and treatment·2026
Same author

Coordination of network heterogeneity and individual preferences promotes collective fairness.

Patterns (New York, N.Y.)·2025
Same author

Lessons from complex systems science for AI governance.

Patterns (New York, N.Y.)·2025
Same author

Determination of Molecular Ground State via Short Square Pulses on Superconducting Qubits.

Physical review letters·2025
Same author

Emergent coordination in temporal partitioning congestion games.

PloS one·2024
Same author

Insights Into the Patient Experience of Hormone Therapy for Early Breast Cancer Treatment Using Patient Forum Discussions and Natural Language Processing.

JCO clinical cancer informatics·2024
Same journal

Erratum: Bacterial Turbulence at Compressible Fluid Interfaces [Phys. Rev. Lett. 136, 138301 (2026)].

Physical review letters·2026
Same journal

Unveiling Light-Quark Yukawa Flavor Structure via Dihadron Fragmentation at Lepton Colliders.

Physical review letters·2026
Same journal

Adaptable Route to Fast Coherent State Transport via Bang-Bang-Bang Protocols.

Physical review letters·2026
Same journal

Topological Transition and Emergence of Elasticity of Dislocation in Skyrmion Lattice: Beyond Kittel's Magnetic-Polar Analogy.

Physical review letters·2026
Same journal

Pound-Drever-Hall Method for Superconducting-Qubit Readout.

Physical review letters·2026
Same journal

Coupling a ^{73}Ge Nuclear Spin to an Electrostatically Defined Quantum Dot in Silicon.

Physical review letters·2026
See all related articles

Graph partitioning reveals a percolation phase transition when dividing complex networks into equal clusters. This transition point, fc = 1-2/k, is crucial for understanding network attacks and immunization strategies.

Area of Science:

  • Network Science
  • Statistical Physics
  • Graph Theory

Background:

  • Graph partitioning is essential for analyzing complex networks, impacting strategies for network attack and immunization.
  • Understanding the behavior of random regular graphs under partitioning is key to network resilience.

Purpose of the Study:

  • To investigate the percolation properties of graph partitioning on random regular graphs.
  • To determine the critical threshold for phase transitions during graph partitioning.
  • To analyze the size and diameter of clusters at the percolation threshold for optimal partitioning.

Main Methods:

  • Studying percolation theory applied to graph partitioning.
  • Analyzing random regular graphs with N vertices and degree k.

Related Experiment Videos

  • Calculating the fraction of edges removed (f) to induce partitioning.
  • Deriving relationships for cluster size (S) and diameter (l) at the percolation threshold.

    • Main Results:

    • A percolation phase transition occurs at fc = 1-2/k for any partitioning process yielding equal-sized connected components.
    • At the percolation threshold for optimal partitioning, cluster size S scales as approximately N^0.4.
    • At the percolation threshold for optimal partitioning, cluster diameter l scales as approximately N^0.25.
    • Multiple nonpercolation transitions are observed for f < fc.

    Conclusions:

    • The study establishes a critical threshold for graph partitioning, relevant to network security and robustness.
    • The scaling laws for cluster size and diameter provide insights into network fragmentation dynamics.
    • Findings are applicable to understanding vulnerabilities and defense mechanisms in complex networks.