289650 Introduction to Random Walks and Diffusions on Graphs and Databases (V) (WiSe 2011/2012)

The most of networks and databases humans have deal with contain large albeit finite number of units. Their structure maintaining functional consistency of the components is essentially not random and calls for a precise quantitative description of relations between nodes or data units and all network components, as having important implications for the network robustness. The intent of the present course is to introduce undergraduate and graduate students to graph theory, to random walks on graphs, and to review the methods based on random walks and diffusions for exploring the structure of finite connected graphs and databases. In graphs, random walks establish probabilistic relations between individual nodes and subgraphs that enable us to attack the applied problems which could not even be started otherwise. We discuss a number of applications of the random walks methodsto the electric resistance networks, estimation of land prices, urban planning, linguistic databases, music, and gene expression regulatory networks that will eventually lead to a useful body of knowledge for broad auditory.

·

In * Introduction to Permutations, Markov Chains, andPartitions;

·* Worth Another Binary Relation: Graphs;

·* Permutations Sieved Through Adjacency: Graph Automorphisms;

·* Exploring Undirected Graphs by Random Walks;

·* Embedding of Graphs in Probabilistic Euclidean Space;

·* Random walks and electric resistance networks;

·* Random Walks and Diffusions on Directed Graphs and Interacting Networks;

·* Structural Analysis of Networks and Databases;

·* When Feedbacks Matter: Epidemics, Synchronization, and Self-Regulation in Complex Networks;

·* Critical Phenomena on Large Graphs with Regular Subgraphs.

External comments page

http://www.physik.uni-bielefeld.de/~volchenk/index.html