Flow motifs in interaction networks (Master thesis)

Κοσυφάκη, Χρυσάνθη


Many real-world phenomena are best represented as interaction networks with dynamic structures (e.g., transaction networks, social networks, traffic networks). Interaction Networks capture flow of data which is transferred between their vertices along a timeline. Analyzing such networks is crucial towards comprehending processes in them. A typical analysis task is the finding of motifs, which are small subgraph patterns that repeat themselves in the network. In this thesis, we introduce network flow motifs, a novel type of motifs that model significant flow transfer among a set of vertices within a constrained time window. We design an algorithm for identifying flow motif instances in a large graph. Our algorithm can be easily adapted to find the top k instances of maximal flow. In addition, we design a dynamic programming module that finds the instance with the maximum flow. We evaluate the performance of the algorithm on three real datasets and identify flow motifs which are significant for these graphs. Our results show that our algorithm is scalable and that the real networks indeed include interesting motifs, which appear much more frequently than in randomly generated networks having similar characteristics.
Institution and School/Department of submitter: Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής
Subject classification: Evaluation
Keywords: Δίκτυα αλληλεπίδρασης,Μοτίβα ροής,Αξιόλογηση,Τέστ σημαντικότης,Interaction networks,Flow motifs,Evaluation,Significance test
URI: http://olympias.lib.uoi.gr/jspui/handle/123456789/29345
Appears in Collections:Διατριβές Μεταπτυχιακής Έρευνας (Masters)

Files in This Item:
File Description SizeFormat 
Μ.Ε. ΚΟΣΥΦΑΚΗ ΧΡΥΣΑΝΘΗ 2019.pdf2.19 MBAdobe PDFView/Open



 Please use this identifier to cite or link to this item:
http://olympias.lib.uoi.gr/jspui/handle/123456789/29345
  This item is a favorite for 0 people.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.