{"id":{"repo_id":"athens","oai_identifier":"oai:lib.uoa.gr:uoadl:2975527"},"canonical_url":"https://search.ndltd.org/etd/athens/oai:lib.uoa.gr:uoadl:2975527","repository":{"repo_id":"athens","name":"National and Kapodistrian University of Athens","base_url":"https://pergamos.lib.uoa.gr/uoa/dl/frontend/oaipmh"},"display":{"title":"Identifying High-Coverage Communities in Edge-Weighted Networks","abstract":"Την τελευταία δεκαετία, η αναζήτηση κοινοτήτων έχει συγκεντρώσει μεγάλη απήχηση σε επιστημονικά πεδία όπως η ανάλυση κοινωνικών και βιολογικών δικτύων. Σχετικές μελέτες χρησιμοποιούν μη σταθμισμένους γράφους για να αναπαριστούν υποκείμενες δομές και στοχεύουν στην εύρεση κοινωτήτων με υψηλή συνοχή. Παράλληλα, νέες έρευνες έχουν επικεντρωθεί στην αναζήτηση κοινοτήτων των οποίων τα μέλη 1) πληρούν ένα σύνολο προκαθορισμένων περιορισμών και 2) συλλογικά μεγιστοποιούν την τιμή μια συνάρτησης. Παρα το γεγονός ότι πλήθος δικτύων του πραγματικού κόσμου διαθέτουν ακμές με βάρη καθώς και κόμβους που σχετίζονται με ένα σύνολο χαρακτηριστικών, οι παραπάνω ήδη καταβληθείσες προσπάθειες επικεντρώνονται κυρίως σε μη σταθμισμένα δίκτυα χωρίς χαρακτηριστικά στους κόμβους. Σε αυτή τη διπλωματική, διερευνούμε μια παραλλαγή του προβλήματος αναζήτησης κοινοτήτων για μη κατευθυνόμενα δίκτυα, με βάρη στις ακμές και κόμβους που διαθέτουν ένα σύνολο χαρακτηριστικών. Δοθέντων ενός γράφου G, ενός συνόλου αρχικών κόμβων, ένα άνω όριο h ως προς το μέγεθος της επιστρεπτέας λύσης, καθώς και ένα κάτω φράγμα s ως προς την συνεκτικότητα, στοχεύουμε στην εύρεση ενός συνδεδεμένου υπογράφου του G ο οποίος: 1) περιέχει τους αρχικούς κόμβους, 2) το μέγεθος της κοινότητας που προσδιορίζεται είναι το πολύ h, 3) το μέτρο συνοχής είναι τουλάχιστον s και 4) ο συνολικός αριθμός των διαφορετικών χαρακτηριστικών που καλύπτονται από τους κόμβους της λύσης μεγιστοποιείται. Ονομάζουμε αυτό το πρόβλημα Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS). Σε αυτή την διπλωματική, εκμεταλλευόμαστε την πληροφορία που προέρχεται από τα βάρη των ακμών για να ποσοτικοποιήσουμε το ελάχιστο άθροισμα των βαρών που πρέπει να έχει κάποιος κόμβος σε κάθε υποψήφιο υπογράφημα. Υπό αυτές τις συνθήκες, αυτό το ελάχιστο άθροισμα των βαρών, χρησιμεύει ως μέτρο συνοχής. Δείχνουμε ότι Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS) είναι ένα NP-δύσκολο πρόβλημα όταν πρόκειται για γενικευμένα δίκτυα και ως εκ τούτου, προτείνουμε τρεις προσεγγίσεις για την αντιμετώπιση του εν λόγω προβλήματος. Πειραματικά αποτελέσματα έξι σύνολου δεδομένων πραγματικού κόσμου, δείχνουν ότι παρά τη δυσκολία του προβλήματός μας, μπορούμε αποδοτικά να εντοπίουμε λύσεις που παρέχουν αποτελεσματική κάλυψη.","abstract_html":"Την τελευταία δεκαετία, η αναζήτηση κοινοτήτων έχει συγκεντρώσει μεγάλη απήχηση σε επιστημονικά πεδία όπως η ανάλυση κοινωνικών και βιολογικών δικτύων. Σχετικές μελέτες χρησιμοποιούν μη σταθμισμένους γράφους για να αναπαριστούν υποκείμενες δομές και στοχεύουν στην εύρεση κοινωτήτων με υψηλή συνοχή. Παράλληλα, νέες έρευνες έχουν επικεντρωθεί στην αναζήτηση κοινοτήτων των οποίων τα μέλη 1) πληρούν ένα σύνολο προκαθορισμένων περιορισμών και 2) συλλογικά μεγιστοποιούν την τιμή μια συνάρτησης. Παρα το γεγονός ότι πλήθος δικτύων του πραγματικού κόσμου διαθέτουν ακμές με βάρη καθώς και κόμβους που σχετίζονται με ένα σύνολο χαρακτηριστικών, οι παραπάνω ήδη καταβληθείσες προσπάθειες επικεντρώνονται κυρίως σε μη σταθμισμένα δίκτυα χωρίς χαρακτηριστικά στους κόμβους. Σε αυτή τη διπλωματική, διερευνούμε μια παραλλαγή του προβλήματος αναζήτησης κοινοτήτων για μη κατευθυνόμενα δίκτυα, με βάρη στις ακμές και κόμβους που διαθέτουν ένα σύνολο χαρακτηριστικών. Δοθέντων ενός γράφου G, ενός συνόλου αρχικών κόμβων, ένα άνω όριο h ως προς το μέγεθος της επιστρεπτέας λύσης, καθώς και ένα κάτω φράγμα s ως προς την συνεκτικότητα, στοχεύουμε στην εύρεση ενός συνδεδεμένου υπογράφου του G ο οποίος: 1) περιέχει τους αρχικούς κόμβους, 2) το μέγεθος της κοινότητας που προσδιορίζεται είναι το πολύ h, 3) το μέτρο συνοχής είναι τουλάχιστον s και 4) ο συνολικός αριθμός των διαφορετικών χαρακτηριστικών που καλύπτονται από τους κόμβους της λύσης μεγιστοποιείται. Ονομάζουμε αυτό το πρόβλημα Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS). Σε αυτή την διπλωματική, εκμεταλλευόμαστε την πληροφορία που προέρχεται από τα βάρη των ακμών για να ποσοτικοποιήσουμε το ελάχιστο άθροισμα των βαρών που πρέπει να έχει κάποιος κόμβος σε κάθε υποψήφιο υπογράφημα. Υπό αυτές τις συνθήκες, αυτό το ελάχιστο άθροισμα των βαρών, χρησιμεύει ως μέτρο συνοχής. Δείχνουμε ότι Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS) είναι ένα NP-δύσκολο πρόβλημα όταν πρόκειται για γενικευμένα δίκτυα και ως εκ τούτου, προτείνουμε τρεις προσεγγίσεις για την αντιμετώπιση του εν λόγω προβλήματος. Πειραματικά αποτελέσματα έξι σύνολου δεδομένων πραγματικού κόσμου, δείχνουν ότι παρά τη δυσκολία του προβλήματός μας, μπορούμε αποδοτικά να εντοπίουμε λύσεις που παρέχουν αποτελεσματική κάλυψη.","abstract_has_math":false,"creators":["Πετσίνης Πέτρος","Petsinis Petros"],"institution":null,"degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2022,"date_issued":"2022","date_published":"2022","updated_at":"2026-11-19T05:45:15Z","subjects":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"languages":["English"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["uoadl:2975527"],"render_values":[{"text":"uoadl:2975527","href":null,"code":true}]}],"person_identifier_entries":[]},"links":{"outbound_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2975527","outbound_label":"Repository record","outbound_source":"dc:identifier","record_url":"https://pergamos.lib.uoa.gr/uoa/dl/object/2975527","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%3A2975527","prefix":"oai_dc"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Πετσίνης Πέτρος","Petsinis Petros"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2022"]},{"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":["Τεχνολογία – Πληροφορική","Technology - Computer 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:2975527","https://pergamos.lib.uoa.gr/uoa/dl/object/2975527"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Την τελευταία δεκαετία, η αναζήτηση κοινοτήτων έχει συγκεντρώσει μεγάλη απήχηση σε επιστημονικά πεδία όπως η ανάλυση κοινωνικών και βιολογικών δικτύων. Σχετικές μελέτες χρησιμοποιούν μη σταθμισμένους γράφους για να αναπαριστούν υποκείμενες δομές και στοχεύουν στην εύρεση κοινωτήτων με υψηλή συνοχή. Παράλληλα, νέες έρευνες έχουν επικεντρωθεί στην αναζήτηση κοινοτήτων των οποίων τα μέλη 1) πληρούν ένα σύνολο προκαθορισμένων περιορισμών και 2) συλλογικά μεγιστοποιούν την τιμή μια συνάρτησης. Παρα το γεγονός ότι πλήθος δικτύων του πραγματικού κόσμου διαθέτουν ακμές με βάρη καθώς και κόμβους που σχετίζονται με ένα σύνολο χαρακτηριστικών, οι παραπάνω ήδη καταβληθείσες προσπάθειες επικεντρώνονται κυρίως σε μη σταθμισμένα δίκτυα χωρίς χαρακτηριστικά στους κόμβους. Σε αυτή τη διπλωματική, διερευνούμε μια παραλλαγή του προβλήματος αναζήτησης κοινοτήτων για μη κατευθυνόμενα δίκτυα, με βάρη στις ακμές και κόμβους που διαθέτουν ένα σύνολο χαρακτηριστικών. Δοθέντων ενός γράφου G, ενός συνόλου αρχικών κόμβων, ένα άνω όριο h ως προς το μέγεθος της επιστρεπτέας λύσης, καθώς και ένα κάτω φράγμα s ως προς την συνεκτικότητα, στοχεύουμε στην εύρεση ενός συνδεδεμένου υπογράφου του G ο οποίος: 1) περιέχει τους αρχικούς κόμβους, 2) το μέγεθος της κοινότητας που προσδιορίζεται είναι το πολύ h, 3) το μέτρο συνοχής είναι τουλάχιστον s και 4) ο συνολικός αριθμός των διαφορετικών χαρακτηριστικών που καλύπτονται από τους κόμβους της λύσης μεγιστοποιείται. Ονομάζουμε αυτό το πρόβλημα Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS). Σε αυτή την διπλωματική, εκμεταλλευόμαστε την πληροφορία που προέρχεται από τα βάρη των ακμών για να ποσοτικοποιήσουμε το ελάχιστο άθροισμα των βαρών που πρέπει να έχει κάποιος κόμβος σε κάθε υποψήφιο υπογράφημα. Υπό αυτές τις συνθήκες, αυτό το ελάχιστο άθροισμα των βαρών, χρησιμεύει ως μέτρο συνοχής. Δείχνουμε ότι Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS) είναι ένα NP-δύσκολο πρόβλημα όταν πρόκειται για γενικευμένα δίκτυα και ως εκ τούτου, προτείνουμε τρεις προσεγγίσεις για την αντιμετώπιση του εν λόγω προβλήματος. Πειραματικά αποτελέσματα έξι σύνολου δεδομένων πραγματικού κόσμου, δείχνουν ότι παρά τη δυσκολία του προβλήματός μας, μπορούμε αποδοτικά να εντοπίουμε λύσεις που παρέχουν αποτελεσματική κάλυψη.","Over the past decade, community search has garnered massive appeal in the areas of social and biology network analysis. Pertinent studies have utilized unweighted graphs to represent underlying structures and seek to reveal highly-cohesive formed groups. Concurrent initiatives have focused on the search for communities whose members 1) comply with designated constraint(s) and 2) collectively present maximization of a score function. Despite the fact that a multitude of real-world networks feature both weighted edges and node attributes, the above already expended efforts focus mostly on unweighted networks without node attributes. In this thesis, we investigate a variant of the community search problem for undirected, edge-weighted, and node-attributed networks modeled as graphs. Given a weighted graph G, a query set of seed nodes Q, a community size constraint h, and a connectivity constraint s, we aim to find a connected subgraph of G that: 1) contains the seed nodes, 2) the size of the community identified is at most h, 3) its cohesiveness measure is at least s and 4) its total number of associated elements is maximized. We term this problem Weighted Covering Community Search (WCCS). In this thesis, we exploit edge-weight-information to quantify the minimum strength within each candidate subgraph considered. In this regard, this minimum strength serves as our cohesiveness measure. We show that the Weighted Covering Community Search (WCCS) is an NP-hard problem when it comes to generalized networks and therefore, we suggest three approaches to address the problem in question. Experimental results with six realworld datasets point to the fact that despite the hardness of our problem, we can efficiently identify solutions that render effective coverage."]},{"key":"dc:title","label":"Title","values":["Identifying High-Coverage Communities in Edge-Weighted Networks"]}]}],"canonical_facts":{"dc:creator":["Πετσίνης Πέτρος","Petsinis Petros"],"dc:date":["2022"],"dc:description":["Την τελευταία δεκαετία, η αναζήτηση κοινοτήτων έχει συγκεντρώσει μεγάλη απήχηση σε επιστημονικά πεδία όπως η ανάλυση κοινωνικών και βιολογικών δικτύων. Σχετικές μελέτες χρησιμοποιούν μη σταθμισμένους γράφους για να αναπαριστούν υποκείμενες δομές και στοχεύουν στην εύρεση κοινωτήτων με υψηλή συνοχή. Παράλληλα, νέες έρευνες έχουν επικεντρωθεί στην αναζήτηση κοινοτήτων των οποίων τα μέλη 1) πληρούν ένα σύνολο προκαθορισμένων περιορισμών και 2) συλλογικά μεγιστοποιούν την τιμή μια συνάρτησης. Παρα το γεγονός ότι πλήθος δικτύων του πραγματικού κόσμου διαθέτουν ακμές με βάρη καθώς και κόμβους που σχετίζονται με ένα σύνολο χαρακτηριστικών, οι παραπάνω ήδη καταβληθείσες προσπάθειες επικεντρώνονται κυρίως σε μη σταθμισμένα δίκτυα χωρίς χαρακτηριστικά στους κόμβους. Σε αυτή τη διπλωματική, διερευνούμε μια παραλλαγή του προβλήματος αναζήτησης κοινοτήτων για μη κατευθυνόμενα δίκτυα, με βάρη στις ακμές και κόμβους που διαθέτουν ένα σύνολο χαρακτηριστικών. Δοθέντων ενός γράφου G, ενός συνόλου αρχικών κόμβων, ένα άνω όριο h ως προς το μέγεθος της επιστρεπτέας λύσης, καθώς και ένα κάτω φράγμα s ως προς την συνεκτικότητα, στοχεύουμε στην εύρεση ενός συνδεδεμένου υπογράφου του G ο οποίος: 1) περιέχει τους αρχικούς κόμβους, 2) το μέγεθος της κοινότητας που προσδιορίζεται είναι το πολύ h, 3) το μέτρο συνοχής είναι τουλάχιστον s και 4) ο συνολικός αριθμός των διαφορετικών χαρακτηριστικών που καλύπτονται από τους κόμβους της λύσης μεγιστοποιείται. Ονομάζουμε αυτό το πρόβλημα Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS). Σε αυτή την διπλωματική, εκμεταλλευόμαστε την πληροφορία που προέρχεται από τα βάρη των ακμών για να ποσοτικοποιήσουμε το ελάχιστο άθροισμα των βαρών που πρέπει να έχει κάποιος κόμβος σε κάθε υποψήφιο υπογράφημα. Υπό αυτές τις συνθήκες, αυτό το ελάχιστο άθροισμα των βαρών, χρησιμεύει ως μέτρο συνοχής. Δείχνουμε ότι Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS) είναι ένα NP-δύσκολο πρόβλημα όταν πρόκειται για γενικευμένα δίκτυα και ως εκ τούτου, προτείνουμε τρεις προσεγγίσεις για την αντιμετώπιση του εν λόγω προβλήματος. Πειραματικά αποτελέσματα έξι σύνολου δεδομένων πραγματικού κόσμου, δείχνουν ότι παρά τη δυσκολία του προβλήματός μας, μπορούμε αποδοτικά να εντοπίουμε λύσεις που παρέχουν αποτελεσματική κάλυψη.","Over the past decade, community search has garnered massive appeal in the areas of social and biology network analysis. Pertinent studies have utilized unweighted graphs to represent underlying structures and seek to reveal highly-cohesive formed groups. Concurrent initiatives have focused on the search for communities whose members 1) comply with designated constraint(s) and 2) collectively present maximization of a score function. Despite the fact that a multitude of real-world networks feature both weighted edges and node attributes, the above already expended efforts focus mostly on unweighted networks without node attributes. In this thesis, we investigate a variant of the community search problem for undirected, edge-weighted, and node-attributed networks modeled as graphs. Given a weighted graph G, a query set of seed nodes Q, a community size constraint h, and a connectivity constraint s, we aim to find a connected subgraph of G that: 1) contains the seed nodes, 2) the size of the community identified is at most h, 3) its cohesiveness measure is at least s and 4) its total number of associated elements is maximized. We term this problem Weighted Covering Community Search (WCCS). In this thesis, we exploit edge-weight-information to quantify the minimum strength within each candidate subgraph considered. In this regard, this minimum strength serves as our cohesiveness measure. We show that the Weighted Covering Community Search (WCCS) is an NP-hard problem when it comes to generalized networks and therefore, we suggest three approaches to address the problem in question. Experimental results with six realworld datasets point to the fact that despite the hardness of our problem, we can efficiently identify solutions that render effective coverage."],"dc:identifier":["uoadl:2975527","https://pergamos.lib.uoa.gr/uoa/dl/object/2975527"],"dc:language":["English"],"dc:subject":["Τεχνολογία – Πληροφορική","Technology - Computer science"],"dc:title":["Identifying High-Coverage Communities in Edge-Weighted Networks"],"dc:type":["born_digital_postgraduate_thesis","Διπλωματική Εργασία","Postgraduate Thesis"]},"updated_at":"2026-11-19T05:45:15Z"}