algorithm - 多图共识

Question

设G = (V,E)为有向无环图（DAG）。V是顶点的集合，而E是边的集合。

G现在，根据众包范式，假设它被人群中的一些注释者破坏：

• 他们中的一些人可能决定删除一些e属于E
• 他们中的一些人可能决定添加一个e不存在的边缘

注释者的工作结果i是一个图，其顶点集V与原始图相同，其边集Ei可能与原始图不同。如果n是注释器的数量，我们会得出n不同的图，它们具有相同的顶点集V，但边集不同E。设G1 = (V,E1), ..., Gn = (V,En)为图集。

我想知道是否有一种方法可以合并这些图，e以便v1,v2就V. 此操作的目的是融合每个注释者对E图中边集的构造的意见G。最终图必须是 DAG。

Answer 1

让...

• U是所有Ei集合加上原始集合的唯一并集E
• T是一些任意的阈值
• H(x)是一些启发式函数
• F成为最终的共识边集

伪代码：

for each Edge e in U
   if H(e) >= T then F.Add(e)

那么问题当然是如何定义你的启发式函数。一种天真的方法将基于投票设置。计算E包含边的集合的数量，如果有足够多的人同意它在图中，则将其包括在内。这是一个简单而高效的实现功能。这种启发式的一些弱点是它无法检测和补偿不良注释器或小人群。

Answer 2

对于每条边，计算包含它的图的数量。如果它大于某个阈值，则假设它是原始边缘。

如果某些操作有偏见，您可能会遇到一些问题。也就是说，每个用户都不会随机选择特定的边缘进行操作。