Comparative study of community detection algorithms in social networks.

Abstract

Τα τελευταία χρόνια γίναμε μάρτυρες μίας άνευ προηγουμένου επανάστασης στα κοινωνικά μέσα ως συνέπειας της εμφάνισης των πρώτων μεγάλων κοινωνικών δικτύων, τα οποία ενθάρρυναν για πρώτη φορά χρήστες να μοιραστούν ιδέες και σκέψεις με μια νεοσύστατη διαδικτυακή κοινότητα. Η υποκείμενη διάρθρωση των δικτύων αυτών απέκτησε τέτοια επιστημονική αλλά και εμπορική αξία ώστε να προσελκύσει εκ νέου το ενδιαφέρον της ακαδημαϊκής κοινότητας στο πρόβλημα της αναγνώριρης κοινοτήτων σε κοινωνικά δίκτυα οθώντας τα όρια των σημερινών μεθόδων συσταδοποίησης. Αναγνωρίζοντας το υφιστάμενο βιβλιογραφικό κενό πάνω σε συγκριτικές μελέτες αλγορίθμων αναγνώρισης κοινοτήτων καταλήξαμε στην ανάπτυξη ενός μεθοδολογικού πακέτου για την σύγκριση πέντε διάσημων αλγορίθμων. Χρησιμοποιώντας ένα ευρύ φάσμα συνθετικών δικτύων καταφέραμε να καταδείξουμε την ανάγκη για ανάπτυξη τεχνικών που θα μπορούσαν να λειτουργήσουν αποδοτικά πάνω σε δίκτυα που συνεχώς μεταβάλλουν μία σειρά παραμέτρων. Εκμεταλλευόμενοι τα πλεονεκτήματα αλλά και τις αδυναμίες αυτών των μεθόδων, όπως αυτές αναδείχτηκαν στο πρώτο σκέλος προχωρήσαμε με μία εμπειρική μελέτη του κοινωνικού δικτύου MySpace. Ο σκοπός της ήταν τριπλός και στόχευε στην σύλληψη της εξέλιξης του πληθυσμού του δικτύου, στην εξέταση της διαδικτυακής δραστηρίοτητας των χρηστών καθώς και στην αποτύπωση των ειδικών χαρακτηριστικών που διέπουν τις κοινότητες του συγκεκριμένου δικτύου χρησιμοποιώντας μόνο τοπικές αλληλεπιδράσεις μεταξύ των κόμβων. Στην κατεύθυνση αυτή, ένα εκατομμύριο τυχαία επιλεγμένα προφίλ χρηστών συλλέχθησαν εντός ενός χρονικού παραθύρου ενός μήνα και αποθηκεύτηκαν σε μία τοπική βάση δεδομένων αναμένοντας περεταίρω επεξεργασία. Μαζί με κάθε προφίλ ανακτήθηκαν από το διαδίκτυο και μία σειρά από χαρακτηριστικά όπως η κατάσταση του χρήστη, οι ημερομηνίες εγγραφής και τελευταίας επίσκεψης, ο αριθμός των φίλων, ο αριθμός εμφανίσεων προφίλ κ.α. Στη συνέχεια τα προφίλ σε συνδυασμό με τις ιδιότητες που τα συνοδεύουν αναλύθηκαν σε μία προσπάθεια να εξάγουμε χρήσιμα συμπεράσματα για την εξέλιξη του πληθυσμού του δικτύου αλλά και της δραστηριότητας των χρηστών. Ακολούθως προχωρήσαμε με την αναγνώριση ενός σεβαστού πλήθους κοινοτήτων στοχεύοντας στην ανάδειξη της διάρθρωσης του υποκείμενου κοινωνικού δικτύου. Χρησιμοποιώντας τον αλγόριθμο του Fortunato καταφέραμε να αναγνωρίσουμε 171 κοινότητες ενώ εφαρμόζοντας την μέθοδο του Clique Percolation προχωρήσαμε στην αποκάλυψη του εντυπωσιακού αριθμού των 201 κοινοτήτων. Σε συνδυασμό με την ανάλυση των δεδομένων που συλλέξαμε προηγουμένως από το δίκτυο μπορέσαμε να χαρακτηρίσουμε τις κοινότητες που σχηματίζουν οι χρήστες ως προς το μέγεθος, την πυκνότητα καθώς και την ομοιογένεια τους. Επ' αυτού, για πρώτη φορά συναντάμε ενδείξεις σημαντικής ομοιογένειας πάνω στην ημερομηνία τελευταίας επίσκεψης στο δίκτυο ενώ αντίστοιχα χαμηλή απόκλιση τιμών εμφανίζεται και για το πλήθος των φίλων μεταξύ διαφορετικών χρηστών ίδιων κοινοτήτων. Εν τέλει, υπάρχουν ισχυρά στοιχεία που δείχνουν ότι η συμμετοχή χρηστών σε κοινότητες λειτουργεί αποτρεπτικά στην εγκατάλειψη του δικτύου, υπόθεση που ενισχύεται από τη διαπίστωση ότι οι χρήστες που φέρονται να έχουν εγκαταλείψει το MySpace μετά από σύντομη παραμονή στο δίκτυο, επονομαζόμενοι και “Τουρίστες” χαρακτηρίζονται από ιδιαίτερα χαμηλή συνδεσιμότητα, δηλαδή πολύ μικρό αριθμό φίλων και ως εκ τούτου δεν ευνοείται η συμμετοχή τους σε κοινότητες.

In recent years, we all became witnesses of an unprecedented revolution in social media as a consequence of the appearance of the first large social networks, which encouraging for the first time individuals to share their thoughts and ideas with the newly formed web society. The underlying community structures of these networks created scientific and business value in such an extent in which to re attract the interest of the academic community on clustering methods pushing the boundaries of community detection methods. Motivated by the recognized void in comparative studies of community detection methods we ended up dealing with an experimental validation and comparison of five state of the art algorithms on a wide range of benchmark graphs demonstrating the necessity to devise local and efficient community detection techniques that perform well under a variety of changing conditions. Presuming on the revealed strengths and weaknesses of these methods we proceeded with an empirical study of the MySpace Online Social Network (OSN). Its purpose was threefold aiming to capture the evolution of user population, to examine user activity, and finally to characterize community formation surrounding seed nodes and utilizing only local interactions between nodes. One million user profiles were randomly collected in a month’s period and stored in a local database for further processing. For each profile certain attributes were fetched: profile status (public, private, invalid), member since and last login dates, number of friends, number of views, etc. The profiles and their attributes were analyzed in order to reveal the evolution in user population and the activity of the participating members. Significant conclusions were drawn for the synthesis of the population based on profile status, the number of friends, and the duration MySpace members stay active. Subsequently, a large number of communities were identified aiming to reveal the structure of the underlying social network graph. The collected data were further analyzed in order to characterize community size and density but also to retrieve correlations in the activity among members of the same community. A total of 171 communities were detected with Fortunato’s algorithm, while using Clique Percolation this number was 201. Results demonstrate that MySpace members tend to form dense communities. For the first time, strong correlation in the last login date (the main attribute that shows user activity) for members of the same community was documented. It was also shown that members participating in the same community have similar values for other attributes like for example number of friends. Lastly, there is strong evidence that participation of users in communities inhibits them from abandoning MySpace. As a last observation, members that abandoned MySpace shortly after their account creation (the so-called Tourists), have very low connectivity and thus they do not participate in communities.