Networks, that is collections of nodes together with sets of edges linking some of these nodes, naturally encode relations (the edges) between entities (the nodes). The trajectories on a network (successions of contiguous edges), called walks, represent the dynamical processes of the system of entities. Networks and walks nowadays play a ubiquitous role across many domains, where graphical models are essential tools to master the interactions and dynamics of complex systems. We will show how walks on graphs actually obey a non-commutative extension of number-theory, complete with its primes, algebraic functions, continued fractions and more. Concrete applications of this theory in algorithmics, machine learning and network analysis will be presented, including the best general purpose algorithm for counting simple cycles, algorithms for exact belief propagation on Gaussian graphical models and the calculation of matrix functions, novel state-of-the-art kernels for the automatic classifications of graphs, the resolution of an old question on large social networks and how a non-commutative Brun sieve changes our perception of both plant-pathogen interactions and the impact of the Dodd-Frank act in one go.