Template-driven team formation
| dc.contributor.author | Αποστόλου, Σπυρίδων | el |
| dc.date.accessioned | 2018-03-30T09:36:35Z | |
| dc.date.available | 2018-03-30T09:36:35Z | |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/29009 | |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.2519 | |
| dc.rights | Default License | |
| dc.subject | Εξόρυξη δεδομένων | el |
| dc.subject | Εξόρυξη από γράφους | el |
| dc.subject | Σχηματισμός ομάδος | el |
| dc.subject | Data mining | en |
| dc.subject | Graph mining | en |
| dc.subject | Team formation | en |
| dc.title | Template-driven team formation | en |
| dc.title | Σχηματισμός ομάδος με χρήση προσχεδίου | el |
| heal.abstract | 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. | en |
| heal.abstract | Το πρόβληματου σχηματισμού ομάδας (team-formation) σε κοινωνικά δίκτυα αϕορά στην αναζήτησημίας ομάδας ατόμων που συνολικά έχει τις απαραίτητες ικανότητες (skills) για να ϕέρει εις πέρας μία εργασία, ενώ ταυτόχρονα το κόστος επικοινωνίας, το οποίο μετριέται ως το άθροισμα των αποστάσεων των μελών στο κοινωνικό δίκτυο, παραμένει σε χαμηλά επίπεδα. Η πρακτική ϕύση του προβλήματος είναι και ο λόγος που έχει προσελκύσει το ενδιαϕέρον των ερευνητών σε μεγάλο βαθμό. Δεν είναι ασυνήθιστο σενάριο μια εταιρία να θέλει να σχηματίσει μια ομάδα για να διεκπεραιώσει μία εργασία ή ένα τμήμα πανεπιστημίου να θέλει να σχηματίσει μια ομάδα από ερευνητές για ένα πρόγραμμα το οποίο απαιτεί άτομα από διαϕορετικούς τομείς της πληροϕορικής. Η βιβλιογραϕία, στην πλειοψηϕία της, υποθέτει πως η ομάδα έχει επίπεδη δομή, όπου δηλαδή όλα τα μέλη είναι ίσα, ή μία απλή δομή αστεριού όπου όλα τα μέλη είναι συγκεντρωμένα γύρω από έναν ηγέτη. Παρ’ όλα αυτά, στην πραγματική ζωή, οι ομάδες έχουν σύνθετες δομές και ιεραρχίες με μεγάλο βάθος καιταμέλητων ομάδων έχουν διακριτούςρόλους.Σε αυτή την εργασία, ορίζουμετο πρόβληματου Σχηματισμού Ομάδος με Πρότυπο, σύμϕωνα με το οποίο δοθέντων ενός κοινωνικού γράϕου που ενώνει, ενός προτύπου δομής της ομάδος σε μορϕή γράϕου και μιας ανάθεσης ρόλων στους κόμβους του προτύπου, αναζητούμε ”εργάτες” οι οποίοι θα καταλάβουν τις θέσεις του προτύπου, ελαχιστοποιώντας το κόστος επικοινωνίας που ορίζεται ως το άθροισμα των αποστάσεων των ατόμων που επιλέχθηκαν για να καταλάβουν τις θέσεις του προτύπου ως προς τις ακμές του προτύπου, δηλαδή η απόσταση δύο ατόμων που δεν ενώνονται με ακμή στο πρότυπο δεν συνυπολογίζεται στο κόστος της ανάθεσης καθώς η καλή επικοινωνία ανάμεσα τους είναι δευτερευόντος σημασίας αϕού δεν προβλέπεται να χρειαστεί να συνεργαστούν. Παρ’ όλο που το πρόβλημα είναι NP-hard, μερικές παραλλαγές του προβλήματος λύνονται βέλτιστα χρησιμοποιώντας δυναμικό προγραμματισμό. Για την γενική περίπτωση, παρέχουμε προσεγγιστικές λύσεις και ευριστικούς αλγόριθμους. Επιπλέον πειραματιζόμαστε σε πραγματικά δεδομένα και παρουσιάζουμε πως οι ευριστικοί αλγόριθμοι αποδίδουν εξίσου καλά ενώ ταυτόχρονα είναι πολύ πιοαποδοτικοί σε θέματα χρόνου εκτέλεσης,και πως οι αλγόριθμοι με τους οποίους επιδιώκουμε να προσεγγίσουμε την βέλτιστη λύση στην γενική περίπτωση δεν απέχουν πολύ από αυτή. Τέλος, διεξάγουμε μια εμπειρική μελέτη των αποτελεσμάτων η οποία επισημαίνει την ποιότητα αυτών, καθώς οι ομάδες που παράγονται για κάθε ομάδα δεδομένων είναι αληθοϕανείς, ενώνει δηλαδή άτομα που είναι λογικό να ανήκουν στην ίδια ομάδα βάσει των προηγούμενων συνεργασιών τους. | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.academicPublisherID | uoi | |
| heal.access | free | |
| heal.advisorName | Τσαπάρας, Παναγιώτης | el |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 31-32 | el |
| heal.classification | Data mining | el |
| heal.committeeMemberName | Τσαπάρας, Παναγιώτης | el |
| heal.committeeMemberName | Πιτουρά, Ευαγγελία | el |
| heal.committeeMemberName | Μαμουλής, Νικόλαος | el |
| heal.dateAvailable | 2018-03-30T09:37:35Z | |
| heal.fullTextAvailability | true | |
| heal.language | en | |
| heal.numberOfPages | 32 σ. | |
| heal.publicationDate | 2018 | |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Η/Υ & Πληροφορικής | el |
| heal.type | masterThesis | |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.type.en | Master thesis | en |
Αρχεία
Πρωτότυπος φάκελος/πακέτο
1 - 1 of 1
Φόρτωση...
- Ονομα:
- Μ.Ε. ΑΠΟΣΤΟΛΟΥ ΣΠΥΡΙΔΩΝ 2018.pdf
- Μέγεθος:
- 456.92 KB
- Μορφότυπο:
- Adobe Portable Document Format
- Περιγραφή:
Φάκελος/Πακέτο αδειών
1 - 1 of 1
Φόρτωση...
- Ονομα:
- license.txt
- Μέγεθος:
- 1.71 KB
- Μορφότυπο:
- Item-specific license agreed upon to submission
- Περιγραφή: