{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2874791"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2874791","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Influence in social networks","abstract":"Στην εργασία αυτή μελετήσαμε δύο κεντρικά προβλήματα σχετικά με την επιρροή στα κοινωνικά δίκτυα. Το πρώτο είναι το πρόβλημα της μεγιστοποίησης της επιρροής στα κοινωνικά δίκτυα για το οποίο παρουσιάζουμε την μαθηματική θεμελείωση πίσω από τους δύο βασικότερους αλγορίθμους που συναντούμε στη βιβλιογραφία καθώς προχωρούμε και στην υλοποίησή τους. Επίσης παρουσιάζουμε και δύο βασικά μοντέλα για την διάδοση της επιρροής, το μοντέλο ανεξάρτητης διάδοσης και το μοντέλου γραμμικού κατωφλίου. Η συνάρτηση επιρρής και στα δύο αυτά μοντέλα παρουσιάζει την σημαντική ιδιότητα submodularity το οποίο εξασφαλίζει την αποδοτικότητα του greedy αλγόριθμου. Το δεύτερο πρόβλημα που μελετήσαμε είναι το πρόβλημα της μάθησης των πιθανοτήτων επιρροής από δεδομένα πραγματικών κοινωνικών δικτύων. Υλοποιήσαμε τους αλγορίθμους που προτείνονται στη βιβλιογραφία τους οποίους χρησιμοποιήσαμε για να υπολογίσουμε της πιθανότητες επιρροής και να αποτιμήσουμε την ακρίβεια πρόβλεψης των διάφορων μοντέλων. Χρειάστηκαν μικρές τροποποιήσεις στους αρχικούς αλγόριθμους για την προσαρμογή τους σε κατευθυνόμενους γράφους. Επίσης δημιουργήσαμε μία βιβλιοθήκη υλοποιημένη σε ruby η οποία μετρατρέπει τα δεδομένα του github archive σε κατάλληλη μορφή αξιοποιήσημη από τους αλγορίθμους. Κατασκευάσαμε λοιπόν ένα καινούργιο σύνολο δεδομένων κατάλληλο για ανάλυση της επιρροής. Τρέξαμε τους αλγορίθμους για την μάθηση της επιρροής στα δεδομένα των κοινωνικών δικτύων digg και github. Επιβεβαιώσαμε την αποτελεσματικότητα των μοντέλων στην πρόβλεψη της διάδοσης των likes/stars μέσα στο δίκτυο. Ωστόσο σε αντίθεση με την βιβλιογραφία δεν διαπιστώσαμε κάποια βελτίωση με την προσθήκη του χρόνου σαν παράγοντα στην συνάρτηση μοντελοποίησης της πιθανότηταςεπιρροής. Παρατηρήσαμε μία μικρή βελτίωση στην προβλεψιμότητα όταν χρησιμοποιήσαμε μόνο τους χρήστες για τους οποίους είχαμε ενδείξεις επιρροής πάνω από ένα δεδομένο κατώφλι. Επίσης προτείνουμε μία καινούργια προσέγγιση στον υπολογισμό της πιθανότητας επιρροής εισάγωντας την διακρισή ανάμεσα σε κάποιες ενέργειες των χρηστών. Αντιμετωπίσαμε την ενέργεια της δημιουργίας μιας δημοσίευσης σαν κάτι το οποίο θα είχε διαφορετική επίδραση στους χρήστες από την ενέργεια του “μου αρέσει” σε μία δημοσίευση. Η βελτίωση αυτή δεν ήταν ιδιαίτερα εμφανής στα roc curves που χρησιμοποιούνται στην βιβλιογραφία αλλά ήταν αρκετά εμφανής στα precission recall curves που θεωρούνται καλύτερες για την εκτίμηση της απόδοσης όταν τα δεδομένα μας δεν είναι ισοκατανεμημένα.","abstract_html":"Στην εργασία αυτή μελετήσαμε δύο κεντρικά προβλήματα σχετικά με την επιρροή στα κοινωνικά δίκτυα. Το πρώτο είναι το πρόβλημα της μεγιστοποίησης της επιρροής στα κοινωνικά δίκτυα για το οποίο παρουσιάζουμε την μαθηματική θεμελείωση πίσω από τους δύο βασικότερους αλγορίθμους που συναντούμε στη βιβλιογραφία καθώς προχωρούμε και στην υλοποίησή τους. Επίσης παρουσιάζουμε και δύο βασικά μοντέλα για την διάδοση της επιρροής, το μοντέλο ανεξάρτητης διάδοσης και το μοντέλου γραμμικού κατωφλίου. Η συνάρτηση επιρρής και στα δύο αυτά μοντέλα παρουσιάζει την σημαντική ιδιότητα submodularity το οποίο εξασφαλίζει την αποδοτικότητα του greedy αλγόριθμου. Το δεύτερο πρόβλημα που μελετήσαμε είναι το πρόβλημα της μάθησης των πιθανοτήτων επιρροής από δεδομένα πραγματικών κοινωνικών δικτύων. Υλοποιήσαμε τους αλγορίθμους που προτείνονται στη βιβλιογραφία τους οποίους χρησιμοποιήσαμε για να υπολογίσουμε της πιθανότητες επιρροής και να αποτιμήσουμε την ακρίβεια πρόβλεψης των διάφορων μοντέλων. Χρειάστηκαν μικρές τροποποιήσεις στους αρχικούς αλγόριθμους για την προσαρμογή τους σε κατευθυνόμενους γράφους. Επίσης δημιουργήσαμε μία βιβλιοθήκη υλοποιημένη σε ruby η οποία μετρατρέπει τα δεδομένα του github archive σε κατάλληλη μορφή αξιοποιήσημη από τους αλγορίθμους. Κατασκευάσαμε λοιπόν ένα καινούργιο σύνολο δεδομένων κατάλληλο για ανάλυση της επιρροής. Τρέξαμε τους αλγορίθμους για την μάθηση της επιρροής στα δεδομένα των κοινωνικών δικτύων digg και github. Επιβεβαιώσαμε την αποτελεσματικότητα των μοντέλων στην πρόβλεψη της διάδοσης των likes/stars μέσα στο δίκτυο. Ωστόσο σε αντίθεση με την βιβλιογραφία δεν διαπιστώσαμε κάποια βελτίωση με την προσθήκη του χρόνου σαν παράγοντα στην συνάρτηση μοντελοποίησης της πιθανότηταςεπιρροής. Παρατηρήσαμε μία μικρή βελτίωση στην προβλεψιμότητα όταν χρησιμοποιήσαμε μόνο τους χρήστες για τους οποίους είχαμε ενδείξεις επιρροής πάνω από ένα δεδομένο κατώφλι. Επίσης προτείνουμε μία καινούργια προσέγγιση στον υπολογισμό της πιθανότητας επιρροής εισάγωντας την διακρισή ανάμεσα σε κάποιες ενέργειες των χρηστών. Αντιμετωπίσαμε την ενέργεια της δημιουργίας μιας δημοσίευσης σαν κάτι το οποίο θα είχε διαφορετική επίδραση στους χρήστες από την ενέργεια του “μου αρέσει” σε μία δημοσίευση. Η βελτίωση αυτή δεν ήταν ιδιαίτερα εμφανής στα roc curves που χρησιμοποιούνται στην βιβλιογραφία αλλά ήταν αρκετά εμφανής στα precission recall curves που θεωρούνται καλύτερες για την εκτίμηση της απόδοσης όταν τα δεδομένα μας δεν είναι ισοκατανεμημένα.","abstract_has_math":false,"creators":["Τουργέλης-Προβατάς Ορέστης","Tourgelis-Provatas Orestis"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2019,"date_issued":"2019","date_published":"2019","updated_at":"2026-11-19T05:35:14Z","subjects":["Θετικές Επιστήμες","Science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2874791"],"render_values":[{"text":"uoadl:2874791","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2874791","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2874791","record_label":"Repository record","record_kind":"record","record_source":"dc:identifier","download_url":null,"download_label":null,"download_source":null,"access_status":null,"embargo_until":null,"access_note":null},"source_record":{"url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh?verb=GetRecord&metadataPrefix=oai_dc&identifier=oai%3Alib.uoa.gr%3Auoadl%3A2874791","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Τουργέλης-Προβατάς Ορέστης","Tourgelis-Provatas Orestis"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2019"]},{"key":"dc:type","label":"Dc Type","values":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Θετικές Επιστήμες","Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2874791","https://pergamos.lib.uoa.gr/uoa/dl/object/2874791"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Στην εργασία αυτή μελετήσαμε δύο κεντρικά προβλήματα σχετικά με την επιρροή στα κοινωνικά δίκτυα. Το πρώτο είναι το πρόβλημα της μεγιστοποίησης της επιρροής στα κοινωνικά δίκτυα για το οποίο παρουσιάζουμε την μαθηματική θεμελείωση πίσω από τους δύο βασικότερους αλγορίθμους που συναντούμε στη βιβλιογραφία καθώς προχωρούμε και στην υλοποίησή τους. Επίσης παρουσιάζουμε και δύο βασικά μοντέλα για την διάδοση της επιρροής, το μοντέλο ανεξάρτητης διάδοσης και το μοντέλου γραμμικού κατωφλίου. Η συνάρτηση επιρρής και στα δύο αυτά μοντέλα παρουσιάζει την σημαντική ιδιότητα submodularity το οποίο εξασφαλίζει την αποδοτικότητα του greedy αλγόριθμου. Το δεύτερο πρόβλημα που μελετήσαμε είναι το πρόβλημα της μάθησης των πιθανοτήτων επιρροής από δεδομένα πραγματικών κοινωνικών δικτύων. Υλοποιήσαμε τους αλγορίθμους που προτείνονται στη βιβλιογραφία τους οποίους χρησιμοποιήσαμε για να υπολογίσουμε της πιθανότητες επιρροής και να αποτιμήσουμε την ακρίβεια πρόβλεψης των διάφορων μοντέλων. Χρειάστηκαν μικρές τροποποιήσεις στους αρχικούς αλγόριθμους για την προσαρμογή τους σε κατευθυνόμενους γράφους. Επίσης δημιουργήσαμε μία βιβλιοθήκη υλοποιημένη σε ruby η οποία μετρατρέπει τα δεδομένα του github archive σε κατάλληλη μορφή αξιοποιήσημη από τους αλγορίθμους. Κατασκευάσαμε λοιπόν ένα καινούργιο σύνολο δεδομένων κατάλληλο για ανάλυση της επιρροής. Τρέξαμε τους αλγορίθμους για την μάθηση της επιρροής στα δεδομένα των κοινωνικών δικτύων digg και github. Επιβεβαιώσαμε την αποτελεσματικότητα των μοντέλων στην πρόβλεψη της διάδοσης των likes/stars μέσα στο δίκτυο. Ωστόσο σε αντίθεση με την βιβλιογραφία δεν διαπιστώσαμε κάποια βελτίωση με την προσθήκη του χρόνου σαν παράγοντα στην συνάρτηση μοντελοποίησης της πιθανότηταςεπιρροής. Παρατηρήσαμε μία μικρή βελτίωση στην προβλεψιμότητα όταν χρησιμοποιήσαμε μόνο τους χρήστες για τους οποίους είχαμε ενδείξεις επιρροής πάνω από ένα δεδομένο κατώφλι. Επίσης προτείνουμε μία καινούργια προσέγγιση στον υπολογισμό της πιθανότητας επιρροής εισάγωντας την διακρισή ανάμεσα σε κάποιες ενέργειες των χρηστών. Αντιμετωπίσαμε την ενέργεια της δημιουργίας μιας δημοσίευσης σαν κάτι το οποίο θα είχε διαφορετική επίδραση στους χρήστες από την ενέργεια του “μου αρέσει” σε μία δημοσίευση. Η βελτίωση αυτή δεν ήταν ιδιαίτερα εμφανής στα roc curves που χρησιμοποιούνται στην βιβλιογραφία αλλά ήταν αρκετά εμφανής στα precission recall curves που θεωρούνται καλύτερες για την εκτίμηση της απόδοσης όταν τα δεδομένα μας δεν είναι ισοκατανεμημένα.","In this thesis we explored two main problems regarding influence in social networks. The one is the influence maximization problem and the main approximation algorithms that can be found throughout literature. In the same context we also present two different models for the information/in- fluence diffusion in the social networks Independent Cascade and Linear Threshold models. Under both of these models the influence function re- mains submodular which ensures the approximation efficiency of the greedy algorithm. We provide a robust python implementation for aforementioned models, the greedy algorithm, as well as an optimized version (lazy-greedy) which exploits the submodular property of the influence function to reduce computation steps. The second problem regarding influence, is how we can learn these influ- ence probabilities that we take for granted in the first problem, in a real social network. We proceed in the implementation of the algorithms proposed in the literature which we use to calculate the influence probabilities and eval- uate the accuracy of the various proposed models. We have implemented minor modifications to the algorithms to adapt them to a directed network instead of the undirected initial implementation. We also create a ruby gem to parse github archive events into mysql tables, digestible from the learning and evaluating algorithms, producing a new social network dataset. Running the learning algorithms over the action logs of both digg and github social networks we managed to confirm the findings in literature regarding the predictability of the proposed models. We did not detect any improvement though using time conscious models, which are a lot more expensive computationally compared to the static models. We found a minor improvement in the digg social network when restricting our evaluation only on users with influenceability above a certain threshold, a finding that is not reproducible on github dataset. We proposed a novice approach in calculating influence probabilities by distinguishing the effect of different types of actions. The new model did not exhibit any improvement in roc curves but there was a significant improve- ment in precision recall curves which might be a better evaluation method for this specific problem due to the fact that our dataset is unbalanced."]},{"key":"dc:title","label":"Title","values":["Influence in social networks"]}]}],"canonical_facts":{"dc:creator":["Τουργέλης-Προβατάς Ορέστης","Tourgelis-Provatas Orestis"],"dc:date":["2019"],"dc:description":["Στην εργασία αυτή μελετήσαμε δύο κεντρικά προβλήματα σχετικά με την επιρροή στα κοινωνικά δίκτυα. Το πρώτο είναι το πρόβλημα της μεγιστοποίησης της επιρροής στα κοινωνικά δίκτυα για το οποίο παρουσιάζουμε την μαθηματική θεμελείωση πίσω από τους δύο βασικότερους αλγορίθμους που συναντούμε στη βιβλιογραφία καθώς προχωρούμε και στην υλοποίησή τους. Επίσης παρουσιάζουμε και δύο βασικά μοντέλα για την διάδοση της επιρροής, το μοντέλο ανεξάρτητης διάδοσης και το μοντέλου γραμμικού κατωφλίου. Η συνάρτηση επιρρής και στα δύο αυτά μοντέλα παρουσιάζει την σημαντική ιδιότητα submodularity το οποίο εξασφαλίζει την αποδοτικότητα του greedy αλγόριθμου. Το δεύτερο πρόβλημα που μελετήσαμε είναι το πρόβλημα της μάθησης των πιθανοτήτων επιρροής από δεδομένα πραγματικών κοινωνικών δικτύων. Υλοποιήσαμε τους αλγορίθμους που προτείνονται στη βιβλιογραφία τους οποίους χρησιμοποιήσαμε για να υπολογίσουμε της πιθανότητες επιρροής και να αποτιμήσουμε την ακρίβεια πρόβλεψης των διάφορων μοντέλων. Χρειάστηκαν μικρές τροποποιήσεις στους αρχικούς αλγόριθμους για την προσαρμογή τους σε κατευθυνόμενους γράφους. Επίσης δημιουργήσαμε μία βιβλιοθήκη υλοποιημένη σε ruby η οποία μετρατρέπει τα δεδομένα του github archive σε κατάλληλη μορφή αξιοποιήσημη από τους αλγορίθμους. Κατασκευάσαμε λοιπόν ένα καινούργιο σύνολο δεδομένων κατάλληλο για ανάλυση της επιρροής. Τρέξαμε τους αλγορίθμους για την μάθηση της επιρροής στα δεδομένα των κοινωνικών δικτύων digg και github. Επιβεβαιώσαμε την αποτελεσματικότητα των μοντέλων στην πρόβλεψη της διάδοσης των likes/stars μέσα στο δίκτυο. Ωστόσο σε αντίθεση με την βιβλιογραφία δεν διαπιστώσαμε κάποια βελτίωση με την προσθήκη του χρόνου σαν παράγοντα στην συνάρτηση μοντελοποίησης της πιθανότηταςεπιρροής. Παρατηρήσαμε μία μικρή βελτίωση στην προβλεψιμότητα όταν χρησιμοποιήσαμε μόνο τους χρήστες για τους οποίους είχαμε ενδείξεις επιρροής πάνω από ένα δεδομένο κατώφλι. Επίσης προτείνουμε μία καινούργια προσέγγιση στον υπολογισμό της πιθανότητας επιρροής εισάγωντας την διακρισή ανάμεσα σε κάποιες ενέργειες των χρηστών. Αντιμετωπίσαμε την ενέργεια της δημιουργίας μιας δημοσίευσης σαν κάτι το οποίο θα είχε διαφορετική επίδραση στους χρήστες από την ενέργεια του “μου αρέσει” σε μία δημοσίευση. Η βελτίωση αυτή δεν ήταν ιδιαίτερα εμφανής στα roc curves που χρησιμοποιούνται στην βιβλιογραφία αλλά ήταν αρκετά εμφανής στα precission recall curves που θεωρούνται καλύτερες για την εκτίμηση της απόδοσης όταν τα δεδομένα μας δεν είναι ισοκατανεμημένα.","In this thesis we explored two main problems regarding influence in social networks. The one is the influence maximization problem and the main approximation algorithms that can be found throughout literature. In the same context we also present two different models for the information/in- fluence diffusion in the social networks Independent Cascade and Linear Threshold models. Under both of these models the influence function re- mains submodular which ensures the approximation efficiency of the greedy algorithm. We provide a robust python implementation for aforementioned models, the greedy algorithm, as well as an optimized version (lazy-greedy) which exploits the submodular property of the influence function to reduce computation steps. The second problem regarding influence, is how we can learn these influ- ence probabilities that we take for granted in the first problem, in a real social network. We proceed in the implementation of the algorithms proposed in the literature which we use to calculate the influence probabilities and eval- uate the accuracy of the various proposed models. We have implemented minor modifications to the algorithms to adapt them to a directed network instead of the undirected initial implementation. We also create a ruby gem to parse github archive events into mysql tables, digestible from the learning and evaluating algorithms, producing a new social network dataset. Running the learning algorithms over the action logs of both digg and github social networks we managed to confirm the findings in literature regarding the predictability of the proposed models. We did not detect any improvement though using time conscious models, which are a lot more expensive computationally compared to the static models. We found a minor improvement in the digg social network when restricting our evaluation only on users with influenceability above a certain threshold, a finding that is not reproducible on github dataset. We proposed a novice approach in calculating influence probabilities by distinguishing the effect of different types of actions. The new model did not exhibit any improvement in roc curves but there was a significant improve- ment in precision recall curves which might be a better evaluation method for this specific problem due to the fact that our dataset is unbalanced."],"dc:identifier":["uoadl:2874791","https://pergamos.lib.uoa.gr/uoa/dl/object/2874791"],"dc:language":["English"],"dc:subject":["Θετικές Επιστήμες","Science"],"dc:title":["Influence in social networks"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:35:14Z"}