问“稳定”多维缩放算法

EN

我有一个节点的无线mesh网络，每个节点都能够向邻居报告自己的“距离”，以(简化的)信号强度测量。节点在3d空间中的地理位置，但由于无线电干扰，节点之间的距离不需要是三角的(三角？)一致的。即，给定节点A、B和C，A和B之间的距离可以是10，A和C之间的距离也是10，但B和C之间的距离是100。

我想做的是根据节点的连接性来可视化逻辑网络布局，即在可视化中包含节点之间的逻辑距离。

到目前为止，我的研究表明，多维缩放(MDS)正是为这类事情设计的。假设我的数据可以直接表示为二维距离矩阵，它甚至是更一般的MDS的更简单的形式。

现在，似乎有许多MDS算法，参见例如http://homepage.tudelft.nl/19j49/Matlab_Toolbox_for_Dimensionality_Reduction.html和http://tapkee.lisitsyn.me/。我需要在C++中做到这一点，我希望我可以使用现成的组件，也就是说，不必从纸上重新实现算法。因此，我认为：https://sites.google.com/site/simpmatrix/将是最好的选择。它是有效的，但是：

• 布局不稳定，即每次重新运行算法时，节点的位置都会改变(参见下图1和2之间的差异-这是因为已经运行了两次，没有任何进一步的更改)。这是由于传递给此算法的初始化矩阵(它包含每个节点的初始位置，然后算法迭代校正)-我传递一个空矩阵，然后该实现派生一个随机矩阵。一般而言，布局确实接近于我从给定输入数据所期望的布局。此外，在不同的运行之间，节点的方向(顺时针或逆时针)可以改变。
• 我认为“解决方案”很明显，就是传递一个稳定的默认初始化矩阵。但是，当我最初将所有节点放在同一位置时，它们根本不会移动；当我将它们放在一个轴上(节点0位于0,0；节点1位于1,0；节点2位于2,0等等)时，它们仅沿该轴移动。(见下图4)。不过，它们之间的相对距离是可以接受的。

因此，这个算法似乎只改变了节点之间的距离，但不改变节点的位置。

感谢你读到这里-我的问题是(我很高兴只有一个或几个问题得到回答，因为每个问题都可能给我一个继续前进的方向的线索)：

• 我在哪里可以找到关于许多algorithms?
• Is中每一个节点的属性的更多信息有一种算法可以推导出网络中每个节点的完整位置，而不必传递每个节点的初始位置？
• 是否有可靠的方法来估计每个点的位置，以便算法可以正确地缩放它们之间的距离？我没有这些节点的地理位置，这就是这个exercise.
• Are的全部要点有没有什么算法可以在两次运行之间保持网络派生的‘角度’恒定？

如果所有其他方法都失败了，我的下一个选择将是使用我上面提到的算法，增加迭代次数以将运行之间的可变性保持在几个像素左右(我必须试验需要多少次迭代)，然后围绕节点0“旋转”每个节点，例如，将节点0和1在一条水平线上从左到右对齐；这样，在MDS算法确定了点的相对距离后，我将“校正”点的位置。我还必须纠正每个节点周围连接的节点的顺序(顺时针或逆时针)。这可能很快就会变得很麻烦。

显然，我更喜欢一种稳定的算法解决方案-增加迭代来消除随机性不是很可靠。

谢谢。

编辑:我被推荐到cs.stackexchange.com，在那里有一些评论；有关算法的建议，请参阅https://cs.stackexchange.com/questions/18439/stable-multi-dimensional-scaling-algorithm。

图1-随机初始化矩阵：

​

​

图2-使用相同的输入数据运行后，与1相比旋转：

​

​

图3-与前2相同，但节点1-3在另一个方向上：

​

​

图4-节点的初始布局在一行上，它们在y轴上的位置没有改变：

​

​