Modulus on temporal graphs

dc.contributor.authorMikheev, Vikenty
dc.date.accessioned2020-05-08T18:08:20Z
dc.date.available2020-05-08T18:08:20Z
dc.date.graduationmonthMay
dc.date.issued2020-05-01
dc.description.abstractp-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.
dc.description.advisorNathan Albin
dc.description.degreeDoctor of Philosophy
dc.description.departmentDepartment of Mathematics
dc.description.levelDoctoral
dc.identifier.urihttps://hdl.handle.net/2097/40639
dc.language.isoen_US
dc.publisherKansas State University
dc.rights© the author. This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).
dc.rights.urihttp://rightsstatements.org/vocab/InC/1.0/
dc.subjectModulus
dc.subjectTemporal Graph
dc.subjectTime-respecting path
dc.subjectTwo-dimensional Dijkstra
dc.titleModulus on temporal graphs
dc.typeDissertation

Files

Original bundle

Now showing 1 - 1 of 1
Loading...
Thumbnail Image
Name:
VikentyMikheev2020.pdf
Size:
742.66 KB
Format:
Adobe Portable Document Format
Description:

License bundle

Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
1.62 KB
Format:
Item-specific license agreed upon to submission
Description: