Don't walk back in anger

  • Date July 12, 2018
  • Hour 3.30 pm
  • Room GSSI Room D
  • Speaker Vanni Noferini (University of Essex, UK)
  • Area Mathematics


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. 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 subset of) Francesca Arrigo (Strathclyde), Des Higham (Strathclyde), and  Peter Grindrod (Oxford).