Centrality measures are used in Network Science to identify the most important (central) elements in a complex interconnected system, such as the Internet, a social network, or a protein interaction network. Among the measures proposed over the years, some quantify the importance of a node based on the number and the length of the walks that start from it. Notably, this problem can be rewritten in terms of matrix functions, which means that it can be efficiently solved using numerical linear algebra tools even when the network is large. In this talk, we will introduce the most popular walk-based centrality measures for complex networks and discuss some issues related to their computation. Then, we will see how walk combinatorics can be used to devise algorithms for updating some of these measures after a graph perturbation.