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 techinques to compute the corresponding centrality. The complexity of this approach is comparable or less than that of computing classical walk entrality. I also plan to discuss how to go beyond nonbacktracking walks by removing cycles of length up to k, arguing that in this case the complexity of an exact computation grows, and discussing approximate computations.
This is based on various papers coauthored with (different subsets of) Francesca Arrigo (Strathclyde), Des Higham (Strathclyde), and Peter Grindrod (Oxford).