Υπολογισμός τριγώνων σε ροές γραφημάτων

Counting triangles in huge graphs (Αγγλική)

  1. Bachelor’s thesis
  2. Ηλίας, Καράλης
  3. Πληροφορική (ΠΛΗ)
  4. 24 Ιουνίου 2019 [2019-06-24]
  5. Ελληνικά
  6. 71
  7. Παπαδόπουλος, Απόστολος
  8. Δεμέστιχας, Κωνσταντίνος | Αμπατζόγλου, Απόστολος
  9. Γράφοι | Τρίγωνα | συσταδοποίηση | συντελεστής μεταβλητότητας | κατανεμημένα συστήματα | Triest | Spark
  10. 25
  11. Περιέχει : πίνακες, διαγράμματα, εικόνες
    • Η μέτρηση τριγώνων σε μεγάλους γράφους είναι ένας διαδεδομένος τρόπος μέτρησης χαρακτηριστικών του γράφου, όπως ο συντελεστής συσταδοποίησης κι ο συντελεστής μεταβλητότητας. Τέτοιου είδους γράφοι είναι για παράδειγμα, σχέσεις ανάμεσα σε οντότητες όπως σύνδεσμοι ιστοσελίδων, χρήστες κοινωνικών δικτύων, μοριακές δομές πρωτεϊνών και δεδομένα πολλών άλλων εφαρμογών. Το τρίγωνο έχει μήκος 3 και είναι ο μικρότερος κυκλικός γράφος και η μικρότερη κλίκα σε ένα γράφο. Η μέτρηση υπογραφημάτων με συγκεκριμένη δομή, όπως η μέτρηση τριγώνων, δίνει τη δυνατότητα να βγουν συμπεράσματα χρήσιμα για τα δεδομένα αυτά. Παραδείγματα αποτελούν, η χαρτογράφηση κοινοτήτων σε κοινωνικά δίκτυα, η ανακάλυψη δραστηριότητας μηνυμάτων spam και κακόβουλων μηνυμάτων, καθώς και κοινότητες με κοινή θεματική. Ο υπολογισμός του πλήθους των τριγώνων σε τόσο μεγάλους γράφους είναι μια διαδικασία η οποία απαιτεί μεγάλη χωρητικότητα σε μνήμη και μεγάλη υπολογιστική δύναμη. Ακόμα και για γράφους μεσαίου μεγέθους δεν είναι εφικτό να γίνει μέτρηση τριγώνων λόγω της πολυπλοκότητας και το μέγεθος του χώρου μνήμης που είναι αναγκαίος, εάν είναι επιθυμητό να βρεθεί ο ακριβής αριθμός τριγώνων. Η ροή δεδομένων είναι ένας τρόπος να επεξεργαστεί κάποιος έναν τεράστιο γράφο, δυναμικά αναπτυσσόμενο, ο οποίος εισέρχεται σε μικρές ομάδες δεδομένων. Αυτό διευκολύνει την επεξεργασία, εφόσον συνοδεύεται με τη χρήση ενός περιορισμένου δείγματος του γράφου, ο οποίος διατηρείται στη μνήμη, αλλάζει δυναμικά με το πέρασμα του χρόνου, ώστε να αποδώσει όσο πιο πιστά γίνεται τα χαρακτηριστικά του γράφου και καταλαμβάνει σταθερό χώρο στη μνήμη. Οι αλγόριθμοι αυτοί δεν βρίσκουν το πλήθος των τριγώνων ακριβώς αλλά κατά προσέγγιση. Μέχρι τώρα έχουν αναφερθεί αλγόριθμοι μέτρησης τριγώνων σε μεγάλο γράφο, οι οποίες δεν λαμβάνουν υπόψη τους τη δυνατότητα χρησιμοποίησης κατανεμημένων συστημάτων, τα οποία μπορούν να αυξήσουν δυναμικά τους πόρους του συστήματος, δηλαδή τη μνήμη και την υπολογιστική δύναμη. Σε αυτή την εργασία εξετάστηκαν διάφοροι αλγόριθμοι και επιλέχτηκε ο αλγόριθμος Triest για την υλοποίηση μέτρησης των τριγώνων. Επιπρόσθετα η υλοποίηση έγινε σε Spark το οποίο έτρεχε πάνω σε resource manager Yarn του Hadoop και επομένως τρέχει πάνω σε κατανεμημένα συστήματα. Τα συστήματα αυτά τρέχουν πάνω σε cloud openstack και είναι σταθερά. Με την κατάλληλη υλοποίηση, η οποία δεν περιγράφεται σε αυτή την εργασία θα ήταν δυνατό οι πόροι να αυξάνονται δυναμικά (scale-out).
    • Counting triangles in huge graphs is a known method of exploring basic characteristics of the graph like clustering co-efficient and transitivity co-efficient. Some of these graphs might be, reference links in web, social networks and protein structures. A triangle is the shortest cyclic graph and the smallest clique in a graph. The number of subgraphs like triangles provides important insights about basic characteristics of the graph, like clustering and transitivity co-efficient, which subsequently analyze the graph to explore communities in social networks, identify thematic structures of networks, spam and fraud detection, link classification and recommendation and basic substructure in proteins. Counting triangles in huge graphs is a challenging procedure, which requires strong computing power and memory capacity. Even for moderate graphs, it is very difficult to calculate the exact number of triangles, in case the graph cannot be fully loaded in the memory and even then, great computing power and time is needed. Data streaming provides a mean to process huge graphs step by step in smaller batches. In case that only a good estimation of the triangle number is needed, algorithms can be applied to estimate this number, using constant memory space. These algorithms will process every new data batch in acceptable time by using constant space. Based on the analysis in related papers presenting state of the art algorithms, Triest was selected to implement triangle counting. Current work targets an implementation of the algorithm in distributed systems. In this context, implementation was done with Apache Spark, using Hadoop’s Yarn resource manager over cloud Openstack virtual machines cluster. This work will not present scale-out mechanism in cloud, in case more power or memory is needed, this might be part of a future work.
  13. Hellenic Open University
  14. Items in Apothesis are protected by copyright, with all rights reserved, unless otherwise indicated.