National and Kapodistrian University of Athens
Identifying High-Coverage Communities in Edge-Weighted Networks
Abstract
dc:descriptionΤην τελευταία δεκαετία, η αναζήτηση κοινοτήτων έχει συγκεντρώσει μεγάλη απήχηση σε επιστημονικά πεδία όπως η ανάλυση κοινωνικών και βιολογικών δικτύων. Σχετικές μελέτες χρησιμοποιούν μη σταθμισμένους γράφους για να αναπαριστούν υποκείμενες δομές και στοχεύουν στην εύρεση κοινωτήτων με υψηλή συνοχή. Παράλληλα, νέες έρευνες έχουν επικεντρωθεί στην αναζήτηση κοινοτήτων των οποίων τα μέλη 1) πληρούν ένα σύνολο προκαθορισμένων περιορισμών και 2) συλλογικά μεγιστοποιούν την τιμή μια συνάρτησης. Παρα το γεγονός ότι πλήθος δικτύων του πραγματικού κόσμου διαθέτουν ακμές με βάρη καθώς και κόμβους που σχετίζονται με ένα σύνολο χαρακτηριστικών, οι παραπάνω ήδη καταβληθείσες προσπάθειες επικεντρώνονται κυρίως σε μη σταθμισμένα δίκτυα χωρίς χαρακτηριστικά στους κόμβους. Σε αυτή τη διπλωματική, διερευνούμε μια παραλλαγή του προβλήματος αναζήτησης κοινοτήτων για μη κατευθυνόμενα δίκτυα, με βάρη στις ακμές και κόμβους που διαθέτουν ένα σύνολο χαρακτηριστικών. Δοθέντων ενός γράφου G, ενός συνόλου αρχικών κόμβων, ένα άνω όριο h ως προς το μέγεθος της επιστρεπτέας λύσης, καθώς και ένα κάτω φράγμα s ως προς την συνεκτικότητα, στοχεύουμε στην εύρεση ενός συνδεδεμένου υπογράφου του G ο οποίος: 1) περιέχει τους αρχικούς κόμβους, 2) το μέγεθος της κοινότητας που προσδιορίζεται είναι το πολύ h, 3) το μέτρο συνοχής είναι τουλάχιστον s και 4) ο συνολικός αριθμός των διαφορετικών χαρακτηριστικών που καλύπτονται από τους κόμβους της λύσης μεγιστοποιείται. Ονομάζουμε αυτό το πρόβλημα Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS). Σε αυτή την διπλωματική, εκμεταλλευόμαστε την πληροφορία που προέρχεται από τα βάρη των ακμών για να ποσοτικοποιήσουμε το ελάχιστο άθροισμα των βαρών που πρέπει να έχει κάποιος κόμβος σε κάθε υποψήφιο υπογράφημα. Υπό αυτές τις συνθήκες, αυτό το ελάχιστο άθροισμα των βαρών, χρησιμεύει ως μέτρο συνοχής. Δείχνουμε ότι Αναζήτηση Κοινωτήτων Υψηλής Κάλυψης σε Δίκτυα με Βάρη Ακμών (WCCS) είναι ένα NP-δύσκολο πρόβλημα όταν πρόκειται για γενικευμένα δίκτυα και ως εκ τούτου, προτείνουμε τρεις προσεγγίσεις για την αντιμετώπιση του εν λόγω προβλήματος. Πειραματικά αποτελέσματα έξι σύνολου δεδομένων πραγματικού κόσμου, δείχνουν ότι παρά τη δυσκολία του προβλήματός μας, μπορούμε αποδοτικά να εντοπίουμε λύσεις που παρέχουν αποτελεσματική κάλυψη.
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Πετσίνης Πέτρος
- Petsinis Petros
Subjects
dc:subject × 2Rights
- Language dc:language
- English
Identifiers
dc:identifier.*- Identifier
- uoadl:2975527