Please use this identifier to cite or link to this item:
https://olympias.lib.uoi.gr/jspui/handle/123456789/32190Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Spyrou, Iro | en |
| dc.date.accessioned | 2022-12-05T08:23:15Z | - |
| dc.date.available | 2022-12-05T08:23:15Z | - |
| dc.identifier.uri | https://olympias.lib.uoi.gr/jspui/handle/123456789/32190 | - |
| dc.identifier.uri | http://dx.doi.org/10.26268/heal.uoi.12002 | - |
| dc.rights | Attribution-NonCommercial-NoDerivs 3.0 United States | * |
| dc.rights | info:eu-repo/semantics/openAccess | * |
| dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/3.0/us/ | * |
| dc.subject | Social networks | en |
| dc.subject | Κοινωνικά δίκτυα | el |
| dc.title | Team formation with mutual respect | en |
| dc.title | Δημιουργία ομάδων με μοιβαίο σεβασμό | el |
| dc.type | info:eu-repo/semantics/masterThesis | * |
| heal.type | masterThesis | - |
| heal.type.en | Master thesis | en |
| heal.type.el | Μεταπτυχιακή εργασία | el |
| heal.classification | Social networks | - |
| heal.dateAvailable | 2022-12-05T08:24:15Z | - |
| heal.language | en | - |
| heal.access | free | - |
| heal.recordProvider | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.publicationDate | 2022 | - |
| heal.bibliographicCitation | Βιβλιογραφία: σ. 37-39 | el |
| heal.abstract | The Team Formation problem in Social Networks [1], asks for a team of experts that covers the skill requirements of a collaborative task, while having low commu nication cost, as this is computed over the social network that connects the experts. The communication cost captures the quality of the team, that is, the ability of the experts to work together. Several extensions of this work have been considered, with different team quality measures, or different team design criteria. In this work, we consider an extension of the Team Formation problem, where team quality is measured as the respect between the team members. Given a directed graph for each skill, which captures the respect relationships between experts, we want to create a team where each skill is assigned an expert and the overall respect that the assigned experts receive from the team members is maximized. The respect maximization problem is NP-hard, and a variety of Greedy heuristics have been proposed for solving it [2]. In our work, we propose an Integer Quadratic Programming (IQP) formulation, and we provide an alternative heuristic algorithm for the respect maximization problem. We then consider a variation of the aforementioned problem, where respect is antisymmetric. This means that if there is positive respect from expert u to expert v for some skill, then there is equal but negative disrespect from expert v to expert u. If expert u is assigned to this skill, adding expert v to the team will impact negatively the quality of the team. We first consider a special case of this problem, where the antisymmetric respect values are derived by a scored ranking of the experts. In this case, we show that the respect maximization problem can be reduced to the maximum weight matching problem, which can be solved optimally (using the Hungarian algorithm), or approximately (using a Greedy algorithm) in polynomial time. Building on this observation, we propose a landmark-based algorithm for the general case that reduces to the ranking case. We implemented and evaluated our algorithms on real datasets against existing baselines. For the general respect maximization problem, our IQP heuristic produces teams with higher respect, albeit with higher computational cost. For the antisymmetric case, for the ranking case, the Greedy algorithm produces solutions very close to the optimal Hungarian algorithm. For the general case, the landmark heuristics perform comparably with the IQP solution and other Greedy approaches, while having lower computational cost. | en |
| heal.abstract | Η συγκρότηση ομάδων είναι ένα πρόβλημα που αντιμετωπίζεται σε διάφορα περιβάλλοντα (π.χ. εκπαίδευση, εργασία, άθληση, παιχνίδια) για την επίτευξη ενός κοινού στόχου. Είναι όμως σημαντικό τα μέλη μιας ομάδας να μπορούν να συνεργαστούν το καλύτερο δυνατό. Συνεπώς, τίθεται το πρόβλημα της Δημιουργίας Ομάδων σε Κοινωνικά Δίκτυα [1], το οποίο λαμβάνει υπόψη τις κοινωνικές σχέσεις των υποψήφιων μελών κατά την δημιουργία τους. Πιο συγκεκριμένα, δοθέντος ενός κοινωνικού δικτύου εργαζόμενων, το οποίο απεικονίζει τις κοινωνικές σχέσεις τους, των δεξιοτήτων τους και ενός συλλογικού έργου, το οποίο απαιτεί ένα σύνολο δεξιοτήτων για την διεκπεραίωσή του, στόχος είναι η δημιουργία μίας ομάδας εργαζόμενων, τα μέλη της οποίας θα καλύπτουν τις απαιτήσεις δεξιοτήτων του έργου και θα έχουν χαμηλό κόστος επικοινωνίας. Το κόστος επικοινωνίας υπολογίζεται βάσει του κοινωνικού δικτύου και δηλώνει την ποιότητα της ομάδας, δηλαδή την ικανότητα των μελών να συνεργαστούν. Έκτοτε έχουν εξεταστεί πολλές επεκτάσεις του προκειμένου προβλήματος, με διαφορετικές μετρικές της ποιότητας των ομάδων ή διαφορετικά κριτήρια σχεδιασμού των ομάδων. Στην παρούσα εργασία μελετάμε μία επέκταση του προβλήματος Δημιουργίας Ομάδων, όπου η ποιότητα των ομάδων μετράται ως προς τον σεβασμό μεταξύ των μελών μιας ομάδας. Δοθέντος ενός συλλογικού έργου, για την ολοκλήρωση του οποίου απαιτούνται συγκεκριμένες δεξιότητες, και ενός κατευθυνόμενου γράφου για κάθε απαιτούμενη δεξιότητα, ο οποίος απεικονίζει τις σχέσεις σεβασμού με ταξύ των εργαζόμενων, στόχος μας είναι η δημιουργία μίας ομάδας, όπου σε κάθε δεξιότητα ανατίθεται ένας εργαζόμενος, μεγιστοποιώντας τον συνολικό σεβασμό που λαμβάνουν οι εργαζόμουν που έχουν ανατεθεί σε κάθε δεξιότητα από τα υπόλοιπα μέλη της ομάδας. Οι διαφορές του προβλήματος μεγιστοποίησης σεβασμού με το γενικό πρόβλημα Δημιουργίας Ομάδων είναι πως το πρόβλημα εξετάζεται ως πρόβλημα ανάθεσης και όχι ως πρόβλημα κάλυψης, δηλαδή απαιτείται ακριβως ένας εργαζόμενος για μία δεξιότητα και ένας εργαζόμενος μπορεί να αναλάβει μόνο μία δεξιότητα του έργου. Εκτός αυτού, το κοινωνικό δίκτυο που χρησιμοποιείται για την εξαγωγή των σχέσεων είναι κατευθυνόμενο, το οποίο σημαίνει ότι οι σχέσεις δεν είναι απαραίτητα αμοιβαιες, και είναι διαφορετικό για κάθε δεξιότητα, δηλώνοντας πως οι σχέσεις σεβασμού εξαρτώνται και από την δεξιότητα την οποία αφορά. Το πρόβλημα της μεγιστοποίησης σεβασμού έχει οριστεί στο [2], όπου αποδεικνύεται ότι η πολυπλοκότητα του είναι NP-Hard και προτείνεται μια ποικιλία ευριστικών αλγορίθμων για την επίλυσή του. Επιπλέον, ορίζουν και επιλύουν μία υποπερίπτωση του προβλήματος μεγιστοποίησης σεβασμού, δοθέντος μιας κατάταξης των εργαζόμενων για κάθε δεξιότητα, αντί ενός κοινωνικού δικτύου. Στην δική μας εργασία προτείνουμε μία διατύπωση Integer Quadratic Programming (IQP) και παρέχουμε έναν εναλλακτικό ευριστικό αλγόριθμο για το πρόβλημα της μεγιστοποίησης σεβασμού. Έπειτα θεωρούμε μια παραλλαγή το προαναφερθέντος προβλήματος, όπου ο σεβασμός είναι αντισυμμετρικός. Αυτό σημαίνει πως εάν υπάρχει θετικός σεβασμός από τον εργαζόμενο u προς τον εργαζόμενο v για κάποια δεξιότητα, τότε υπάρχει ίση αλλά αρνητική ασέβεια ή έλλειψη σεβασμού από τον εργαζόμενο v προς τον εργαζόμενο u. Αν ο εργαζόμενος u ανατεθεί σε αυτήν την δεξιότητα, τότε η προσθήκη του v στην ομάδα, σε κάποια άλλη δεξιότητα, θα επηρεάσει αρνητικά την ποιότητα της ομάδας. Αρχικά θεωρούμε μία ειδική περίπτωση του προβλήματος, όπου οι αντισυμμετρικές τιμές σεβασμού εξάγονται από μία βαθμολογημένη κατάταξη των εργαζόμενων. Σε αυτήν την περίπτωση, δείχνουμε ότι το πρόβλημα της μεγιστοποίησης σεβασμού μπορεί να αναχθεί σε πρόβλημα maximum weight matching, το οποίο μπορεί να λυθεί βέλτιστα (με την χρήση του Hungarian αλγορίθμου), ή προσεγγιστικά (με την χρήση ενός Greedy αλγορίθμου) σε πολυωνυμικό χρόνο. Βάσει αυτής της παρατή ρησης προτείνουμε αλγόριθμο με ορόσημα, ύστερα από μελέτη διάφορων τρόπων για την βέλτιστη επιλογή ορόσημων, για την γενική περίπτωση του προβλήματος, το οποίο ανάγεται στην περίπτωση της κατάταξης. Επιπροσθέτως, προτείνουμε πα ix ραλλαγές κάποιων ευριστικών αλγορίθμων οι οποίοι έχουν προταθεί στο [2] για την επίλυση του νέου προβλήματος με αντισυμμετρικό σεβασμό. Τέλος, εξετάσαμε την εφαρμογή του ευριστικού αλγορίθμου βάσει της διατύπωσης IQP, τον οποίο προτείνουμε για το γενικό πρόβλημα μεγιστοποίησης σεβασμού. Υλοποιήσαμε και αξιολογήσαμε τους αλγορίθμους μας σε πραγματικά σύνολα δεδομένων έναντι υπαρχόντων μελετών ή αλγορίθμων. Για το γενικό πρόβλημα μεγι στοποίησης σεβασμού, ο ευριστικός αλγόριθμος IQP παράγει ομάδες με υψηλότερο σεβασμό, έχοντας όμως μεγαλύτερο υπολογιστικό κόστος. Για την αντισυμμετρική περίπτωση, για την περίπτωση με την κατάταξη, παρατηρούμε πως ο Greedy αλ γόριθμος παράγει λύσεις πολύ κοντά σε αυτές του Hungarian αλγορίθμου. Για την γενική περίπτωση με γράφο, οι ευριστικοί αλγόριθμοι με τα ορόσημα αποδίδουν παρόμοια με την λύση του IQP και των άλλων ευριστικών προσεγγίσεων, έχοντας χαμηλότερο υπολογιστικό κόστος. | el |
| heal.advisorName | Τσαπάρας, Παναγιώτης | el |
| heal.committeeMemberName | Τσαπάρας, Παναγιώτης | el |
| heal.committeeMemberName | Πιτουρά, Ευαγγελία | el |
| heal.committeeMemberName | Κοντογιάννης, Σπυρίδων | el |
| heal.academicPublisher | Πανεπιστήμιο Ιωαννίνων. Πολυτεχνική Σχολή. Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής | el |
| heal.academicPublisherID | uoi | - |
| heal.numberOfPages | 39 σ. | - |
| heal.fullTextAvailability | true | - |
| Appears in Collections: | Διατριβές Μεταπτυχιακής Έρευνας (Masters) - ΜΗΥΠ | |
Files in This Item:
| File | Description | Size | Format | |
|---|---|---|---|---|
| Μ.Ε. ΣΠΥΡΟΥ ΗΡΩ 2022.pdf | 644.49 kB | Adobe PDF | View/Open |
This item is licensed under a Creative Commons License
