Αλγόριθμοι εύρεσης κοινοτήτων σε δίκτυα:
Creators: name: Γρηγοριάδης, Ιωάννης Αντωνίου
Publisher: name: Aristotle University of Thessaloniki
Year: 2014
Subjects: Αλγόριθμος
Κοινότητα
Δίκτυο
Algorithm
Community
Network

description: Στην παρούσα διπλωματική εργασία γίνεται ανασκόπηση και εφαρμογή πέντε γνωστών αλγορίθμων που χρησιμοποιούνται στη βιβλιογραφία για τον εντοπισμό των κοινοτήτων που δημιουργούνται μέσα σε ένα δίκτυο. Αν και δεν υπάρχει σαφής ορισμός για την έννοια της κοινότητας έχει παρατηρηθεί ότι η εφαρμογή των προηγουμένων αλγορίθμων δίνει σημαντικές πληροφορίες για τη δομή και την εξέλιξη των δικτύων. Ίσως ο συνηθέστερος τρόπος αξιολόγησης της διαμέρισης ενός δικτύου σε κοινότητες προέρχεται από την εφαρμογή της έννοιας της δομικότητας, η οποία βασίζεται στην εύρεση του πλήθους των ακμών μεταξύ κόμβων που εν δυνάμει ανήκουν στην ίδια κοινότητα συγκριτικά με το πλήθος των ακμών που συνδέουν τους κόμβους αυτούς με τους υπόλοιπους εκτός κοινότητας. Παρουσιάστηκαν οι αλγόριθμοι Edge Betweenness, Fast Greedy, Louvain, Walktrap και Infomap, οι οποίοι αντιπροσωπεύουν και διαφορετικές προσεγγίσεις της έννοιας της κοινότητας, όπως είναι η διαμεσότητα των ακμών μεταξύ κοινοτήτων, η πυκνότητα των κοινοτήτων, η ομοιότητα των κόμβων σε κάθε κοινότητα και η ελαχιστοποίηση της απόστασης στο εσωτερικό των κοινοτήτων αντίστοιχα. Στο πρωτότυπο μέρος έγινε εφαρμογή των προηγουμένων αλγορίθμων σε τεχνητά δίκτυα παραγόμενα από τον αλγόριθμο LFR, καθώς και στο οικονομικό δίκτυο 212 εισηγμένων μετοχών του Χρηματιστηρίου Αξιών Αθηνών (Χ.Α.Α). Στις κατηγορίες των δικτύων που δημιουργήθηκαν με τον αλγόριθμο LFR παρατηρήθηκε ότι ο αλγόριθμος Infomap συμφωνεί με τον προηγούμενο αλγόριθμο, τόσο στην τιμή της δομικότητας, όσο και στο πλήθος των κοινοτήτων. Το οικονομικό δίκτυο χωρίστηκε σε δύο περιόδους με κριτήριο την εξαγγελία των εκλογών στις 2/9/2009. Η εφαρμογή των αλγορίθμων εύρεσης κοινοτήτων με βάση τη δομικότητα ανέδειξε την αδυναμία του συγκεκριμένου τρόπου στα δύο δίκτυα, τα οποία είναι πλήρη και σταθμισμένα. Σε αντίθεση, η συνηθέστερη μέθοδος μελέτης οικονομικών δικτύων με τη διαδικασία του Ελαχίστου Δένδρου Ζεύξης ανέδειξε μεταβολές μεταξύ των δύο περιόδων, τόσο σε επίπεδο συγκεκριμένων μετοχών, όσο και σε επίπεδο κλάδων του Χ.Α.Α.
description: In this thesis, review and implementation of five known algorithms used in the literature to identify communities which are created within a network. Although there is no clear definition of the concept of community has been observed that the application of the above algorithm gives important information about the structure and evolution of the networks. Perhaps the most common way to assess the partitioning of a network into communities derived from the application of the concept of modularity, which is based on finding the number of edges between nodes that potentially belong to the same community compared to the number of edges connecting these nodes with others outside the community. Presented algorithms Edge Betweenness, Fast Greedy, Louvain, Walktrap and Infomap, who represent different approaches to the concept of community, such as link centrality of edges between communties, the density of the communities, the similarity of nodes in each community and the minimizing of distance within the respective communities. The original application was part of the previous algorithms in artificial networks generated by the algorithm LFR, and the financial network 212 listed shares of the Athens Stock Exchange (A.S.E.). In classes of networks created with the algorithm LFR observed that the algorithm Infomap agrees with the previous algorithm, so the price of modularity, and the multitude of communities. The financial network was divided into two periods in terms of the announcement of elections on 2/9/2009. The implementation of algorithms communities by building modularity highlighted the weakness of this mode in the two systems, which are complete and balanced. In contrast, the most common method of studying financial networks with the procedure Minimum Spanning Tree revealed changes between the two periods, both at the level of specific shares and at sectors of the A.S.E.