Template-driven team formation
Φόρτωση...
Ημερομηνία
Συγγραφείς
Αποστόλου, Σπυρίδων
Τίτλος Εφημερίδας
Περιοδικό ISSN
Τίτλος τόμου
Εκδότης
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Περίληψη
Τύπος
Είδος δημοσίευσης σε συνέδριο
Είδος περιοδικού
Είδος εκπαιδευτικού υλικού
Όνομα συνεδρίου
Όνομα περιοδικού
Όνομα βιβλίου
Σειρά βιβλίου
Έκδοση βιβλίου
Συμπληρωματικός/δευτερεύων τίτλος
Περιγραφή
The team-formation problem on social networks asks for a team of individuals that collectively possess the skills to perform a task and have low communication cost, as measured by their distances in the social network. This is a problem of greatpracticalimportancethathasattractedconsiderableattention.Mostrelatedwork assumesaflatstructureintheteam,whereteammembersareallindistinguishable,or asimplestarstructurecenteredaroundaleader.However,inreallife,teamsoftenhave complex structures and deep hierarchies, and members with distinct roles in these structures. In this thesis, we consider the Template-Driven Team Formation problem, where given a fixed template structure for the team in the form of a graph and a designated role for each node in the template, we ask for workers that can fill the roles in the template, while minimizing the communication cost along the template edges.Although the problem is in general NP-hard, there are variantsof the problem that can be solved optimally using dynamic programming. For the general case, we provide approximation and heuristic polynomial-time algorithms. We experiment on real data and we demonstrate that our heuristic algorithms perform well in practice while being significantly more efficient. Our case studies highlight the quality of the teams produced by our algorithms.
Το πρόβληματου σχηματισμού ομάδας (team-formation) σε κοινωνικά δίκτυα αϕορά στην αναζήτησημίας ομάδας ατόμων που συνολικά έχει τις απαραίτητες ικανότητες (skills) για να ϕέρει εις πέρας μία εργασία, ενώ ταυτόχρονα το κόστος επικοινωνίας, το οποίο μετριέται ως το άθροισμα των αποστάσεων των μελών στο κοινωνικό δίκτυο, παραμένει σε χαμηλά επίπεδα. Η πρακτική ϕύση του προβλήματος είναι και ο λόγος που έχει προσελκύσει το ενδιαϕέρον των ερευνητών σε μεγάλο βαθμό. Δεν είναι ασυνήθιστο σενάριο μια εταιρία να θέλει να σχηματίσει μια ομάδα για να διεκπεραιώσει μία εργασία ή ένα τμήμα πανεπιστημίου να θέλει να σχηματίσει μια ομάδα από ερευνητές για ένα πρόγραμμα το οποίο απαιτεί άτομα από διαϕορετικούς τομείς της πληροϕορικής. Η βιβλιογραϕία, στην πλειοψηϕία της, υποθέτει πως η ομάδα έχει επίπεδη δομή, όπου δηλαδή όλα τα μέλη είναι ίσα, ή μία απλή δομή αστεριού όπου όλα τα μέλη είναι συγκεντρωμένα γύρω από έναν ηγέτη. Παρ’ όλα αυτά, στην πραγματική ζωή, οι ομάδες έχουν σύνθετες δομές και ιεραρχίες με μεγάλο βάθος καιταμέλητων ομάδων έχουν διακριτούςρόλους.Σε αυτή την εργασία, ορίζουμετο πρόβληματου Σχηματισμού Ομάδος με Πρότυπο, σύμϕωνα με το οποίο δοθέντων ενός κοινωνικού γράϕου που ενώνει, ενός προτύπου δομής της ομάδος σε μορϕή γράϕου και μιας ανάθεσης ρόλων στους κόμβους του προτύπου, αναζητούμε ”εργάτες” οι οποίοι θα καταλάβουν τις θέσεις του προτύπου, ελαχιστοποιώντας το κόστος επικοινωνίας που ορίζεται ως το άθροισμα των αποστάσεων των ατόμων που επιλέχθηκαν για να καταλάβουν τις θέσεις του προτύπου ως προς τις ακμές του προτύπου, δηλαδή η απόσταση δύο ατόμων που δεν ενώνονται με ακμή στο πρότυπο δεν συνυπολογίζεται στο κόστος της ανάθεσης καθώς η καλή επικοινωνία ανάμεσα τους είναι δευτερευόντος σημασίας αϕού δεν προβλέπεται να χρειαστεί να συνεργαστούν. Παρ’ όλο που το πρόβλημα είναι NP-hard, μερικές παραλλαγές του προβλήματος λύνονται βέλτιστα χρησιμοποιώντας δυναμικό προγραμματισμό. Για την γενική περίπτωση, παρέχουμε προσεγγιστικές λύσεις και ευριστικούς αλγόριθμους. Επιπλέον πειραματιζόμαστε σε πραγματικά δεδομένα και παρουσιάζουμε πως οι ευριστικοί αλγόριθμοι αποδίδουν εξίσου καλά ενώ ταυτόχρονα είναι πολύ πιοαποδοτικοί σε θέματα χρόνου εκτέλεσης,και πως οι αλγόριθμοι με τους οποίους επιδιώκουμε να προσεγγίσουμε την βέλτιστη λύση στην γενική περίπτωση δεν απέχουν πολύ από αυτή. Τέλος, διεξάγουμε μια εμπειρική μελέτη των αποτελεσμάτων η οποία επισημαίνει την ποιότητα αυτών, καθώς οι ομάδες που παράγονται για κάθε ομάδα δεδομένων είναι αληθοϕανείς, ενώνει δηλαδή άτομα που είναι λογικό να ανήκουν στην ίδια ομάδα βάσει των προηγούμενων συνεργασιών τους.
Το πρόβληματου σχηματισμού ομάδας (team-formation) σε κοινωνικά δίκτυα αϕορά στην αναζήτησημίας ομάδας ατόμων που συνολικά έχει τις απαραίτητες ικανότητες (skills) για να ϕέρει εις πέρας μία εργασία, ενώ ταυτόχρονα το κόστος επικοινωνίας, το οποίο μετριέται ως το άθροισμα των αποστάσεων των μελών στο κοινωνικό δίκτυο, παραμένει σε χαμηλά επίπεδα. Η πρακτική ϕύση του προβλήματος είναι και ο λόγος που έχει προσελκύσει το ενδιαϕέρον των ερευνητών σε μεγάλο βαθμό. Δεν είναι ασυνήθιστο σενάριο μια εταιρία να θέλει να σχηματίσει μια ομάδα για να διεκπεραιώσει μία εργασία ή ένα τμήμα πανεπιστημίου να θέλει να σχηματίσει μια ομάδα από ερευνητές για ένα πρόγραμμα το οποίο απαιτεί άτομα από διαϕορετικούς τομείς της πληροϕορικής. Η βιβλιογραϕία, στην πλειοψηϕία της, υποθέτει πως η ομάδα έχει επίπεδη δομή, όπου δηλαδή όλα τα μέλη είναι ίσα, ή μία απλή δομή αστεριού όπου όλα τα μέλη είναι συγκεντρωμένα γύρω από έναν ηγέτη. Παρ’ όλα αυτά, στην πραγματική ζωή, οι ομάδες έχουν σύνθετες δομές και ιεραρχίες με μεγάλο βάθος καιταμέλητων ομάδων έχουν διακριτούςρόλους.Σε αυτή την εργασία, ορίζουμετο πρόβληματου Σχηματισμού Ομάδος με Πρότυπο, σύμϕωνα με το οποίο δοθέντων ενός κοινωνικού γράϕου που ενώνει, ενός προτύπου δομής της ομάδος σε μορϕή γράϕου και μιας ανάθεσης ρόλων στους κόμβους του προτύπου, αναζητούμε ”εργάτες” οι οποίοι θα καταλάβουν τις θέσεις του προτύπου, ελαχιστοποιώντας το κόστος επικοινωνίας που ορίζεται ως το άθροισμα των αποστάσεων των ατόμων που επιλέχθηκαν για να καταλάβουν τις θέσεις του προτύπου ως προς τις ακμές του προτύπου, δηλαδή η απόσταση δύο ατόμων που δεν ενώνονται με ακμή στο πρότυπο δεν συνυπολογίζεται στο κόστος της ανάθεσης καθώς η καλή επικοινωνία ανάμεσα τους είναι δευτερευόντος σημασίας αϕού δεν προβλέπεται να χρειαστεί να συνεργαστούν. Παρ’ όλο που το πρόβλημα είναι NP-hard, μερικές παραλλαγές του προβλήματος λύνονται βέλτιστα χρησιμοποιώντας δυναμικό προγραμματισμό. Για την γενική περίπτωση, παρέχουμε προσεγγιστικές λύσεις και ευριστικούς αλγόριθμους. Επιπλέον πειραματιζόμαστε σε πραγματικά δεδομένα και παρουσιάζουμε πως οι ευριστικοί αλγόριθμοι αποδίδουν εξίσου καλά ενώ ταυτόχρονα είναι πολύ πιοαποδοτικοί σε θέματα χρόνου εκτέλεσης,και πως οι αλγόριθμοι με τους οποίους επιδιώκουμε να προσεγγίσουμε την βέλτιστη λύση στην γενική περίπτωση δεν απέχουν πολύ από αυτή. Τέλος, διεξάγουμε μια εμπειρική μελέτη των αποτελεσμάτων η οποία επισημαίνει την ποιότητα αυτών, καθώς οι ομάδες που παράγονται για κάθε ομάδα δεδομένων είναι αληθοϕανείς, ενώνει δηλαδή άτομα που είναι λογικό να ανήκουν στην ίδια ομάδα βάσει των προηγούμενων συνεργασιών τους.
Περιγραφή
Λέξεις-κλειδιά
Εξόρυξη δεδομένων, Εξόρυξη από γράφους, Σχηματισμός ομάδος, Data mining, Graph mining, Team formation
Θεματική κατηγορία
Data mining
Παραπομπή
Σύνδεσμος
Γλώσσα
en
Εκδίδον τμήμα/τομέας
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Όνομα επιβλέποντος
Τσαπάρας, Παναγιώτης
Εξεταστική επιτροπή
Τσαπάρας, Παναγιώτης
Πιτουρά, Ευαγγελία
Μαμουλής, Νικόλαος
Πιτουρά, Ευαγγελία
Μαμουλής, Νικόλαος
Γενική Περιγραφή / Σχόλια
Ίδρυμα και Σχολή/Τμήμα του υποβάλλοντος
Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Η/Υ & Πληροφορικής
Πίνακας περιεχομένων
Χορηγός
Βιβλιογραφική αναφορά
Βιβλιογραφία: σ. 31-32
Ονόματα συντελεστών
Αριθμός σελίδων
32 σ.