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

Parallel dynamics and computational complexity of network growth models.

Benjamin Machta1, Jonathan Machta

  • 1Department of Physics, University of Massachusetts, Amherst, Massachusetts 01003-3720, USA.

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

PROTEIN-PROTEIN INTERACTION NETWORKS CAN BE HIGHLY SENSITIVE TO THE MEMBRANE PHASE TRANSITION.

bioRxiv : the preprint server for biology·2025
Same author

Behavior of Ising spins and ecological oscillators on dynamically rewired small-world networks.

Physical review. E·2025
Same author

The membrane transition strongly enhances biopolymer condensation through prewetting.

bioRxiv : the preprint server for biology·2024
Same author

Optimal schedules for annealing algorithms.

Physical review. E·2024
Same author

Variation in Avian Predation Pressure as a Driver for the Diversification of Periodical Cicada Broods.

The American naturalist·2024
Same author

Modeling and prediction of phase shifts in noisy two-cycle oscillations.

Journal of mathematical biology·2023

Parallel algorithms efficiently generate growing network models. For power-law exponents greater than one, constant time is achieved, while less than one requires logarithmic time, revealing minimal network depth.

Area of Science:

  • Computational complexity theory
  • Network science
  • Parallel algorithms

Background:

  • Growing network models are fundamental in understanding complex systems.
  • Preferential attachment rules govern network evolution, influencing structure and dynamics.
  • Assessing the computational cost of generating these networks is crucial for scalability.

Purpose of the Study:

  • To investigate the parallel computational complexity and depth of growing network models.
  • To analyze the impact of preferential attachment rules on network generation efficiency.
  • To identify algorithmic strategies for rapid parallel generation of these networks.

Main Methods:

  • Development and analysis of parallel algorithms for network generation.
  • Study of preferential attachment rules with varying power-law exponents (alpha).

Related Experiment Videos

  • Examination of computational depth and time complexity for different alpha regimes.

    • Main Results:

    • Distinct algorithms are required for sublinear (0 <= alpha < 1) and superlinear (alpha > 1) cases.
    • A discontinuous transition in parallel complexity occurs at alpha = 1, coinciding with scale-free network emergence.
    • Constant parallel time is achieved for alpha > 1, while logarithmic time is needed for 0 <= alpha < 1.

    Conclusions:

    • Growing networks generated via preferential attachment exhibit low parallel computational complexity.
    • Despite sequential growth rules, these networks demonstrate minimal depth and history dependence.
    • Efficient parallel generation is feasible, with complexity dictated by the preferential attachment exponent.