Μεγιστοποίηση επιρροής σε κοινωνικά δίκτυα και γράφους με παραλληλοποίηση υπολογισμών
Η εύρεση των κορυφαίων ατόμων με επιρροή για τη μεγιστοποίηση της εξάπλωσής της σε ένα κοινωνικό δίκτυο, παραμένει ένα σημαντικό αλλά και δύσκολο πρόβλημα. Αποδεδειγμένο ότι είναι πολυπλοκότητας NP- hard, το πρόβλημα μεγιστοποίησης επιρροής έχει προσελκύσει αρκετές μελέτες. Τα κοινωνικά δίκτυα πραγμ...
| Κύριος συγγραφέας: | |
|---|---|
| Άλλοι συγγραφείς: | |
| Γλώσσα: | Greek |
| Έκδοση: |
2022
|
| Θέματα: | |
| Διαθέσιμο Online: | http://hdl.handle.net/10889/15949 |
| id |
nemertes-10889-15949 |
|---|---|
| record_format |
dspace |
| spelling |
nemertes-10889-159492022-09-05T04:59:30Z Μεγιστοποίηση επιρροής σε κοινωνικά δίκτυα και γράφους με παραλληλοποίηση υπολογισμών Influence maximalization in social networks and graphs with parallel calculations Τσιαούση, Ειρήνη Ελένη Tsiaousi, Eirini Eleni Μεγιστοποίηση επιρροής Παράλληλος υπολογισμός Μετρικές κεντρικότητας Κοινωνικά δίκτυα μεγάλης κλίμακας Μηχανική μάθηση GPUs Machine learning Social networks Η εύρεση των κορυφαίων ατόμων με επιρροή για τη μεγιστοποίηση της εξάπλωσής της σε ένα κοινωνικό δίκτυο, παραμένει ένα σημαντικό αλλά και δύσκολο πρόβλημα. Αποδεδειγμένο ότι είναι πολυπλοκότητας NP- hard, το πρόβλημα μεγιστοποίησης επιρροής έχει προσελκύσει αρκετές μελέτες. Τα κοινωνικά δίκτυα πραγματικού κόσμου είναι μεγάλα και σύνθετα. Αυτό καθιστά την εκτέλεση των αλγορίθμων που σχετίζονται με το πρόβλημα αρκετά αργή. Στην εργασία αυτή ερευνώνται μέθοδοι παραλληλοποίησης των αλγορίθμων αυτών, με σκοπό την βελτιστοποίηση και την ταχύτερη εκτέλεση τους. Το κύριο μοντέλο που χρησιμοποιήθηκε είναι αυτό του ανεξάρτητου καταρράκτη (IC), το οποίο αποτελεί και μέρος του αλγόριθμου CELF, του οποίου έγινε προσομοίωση και παράλληλη εκτέλεση, καθώς και αυτό του γραμμικού κατωφλίου (LT), που με τη βοήθεια παράλληλων υπολογισμών αντιμετωπίζεται το αρχικό πρόβλημα για το μοντέλο διάχυσης SIR. Επιπλεόν, πραγματοποιούνται τεχνικές ανίχνευσης κοινοτήτων αλλά και γνωστές μέθοδοι κεντρικότητας κόμβων. Διεξάγονται πειράματα σε πέντε κοινωνικά δίκτυα του πραγματικού κόσμου. Τα πειραματικά αποτελέσματα αποδεικνύουν την αποτελεσματικότητα των μεθόδων με εξαιρετική απόδοση. Finding the most influential people to maximize its spread on a social network remains an important and difficult problem. Proven to be NP- hard, the influence maximization problem has attracted several studies. Real-world social networks are large and complex. This makes the execution of the algorithms associated with the problem quite slow. In this work, methods of parallelization of these algorithms are investigated, in order to optimize and execute them faster. The main model used is that of the independent waterfall (IC), which is also part of the CELF algorithm, which was simulated and executed in parallel, as well as that of the linear threshold (LT), which with the help of parallel calculations treats the initial problem for the SIR diffusion model. In addition, community detection techniques and known node centralization methods are performed. Experiments are being conducted on five real-world social networks. Experimental results prove the effectiveness of the methods with excellent efficiency. 2022-03-10T09:50:08Z 2022-03-10T09:50:08Z 2022-03-09 http://hdl.handle.net/10889/15949 gr application/pdf |
| institution |
UPatras |
| collection |
Nemertes |
| language |
Greek |
| topic |
Μεγιστοποίηση επιρροής Παράλληλος υπολογισμός Μετρικές κεντρικότητας Κοινωνικά δίκτυα μεγάλης κλίμακας Μηχανική μάθηση GPUs Machine learning Social networks |
| spellingShingle |
Μεγιστοποίηση επιρροής Παράλληλος υπολογισμός Μετρικές κεντρικότητας Κοινωνικά δίκτυα μεγάλης κλίμακας Μηχανική μάθηση GPUs Machine learning Social networks Τσιαούση, Ειρήνη Ελένη Μεγιστοποίηση επιρροής σε κοινωνικά δίκτυα και γράφους με παραλληλοποίηση υπολογισμών |
| description |
Η εύρεση των κορυφαίων ατόμων με επιρροή για τη μεγιστοποίηση της εξάπλωσής της σε ένα κοινωνικό δίκτυο, παραμένει ένα σημαντικό αλλά και δύσκολο πρόβλημα. Αποδεδειγμένο ότι είναι πολυπλοκότητας NP- hard, το πρόβλημα μεγιστοποίησης επιρροής έχει προσελκύσει αρκετές μελέτες. Τα κοινωνικά δίκτυα πραγματικού κόσμου είναι μεγάλα και σύνθετα. Αυτό καθιστά την εκτέλεση των αλγορίθμων που σχετίζονται με το πρόβλημα αρκετά αργή. Στην εργασία αυτή ερευνώνται μέθοδοι παραλληλοποίησης των αλγορίθμων αυτών, με σκοπό την βελτιστοποίηση και την ταχύτερη εκτέλεση τους. Το κύριο μοντέλο που χρησιμοποιήθηκε είναι αυτό του ανεξάρτητου καταρράκτη (IC), το οποίο αποτελεί και μέρος του αλγόριθμου CELF, του οποίου έγινε προσομοίωση και παράλληλη εκτέλεση, καθώς και αυτό του γραμμικού κατωφλίου (LT), που με τη βοήθεια παράλληλων υπολογισμών αντιμετωπίζεται το αρχικό πρόβλημα για το μοντέλο διάχυσης SIR. Επιπλεόν, πραγματοποιούνται τεχνικές ανίχνευσης κοινοτήτων αλλά και γνωστές μέθοδοι κεντρικότητας κόμβων. Διεξάγονται πειράματα σε πέντε κοινωνικά δίκτυα του πραγματικού κόσμου. Τα πειραματικά αποτελέσματα αποδεικνύουν την αποτελεσματικότητα των μεθόδων με εξαιρετική απόδοση. |
| author2 |
Tsiaousi, Eirini Eleni |
| author_facet |
Tsiaousi, Eirini Eleni Τσιαούση, Ειρήνη Ελένη |
| author |
Τσιαούση, Ειρήνη Ελένη |
| author_sort |
Τσιαούση, Ειρήνη Ελένη |
| title |
Μεγιστοποίηση επιρροής σε κοινωνικά δίκτυα και γράφους με παραλληλοποίηση υπολογισμών |
| title_short |
Μεγιστοποίηση επιρροής σε κοινωνικά δίκτυα και γράφους με παραλληλοποίηση υπολογισμών |
| title_full |
Μεγιστοποίηση επιρροής σε κοινωνικά δίκτυα και γράφους με παραλληλοποίηση υπολογισμών |
| title_fullStr |
Μεγιστοποίηση επιρροής σε κοινωνικά δίκτυα και γράφους με παραλληλοποίηση υπολογισμών |
| title_full_unstemmed |
Μεγιστοποίηση επιρροής σε κοινωνικά δίκτυα και γράφους με παραλληλοποίηση υπολογισμών |
| title_sort |
μεγιστοποίηση επιρροής σε κοινωνικά δίκτυα και γράφους με παραλληλοποίηση υπολογισμών |
| publishDate |
2022 |
| url |
http://hdl.handle.net/10889/15949 |
| work_keys_str_mv |
AT tsiaousēeirēnēelenē megistopoiēsēepirroēssekoinōnikadiktyakaigraphousmeparallēlopoiēsēypologismōn AT tsiaousēeirēnēelenē influencemaximalizationinsocialnetworksandgraphswithparallelcalculations |
| _version_ |
1771297128427028480 |
