Ποιοτικές και ποσοτικές μέθοδοι σύγκρισης μεταξύ αλγορίθμων εύρεσης κοινοτήτων σε δίκτυα:
Creators: name: Μητράκος, Δημήτριος Γεωργίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2014
Subjects: Εύρεση κοινοτήτων
Ποιοτικά και ποσοτικά μέτρα
Σύγκριση αλγορίθμων
Community detection
Qualitative and quantitative measures
Comparing algorithms

description: Η εύρεση κοινοτήτων είναι ένα ενεργό πεδίο στην ανάλυση δικτύων και έγγυται στην αναγνώριση ομάδων από κόμβους οι οποίοι είναι ποιό πυκνά διασυνδεδεμένοι σε σχέση με το υπόλοιπο δίκτυο. Υπάρχει μία πληθώρα αλγορίθμων εύρεσης κοινοτήτων, καθένας εκ των οποίων ακολουθεί διαφορετική προσέγγιση κατά τη διαμέριση ενός δικτύου σε κοινότητες. Το ερώτημα που τίθεται είναι το ποιός από τους αλγορίθμους αυτούς δίνει την διαμέριση σε κοινότητες η οποία συμφωνεί με την άγνωστη διαμέριση του υπό εξέταση δικτύου. Για την απάντηση σε αυτό το ερώτημα, οι αλγόριθμοι εύρεσης κοινοτήτων θα πρέπει να δοκιμαστούν σε κατασκευασμένα στον υπολογιστή τεχνητά δίκτυα και να εκτιμηθεί η συμφωνία των διαμερίσεών τους. Σε αυτή την εργασία χρησιμοποιήθηκε ο αλγόριθμος LFR για την κατασκευή τεχνητών δικτύων. Έπειτα εφαρμόστηκαν πέντε αλγόριθμοι εύρεσης κοινοτήτων σε αυτά και συγκρίθηκαν οι δομές των κοινοτήτων τους, χρησιμοποιώντας ποσοτικά και ποιοτικά μέτρα. Όσον αφορά την ποσοτική προσέγγιση, αυτά που χρησιμοποιούνται στη βιβλιογραφία είναι το Adjusted Rand Index, η κανονικοποιημένη αμοιβαία πληροφορία, και η διακύμανση της πληροφορίας. Όσον αφορά τα ποιοτικά μέτρα, μελετήθηκαν η κατανομή των μεγεθών των κοινοτήτων, η κατανομή εμβύθυνσης των κόμβων, η κλιμακωτή πυκνότητα κοινότητας, η μέση απόσταση κοινότητας και η κυριαρχία ομφαλού κοινότητας. Το πρωτότυπο μέρος αυτής της εργασίας αποτελείται από δύο μέρη. Πρώτον δημιουργήθηκε κώδικας στην R για τον υπολογισμό και τη γραφική απεικόνιση όλων των ποιοτικών μέτρων που αναφέρθηκαν παραπάνω και δόθηκαν παραδείγματα με τεχνητά δίκτυα που δημιουργήθηκαν με το πρόγραμμα του LFR. Ένα βασικό συμπέρασμα που προέκυψε είναι πως ο αλγόριθμος Infomap βρίσκει τη φυσική διαμέριση του δικτύου του LFR. Δεύτερον χρησιμοποιήθηκε ο κώδικας για να συγκριθούν τα αποτελέσματα πέντε αλγορίθμων εύρεσης κοινοτήτων, στο αντίστοιχο δυαδικό δίκτυο που προέκυψε από το συντελεστή συσχέτισης 212 μετοχών του Χ.Α.Α στο διάστημα 2007-2011. Το δίκτυο αυτό χωρίστηκε σε δύο μέρη. Το πρώτο μέρος αφορά την περίοδο πρίν τις εκλογές (2/9/2009) και το άλλο τη χρονική περίοδο που ακολούθησε. Και στις δύο χρονικές περιόδους, τόσο τα ποιοτικά όσο και τα ποσοτικά μέτρα σύγκρισης ανέδειξαν ότι οι αλγόριθμοι εύρεσης κοινοτήτων που χρησιμοποιήθηκαν, δίνουν αποτελέσματα τα οποία δεν αντιστοιχούν στη φυσική διαμέριση του δικτύου των μετοχών, η οποία αντιστοιχεί στους 17 κλάδους του X.A.A.. Επιπλέον, στα πλήρη και με βάρη δίκτυα των 212 μετοχών, η χρήση των ποσοτικών μέτρων σύγκρισης, έδειξε πλήρη ασυμφωνία μεταξύ των πέντε αλγορίθμων, στους οποίους το πλήθος των κοινοτήτων στηρίχθηκε στη μέγιστη τιμή της δομικότητας.
description: Community detection is a very active field in complex networks analysis, consisting in identifying groups of nodes more densely interconnected relatively to the rest of the network. There exists a plethora of community detection algorithms, each of which takes a different approach on partitioning a network into communities. The main question that arises is which one of them produces the community partition that best matches the unknown natural community partition of the network. To answer that question the community detection algorithms have to be tested in computer generated artificial networks, for whom the community structure is known a priori and to assess the agreement of their partitions. In this study we use the LFR model to produce artificial networks. Then we apply five selected community detection algorithms on them and we compare their community structures using both qualitative and quantitative measures. The most used in the literature concerning quantitative approach are Adjusted Rand Index, Normalized Mutual Information and Variation of Information. Concerning qualitative measures we study Community Size Distribution, Embeddedness, Community Scaled Density, Community Average Distance and Hub Dominance. The innovation of this master thesis consists of two results. Firstly we produce R code to calculate and plot all of the quantitative measures mentioned above by giving examples on artificial networks generated with the LFR code. A key conclusion drawn is that Infomap finds the physical partitioning of the network of LFR. Secondly we use the produced R code to compare the results of five community detection algorithms on the binary transformed network produced from the correlation between 212 daily stock returns of Athens Stocks Exchange from 2007 to 2011. The network was divided into two parts. The first part deals with the period before the elections (2/9/2009) and the second to the period that followed. In both periods, both qualitative and quantitative measures, show that the community detection algorithms used, give results which do not correspond to the natural partition of the stock exchange network, which corresponds to the 17 sectors of each stock. Moreover, in the full weighted networks of the 212 stocks, the use of the quantitative measures showed complete mismatch between the results of the five algorithms, on which the number of communities is based on the maximum value of modularity of the network.