cma*_*ant 5 graph-theory graph random-walk
我有一个有限的无向图,其中一个节点被标记为"开始"而另一个被标记为"目标".
最初将代理放置在起始节点处,并且它随机地导航通过该图,即,在每个步骤中,它随机地均匀地选择邻居节点并移动到该节点.当它到达目标节点时它停止.
我正在寻找一种算法,该算法针对每个节点,在从开始到目标的过程中给出关于代理访问它的概率的指示.谢谢.
And*_*ker 11
与图表的情况一样,只需要知道描述问题的适当方式.
编写图形的一种方法是作为邻接矩阵.如果图表G =(V,E)具有| V | 节点(其中| V |是顶点数),该矩阵将为| V | x | V |.如果在一对顶点之间存在边,则将邻接矩阵中的项设置为1,如果不存在则设置为0.
这是对加权图的自然延伸.这里,邻接矩阵不是0或1,而是具有一些权重概念.
在您描述的情况下,您有一个加权图,其中权重是从一个节点转换到另一个节点的概率.这种类型的矩阵有一个特殊的名称,它是一个随机矩阵.根据您排列矩阵的方式,此矩阵将具有分别为1,左右随机矩阵的行或列.
随机矩阵和图之间的一个联系是马尔可夫链.在马尔可夫链文献中,您需要的关键事项是转移矩阵(邻接矩阵的权重等于一个时间步后的转换概率).让我们把过渡矩阵P.
通过P ^ k 给出k个时间步后从一个状态转换到另一个状态的概率.如果你有一个已知的源状态i,那么第二行P ^ k将给你转换到任何其他状态的概率.这可以估算出短期内处于特定状态的概率
根据您的源图,可能P ^ k达到稳态分布 - 即,对于某个k值,P ^ k = P ^(k + 1).这可以估算出长期处于特定状态的概率
顺便说一句,在你做任何这些之前,你应该能够看一下你的图表,然后说一些关于在某个时间处于特定状态的概率的事情.