Εύρεση αντιπροσώπων από πιθανοτικά γραφήματα
Creators: name: Λαζαρίδου, Κωνσταντίνα Νικολάου
Publisher: name: Aristotle University of Thessaloniki
Year: 2015
Subjects: πιθανοτικά γραφήματα
εξόρυξη δεδομένων
ανάλυση γραφημάτων
probabilistic graphs
data mining
graph analysis

description: Πολλές πραγματικές εφαρμογές και ειδικότερα διαδικτυακές αναπαριστούν τα δεδομένα τους με τη μορφή του γράφου. Ενδεικτικά παραδείγματα γραφημάτων είναι τα κοινωνικά δίκτυα, τα δίκτυα προτεινών (PPI), δίκτυα συνεργασίας (collaboration networks) κ.α. Κάτω από διάφορες συνθήκες, τα δεδομένα και κατεπέκταση οι γράφοι είναι απαραίτητο να συσχετιστούν με ένα είδος αβεβαιότητας. Για παράδειγμα, κατά την διάρκεια της συλλογής τους τα δεδομένα μπορεί να αλλοιωθούν και να περιέχουν θόρυβο ή διαφορετικά, μπορεί ένα είδος αβεβαιότηας να εσωματωθεί σε αυτά μετά την συλλογή τους, για λόγους προστασίας της ιδιωτικότητας των χρηστών του δικτύου (privacy preserving mechanisms). Ένας πιθανοτικός ή αβέβαιος γράφος είναι ένα δίκτυο με πεπερασμένο αριθμό κόμβων, των οποίων οι ακμές είναι συνιφασμένες με μια πιθανότητα εμφάνισης. Επομένως, ένα πιθανοτικός γράφος είναι ένα μοντέλο δημιουργίας πολλαπλών ντετερμινιστικών γραφημάτων. Προκειμένου να αποφευχθεί η εξαγωγή πολλαπλών δειγμάτων από τον αρχικό γράφο για την ανάλυση του, οι συγγραφείς Parchas et al. (The pursuit of a good possible world: extracting representative instances of uncertain graphs) εισάγουν την καινοτόμα ιδέα της εξαγωγής ενός Αντιπροσωπευτικού (ντετερμινιστικού) Κόσμου από τον αβέβαιο γράφο. Κατ'επέκταση, παραδοσιακοί αλγόριθμοι εξόρυξης δεδομένων θα χρειάζεται πλέον να εφαρμοστούν μόνο μια φορά, στον αντιπρόσωπο του γραφήματος. Επιπρόσθετα, δυο νέες μέθοδοι προτείνονται από τους συγγραφείς, οι οποίες επιλύουν το πρόβλημα εύρεσης αντιπροσώπου, στοχεύοντας στην διατήρηση του αναμενόμενου βαθμού των κόμβων (expected vertex degrees) στον νέο ντετερμιστικό κόσμο. Ο πρώτος αλγόριθμος ονομάζεται ADR (Average-Degree-Rewiring) και διατηρεί τον μέσο αναμενόμενο βαθμό κόμβων του αβέβαιου στο αντιπροσωπευτικό γράφημα και ο δεύτερος ονομάζεται ABM (Approximate-b-matching) και βασίζεται στην μέθοδο b-matching. Οι δυο τεχνικές χρησιμοποιούν την έννοια της απόκλισης (graph discrepancy), ως μέτρο του πόσο αντιπροσωπευτικός είναι ο νέος γράφος σε σχέση με τον αρχικό. Επιπλέον, στα πλαίσια της διπλωματικής εργασίας, υλοποιήσαμε τους δυο αλγορίθμους και μέσα από την εκτενή πειραματική μελέτη τους, αναγνωρίσαμε τα πλεονεκτήματα και τα μειονεκτήματα τους. Αναφέρουμε τα αποτελέσματα μας σχετικά με την απόδοση τους και σκοπεύουμε στην βελτίωση τους, όσον αφορά τον χρονική-χωρική πολυπλοκότητα τους και τα χαρακτηριστικά του αρχικού γραφήματος που καταφέρνουν να διατηρήσουν με επιτυχία στον αντιπροσωπευτικό κόσμο.
description: In many real-world concepts, especially in World Wide Web, there is a wide range of applications that represent their data as graphs. There are several examples of graphs, such as social networks, protein-protein interaction networks and so on. Under several circumstances, all kinds of data and by extension graphs are sometimes associated with uncertainty. For instance, during the collection phase, noisy measurements may occur or uncertainty needs to be injected after the data aggregation for privacy-preserving purposes. An uncertain or probabilistic graph stands for a graph with a finite number of vertices, whose edges are attached to a probability of existence. Hence, a probabilistic graph is a generative model of multiple deterministic ones. Towards avoiding sampling of various certain graphs to analyze the uncertain one, Parchas et. Al (The pursuit of a good possible world: extracting representative instances of uncertain graphs) introduce the novel idea of extracting a (deterministic) Representative World from a probabilistic graph. Therefore, conventional data mining algorithms will be applied to the representative certain instance, instead of the original uncertain network. Moreover, two novel methods are introduced for addressing the Representative Problem, focusing on preserving the expected vertex degrees in the new deterministic world. The first one is called Average-Degree-Rewiring and manages to preserve the expected average degree of the uncertain network to the certain representative world. The second one is the Approximate-b-matching method, which is based on the b-matching algorithm. Both methods make use of the notion of graph discrepancy, as a measure of how successful the representative is compared to the original graph. We have implemented an extended experimental evaluation of the above techniques, revealing their advantages and disadvantages. Furthermore, we state our findings concerning their performance and aim at improving it with respect to the memory requirements, the time complexity and the graph features that the representative can successfully maintain from the probabilistic graph.