NobleBlocks

Research indexJournal article

Ποιοτικές και ποσοτικές μέθοδοι σύγκρισης μεταξύ αλγορίθμων εύρεσης κοινοτήτων σε δίκτυα:

Μητράκος

Aristotle University of Thessaloniki1 Jan 2014Open access

NobleIDark:/48914/w1/20260524/646BB496DOI10.26262/heal.auth.ir.134781

Free to read at the publisher

You can read the abstract here, or the full text at the publisher.

Read at the publisher

Abstract

Η εύρεση κοινοτήτων είναι ένα ενεργό πεδίο στην ανάλυση δικτύων και έγγυται στην αναγνώριση ομάδων από κόμβους οι οποίοι είναι ποιό πυκνά διασυνδεδεμένοι σε σχέση με το υπόλοιπο δίκτυο. Υπάρχει μία πληθώρα αλγορίθμων εύρεσης κοινοτήτων, καθένας εκ των οποίων ακολουθεί διαφορετική προσέγγιση κατά τη διαμέριση ενός δικτύου σε κοινότητες. Το ερώτημα που τίθεται είναι το ποιός από τους αλγορίθμους αυτούς δίνει την διαμέριση σε κοινότητες η οποία συμφωνεί με την άγνωστη διαμέριση του υπό εξέταση δικτύου. Για την απάντηση σε αυτό το ερώτημα, οι αλγόριθμοι εύρεσης κοινοτήτων θα πρέπει να δοκιμαστούν σε κατασκευασμένα στον υπολογιστή τεχνητά δίκτυα και να εκτιμηθεί η συμφωνία των διαμερίσεών τους. Σε αυτή την εργασία χρησιμοποιήθηκε ο αλγόριθμος LFR για την κατασκευή τεχνητών δικτύων. Έπειτα εφαρμόστηκαν πέντε αλγόριθμοι εύρεσης κοινοτήτων σε αυτά και συγκρίθηκαν οι δομές των κοινοτήτων τους, χρησιμοποιώντας ποσοτικά και ποιοτικά μέτρα. Όσον αφορά την ποσοτική προσέγγιση, αυτά που χρησιμοποιούνται στη βιβλιογραφία είναι το Adjusted Rand Index, η κανονικοποιημένη αμοιβαία πληροφορία, και η διακύμανση της πληροφορίας. Όσον αφορά τα ποιοτικά μέτρα, μελετήθηκαν η κατανομή των μεγεθών των κοινοτήτων, η κατανομή εμβύθυνσης των κόμβων, η κλιμακωτή πυκνότητα κοινότητας, η μέση απόσταση κοινότητας και η κυριαρχία ομφαλού κοινότητας. Το πρωτότυπο μέρος αυτής της εργασίας αποτελείται από δύο μέρη. Πρώτον δημιουργήθηκε κώδικας στην R για τον υπολογισμό και τη γραφική απεικόνιση όλων των ποιοτικών μέτρων που αναφέρθηκαν παραπάνω και δόθηκαν παραδείγματα με τεχνητά δίκτυα που δημιουργήθηκαν με το πρόγραμμα του LFR. Ένα βασικό συμπέρασμα που προέκυψε είναι πως ο αλγόριθμος Infomap βρίσκει τη φυσική διαμέριση του δικτύου του LFR. Δεύτερον χρησιμοποιήθηκε ο κώδικας για να συγκριθούν τα αποτελέσματα πέντε αλγορίθμων εύρεσης κοινοτήτων, στο αντίστοιχο δυαδικό δίκτυο που προέκυψε από το συντελεστή συσχέτισης 212 μετοχών του Χ.Α.Α στο διάστημα 2007-2011. Το δίκτυο αυτό χωρίστηκε σε δύο μέρη. Το πρώτο μέρος αφορά την περίοδο πρίν τις εκλογές (2/9/2009) και το άλλο τη χρονική περίοδο που ακολούθησε. Και στις δύο χρονικές περιόδους, τόσο τα ποιοτικά όσο και τα ποσοτικά μέτρα σύγκρισης ανέδειξαν ότι οι αλγόριθμοι εύρεσης κοινοτήτων που χρησιμοποιήθηκαν, δίνουν αποτελέσματα τα οποία δεν αντιστοιχούν στη φυσική διαμέριση του δικτύου των μετοχών, η οποία αντιστοιχεί στους 17 κλάδους του X.A.A.. Επιπλέον, στα πλήρη και με βάρη δίκτυα των 212 μετοχών, η χρήση των ποσοτικών μέτρων σύγκρισης, έδειξε πλήρη ασυμφωνία μεταξύ των πέντε αλγορίθμων, στους οποίους το πλήθος των κοινοτήτων στηρίχθηκε στη μέγιστη τιμή της δομικότητας.

Discussion

Topics

More

Suggest a correction or report