数学を使おう！フォーラムで楽しくお話してみませんか？

Dimitri Volchenkov 氏（Bielefeld University）

講演題目

Random Walks and Diffusions on Graphs and Databases

内容

Most networks and databases that humans have to deal with contain large, albeit finite number of units. Their structure, for 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. Classical graph theory has been developed in regard to its applications in urban planning, transport, energetics, and many other fields. The general optimization mindset dominating these researches had addressed to graph theory the questions which were often related to finding the shortest path between nodes, as being of the minimum time delay for information transmission and of the minimum cost for connection maintenance. Not surprisingly, the very definition of distance between two vertices in a graph is given as the geodesic distance, i.e., the shortest path connecting them. In contrast to classical graph theory paying attention to the shortest paths of least cost, in our approach all possible paths between the two vertices in a connected graph are taken into account, although some paths shall be more preferable than others. Such a formulation of graph theory can be called as of a "path integral". Random walks respecting all graph symmetries assign a probability to each path in the graph to be traversed by a random walker. Perhaps, the most interesting fact about such a "path integral" approach to graphs is that the probabilistic distance naturally induces a Euclidean metric on a graph (sometimes called the 'diffusion metric', or the 'effective resistance metric') allowing for a geometric representation of the relationships between vertices in a graph, in terms of distances and angles, as in Euclidean geometry of everyday intuition. The probabilistic geometry provides us with the necessary basis for consistently discussing a number of applications such diverse as electric resistance networks, estimation of land prices, urban planning, linguistic databases, music, and gene expression regulatory networks.