The Sum-over-Paths Covariance Kernel: A Novel Covariance Measure between Nodes of a Directed Graph
The Sum-over-Paths Covariance Kernel: A Novel Covariance Measure between Nodes of a Directed Graph
复制标题
DOI：
10.1109/tpami.2009.78
复制
发表时间：
2010-06
影响因子：
23.6
通讯作者：
Amin Mantrach;Luh Yen;Jérôme Callut;Kevin Françoisse;M. Shimbo;M. Saerens
中科院分区：
文献类型：
--
作者：
Amin Mantrach;Luh Yen;Jérôme Callut;Kevin Françoisse;M. Shimbo;M. Saerens
这项工作介绍了一个基于链接的加权有向图的节点之间的协方差测量，其中成本与每个弧。为此，通过最小化所有节点对之间的总期望成本，同时固定图中的总相对熵扩散，来定义通过图的（通常是无限的）可数路径集上的概率分布。这导致路径集合上的玻尔兹曼分布，使得长（高成本）路径以低概率出现，而短（低成本）路径以高概率出现。节点之间的路径和（SoP）协方差测量则根据此概率分布定义：如果两个节点经常在相同（最好是短）路径上共同出现，则认为它们高度相关。节点之间的结果协方差矩阵（假设总共n个节点）是一个Gram矩阵，因此定义了图上的有效核。它是通过根据分配给弧的成本对n × n矩阵求逆而获得的。基于同样的思想，本文还定义了一个介数得分，用来度量节点在路径上出现的期望次数，所提出的度量方法可用于各种图挖掘任务，如计算介数中心度、节点的半监督分类、可视化等，如第7节所示。
This work introduces a link-based covariance measure between the nodes of a weighted directed graph, where a cost is associated with each arc. To this end, a probability distribution on the (usually infinite) countable set of paths through the graph is defined by minimizing the total expected cost between all pairs of nodes while fixing the total relative entropy spread in the graph. This results in a Boltzmann distribution on the set of paths such that long (high-cost) paths occur with a low probability while short (low-cost) paths occur with a high probability. The sum-over-paths (SoP) covariance measure between nodes is then defined according to this probability distribution: two nodes are considered as highly correlated if they often co-occur together on the same - preferably short - paths. The resulting covariance matrix between nodes (say n nodes in total) is a Gram matrix and therefore defines a valid kernel on the graph. It is obtained by inverting an n\times n matrix depending on the costs assigned to the arcs. In the same spirit, a betweenness score is also defined, measuring the expected number of times a node occurs on a path. The proposed measures could be used for various graph mining tasks such as computing betweenness centrality, semi-supervised classification of nodes, visualization, etc., as shown in Section 7.