论文标题
图表上信息传播的模型
Models for information propagation on graphs
论文作者
论文摘要
我们建议并统一不同模型的类别，以在图形上进行信息传播。在头等舱中，传播被建模为一个波浪，该波在初始时间从一组\ emph {已知}节点发出，以稍后的时间到所有其他\ emph {Unknown}节点，并由信息波前的到达时间确定的顺序确定。第二类模型基于沿节点之间的路径的旅行时间的概念。从初始\ emph {已知}集对节点的集合集合的信息传播时间定义为所有可允许路径的子集的广义旅行时间的最小值。通过在每个\ emph {unknown}节点上施加eikonal形式的局部方程，并在\ emph {已知}节点处的边界条件来给出最后一类。节点上局部方程的解相值与值较低的相邻节点的解相耦合。我们提供模型类的精确表述，并证明它们之间的等价。最后，我们通过标签传播和信任网络上的信息传播将图表上的前传代模型应用于半监督学习。
We propose and unify classes of different models for information propagation over graphs. In a first class, propagation is modelled as a wave which emanates from a set of \emph{known} nodes at an initial time, to all other \emph{unknown} nodes at later times with an ordering determined by the arrival time of the information wave front. A second class of models is based on the notion of a travel time along paths between nodes. The time of information propagation from an initial \emph{known} set of nodes to a node is defined as the minimum of a generalised travel time over subsets of all admissible paths. A final class is given by imposing a local equation of an eikonal form at each \emph{unknown} node, with boundary conditions at the \emph{known} nodes. The solution value of the local equation at a node is coupled to those of neighbouring nodes with lower values. We provide precise formulations of the model classes and prove equivalences between them. Finally we apply the front propagation models on graphs to semi-supervised learning via label propagation and information propagation on trust networks.
