B0353
Title: Targeted or lagged walk sampling for estimation of finite-order graph parameters
Authors: Li-Chun Zhang - University of Southampton (United Kingdom) [presenting]
Abstract: A pure random walk in a graph is a probabilistic depth-first search algorithm that moves strictly over the edges of the graph. More generally, a walk is said to be targeted if the transition probabilities from the current node are also subject to other devices, such as random jumps or acceptance-rejection mechanisms for the proposed moves. Finally, we call a walk lagged if the transition probabilities depend on not only the current node but also a given number of previous nodes, such that it is not memoryless like either pure or targeted random walks. A novel approach is presented for estimating finite-order graph parameters based on targeted or lagged walk sampling. As an example, let y be a binary community membership indicator associated with the nodes, such as a group of pathogen carriers or a fraternal society. Let be the total number of triangles where all the three nodes belong to the community and let be that of the other triangles. The larger the ratio between and is, the higher is the transitivity among the community members compared to the overall transitivity in the graph.
