Περίληψη: | Η εύρεση των κορυφαίων ατόμων με επιρροή για τη μεγιστοποίηση της εξάπλωσής της σε ένα κοινωνικό δίκτυο, παραμένει ένα σημαντικό αλλά και δύσκολο πρόβλημα. Αποδεδειγμένο ότι είναι πολυπλοκότητας NP- hard, το πρόβλημα μεγιστοποίησης επιρροής έχει προσελκύσει αρκετές μελέτες. Τα κοινωνικά δίκτυα πραγματικού κόσμου είναι μεγάλα και σύνθετα. Αυτό καθιστά την εκτέλεση των αλγορίθμων που σχετίζονται με το πρόβλημα αρκετά αργή. Στην εργασία αυτή ερευνώνται μέθοδοι παραλληλοποίησης των αλγορίθμων αυτών, με σκοπό την βελτιστοποίηση και την ταχύτερη εκτέλεση τους. Το κύριο μοντέλο που χρησιμοποιήθηκε είναι αυτό του ανεξάρτητου καταρράκτη (IC), το οποίο αποτελεί και μέρος του αλγόριθμου CELF, του οποίου έγινε προσομοίωση και παράλληλη εκτέλεση, καθώς και αυτό του γραμμικού κατωφλίου (LT), που με τη βοήθεια παράλληλων υπολογισμών αντιμετωπίζεται το αρχικό πρόβλημα για το μοντέλο διάχυσης SIR. Επιπλεόν, πραγματοποιούνται τεχνικές ανίχνευσης κοινοτήτων αλλά και γνωστές μέθοδοι κεντρικότητας κόμβων. Διεξάγονται πειράματα σε πέντε κοινωνικά δίκτυα του πραγματικού κόσμου. Τα πειραματικά αποτελέσματα αποδεικνύουν την αποτελεσματικότητα των μεθόδων με εξαιρετική απόδοση.
|