Modulus on temporal graphs

Abstract

p-Modulus was adopted by Graph Theory from Complex Analysis and became a powerful and versatile tool for exploring the structure of graphs and networks. Clustering and community detection, the construction of a large class of graph metrics, measures of centrality, hierarchical graph decomposition, and the solution to game-theoretic models of secure network broadcast are successful applications. The flexibility of p-modulus allows it to be applied to a wide variety of graph types; the essential definitions are easily adapted for directed or undirected graphs, for weighted or unweighted graphs, for simple graphs or multigraphs, or even for hypergraphs. In this work, we study application of p-modulus to temporal networks --- that is, networks whose structure can change over time.

We introduce a definition of temporal p-modulus for a temporal graph with discrete time availability moments assigned to edges. We provide theorems allowing to adjust static p-modulus algorithms to compute temporal p-modulus. We present the dual problem. For the p=2 case, it has a probabilistic interpretation. Also, we give a mass-transportation interpretation of temporal Modulus for various values of p between 1 and infinity including the endpoints. We consider different types of penalty function and study properties of temporal p-modulus with it. We show examples on several standard graphs modified to temporal ones. Time-respecting paths are given special attention. In order to obtain an efficient numerical algorithm to compute p-modulus we adjust the well-know Dijkstra algorithm to find optimal paths by two criteria --- that is, time of arrival and static length. We compare this algorithm with another way: building a directed static graph equivalent to a given temporal one and running classic Dijkstra algorithm. Computational complexity estimates for both algorithms are the same.