Top-k butterfly detection in probabilistic networks
Creators: name: Γεροχρήστου, Μαργαρίτα Περικλή
Publisher: name: Aristotle University of Thessaloniki
Year: 2024
Subjects: Πεταλούδα
Διμερή
Ανίχνευση Κ-Κορυφαίων
Butterfly
Bipartite
Top-k detection

description: In this thesis, we look at the problem of butterfly counting and, with particular emphasis, the problem of top-k butterfly detection in uncertain bipartite networks, which are important topics in network research with applications spanning from recommendation systems to biological networks. Butterfly motifs are crucial structures in bipartite graphs, and identifying them gives valuable information regarding the network’s connectivity and robustness. However, in uncertain networks with probabilistic edges, both butterfly counting and identifying the top-k butterflies -those with the highest probability of existence- become computationally difficult. We reproduced and reimplemented an already existing butterfly counting algorithm and its improvements in C++. Then we translated them, for our convenience, into Python for further enhancement. Our contributions include refining the algorithms for both butterfly counting and top-k butterfly identification, as well as introducing kernel-based optimization. This approach concentrates on high-connectivity subgraphs, which greatly reduces execution time while maintaining accuracy in butterfly counting and top-k butterfly recognition. We illustrate the effectiveness of our methods by doing dataset evaluations. The kernel-optimized techniques reduce execution time while retaining accurate top-k butterfly recognition, making them appropriate for large-scale applications. Our approach serves as a foundation for future study on uncertain bipartite networks, with possible extensions to the detection of other important network motifs beyond butterflies. Further work could explore adapting the algorithms to handle dynamic networks, applying the methods to different types of graphs, developing real-time analysis methods for continuous data streams and more.
description: Σε αυτή τη διατριβή, εξετάζουμε το πρόβλημα της καταμέτρησης πεταλούδων και με περισσότερη έμφαση το πρόβλημα της ανίχνευσης των κ-κορυφαίων πεταλούδων σε αβέβαια διμερή δίκτυα, που αποτελούν σημαντικά θέματα στην έρευνα δικτύων, με εφαρμογές που εκτείνονται από συστήματα συστάσεων έως βιολογικά δίκτυα. Τα μοτίβα των πεταλούδων είναι κρίσιμες δομές σε διμερή γραφήματα και η ταυτοποίησή τους παρέχει πολύτιμες πληροφορίες για τη συνδεσιμότητα και την ανθεκτικότητα του δικτύου. Ωστόσο, σε αβέβαια δίκτυα με ακμές που έχουν πιθανότητα, η καταμέτρηση των πεταλούδων και η ταυτοποίηση των κ-κορυφαίων πεταλούδων -αυτών με την υψηλότερη πιθανότητα ύπαρξης- γίνεται υπολογιστικά δύσκολη. Αναπαράξαμε και υλοποιήσαμε εκ νέου έναν υπάρχοντα αλγόριθμο καταμέτρησης πεταλούδων και τις βελτιώσεις του σε C++, και στη συνέχεια τον μεταφράσαμε σε Python για ευκολία και περαιτέρω βελτιώσεις. Οι συνεισφορές μας περιλαμβάνουν την προσθήκη της ανίχνευσης των κ-κορυφαίων πεταλούδων καθώς και την εισαγωγή βελτιστοποίησης βασισμένης στην προσέγγιση ”kernel”. Αυτή η προσέγγιση εστιάζει σε υπογραφήματα με υψηλή συνδεσιμότητα, μειώνοντας σημαντικά τον χρόνο εκτέλεσης, ενώ ταυτόχρονα διατηρεί πολύ καλά την ακρίβεια στην καταμέτρηση των πεταλούδων και την αναγνώριση των κ-κορυφαίων πεταλούδων. Δείχνουμε την αποτελεσματικότητα των μεθόδων μας με αξιολογήσεις δεδομένων. Οι τεχνικές βελτιστοποιημένες με βάση τον ”kernel” μειώνουν τον χρόνο εκτέλεσης διατηρώντας την ακρίβεια στην αναγνώριση των κ-κορυφαίων πεταλούδων, καθιστώντας τες κατάλληλες ειδικά για εφαρμογές μεγάλης κλίμακας. Η προσέγγισή μας λειτουργεί ως βάση για μελλοντικές μελέτες σε αβέβαια διμερή δίκτυα, με πιθανές επεκτάσεις στην ανίχνευση άλλων σημαντικών δικτυακών μοτίβων πέρα από τις πεταλούδες. Περαιτέρω έρευνα μπορεί να γίνει στην προσαρμογή των αλγορίθμων για τη διαχείριση δυναμικών δικτύων, στην εφαρμογή των μεθόδων σε διαφορετικούς τύπους γραφημάτων, στην ανάπτυξη τεχνικών ανάλυσης σε πραγματικό χρόνο για συνεχείς ροές δεδομένων και άλλα.