Adaptive random walks on the class of Web graphs
Adaptive random walks on the class of Web graphs
复制标题
DOI：
10.1007/s100510170071
复制
发表时间：
2001-09
期刊：
影响因子：
--
通讯作者：
B. Tadić
中科院分区：
文献类型：
--
作者：
B. Tadić
研究了一类具有可变布线图的有向图上具有自适应移动策略的随机游动。这些图是从与万维网的动态兼容的演化规则中生长出来的[B。Tadić，Physica A293，273（2001）]，并且通过对于参数β的每个值的出度和入度的一对幂律分布来表征，该参数β测量图中重新布线的程度。步行者根据访问节点的出度和目标节点的入度这两个局部可用信息来调整其移动策略。另一方面，标准的随机游走只使用出度。我们计算步行者集合访问的连通子图的分布、步行的平均访问时间和生存概率。我们讨论了当控制参数β变化时，行走动力学相对于全局图结构变化的这些性质。当β≥ 3时，对应于万维网，与同一图上的标准随机游走相比，游走到图上给定层次的访问时间要短得多。通过减少向刚性极限β <$βc <$0.1（对应于自然发生的生化网络的范围）的重新布线量，自适应随机游走和标准随机游走的生存概率变得越来越相似。自适应随机游走可以作为一个有效的消息传递算法在这类图的大程度的重新布线。
We study random walk with adaptive move strategies on a class of directed graphs with variable wiring diagram. The graphs are grown from the evolution rules compatible with the dynamics of the world-wide Web [B. Tadić, Physica A293, 273 (2001)], and are characterized by a pair of power-law distributions of out- and in-degree for each value of the parameter β, which measures the degree of rewiring in the graph. The walker adapts its move strategy according to locally available information both on out-degree of the visited node and in-degree of target node. A standard random walk, on the other hand, uses the out-degree only. We compute the distribution of connected subgraphs visited by an ensemble of walkers, the average access time and survival probability of the walks. We discuss these properties of the walk dynamics relative to the changes in the global graph structure when the control parameter β is varied. For β≥ 3, corresponding to the world-wide Web, the access time of the walk to a given level of hierarchy on the graph is much shorter compared to the standard random walk on the same graph. By reducing the amount of rewiring towards rigidity limit β↦βc≲ 0.1, corresponding to the range of naturally occurring biochemical networks, the survival probability of adaptive and standard random walk become increasingly similar. The adaptive random walk can be used as an efficient message-passing algorithm on this class of graphs for large degree of rewiring.