Abstract
| Original language | English |
|---|---|
| Pages (from-to) | 310-341 |
| Number of pages | 32 |
| Journal | SIAM Journal on Matrix Analysis and Applications |
| Volume | 39 |
| Issue number | 1 |
| DOIs | |
| Publication status | Published - 1 Mar 2018 |
Fingerprint
Keywords
- centrality index
- deformed graph Laplacian
- matrix polynomial
- nonbacktracking
- complex networks
- generating function
Cite this
}
The deformed graph Laplacian and its applications to network centrality analysis. / Grindrod, Peter; Higham, Desmond J.; Noferini, Vanni.
In: SIAM Journal on Matrix Analysis and Applications, Vol. 39, No. 1, 01.03.2018, p. 310-341.Research output: Contribution to journal › Article
TY - JOUR
T1 - The deformed graph Laplacian and its applications to network centrality analysis
AU - Grindrod, Peter
AU - Higham, Desmond J.
AU - Noferini, Vanni
PY - 2018/3/1
Y1 - 2018/3/1
N2 - 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, and further results are given on real networks.
AB - 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, and further results are given on real networks.
KW - centrality index
KW - deformed graph Laplacian
KW - matrix polynomial
KW - nonbacktracking
KW - complex networks
KW - generating function
UR - https://www.siam.org/journals/simax.php
U2 - 10.1137/17M1112297
DO - 10.1137/17M1112297
M3 - Article
VL - 39
SP - 310
EP - 341
JO - SIAM Journal on Matrix Analysis and Applications
JF - SIAM Journal on Matrix Analysis and Applications
SN - 0895-4798
IS - 1
ER -