MATH Seminar
| Title: Non-backtracking walk centrality for directed networks |
|---|
| Seminar: Numerical Analysis and Scientific Computing |
| Speaker: Francesca Arrigo of University of Strathclyde |
| Contact: Michele Benzi, benzi@mathcs.emory.edu |
| Date: 2017-04-28 at 1:00PM |
| Venue: MSC W301 |
| Download Flyer |
| Abstract: The talk is motivated by a practical issue: walk-based centrality measures regard all walks of the same length as being equally important, whereas it is intuitively reasonable to rule out certain classes of walk. We focus here on non-backtracking walks. The theory of zeta functions provides an expression for the generating function of non-backtracking walk counts on a directed network. This expression can be used to produce a centrality measure that eliminates backtracking walks at no cost. The new centrality measure may be interpreted as standard Katz on a modified network, where self loops are added, and where non-reciprocated edges are augmented with negative weights. We also give a multilayer interpretation of the new centrality measure, where (negatively) weighted walks between layers compensate for backtracking walks on the only non-empty layer. We further show that the radius of convergence of the generating function is determined by the spectrum of a three-by-three block matrix involving the original adjacency matrix. This gives a means to choose appropriate values of the attenuation parameter and, in particular, we show that we obtain a larger range of choices for the attenuation parameter than that obtained for standard Katz. By studying the effect of pruning operations on the network (i.e., removing nodes), we show that there is potential for the non-backtracking centrality to be computed more cheaply than Katz for appropriate network structures. Studying the limit as the attenuation parameter approaches its upper bound allows us to propose an eigenvector-based non-backtracking centrality measure in this directed network setting. We illustrate the centrality measure on a synthetic network, where it is shown to eliminate a localization effect present in standard Katz centrality. We also give results for real networks. Finally, we discuss some preliminary results on the non-backtracking version of the total communicability and of some alternating walk-based centrality measures.\\ \\This talk is based on joint work with Prof. Peter Grindrod (University of Oxford, UK), Prof. Desmond J. Higham (University of Strathclyde, UK), and Dr. Vanni Noferini (University of Essex, UK). |
See All Seminars