如何计算网络中节点值的平均值（或总和）？

Question

考虑一个由 N 个节点组成的网络（图形），每个节点都有一个值，如何设计一个 program/algorithm（对于每个节点），允许每个节点计算平均值（或总和）网络中的所有节点值？

假设是：

1. 节点之间的直接通信受图拓扑的限制，图拓扑不是完整的图。如果您的算法需要，任何其他假设都是允许的。我认为最弱的一个是图中有一个包含所有节点的循环。
2. N 是有限的。
3. N 足够大以至于您无法存储所有值然后计算其平均值（或总和）。出于同样的原因，你不能 "remember" 你收到的值（因此你不能只重新分配你收到的值并将你没有看到的值添加到缓冲区并得到结果）。

（Tags可能不对，因为我不知道这种问题在哪个领域，如果是某种普遍的问题。）

Answer 1

这是一个有趣的问题，在我提出部分解决方案之前，我做了一些假设：

1. 图是连通的（在有向图的情况下，强连通）
2. 节点只与它们的直接邻居通信
3. 可以保存和发送所有数字的总和，这意味着总和不会超过 long 或者你有一个足够大的数据结构，它不会超过

我会选择深度优先搜索。节点 N0 将启动算法并将其值 + 计数发送给第一个邻居 (N0.1)。 N0.1 将添加它自己的值 + 计数并将消息转发给下一个邻居 (N0.1.1)。如果消息返回到 N0 或 N0.1，他们只是将其转发给他们的另一个邻居。 （N0.2 或 N0.1.2）。

现在的问题是知道什么时候终止算法。最好您希望在到达所有节点后立即终止它，然后广播最后一条消息。如果您知道图中有多少个节点，只需继续将其转发到下一个节点，直到最终到达每个节点。最后一个节点将知道已经到达（它可以将计数变量与图中的节点数进行比较）并广播消息。

如果您不知道有多少个节点，并且它是无向图，那么它将只是图中的深度优先实现。这意味着，如果 N0.1 从 N0.1.1 以外的任何人那里收到消息，它只会将消息退回，因为在执行深度优先搜索时您无法将消息发送给父级。如果它是一个有向图并且你不知道节点的数量，那么你要么想出一个数学模型来证明算法何时完成，要么你学习节点的数量。

我在这里找到了一篇论文，提出了一种基于八卦的算法来计算动态网络中的节点数量：https://gnunet.org/sites/default/files/Gossipico.pdf 也许这会有所帮助。也许你甚至可以用它来总结节点。