Clustering attributed multi-graphs

Abstract

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

An attributed multigraph is a structure that efficiently represents real world networks. In an attributed graph, a vertex represents an object. A vertex is characterized by some attributes corresponding to the object's properties. Edges capture the objects' relationships. Clustering aims to partition the objects into groups, namely clusters, based on various criteria. In real world networks each object property, i.e. attribute and edge-type, contains different information. Some of these properties may be irrelevant to the clustering task. Hence, we must identify the significance of each attribute and edge-type. Clustering process must consider the significance of vertex properties to achieve high-quality results. Many existing attributed graph clustering methods assume the vertex properties are equally important, or they ignore that many edge types exist. Also, they discover clusters characterized by attribute homogeneity that form densely connected components. Yet, identifying clusters of objects that share similar connections is also important. We propose a collection of novel methods to detect clusters in an attributed multigraph. Proposed methods can exploit the computational power of modern multicore architectures. Hence, they can handle large datasets. We propose unified similarity or distance functions that efficiently combine the various vertex properties. We additionally design weighting mechanisms. The proposed methods identify the importance of each vertex property using these mechanisms. They so balance and combine the vertex properties efficiently. The result is the improvement of clustering quality in terms of various evaluation measures. Our goal is to maximize the unified similarity among vertices in the same cluster. Cluster members must have high similar connectivity, i.e. relate/connect to the same vertices. Also, they must be characterized by close attribute values (low entropy). To the best of our knowledge, we are among the first to optimize similar connectivity. Moreover, we leverage proposed methods to solve a practical issue. That is, how to offer reliable, evidence-based recommendations to European organizations. To do so, we cluster the European research activities network. That is, the network of all organizations that participated to projects funded by the European Union. We propose a clustering-based recommendation method that analyzes the clustering results to provide recommendations. Organization and researchers can use our system to establish new collaborations. To the best of our knowledge, this is the first system to offer such services to the community.