Random walks and diffusions on graphs and databases. An introduction. (Q633358)

This book aims to examine aspects of graph theory from an applied viewpoint, being based on an interdisciplinary lecture course on stochastic analysis of complex networks and databases. A running theme is the idea that stochastic process ideas, e.g. about diffusions or random walks, can give insight into the graph (or database). The first three chapters recall basics of permutations, partitions, graphs (including their adjacency matrices) and Markov chains. Chapter 4 deals with exploring (undirected) graphs using random walks. Chapter 5 discusses embedding graphs in probabilistic Euclidean space, using generalised inverses of Laplacian matrices. Chapter 6 is on random walks and electrical networks, Chapter 7 is on random walks and diffusions in directed graphs. Chapter 8 looks for structure in various databases and graphs related to e.g. linguistics, land values in a city, musical dice games, etc. Chapter 9 deals with epidemic models, and issues of synchronization and self-regulation, e.g. in large gene expression regulatory networks. Chapter 10 discusses critical phenomena on large graphs with (e.g.) well-structured regular subgraphs. There is a substantial bibliography.