1

如果我添加或删除一条比计算前后距离更快然后减去的单条边，有什么方法可以找出图形的平均测地线距离会改变多少？

我正在对其状态由无向图表示的系统进行 Metropolis Monte Carlo 模拟。系统的能量取决于该图的平均测地距离。

在每一个蒙特卡洛步骤，我必须提议对图表进行修改，然后计算由于该修改引起的能量变化。我只是选择一个随机边缘并翻转它（如果边缘不存在，则添加边缘，如果存在则移除边缘）。我现在做的是一种蛮力：

Graph = initialize;
L = avgGeodesicLength(Graph)
E0 = energy(L)
for(i = 0; i < mcsteps; i++) {
   newGraph = copy Graph;
   flip a random edge of newGraph;
   L = avgGeodesicLength(newGraph);
   E1 = energy(L);
   dE = E1 - E0
   if (metropolis criteria(dE) is true) {
      Graph = newGraph;
      E0 = E1;
   } 
   else {
      throw the copy away and keep the current state;
   }
}

我宁愿这样做：

Graph = initialize;
L = avgGeodesicLength(Graph);
E0 = energy(L);
for(i = 0; i < mcsteps; i++) {
   edge = random edge of Graph;
   dL = difference in AvgGeodesicLength if I flip edge;
   dE = differenceInEnergy(dL);
   if (metropolis criteria(dE) is true) {
      flip edge; 
      E0 += dE;
   }
   else { do nothing;}
}

如果计算能量差异比计算能量本身快得多。如果给定边缘以更快的方式翻转（big-O-wise），如果有一种方法可以计算平均测地线长度的差异，这是可能的。

有没有办法做到这一点？我知道很难预测一条边的变化会影响哪些路径，但是……也许我很幸运！:D

编辑：我不在乎我必须为你想到的任何算法使用什么表示。如果它节省了我的时间，我愿意这样做。

我的图通常有点小（顶点数通常少于一百，边数在少数和完全连接之间变化）。问题是我必须重复这个循环很多很多步骤以达到平衡，并且他们为很多很多不同的条件中的每一个计算许多可观察的...... :(

编辑 2：我不需要单独的测地线路径或其长度，只需要平均测地线长度。

4

0 回答 0