Entropy methods for community detection in social networks (directed and undirected)
Creators: name: Κοτρώτσιου, Μαρία Δημητρίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2023
Subjects: Κοινωνικά δίκτυα
Εντροπία
Αλγόριθμοι ανίχνευσης κοινοτήτων
Social networks
Entropy
Community detection algorithms

description: In the first chapter of this thesis, are presented some basic definitions of Network Theory, is made a brief reference to the types of networks that exist and a more detailed one to social networks and their characteristics. It is also defined the concept of community, which is the core of our work, Shannon’s entropy, as well as the entropy of a node and the entropy of entire network. The second chapter analyzes some community detection methods without the use of entropy, such as the Edge Betweenness Algorithm, the Cluster Overlap Newman Girvan Algorithm (CONGA), the Walktrap Algorithm, the Infomap Algorithm and the Clique Percolation Method (CPM). Algorithms based on modularity and its optimization are also presented, such as Louvain Algorithm, Leading Eigenvector Algorithm and Spinglass Algorithm. In the third chapter, is presented a community detection method based on entropy centrality. In order to be more understandable the connection between entropy and centrality, is given an example of a network between some friends who transfer an object to each other. The transport of this object is described as Markovian transport process via a random walk. In the fourth chapter, the algorithms mentioned above are applied to four real social networks using the R language and the iGraph library. Three of them are undirected and one is directed. More specifically, is made an attempt to detect communities in Zachary’s karate club network, Dolphin’s network, Les Miserables network and Football network, in order to check whether the communities that appear correspond to reality or not. Finally, the fifth chapter presents some conclusions about the community structure identified in the four networks we studied, as well as a comparison of the algorithms used to detect clusters, in order to understand who is closer to the certified results and who deviates enough or is just unsuitable.
description: Στο πρώτο κεφάλαιο της εργασίας αυτής παρουσιάζονται κάποιοι βασικοί ορισμοί της Θεωρίας Δικτύων, γίνεται μια σύντομη αναφορά στα είδη δικτύων που υπάρχουν και μια πιο λεπτομερής στα κοινωνικά δίκτυα και στα χαρακτηριστικά αυτών. Ορίζεται ακόμη η έννοια της κοινότητας, η οποία είναι ο πυρήνας της εργασίας μας, της εντροπίας του Shannon, καθώς και της εντροπίας ενός κόμβου αλλά και ολόκληρου του δικτύου. Στο δεύτερο κεφάλαιο αναλύονται ορισμένες μέθοδοι ανίχνευσης κοινοτήτων χωρίς την χρήση εντροπίας, όπως ο αλγόριθμος Edge Betweenness, ο Cluster Overlap Newman Girvan Algorithm (CONGA), o Walktrap, o Infomap και η μέθοδος Clique Percolation (CPM). Παρουσιάζονται επίσης και αλγόριθμοι που βασίζονται στη modularity και στην βελτιστοποίησή της, όπως ο αλγόριθμος Louvain, o Leading Eigenvector και ο Spinglass. Στο τρίτο κεφάλαιο παρουσιάζεται μια μέθοδος ανίχνευσης κοινοτήτων η οποία βασίζεται στην κεντρικότητα εντροπίας. Προκειμένου να γίνει πιο κατανοητή η σύνδεση μεταξύ εντροπίας και κεντρικότητας δίνεται ως παράδειγμα ένα δίκτυο μεταξύ φίλων που μεταφέρουν ένα αντικείμενο μεταξύ τους. Η μεταφορά αυτού του αντικειμένου περιγράφεται ως μια Μαρκοβιανή διαδικασία μεταφοράς μέσω ενός τυχαίου περιπάτου. Στο τέταρτο κεφάλαιο γίνεται η εφαρμογή των αλγορίθμων που αναφέρθηκαν παραπάνω σε τέσσερα πραγματικά κοινωνικά δίκτυα με χρήση της γλώσσας R και τη βοήθεια της βιβλιοθήκης iGraph, εκ των οποίων τα τρία είναι μη – κατευθυνόμενα και το ένα κατευθυνόμενο. Πιο συγκεκριμένα γίνεται μια προσπάθεια ανίχνευσης κοινοτήτων στα δίκτυα Zachary’s karate club network, the Dolphin network, Les Miserables network και στο Football network, προκειμένου να ελέγξουμε αν οι κοινότητες που εμφανίζονται ανταποκρίνονται ή όχι στην πραγματικότητα. Τέλος, στο πέμπτο κεφάλαιο παρουσιάζονται κάποια συμπεράσματα σχετικά με την δομή κοινοτήτων που εντοπίστηκε στα τέσσερα δίκτυα που μελετήσαμε, καθώς και μια σύγκριση των αλγορίθμων που χρησιμοποιήθηκαν για την ανίχνευση συστάδων, ώστε να καταλάβουμε ποιος είναι πιο κοντά στα πιστοποιημένα αποτελέσματα και ποιος αποκλίνει αρκετά ή κρίνεται ακατάλληλος.