Don't walk back in anger

In network theory, a system of interacting actors (for example, a social network and its users, with the interaction of being friends/followers/etc.) is modelled by a graph. It is of interest to define and compute a ranking of the nodes, called a centrality measure, representing the relative importance of the actors. Several efficient techniques based on matrix theory are available to compute centrality measures based on the combinatorics of walks on the graph. However, depending on the underlying model, not all walks are equally good. I will discuss some very recently introduced centrality measure that only counts nonbacktracking walks, i.e., walks that do not include subsequence of nodes of the form ...iji... I will illustrate the motivation to do this, the mathematical theory developed to study these walks, and finally the techniques to compute the corresponding centrality. If time permits, I will also discuss several possible variations on the theme of the new centrality, as well as theoretical results, applications, challenges, and open problems.

This is based on various papers coauthored with (different subsets of) Francesca Arrigo (Strathclyde), Des Higham (Strathclyde), and Peter Grindrod (Oxford).