根据权重对图中的顶点进行分类的算法
Algorithm for classification of vertices in a graph based on their weight
我有以下完整的加权图，其中每个权重代表一个顶点与下一个顶点属于同一类别的概率。我先验地知道某些顶点所属的类别；我如何才能对所有其他顶点进行分类？
我可以更详细地描述问题如下；从所有的顶点 N 和簇 C，我们有一个集合，我们可以确定一个节点所属的特定簇：P(v_n|C_n)=1。从给定的图中我们还知道每个节点与它属于同一集群的每个其他节点的概率：P(v_n1∩C_n2)。由此，我们如何估计每个其他节点的集群？
设 w_i 为向量，其中 w_i[j] 是节点 j 在迭代 i.
时位于聚类中的概率
我们定义w_i:
w_0[j] = 1 j is given node in the class
0 otherwise
w_{i}[j] = P(j | w_{i-1})
其中：P(j | w_{i-1}) 是概率 j 在集群中，假设我们知道每个其他节点 k 在集群中的概率，如 w_{i-1}[k].
我们可以计算出上面的概率：
P(j | w_{i-1}) = 1- (1- w_{i-1}[0]*c(0,j))*(1- w_{i-1}[1]*c(1,j))*...*(1- w_{i-1}[n-1]*c(n-1,j))
在这里：
w_{i-1} 是最后一次迭代的输出。- c(x,y)是边(x,y)的权重
- c(x,x) = 1
重复直到收敛，在收敛的向量中（设w），j在簇中的概率为w[j]
概率函数的解释：
为了使一个节点不在集合中，它需要所有其他节点 "decide" 不共享它。
所以，发生这种情况的概率是：
(1- w_{i-1}[0]*c(0,j))*(1- w_{i-1}[1]*c(1,j))*...*(1- w_{i-1}[n-1]*c(n-1,j))
^ ^ ^
node 0 doesn't share node 1 doesn't share node n-1 doesn't share
为了在class中，至少有一个节点需要"share"，所以发生这种情况的概率是互补的，这是我们为[=24=推导出的公式]
你应该从结果的定义开始。您应该如何显示归属概率？
恕我直言，结果应该是一组类别和一个 table：顶点的行和类别的列，并且在单元格中，该顶点可能属于该类别。
只有当您已经有了一些开始已知的概率时，您的图表才能设置一些归属概率。也就是说，table 已经部分填充了。
根据边的起始值和权重填充 table 时，我们肯定会遇到这样的情况，当我们在单元格中获得不同的概率时，通过不同的方式进入它。还有一点应该设置：我们可以更改 table 中的起始值还是很难设置？边缘权重的相同问题。
现在任务已经部分定义了，这部分非常非常小。你连分类数都不知道！
设置所有这些规则和数字后，一切都变得微不足道 - 使用小二乘法的高斯方法。至于迭代方式，要小心——你事先不知道解是 stable 或者它是否存在。否则，迭代就不会收敛，你为它写的那段代码就白搭了。通过高斯方法，你得到了一组线性方程，并且编写了标准算法来解决所有情况。最后，您不仅得到了解决方案，而且得到了每个最终值可能出现的错误。
我有以下完整的加权图，其中每个权重代表一个顶点与下一个顶点属于同一类别的概率。我先验地知道某些顶点所属的类别；我如何才能对所有其他顶点进行分类？
我可以更详细地描述问题如下；从所有的顶点 N 和簇 C，我们有一个集合，我们可以确定一个节点所属的特定簇：P(v_n|C_n)=1。从给定的图中我们还知道每个节点与它属于同一集群的每个其他节点的概率：P(v_n1∩C_n2)。由此，我们如何估计每个其他节点的集群？
设 w_i 为向量，其中 w_i[j] 是节点 j 在迭代 i.
我们定义w_i:
w_0[j] = 1 j is given node in the class
0 otherwise
w_{i}[j] = P(j | w_{i-1})
其中：P(j | w_{i-1}) 是概率 j 在集群中，假设我们知道每个其他节点 k 在集群中的概率，如 w_{i-1}[k].
我们可以计算出上面的概率：
P(j | w_{i-1}) = 1- (1- w_{i-1}[0]*c(0,j))*(1- w_{i-1}[1]*c(1,j))*...*(1- w_{i-1}[n-1]*c(n-1,j))
在这里：
w_{i-1}是最后一次迭代的输出。- c(x,y)是边(x,y)的权重
- c(x,x) = 1
重复直到收敛，在收敛的向量中（设w），j在簇中的概率为w[j]
概率函数的解释：
为了使一个节点不在集合中，它需要所有其他节点 "decide" 不共享它。
所以，发生这种情况的概率是：
(1- w_{i-1}[0]*c(0,j))*(1- w_{i-1}[1]*c(1,j))*...*(1- w_{i-1}[n-1]*c(n-1,j))
^ ^ ^
node 0 doesn't share node 1 doesn't share node n-1 doesn't share
为了在class中，至少有一个节点需要"share"，所以发生这种情况的概率是互补的，这是我们为[=24=推导出的公式]
你应该从结果的定义开始。您应该如何显示归属概率？
恕我直言，结果应该是一组类别和一个 table：顶点的行和类别的列，并且在单元格中，该顶点可能属于该类别。
只有当您已经有了一些开始已知的概率时，您的图表才能设置一些归属概率。也就是说，table 已经部分填充了。
根据边的起始值和权重填充 table 时，我们肯定会遇到这样的情况，当我们在单元格中获得不同的概率时，通过不同的方式进入它。还有一点应该设置：我们可以更改 table 中的起始值还是很难设置？边缘权重的相同问题。
现在任务已经部分定义了，这部分非常非常小。你连分类数都不知道！
设置所有这些规则和数字后，一切都变得微不足道 - 使用小二乘法的高斯方法。至于迭代方式，要小心——你事先不知道解是 stable 或者它是否存在。否则，迭代就不会收敛，你为它写的那段代码就白搭了。通过高斯方法，你得到了一组线性方程，并且编写了标准算法来解决所有情况。最后，您不仅得到了解决方案，而且得到了每个最终值可能出现的错误。