The Deformed Graph Laplacian and Its Applications to Network Centrality Analysis
The Deformed Graph Laplacian and Its Applications to Network Centrality Analysis
复制标题
变形图拉普拉斯算子及其在网络中心性分析中的应用
DOI：
10.1137/17m1112297
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
V. Noferini
中科院分区：
文献类型：
--
作者：
P. Grindrod;D. Higham;V. Noferini
我们引入并研究了一种新的基于非回溯行走概念的网络中心性度量，即不包含uvu形式的子序列的行走，其中u和v是底层图的任意不同的连通顶点。我们认为，与传统的基于步行的中心性度量相比，这一特征可以产生更有意义的排名。我们表明，由此产生的卡兹式中心性度量可以通过所谓的变形图拉普拉斯来计算——一个可以与任何图相关联的二次矩阵多项式。通过证明关于这个矩阵多项式的一系列新结果，我们深入了解了算法相对于其类katz参数的行为。研究结果还为实施问题提供了信息。特别是，我们表明，在适当的限制下，新度量与Martin， Zhang和Newman在2014年引入的特征向量中心性的非回溯版本一致。对星形和类星形网络的严格分析说明了新方法的好处，……
We introduce and study a new network centrality measure based on the concept of nonbacktracking walks, that is, walks not containing subsequences of the form uvu where u and v are any distinct connected vertices of the underlying graph. We argue that this feature can yield more meaningful rankings than traditional walk-based centrality measures. We show that the resulting Katz-style centrality measure may be computed via the so-called deformed graph Laplacian---a quadratic matrix polynomial that can be associated with any graph. By proving a range of new results about this matrix polynomial, we gain insights into the behavior of the algorithm with respect to its Katz-like parameter. The results also inform implementation issues. In particular we show that, in an appropriate limit, the new measure coincides with the nonbacktracking version of eigenvector centrality introduced by Martin, Zhang, and Newman in 2014. Rigorous analysis on star and star-like networks illustrates the benefits of the new approach,...
影响因子：
3.1
作者：
Schoch, David;Valente, Thomas W.;Brandes, Ulrik
通讯作者：
Brandes, Ulrik