Spreading dynamics in complex networks with applications in vehicular networks

Abstract

The analysis of complex networks has received tremendous attention over the last few years due to the development of online social networks and the existence of a huge volumes of data related to technology (Internet, Web, power grids), biological networks (protein interactions, genes, diseases), etc. This dissertation explored the issue of disseminating "information" (rumors, viruses, ...) to complex networks, as well as applications of related problems in vehicular ad hoc networks. In particular, the problem of influence maximization has been studied, and state-of-the-art algorithms have been developed to find the most influential spreaders in single-layer and multi-layer complex networks, as well as adapting them to routing protocols in ad hoc networks of vehicles. Additionally, the dual problem of minimizing the spread of "malicious" information to complex networks, for the first time in online fashion has been studied, and an algorithm has been developed to select the best network components (nodes or edges) to block the outspread of undesired propagations. Under the light of recent developments in self-driving cars, the aforementioned problem has also been studied for ad hoc vehicular networks, and a black-listing technique has been developed for vehicles that have been controlled by an adversary. Finally, the power of the "paradox of friendship" was studied and generalized for a series of topological features for the nodes of a network, and several applications were developed to maximize (minimize) the dissemination of information on complex networks based on the paradox intuition.

Η ανάλυση σύμπλεκτων (complex) δικτύων έχει λάβει τεράστια προσοχή τα τελευταία χρόνια, εξαιτίας της ανάπτυξης των online social δικτύων, και της ύπαρξης τεραστίου όγκου δεδομένων σχετικών με τεχνολογικά (Internet, Web, power grids), βιολογικά δίκτυα (αλληλεπιδράσεων πρωτεϊνών, γονιδίων, εξάπλωση ασθενειών), κ.τ.λ. Η παρούσα διατριβή εξερεύνησε το ζήτημα της διάδοσης “πληροφορίας” (φημών, ιών,…) σε σύμπλεκτα δίκτυα, καθώς και εφαρμογές των σχετικών αποτελεσμάτων σε ad hoc δίκτυα οχημάτων. Ειδικότερα, μελετήθηκε το πρόβλημα της μεγιστοποίησης διάδοσης (influence maximization), και αναπτύχθηκαν state-of-the-art αλγορίθμοι για την εύρεση των πιο ικανών διασκορπιστών πληροφορίας (influential spreaders) σε μονοεπίπεδα και πολυεπίπεδα σύμπλεκτα δίκτυα, καθώς και προσαρμογή αυτών σε πρωτόκολλα δρομολόγησης σε ad hoc δίκτυα οχημάτων (vehicular ad hoc networks). Επιπρόσθετα, μελετήθηκε το δυϊκό πρόβλημα της ελαχιστοποίησης διάδοσης “κακοήθους” (malicious) πληροφορίας σε σύμπλεκτα δίκτυα, για πρώτη φορά σε online fashion, και αναπτύχθηκε αλγόριθμος για την επιλογή των καλύτερων παρακωλυτών διάδοσης κακοήθους πληροφορίας. Κάτω από το πρίσμα των προσφάτων εξελίξεων στα self-driving cars, το προαναφερθέν πρόβλημα μελετήθηκε και για ad hoc δίκτυα οχημάτων, και αναπτύχθηκε μια τεχνική black-listing για όσα οχήματα έχουν περάσει στον έλεγχο κάποιου “adversary”. Τέλος, μελετήθηκε και γενικεύτηκε η ισχύς του “παραδόξου της φιλίας” για μια σειρά από τοπολογικά χαρακτηριστικά των κόμβων ενός δικτύου, και αναπτύχθηκαν εφαρμογές του για την μεγιστοποίηση (ελαχιστοποίηση) της διάδοσης της πληροφορίας στα σύμπλεκτα δίκτυα.