Clustering attributed multi-graphs
Andreas Papadopoulos · Gnosis · 2017
Ένα δικτύων πληροφοριών (information networks) μπορεί να μοντελοποιηθεί αποτελεσματικά ως ένας πολυγράφος ιδιοτήτων (attributed multi-graph). Σε ένα πολυγράφο ιδιοτήτων μια κορυφή (vertex) αντιπροσωπεύει ένα αντικείμενο. Κάθε κορυφή χαρακτηρίζεται από κάποιες τιμές που αντιστοιχούν στις ιδιότητες του αντικειμένου που αντιπροσωπεύει. Οι συνδέσεις αναπαριστούν τις σχέσεις που έχουν τα αντικείμενα. Η ομαδοποίηση (clustering) αποσκοπεί στη διαίρεση των αντικειμένων σε ομάδες βάση διαφόρων κριτηρίων. Σε πραγματικά δίκτυα πληροφοριών, κάθε χαρακτηριστικό των αντικειμένων, π.χ. ιδιότητες και τύποι συνδέσεων, περιέχει διαφορετική πληροφορία, και ορισμένα από αυτά τα χαρακτηριστικά μπορεί να μην είναι χρήσιμα στην διαδικασία ομαδοποίησης. Επομένως, πρέπει να προσδιορίσουμε πόσο σημαντική είναι η κάθε ιδιότητας και ο κάθε τύπος ακμής. Όταν η διαδικασία ομαδοποίησης λαμβάνει υπόψη το πόσο σημαντικά είναι τα χαρακτηριστικά των αντικειμένων επιτυγχάνει αποτελέσματα υψηλής ποιότητας. Πολλές υπάρχουσες μέθοδοι ομαδοποίησης αντικειμένων/κόμβων σε γράφους ιδιοτήτων θεωρούν ότι οι ιδιότητες των αντικειμένων είναι το ίδιο σημαντικές ή αγνοούν την ύπαρξη συνδέσεων πολλαπλών τύπων. Επίσης, ανακαλύπτουν ομάδες που χαρακτηρίζονται από ομοιογένεια χαρακτηριστικών και είναι πυκνά συνδεδεμένες (densely connected components). Ωστόσο, η αναγνώριση ομάδων αντικειμένων που μοιράζονται παρόμοιες συνδέσεις είναι επίσης σημαντική. Προτείνουμε μια συλλογή καινοτόμων μεθόδων για την εύρεση ομάδων σε ένα δίκτυο πληροφοριών που μοντελοποιείται ως ένας πολυγράφος ιδιοτήτων. Οι προτεινόμενες μέθοδοι μπορούν να εκμεταλλευτούν την υπολογιστική ισχύ των σύγχρονων πολυπύρηνων υπολογιστών έτσι ώστε να είναι ικανές να χειριστούν μεγάλα σύνολα δεδομένων. Προτείνουμε συναρτήσεις ενοποιημένης ομοιότητας ή απόστασης που συνδυάζουν αποτελεσματικά τα χαρακτηριστικά των κορυφών και σχεδιάζουμε μηχανισμούς στάθμισης. Οι προτεινόμενες μέθοδοι ομαδοποίησης προσδιορίζουν τη σημαντικότητα κάθε χαρακτηριστικού (ιδιότητας και τύπου ακμών) των αντικειμένων χρησιμοποιώντας αυτούς τους μηχανισμούς στάθμισης, και έτσι εξισορροπούν και συνδυάζουν αποτελεσματικά όλα τα χαρακτηριστικά των κορυφών. Το αποτέλεσμα είναι η βελτίωση της ποιότητας της ομαδοποίησης με βάση διάφορα ευρέως αποδεκτά μέτρα αξιολόγησης αλγορίθμων ομαδοποίησης. Ο στόχος μας είναι να μεγιστοποιήσουμε την ενοποιημένη ομοιότητα μεταξύ των κορυφών που ανήκουν στην ίδια ομάδα. Τα μέλη μιας ομάδας πρέπει να έχουν υψηλή παρόμοια συνδεσιμότητα (similar connectivity), δηλαδή να σχετίζονται/συνδέονται με τις ίδιες κορυφές. Επίσης, πρέπει να χαρακτηρίζονται από κοντινές τιμές ιδιοτήτων (χαμηλή εντροπία). Είμαστε από τους πρώτους που βρίσκουμε ομάδες με παρόμοια συνδεσιμότητα σε πολυγράφους ιδιοτήτων. Επιπλέον, αξιοποιούμε τις προτεινόμενες μεθόδους για την επίλυση ενός πρακτικού ζητήματος. Συγκεκριμένα, αναπτύσσουμε ένα σύστημα το οποίο προσφέρει αξιόπιστες συστάσεις (recommendations) σε ευρωπαϊκούς οργανισμούς για καινούριες συνεργασίες. Για να το επιτύχουμε αυτό ομαδοποιούμε τους οργανισμούς που έχουν συμμετάσχει σε έργα που χρηματοδοτήθηκαν από την Ευρωπαϊκή Ένωση στο πλαίσιο του προγράμματος Horizon 2020. Στην συνέχεια, προτείνουμε μια μέθοδο που αναλύει τα αποτελέσματα της ομαδοποίησης για να εξάγει πιθανές συνεργασίες. Οι οργανισμοί και οι ερευνητές μπορούν να χρησιμοποιήσουν το σύστημά μας για να για να εντοπίσουν νέους συνεργάτες. Από όσο γνωρίζουμε, το σύστημα μας είναι το πρώτο που προσφέρει τέτοιες υπηρεσίες στην κοινότητα.