Μεγιστοποίηση επιρροής σε δυναμικά κοινωνικά δίκτυα και γράφους, πλήρως και μερικώς παρατηρούμενα

Abstract

Influence maximization in dynamic social networks is a critical problem in the study of socialgraphs, with applications in marketing, information diffusion, and public policy. This dissertation analyzes influence maximization in dynamic social networks, considering both fully and partially observable environments. Initially, existing approaches are presented, including Monte Carlosimulation-based and heuristic-based methods, as well as community detection techniques to improve the performance of seed node selection algorithms. This research introduces novel methodologies that combine knowledge from both static and dynamic networks, leveraging community-based information to enhance influence propagation. Additionally, approaches that rely on partially observable environments—where the full network topology is not available—are explored. The advantages and limitations of the proposed algorithms are examined, and their performance is compared against existing methods using simulations and real-world social network data. The experimental results demonstrate that utilizing community structure and targeted network probing can lead to significantly improved influence spread with lower computational costs

Η μεγιστοποίηση επιρροής σε δυναμικά κοινωνικά δίκτυα αποτελεί ένα κρίσιμο πρόβλημα στημελέτη των κοινωνικών γραφημάτων, με εφαρμογές στο μάρκετινγκ, τη διάδοση πληροφοριών και τη δημόσια πολιτική. Στην παρούσα διατριβή, αναλύεται η μεγιστοποίηση επιρροής σε δυναμικά κοινωνικά δίκτυα, λαμβάνοντας υπόψη τόσο πλήρως όσο και μερικώς παρατηρούμενα περιβάλλοντα. Αρχικά, παρουσιάζονται οι υπάρχουσες προσεγγίσεις, όπως οι Monte-Carlosimulation-based και heuristic-based μέθοδοι, καθώς και τεχνικές βασισμένες σε community detection για τη βελτίωση της απόδοσης των αλγορίθμων επιλογής seed κόμβων. Μέσω της μελέτης, προτείνονται νέες μεθοδολογίες που συνδυάζουν τη γνώση από στατικά και δυναμικά δίκτυα, αξιοποιώντας την πληροφόρηση από κοινότητες μέσα στο γράφημα. Επιπλέον, διερευνώνται προσεγγίσεις που βασίζονται σε μερικώς παρατηρούμενα περιβάλλοντα, όπου δεν είναι διαθέσιμη η πλήρης τοπολογία του δικτύου. Αναλύονται τα πλεονεκτήματα και οι περιορισμοί των προτεινόμενων αλγορίθμων, ενώ η απόδοσή τους συγκρίνεται με υφιστάμενες μεθόδους χρησιμοποιώντας προσομοιώσεις και πραγματικά δεδομένα κοινωνικών δικτύων. Τα πειραματικά αποτελέσματα αποδεικνύουν ότι η αξιοποίηση της δομής των κοινοτήτων και η στοχευμένη ανίχνευση της δυναμικής του δικτύου μπορούν να οδηγήσουν σε σημαντικά βελτιωμένη επιρροή με μικρότερο υπολογιστικό κόστος.