Book contents
- Frontmatter
- Contents
- Preface
- Acknowledgements
- List of abbreviations
- 1 Preliminaries: networks and graphs
- 2 Networks and complexity
- 3 Network models
- 4 Introduction to dynamical processes: theory and simulation
- 5 Phase transitions on complex networks
- 6 Resilience and robustness of networks
- 7 Synchronization phenomena in networks
- 8 Walking and searching on networks
- 9 Epidemic spreading in population networks
- 10 Social networks and collective behavior
- 11 Traffic on complex networks
- 12 Networks in biology: from the cell to ecosystems
- 13 Postface: critically examining complex networks science
- Appendix 1 Random graphs
- Appendix 2 Generating functions formalism
- Appendix 3 Percolation in directed networks
- Appendix 4 Laplacian matrix of a graph
- Appendix 5 Return probability and spectral density
- References
- Index
8 - Walking and searching on networks
Published online by Cambridge University Press: 05 September 2012
- Frontmatter
- Contents
- Preface
- Acknowledgements
- List of abbreviations
- 1 Preliminaries: networks and graphs
- 2 Networks and complexity
- 3 Network models
- 4 Introduction to dynamical processes: theory and simulation
- 5 Phase transitions on complex networks
- 6 Resilience and robustness of networks
- 7 Synchronization phenomena in networks
- 8 Walking and searching on networks
- 9 Epidemic spreading in population networks
- 10 Social networks and collective behavior
- 11 Traffic on complex networks
- 12 Networks in biology: from the cell to ecosystems
- 13 Postface: critically examining complex networks science
- Appendix 1 Random graphs
- Appendix 2 Generating functions formalism
- Appendix 3 Percolation in directed networks
- Appendix 4 Laplacian matrix of a graph
- Appendix 5 Return probability and spectral density
- References
- Index
Summary
The navigation and exploration of complex networks are obviously affected by the underlying connectivity properties and represent a challenging scientific problem with a large number of practical applications. The most striking example is the World Wide Web (WWW), an immense data repository which acquires a practical interest and value only if it is possible to locate the particular information one is seeking. It is in this context and having in mind large-scale information and communication technologies (ICTs) that most of the models and studies are developed. Because information discovery and retrieval rely on the understanding of the properties of random walks and diffusion phenomena in complex networks, considerable activity has been devoted to the investigation of these basic processes.
In this chapter we will review the main strategies that can be used to explore and retrieve information from the vertices of a network. In particular, we want to expose how the topological properties of networks might affect search and retrieval strategies and how these strategies can effectively take advantage of the network's connectivity structure. We start from basic considerations on diffusion processes taking place on networks and naturally dive into more applied works that consider well-defined problems encountered in the ICT world.
Diffusion processes and random walks
The discovery process and the related algorithms in large-scale networks are clearly related to the properties of a random walk diffusing in a network of given topology.
- Type
- Chapter
- Information
- Dynamical Processes on Complex Networks , pp. 160 - 179Publisher: Cambridge University PressPrint publication year: 2008