Μέθοδοι συσταδοποίησης για τον εντοπισμό κοινοτήτων σε πολύπλοκα δίκτυα = Clustering methods for community detection in complex networks

Περίληψη

Τα δίκτυα χρησιμοποιούνται ευρέως για να περιγράφουν πολύπλοκες σχέσεις μεταξύ οντοτήτων και η δομή κοινοτήτων είναι ένα σημαντικό χαρακτηριστικό που εμφανίζεται κυρίωςστην μελέτη των πραγματικών δικτύων.
Ο σκοπός της εργασίας είναι η ανάπτυξη μεθοδολογίας για την ανίχνευση κοινοτήτων σε πολύπλοκα δίκτυα με την μέθοδο συσταδοποίησης k-Μeans. Ο αλγόριθμος k-Μeans βασίζεται σε αποστάσεις σημείων ορισμένων σε ένα μετρικό χώρο, όπου αρχικά επιλέγονται τυχαία k από αυτά ως τα κέντρα των συστάδων. Συνεπώς, δημιουργείται το πρόβλημα του εντοπισμού των αρχικών κέντρων (initial seeds) αλλά και της επιλογής του αριθμού αυτών, ώστε η λύση του αλγορίθμου να είναι η βέλτιστη.
Στην παρούσα εργασία απαντώνται τα συγκεκριμένα προβλήματα και προτείνεται ένας τροποποιημένος αλγόριθμος K-Means ο οποίος μετατρέπει αρχικά το δίκτυο σε μετρικό χώρο και στην συνέχεια για την επιλογή των k αρχικών κέντρων κάνει την παραδοχή ότι τα αρχικά κέντρα θα πρέπει να είναι σημαντικοί κόμβοι του δικτύου οι οποίοι θα απέχουν όσο το δυνατόν περισσότερο μεταξύ τους. Ως εκ τούτου, οι κόμβοι ταξινομούνται ως προς δύο μεταβλητές, την Pagerank κεντρικότητα και την απόσταση από τους άλλους κόμβους με μεγαλύτερη Pagerank.
Συνεπώς, η Pagerank ενισχύεται από την από την απόσταση καθότι οι τιμές της ενδέχεται να μην έχουν μεγάλη διακύμανση. Από την ταξινόμηση των κόμβων προκύπτει ένα δισδιάστατο διάγραμμα απόφασης από το οποίο επιλέγεται ο αριθμός k των συστάδων αλλά και τα αρχικά κέντρα που θα χρησιμοποιήσει ο αλγόριθμος για τη συσταδοποίηση. Αφού, επιλεγούν τα κέντρα, ο αλγόριθμος εξάγει τις κοινότητες του δικτύου οι οποίες αξιολογούνται ποσοτικά από τον δείκτη Silhouette.
Για την αξιολόγηση του αλγορίθμου πραγματοποιήθηκε σύγκριση αυτού με έναν κλασικό αλγόριθμο εύρεσης κοινοτήτων σε έξι τεχνητά δίκτυα που η δομή κοινοτήτων ήταν γνωστή εκ των προτέρων και σε ένα πραγματικό δίκτυο.
Τέλος, ο προτεινόμενος αλγόριθμος εφαρμόστηκε σε ένα πραγματικό δίκτυο που δημιουργήθηκε από αναφορές μεταξύ λογαριασμών στο Twitter και εντοπίστηκε σε ποια κοινότητα ανήκουν οι πιο σημαντικοί κόμβοι του.

Community detection is a very important problem in social network analysis. Classical clustering approach, K-means, has been shown to be very efficient to detect communities in networks. However, K-means is quite sensitive to the initial centroids or seeds, especially when it is used to detect communities. Additionally, in K-means, the number of communities should be specified in advance. Till now, it is still an open problem on how to select initial seeds and how to determine the number of communities.
To address this problem in this study, a modification of the classical K-Means algorithm is proposed, which selects the top-K nodes with the highest rank centrality as the initial seeds, and updates these seeds by using an iterative technique like K-means. First, based on the fact that good initial seeds usually have high importance and are dispersedly located in a network, a modified PageRank centrality is proposed to evaluate the importance of each node, and drew a decision graph to depict the importance and the dispersion of nodes. Then, the initial seeds and the number of communities are selected from the decision graph actively and intuitively as the ‘start’ parameter of K-means.
The proposed algorithm is compared with a classical algorithm for community detection on artificial networks whose community structure is already known, as well as a real network. Then, the outputs are evaluated by the Silhouette index and the relevant diagram.
Finally, the K-Means algorithm is applied in a real Twitter network formed by references among Twitter accounts-ids, detecting the important nodes as well as the community that they belong to.