The effect of antagonism on information propagation in social and technological networks
Φόρτωση...
Ημερομηνία
Συγγραφείς
Λιούκα, Ελευθερία
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
The possession of massive digital records of human interactions (e.g., email or file exchanges, friendships or acquaintances, collaborations, phone calls, etc) in recent years provides a new system-wide perspective on social networks. In addition to observing and predicting patterns of collective human behavior, in many cases the dynamics of the network can be engineered. One such example is when attempting to initiate a large cascade by seeding it at certain ``influential'' nodes in the network to promote a novel idea or, a new product through word-of-mouth. The algorithmic challenge of selecting individuals who can serve as early adopters in a manner that will trigger a large cascade in the social network, is known as influence maximization. One might consider several metrics which estimate the ``importance'' of a node in a network. For example, it is well known that high-degree nodes are indeed quite influential in the network. Other popular metrics, such as Betweeness Centrality, Closeness Centrality, or Eigenvector Centrality, might also be considered as good candidates. Moreover, one might consider choosing seeds adaptively, e.g., by choosing the next seed given the subset of already chosen seeds so far.
This thesis studies the effect of competition in influence maximization. We consider a scenario in which two competing firms try to advertise their own product within the same social network. The firms are assumed to assess the importance of the nodes in the network, as ``influencers'' of other nodes towards buying the same product. Each of them selfishly chooses an importance-assessment strategy, i.e., a metric (from a predetermined set of available metrics) to order the nodes in the network. Due to limitations of their advertising budget, each firm is assumed to be able to seed at most $k$ nodes. Therefore, given the importance-orders of the two firms, a seed-selection policy determines the k most important seeds per firm. We then consider two different information-propagation models (De Groot and Threshold) to simulate the dispersion of the new products in the entire network. The measure of success per firm is its own degree of penetration in the market, i.e., the fraction of nodes which will eventually adopt the firm's product. We have implemented algorithms for computing (exactly or in approximation, statically or adaptively) several quite popular importance-assessment metrics. We have also conducted extensive experimental evaluation of this scenario, in order to assess the validity of each importance assessment strategy, under the lens of competition between the two firms, in several benchmark data sets which are widely used in the literature.
Τα κοινωνικά δίκτυα, όσον αφορά τις ανθρώπινες αλληλεπιδράσεις, έχουν αποκτήσει μεγάλη σημασία στις μέρες μας. Για αυτό τον λόγο, διάφορες μορφές πληροφορίας μπορούν να διαδοθούν μέσα από αυτά, όπως για παράδειγμα η διαφήμιση ενός προϊόντος, η εξάπλωση μιας άποψης κτλ. Είναι σημαντικό λοιπόν να μπορούμε να εντοπίζουμε τους ``σημαντικούς'' κόμβους μέσα σε ένα τέτοιο δίκτυο, δηλαδή εκείνους τους κόμβους που μπορούν να επηρεάσουν πολλούς άλλους. Για να το επιτύχουμε αυτό, χρειαζόμαστε κάποιες μετρικές που να ξεχωρίζουν τέτοιους κόμβους μέσα στο δίκυο. ΚάποιεςαπόαυτέςμπορούνναείναιοιμετρικέςBetweeness Centrality, Closeness Centrality, ή Degree Centrality. Ωστόσο, υπάρχουν πολλές και διαφορετικές τέτοιες μέθοδοι στη βιβλιογραφία, για να εξετάσει κάποιος. Στην παρούσα εργασία μελετάται η επίδραση του ανταγωνισμού στη μεγιστοποίηση της επιρροής μέσα στο δίκτυο. Θεωρούμε ότι υπάρχουν δυο ανταγωνιστικές εταιρείες που προσπαθούν να διαφημίσουν το προϊόν τους μέσα στο ίδιο δίκτυο. Για τον σκοπό αυτό, η κάθε μία διαλέγει ανεξάρτητα από την άλλη, μια από τις μετρικές σημαντικότητας, και δημιουργεί μια φθίνουσα σειρά των ατόμων (αντιπροσωπεύονται από κόμβους μέσα στο κοινωνικό δίκτυο) με βάση το επίπεδο επιρροής τους σε άλλα άτομα. Έπειτα, οι δυο φίρμες διαλέγουν τους πρώτους $k$ κόμβους από αυτές τις λίστες και εφαρμόζεται μια μέθοδος που επιλύει τις συγκρούσεις, δηλαδή ορίζει ποια εταιρεία θα κρατήσει έναν κόμβο στην περίπτωση που τον έχουν επιλέξει και οι δυο για να τις αντιπροσωπεύσει. Τέλος, τα δυο τελικά σύνολα αρχικών κόμβων επιρροής για τις δυο εταιρείες ανταγωνίζονται για την διάδοση των προϊόντων που αντιπροσωπεύουν, με βάση δύο μοντέλα προσομοίωσης της διάχυσης πληροφορίας (μοντέλα DeGroot και Threshold) σε ένα κοινωνικό ή τεχνολογικό δίκτυο. Στο τέλος της διαδικασίας, μπορούμε να αποφανθούμε για το ποια από τις δυο εταιρείες πέτυχε τη μεγαλύτερη διείσδυση του προϊόντος της στην αγορά, δηλαδή, τη μεγαλύτερη εξάπλωση του προϊόντος της στο δίκτυο, και κατά πόσο και οι δυο εταιρείες επηρεάστηκαν τελικά από το γεγονός της ύπαρξης του ανταγωνισμού μεταξύ τους. Στο πλαίσιο της παρούσας εργασίας διεξήχθησαν εκτενή πειράματα σε πραγματικά powerlaw κοινωνικά και τεχνολογικά δίκτυα, τα οποία κατέγραψαν μια λεπτομερή εικόνα για την επίδραση του ανταγωνισμού στη διάχυση πληροφορίας.
Τα κοινωνικά δίκτυα, όσον αφορά τις ανθρώπινες αλληλεπιδράσεις, έχουν αποκτήσει μεγάλη σημασία στις μέρες μας. Για αυτό τον λόγο, διάφορες μορφές πληροφορίας μπορούν να διαδοθούν μέσα από αυτά, όπως για παράδειγμα η διαφήμιση ενός προϊόντος, η εξάπλωση μιας άποψης κτλ. Είναι σημαντικό λοιπόν να μπορούμε να εντοπίζουμε τους ``σημαντικούς'' κόμβους μέσα σε ένα τέτοιο δίκτυο, δηλαδή εκείνους τους κόμβους που μπορούν να επηρεάσουν πολλούς άλλους. Για να το επιτύχουμε αυτό, χρειαζόμαστε κάποιες μετρικές που να ξεχωρίζουν τέτοιους κόμβους μέσα στο δίκυο. ΚάποιεςαπόαυτέςμπορούνναείναιοιμετρικέςBetweeness Centrality, Closeness Centrality, ή Degree Centrality. Ωστόσο, υπάρχουν πολλές και διαφορετικές τέτοιες μέθοδοι στη βιβλιογραφία, για να εξετάσει κάποιος. Στην παρούσα εργασία μελετάται η επίδραση του ανταγωνισμού στη μεγιστοποίηση της επιρροής μέσα στο δίκτυο. Θεωρούμε ότι υπάρχουν δυο ανταγωνιστικές εταιρείες που προσπαθούν να διαφημίσουν το προϊόν τους μέσα στο ίδιο δίκτυο. Για τον σκοπό αυτό, η κάθε μία διαλέγει ανεξάρτητα από την άλλη, μια από τις μετρικές σημαντικότητας, και δημιουργεί μια φθίνουσα σειρά των ατόμων (αντιπροσωπεύονται από κόμβους μέσα στο κοινωνικό δίκτυο) με βάση το επίπεδο επιρροής τους σε άλλα άτομα. Έπειτα, οι δυο φίρμες διαλέγουν τους πρώτους $k$ κόμβους από αυτές τις λίστες και εφαρμόζεται μια μέθοδος που επιλύει τις συγκρούσεις, δηλαδή ορίζει ποια εταιρεία θα κρατήσει έναν κόμβο στην περίπτωση που τον έχουν επιλέξει και οι δυο για να τις αντιπροσωπεύσει. Τέλος, τα δυο τελικά σύνολα αρχικών κόμβων επιρροής για τις δυο εταιρείες ανταγωνίζονται για την διάδοση των προϊόντων που αντιπροσωπεύουν, με βάση δύο μοντέλα προσομοίωσης της διάχυσης πληροφορίας (μοντέλα DeGroot και Threshold) σε ένα κοινωνικό ή τεχνολογικό δίκτυο. Στο τέλος της διαδικασίας, μπορούμε να αποφανθούμε για το ποια από τις δυο εταιρείες πέτυχε τη μεγαλύτερη διείσδυση του προϊόντος της στην αγορά, δηλαδή, τη μεγαλύτερη εξάπλωση του προϊόντος της στο δίκτυο, και κατά πόσο και οι δυο εταιρείες επηρεάστηκαν τελικά από το γεγονός της ύπαρξης του ανταγωνισμού μεταξύ τους. Στο πλαίσιο της παρούσας εργασίας διεξήχθησαν εκτενή πειράματα σε πραγματικά powerlaw κοινωνικά και τεχνολογικά δίκτυα, τα οποία κατέγραψαν μια λεπτομερή εικόνα για την επίδραση του ανταγωνισμού στη διάχυση πληροφορίας.
Περιγραφή
Λέξεις-κλειδιά
Ανταγωνισμός, Κοινωνικά Δίκτυα, Διάχυση Πληροφορίας, Antagonism, Competition, Information propagation
Θεματική κατηγορία
Ανταγωνισμός
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Κοντογιάννης, Σπυρίδων
Εξεταστική επιτροπή
Κοντογιάννης, Σπυρίδων
Νικολόπουλος, Σταύρος
Μαμουλής, Νικόλαος
Νικολόπουλος, Σταύρος
Μαμουλής, Νικόλαος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Σχολή Θετικών Επιστημών. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία : σ. 81-84
Ονόματα συντελεστών
Αριθμός σελίδων
84 σ.
Λεπτομέρειες μαθήματος
item.page.endorsement
item.page.review
item.page.supplemented
item.page.referenced
Άδεια Creative Commons
Άδεια χρήσης της εγγραφής: An error occurred on the license name.