Abstract
dc:descriptionNumerous real-world applications can be represented as networks of dynamic structure, since the vertices correspond to entities that exchange data over time. Ex- amples include transportation networks, financial networks, social networks, traffic networks etc. We call these Temporal Interaction Networks (TINs). The importance of studying and analyzing TINs is high as we can use them to solve problems related to transportation and financial transactions. Moreover, analyzing TINs can extract interesting insights or reveal important information (e.g., cyclic transactions, message interception).TINs capture the data transfers between entities along a timeline. Specifically, at each interaction, a quantity (money, message, traffic) moves from one network vertex (entity) to another. We call this quantity flow. The main objective of this thesis is to introduce and analyze the flow concept in a variety of problems (flow computation, tracking the provenance of a quantity, extracting patterns etc.). Flow analysis in TINs can be used for congestion detection and explanation in traffic networks, identification of suspicious transactions in financial networks, to name a few applications. It also comes with a number of challenges and difficulties, most notably the potentially large graph size and huge number of interactions between the vertices of the TIN. Another issue is that solutions to well-studied problems in graphs, such as max-flow computation in static networks, cannot directly be applied to solve flow computation problems in TINs. Hence, it is necessary to design novel, scaleable, and memory- efficient solutions for this problem. In this thesis, we introduce and study a number of flow computation problems in TINs. In the first part of the thesis, we study the problem of computing in a sub- graph (DAG) of the TIN the total flow from a designated source node to a designated sink node. Specifically, for this problem we propose and study two models of flow computation. The first model is a greedy flow transfer approach where each inter- action transfers the maximum possible quantity. The second model is an approach inspired from the maximum flow computation problem. In this case, the interactions may not transfer the maximum possible quantity, but the one which results in the maximum flow transfer from the source to the sink along the timeline. This problem can be formulated and solved as a linear programming (LP) problem. We propose a number of preprocessing and graph simplification techniques that greatly reduce the complexity of the problem in practice. Lastly, we propose algorithms that enumerate DAG pattern instances and their flow in large graphs.The second problem we study is flow provenance tracking in TINs. Specifically, given a node in the graph, we study provenance of the total quantity that has been accumulated at the node by a time instant. We study provenance under a number of different models for the propagation of quantities; for each such model we define an- notation generation and propagation algorithm that can be used to track provenance. We also propose scaleable techniques for the most expensive model (propagation se- lection) in large graphs and analyze the space and time complexity of the provenance mechanisms that we propose.In the last part of this thesis, we introduce spatio-temporal flow patterns of pas- sengers in transportation networks. We study the problem of identifying interesting origin-destination-time (ODT patterns) at varying granularity. We propose algorithms for extracting such patterns efficiently. We also propose a number of optimizations to our baseline algorithm, which significantly reduce the time spent for generating candidate patterns and counting their support. Since the pattern enumeration can still be expensive, we propose practical variants of pattern search.For our evaluation, we use a number of real datasets from different application domain (e.g., bitcoin exchange network, passenger transportation network, loan exchange network) of varying scales and densities. Our results show that our proposed algorithms are scaleable and that their output can be useful in many applications of flow analysis in temporal networks.
Degree
thesis:*- Grantor dc:publisher
- University of Ioannina
- Year dc:date
- 2023
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Kosyfaki, Chrysanthi
- Κοσυφάκη, Χρυσάνθη
Subjects
dc:subject × 14- μεγάλοι γράφοι
- Ροή
- Προέλευση
- Μοτίβα
- large graphs
- Flow
- Provenance
- Patterns
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Επιστήμες Μηχανικού και Τεχνολογία
- Υπολογιστές, Υλικό (hardware) και Αρχιτεκτονική
- Electrical Engineering, Electronic Engineering, Information Engineering
- Engineering and Technology
- Computer science, Hardware and Architecture
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/53769