Modulus on temporal graphs

K-REx Repository

Show simple item record Mikheev, Vikenty 2020-05-08T18:08:20Z 2020-05-08T18:08:20Z 2020-05-01
dc.description.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. en_US
dc.language.iso en_US en_US
dc.subject Modulus, Temporal Graph, Time-respecting path, Two-dimensional Dijkstra en_US
dc.title Modulus on temporal graphs en_US
dc.type Dissertation en_US Doctor of Philosophy en_US
dc.description.level Doctoral en_US
dc.description.department Department of Mathematics en_US
dc.description.advisor Nathan Albin en_US 2020 en_US May en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search K-REx

Advanced Search


My Account


Center for the

Advancement of Digital