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

Computational complexity arising from degree correlations in networks.

Alexei Vázquez1, Martin Weigt

  • 1INFN and International School for Advanced Studies, Via Beirut 4, 34014 Trieste, Italy.

Physical Review. E, Statistical, Nonlinear, and Soft Matter Physics
|March 15, 2003
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

Author Correction: Exploring the space of self-reproducing ribozymes using generative models.

Nature communications·2025
Same author

adabmDCA 2.0-A Flexible but Easy-to-Use Package for Direct Coupling Analysis.

Methods in molecular biology (Clifton, N.J.)·2025
Same author

Integrating experimental feedback improves generative models for biological sequences.

Nucleic acids research·2025
Same author

Exploring the space of self-reproducing ribozymes using generative models.

Nature communications·2025
Same author

Emergence of network communities driven by local rules.

Physical review. E·2025
Same author

Fluctuations and the limit of predictability in protein evolution.

Reports on progress in physics. Physical Society (Great Britain)·2025
Same journal

Tension on dsDNA bound to ssDNA-RecA filaments may play an important role in driving efficient and accurate homology recognition and strand exchange.

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Amplitude-phase coupling drives chimera states in globally coupled laser networks [Phys. Rev. E 91, 040901(R) (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Shapes of sedimenting soft elastic capsules in a viscous fluid [Phys. Rev. E 92, 033003 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Erratum: Attenuation of excitation decay rate due to collective effect [Phys. Rev. E 90, 022142 (2014)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Role of connectivity and fluctuations in the nucleation of calcium waves in cardiac cells [Phys. Rev. E 92, 052715 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
Same journal

Publisher's Note: Lattice Boltzmann approach for complex nonequilibrium flows [Phys. Rev. E 92, 043308 (2015)].

Physical review. E, Statistical, nonlinear, and soft matter physics·2016
See all related articles

Correlations in random networks significantly alter solutions for minimal vertex covers. Highly correlated networks present greater computational complexity, challenging simple algorithms unlike uncorrelated networks.

Area of Science:

  • Statistical mechanics
  • Network science
  • Computational complexity theory

Background:

  • Random networks are foundational in statistical mechanics and network science.
  • Understanding network properties, like degree correlations, is crucial for modeling complex systems.
  • The minimal vertex cover problem is a classic NP-hard problem in graph theory.

Purpose of the Study:

  • To investigate the impact of degree correlations in random networks on combinatorial optimization problems.
  • To analyze how network complexity changes with varying degrees of correlation between neighboring vertices.
  • To compare the solvability of the minimal vertex cover problem on correlated versus uncorrelated random networks.

Main Methods:

  • Application of the Bethe-Peierls approach to statistical-mechanics models.

Related Experiment Videos

  • Analysis of random networks with arbitrary degree distributions and correlations.
  • Utilizing the minimal vertex cover problem as a benchmark for computational complexity.

    • Main Results:

    • Degree correlations introduce qualitatively different solution structures compared to uncorrelated networks.
    • Highly correlated networks exhibit increased computational complexity for finding minimal vertex covers.
    • Simple heuristic algorithms are shown to fail on highly correlated networks, unlike uncorrelated ones.

    Conclusions:

    • Degree correlations are a critical factor influencing the computational complexity of network optimization problems.
    • The presence or absence of correlations can distinguish between computationally simple and complex networks.
    • Findings highlight the importance of considering network structure beyond simple degree distributions.