多图的共识

Question

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

现在，假设G被人群中的一些注释者破坏了，根据众包范例:

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

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

我想知道是否有一种合并这些图的方法，以便在V的两个顶点v1,v2之间找到每个可能的边e的存在/不存在的共识。该操作的目的是融合每个注释者对图G中边集E的构造的意见。最后的图形必须是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

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

如果一些行为是有偏见的，你可能会面临一些问题。也就是说，每个用户不会随机选择一个特定的边来操作。