Ranking hubs and authorities using matrix functions
Ranking hubs and authorities using matrix functions
复制标题
DOI：
10.1016/j.laa.2012.10.022
复制
发表时间：
2013-03-01
影响因子：
1.1
通讯作者：
Klymko, Christine
中科院分区：
文献类型：
--
作者：
Benzi, Michele;Estrada, Ernesto;Klymko, Christine
基于图的邻接矩阵指数的子图中心性和可通信性的概念已被有效地应用于无向网络的分析。在本文中，我们提出了一种将这些度量扩展到有向网络的方法，并将它们应用于对中心和权威进行排序的问题。扩展是通过二部法实现的，即将有向网络映射到一个节点数加倍的二部无向网络上，从而得到一个具有对称邻接矩阵的网络。我们根据原始有向网络的邻接矩阵明确地确定了这个邻接矩阵的指数，并在这个新的上下文中给出了中心性和通信性的解释，从而得到了一种对中心和权威机构进行排序的技术。无论是在小的人工示例上还是在更现实的真实网络上，用于计算中心和权威机构的矩阵指数方法都与众所周知的HITS算法进行了比较。文中还讨论了其他几种排序算法，并与我们的技术进行了比较。讨论了使用高斯求积规则来计算中心分数和权威分数。(C)2012 Elsevier Inc.保留所有权利。
The notions of subgraph centrality and communicability, based on the exponential of the adjacency matrix of the underlying graph, have been effectively used in the analysis of undirected networks. In this paper we propose an extension of these measures to directed networks, and we apply them to the problem of ranking hubs and authorities. The extension is achieved by bipartization, i.e., the directed network is mapped onto a bipartite undirected network with twice as many nodes in order to obtain a network with a symmetric adjacency matrix. We explicitly determine the exponential of this adjacency matrix in terms of the adjacency matrix of the original, directed network, and we give an interpretation of centrality and communicability in this new context, leading to a technique for ranking hubs and authorities. The matrix exponential method for computing hubs and authorities is compared to the well known HITS algorithm, both on small artificial examples and on more realistic real-world networks. A few other ranking algorithms are also discussed and compared with our technique. The use of Gaussian quadrature rules for calculating hub and authority scores is discussed. (C) 2012 Elsevier Inc. All rights reserved.