Graph Theory Blink 6.2 (Search information using random walk on graph)

#GraphTheory #GraphEfficiency #Diffusion #RandomWalker #Morphospace #Communicability #InformationFlow

A roadmap to navigate Graph Theory Blinks.
This course comes at the intersection of mathematics, learning, and algorithms.

*** Primarily textbooks:
1) Bullmore, Edward T. Fornito, Alex Zalesky, Andrew - Fundamentals of Brain Network Analysis-Academic Press, Elsevier (2016)
2) Arthur Benjamin, Gary Chartrand, Ping Zhang - The Fascinating World of Graph Theory-Princeton University Press (2015)
3) (Graduate Texts in Mathematics) Reinhard Diestel - Graph theory-Springer (2006)

*** Library: SNAP library (network analysis tool),

=======================================================================================================
Lecture 6 will cover shortest random walk and diffusion on graphs to derive diffusion-based efficiency measures
=======================================================================================================

6. Diffusion-based graph efficiency using random walks
6.1 Comparing shortest path routing and diffusion on graphs
6.2 Search information using random walk on graph
6.3 Shortest path probability of a random walker and graph Laplacian
6.4 Mean first passage of a random walker on a graph
6.5 Graph diffusion efficiency and communicability

**** Resources and further readings ****

1. Estrada, E., Hatano, N., 2008. Communicability in complex networks. Physical Review E 77, 036111.
2. Goni, J. et al., 2013. Exploring the morphospace of communication efficiency in complex networks. PLoS One 8,
e58070.
2. Goni, J., et al., 2014. Resting-brain functional connectivity predicted by analytic measures of network communication. Proceedings of the National Academy of Sciences 111, 833–838.
3. Latora, V., Marchiori, M., 2001. Efficient behavior of small-world networks. Physical review letters 87, 198701.
4. Newman, M.E., 2003. The structure and function of complex networks. SIAM review 45, 167–256.
5. Sneppen, K., Trusina, A., Rosvall, M., 2005. Hide-and-seek on complex networks. EPL (Europhysics
Letters) 69, 853.
6. Wang, S.P., Pei, W.J., 2008. First passage time of multiple brownian particles on networks with applications. Physica A: Statistical Mechanics and its Applications 387, 4699–4708.
7. Watts, D.J., Strogatz, S.H., 1998. Collective dynamics of ‘small-world’ networks. nature 393, 440.