We propose a family of lagged random walk sampling methods in simple undirected graphs, where transition to the next state (i.e. node) depends on both the current and previous states -- hence, lagged. The existing random walk sampling methods can be incorporated as special cases. We develop a novel approach to estimation based on lagged random walks at equilibrium, where the target parameter can be any function of values associated with finite-order subgraphs, such as edge, triangle, 4-cycle and others.
翻译:我们用简单的无方向图表提出一组滞后随机步行抽样方法,其中向下一个状态(即节点)的过渡取决于当前状态和以往状态,因此是滞后的。现有的随机步行抽样方法可以作为特例纳入。我们开发了一种新的估算方法,其依据是平衡时滞后随机行走,目标参数可以是与边缘、三角、四周期等定点子相关的值的任何函数。