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

Exploring complex networks through random walks.

Luciano da Fontoura Costa1, Gonzalo Travieso

  • 1Instituto de Física de São Carlos, Universidade de São Paulo, Caixa Postal 369, São Carlos, Sao Paulo, 13560-970, Brazil. luciano@ifsc.usp.br

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

Interrelating neuronal morphology by coincidence similarity networks.

Journal of theoretical biology·2025
Same author

Correlations between structure and random walk dynamics in directed complex networks.

Applied physics letters·2020
Same author

Comparison of Different Spike Train Synchrony Measures Regarding Their Robustness to Erroneous Data From Bicuculline-Induced Epileptiform Activity.

Neural computation·2020
Same author

Morphological Neuron Classification Based on Dendritic Tree Hierarchy.

Neuroinformatics·2018
Same author

Gene regulatory and signaling networks exhibit distinct topological distributions of motifs.

Physical review. E·2018
Same author

Effects of threshold on the topology of gene co-expression networks.

Molecular bioSystems·2017
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

Exploring partially known complex networks like social contacts and the internet is crucial. Random walks on Barabási-Albert networks can heavily bias estimations of average node degree and clustering coefficient.

Area of Science:

  • Complex networks analysis
  • Network science
  • Computational social science

Background:

  • Real-world complex networks (e.g., protein interactions, social contacts, Internet) are often partially known.
  • Network exploration frequently involves random walk processes.
  • Understanding coverage efficiency and topological measurement accuracy during exploration is vital.

Purpose of the Study:

  • To investigate node and edge coverage efficiency in different network models using various random walk strategies.
  • To assess the accuracy of topological measurements (average node degree, clustering coefficient) during network exploration.
  • To compare random, Barabási-Albert (BA), and geographical network models.

Main Methods:

  • Simulated random walks on random, BA, and geographical network models.

Related Experiment Videos

  • Employed three distinct random walk strategies: traditional, preferential to untracked edges, and preferential to unvisited nodes.
  • Analyzed node and edge coverage percentages and estimated topological properties.

    • Main Results:

    • Network models with identical size and average node degree exhibit similar node/edge coverage efficiency.
    • Identified linear scaling between network size and the number of random walk steps required for a given coverage percentage.
    • Random walks on BA networks often yield significantly biased estimations of average node degree and clustering coefficient.

    Conclusions:

    • Network topology influences exploration efficiency, but coverage can be similar across models under specific conditions.
    • The linear scaling of coverage provides a predictable model for network exploration.
    • Caution is advised when using random walks on BA networks for estimating key topological metrics due to potential biases.