Πώς ο αλγόριθμος Fast Unfolding εντοπίζει κοινότητες σε μεγάλα δίκτυα

Η ανάλυση κοινωνικών δικτύων περιλαμβάνει τη μελέτη προτύπων σε μεγάλα δίκτυα πραγματικής ζωής που αποτελούνται από εκατομμύρια κόμβους. Εάν έχετε μια βασική γνώση της θεωρίας γραφημάτων, μπορείτε να πραγματοποιήσετε αυτές τις αναλύσεις.

Ο ψηφιακός κόσμος έχει ανοίξει έναν εντελώς διαφορετικό τρόπο δημιουργίας σχέσεων. Επίσης, απελευθερώθηκε ένας ωκεανός δεδομένων που μπορούμε να αναλύσουμε για να κατανοήσουμε καλύτερα την ανθρώπινη συμπεριφορά.

Τα δεδομένα κοινωνικών μέσων αναφέρονται σε όλες τις πρώτες πληροφορίες και τις πληροφορίες που συλλέγονται από τη δραστηριότητα κοινωνικών μέσων ενός ατόμου. Μπορούμε να δημιουργήσουμε δίκτυα από αυτές τις δραστηριότητες κοινωνικών μέσων για να κατανοήσουμε καλύτερα αυτό το άτομο.

Αυτά τα δίκτυα μπορούν να κυμαίνονται ευρέως και μπορεί να περιλαμβάνουν τους φίλους σας στο Facebook, τα προϊόντα που αγοράσατε πρόσφατα στο Amazon, τα tweets που σας άρεσαν ή το retweeted, το αγαπημένο σας φαγητό που παραγγείλατε από το Zomato, την αναζήτηση που κάνατε στο Google ή την εικόνα που σας άρεσε πρόσφατα στο Instagram .

Οι εταιρείες χρησιμοποιούν αυτά τα δίκτυα για να ταξινομήσουν τους χρήστες τους σε διαφορετικές ομάδες. Αυτό τους βοηθά

  • κάνετε έρευνα αγοράς
  • δημιουργήστε δυνητικούς πελάτες
  • να εξυπηρετούν καλύτερα τους πελάτες τους
  • εύρεση και κοινή χρήση φωτογραφιών και βίντεο
  • ανακαλύψτε και συζητήστε το δημοφιλές περιεχόμενο
  • μοιραστείτε πληροφορίες σχετικά με τις υπηρεσίες και τα εστιατόρια
  • συνδεθείτε με άλλους γύρω από κοινό ενδιαφέρον ή χόμπι
  • κι αλλα.

Η λίστα είναι σχεδόν ατελείωτη.

Πριν μπουν στα ζιζάνια, ας αναλύσουμε γρήγορα τη διάκριση μεταξύ διαφορετικών συνιστωσών ενός δικτύου.

Τι είναι το δίκτυο;

Ένα δίκτυο είναι ένας ιστός διασυνδεδεμένων προσωπικών σχέσεων. Για παράδειγμα, διαφορετικά άτομα μπορούν να επικοινωνούν μεταξύ τους σε μια ομάδα κοινωνικών μέσων μέσω ενός δυναμικού ιστού σχέσεων.

Ένα δίκτυο αποτελείται από κόμβους (μεμονωμένους φορείς, άτομα ή πράγματα μέσα στο δίκτυο) και τους δεσμούς , τις άκρες ή τους συνδέσμους (σχέσεις ή αλληλεπιδράσεις) που τα συνδέουν.

Τι είναι μια ομάδα;

Reicher SD στο Ο προσδιορισμός της συλλογικής συμπεριφοράς περιγράφει μια ομάδα ως μια συλλογή ατόμων που θεωρούν τον εαυτό τους ως ομάδα. Τα μέλη της ίδιας ομάδας έχουν ένα σύνολο κοινών πεποιθήσεων και συμπεριφορών.

Τι είναι μια κοινότητα;

Σύμφωνα με τον David W. McMillan ( Sense of Community: A Definition and Theory ) , η κοινότητα μπορεί να οριστεί ως εξής:

«Η αίσθηση της κοινότητας είναι ένα συναίσθημα που έχουν τα μέλη που ανήκουν, ένα συναίσθημα ότι τα μέλη έχουν σημασία μεταξύ τους και στην ομάδα, και μια κοινή πίστη ότι οι ανάγκες των μελών θα ικανοποιηθούν μέσω της δέσμευσής τους να είναι μαζί. "

Οι κοινότητες ή οι υπομονάδες είναι τα δευτερεύοντα δίκτυα ενός δικτύου που είναι πολύ διασυνδεδεμένοι κόμβοι.

Η κοινότητα υποδεικνύει την ύπαρξη εσωτερικών δομών που έχουν ειδικά χαρακτηριστικά ή παίζουν τον ίδιο ρόλο σε ένα δίκτυο.

Πολύ συνδεδεμένες ομάδες ατόμων ή αντικειμένων μέσα σε αυτά τα δίκτυα είναι κοινότητες. Συνήθως βρίσκεται στο σημείο τομής του δικτύου και της ομάδας.

Τώρα που έχουμε μια ξεκάθαρη ιδέα για το τι είναι ένα δίκτυο, μια ομάδα και μια κοινότητα, ας δούμε πιο βαθιά πώς αυτά τα δίκτυα χωρίζονται σε μικρές κοινότητες.

Θα εξετάσουμε τον δημοφιλή αλγόριθμο Fast Unfolding . Ο Vincent C. Blondel και οι συν-συγγραφείς της εργασίας συνέκριναν αυτόν τον αλγόριθμο με άλλους αλγόριθμους ανίχνευσης κοινότητας. Ανακάλυψαν ότι αυτός ο αλγόριθμος ξεπερνά κάθε άλλο αλγόριθμο σε μεγάλα δίκτυα.

Τι είναι ο αλγόριθμος Fast Unfolding;

Ο αλγόριθμος Fast Unfolding χρησιμοποιήθηκε για τον εντοπισμό γλωσσικών κοινοτήτων σε ένα βελγικό δίκτυο κινητών τηλεφώνων με 2,6 εκατομμύρια πελάτες.

Χρησιμοποιήθηκε επίσης για την ανάλυση ενός γραφήματος ιστού 118 εκατομμυρίων κόμβων και περισσότερων από ενός δισεκατομμυρίου συνδέσμων.

Ο εντοπισμός κοινοτήτων σε ένα τόσο μεγάλο δίκτυο χρειάστηκε μόνο 152 λεπτά. Επομένως, αυτός ο αλγόριθμος είναι γρήγορος και αποτελεσματικός.

Πώς λειτουργεί ο αλγόριθμος

Ο αλγόριθμος λειτουργεί σε δύο φάσεις:

Φάση 1

  1. Εκχωρήστε μια διαφορετική κοινότητα σε κάθε κόμβο σε ένα δίκτυο.
  2. Στη συνέχεια, για κάθε κόμβο, εξετάζω τον κόμβο j και αξιολογώ το κέρδος σε modularity αφαιρώντας τον κόμβο i από την κοινότητά του και τοποθετώντας τον στην κοινότητα του j.
  3. Ο κόμβος i τοποθετείται στην κοινότητα για την οποία αποκτά μέγιστη αρθρωτότητα, αλλά το κέρδος πρέπει να είναι θετικό. Αν το κέρδος είναι αρνητικό, τότε ο κόμβος i παραμένει στην ίδια κοινότητα.

Φάση 2

  1. Η δεύτερη φάση του αλγορίθμου συνίσταται στη δημιουργία ενός νέου δικτύου του οποίου οι κόμβοι είναι τώρα οι κοινότητες που βρέθηκαν κατά την πρώτη φάση. Έτσι, δημιουργούμε κόμβους συγχωνεύοντας όλους τους κόμβους στην κοινότητα ως έναν μόνο κόμβο.
  2. Τα βάρη του συνδέσμου μεταξύ των κόμβων δίδονται από το άθροισμα των βαρών των συνδέσεων μεταξύ κόμβων στις αντίστοιχες δύο κοινότητες.
  3. Η σύνδεση μεταξύ κόμβων της ίδιας κοινότητας οδηγεί σε αυτο-βρόχους για την κοινότητα στο νέο δίκτυο.
  4. Επαναλάβετε τη Φάση 1 έως ότου δεν μπορεί να επιτευχθεί περαιτέρω βελτίωση.

Πώς υπολογίζεται το κέρδος στη λειτουργικότητα

Η ποιότητα του διαμερίσματος ( Q ) μετράται από το Modularity (γνωστός και ως modularity του διαμερίσματος). Είναι μια κλιμακούμενη τιμή μεταξύ -1 και 1, και μετρά την πυκνότητα των συνδέσμων εντός των κοινοτήτων σε σύγκριση με τους δεσμούς μεταξύ των κοινοτήτων.

Το κέρδος στην αρθρωτότητα (ΔQ) που λαμβάνεται μετακινώντας έναν απομονωμένο κόμβο i σε μια κοινότητα Γ μπορεί εύκολα να υπολογιστεί από:

Σin είναι το άθροισμα των βαρών των συνδέσμων μέσα στο C.

Σtot είναι το άθροισμα των βαρών των συνδέσμων που συνδέονται με κόμβους στο C.

ki είναι το άθροισμα των βαρών των συνδέσμων από το i στον κόμβο του C.

m είναι το άθροισμα των βαρών όλων των συνδέσμων στο δίκτυο.

Το κέρδος στη λειτουργικότητα αξιολογείται αφαιρώντας το i από την κοινότητά του και μετά το μετακινεί σε μια γειτονική κοινότητα. Εάν το κέρδος είναι θετικό, τότε αυτός ο κόμβος τοποθετείται στη γειτονική κοινότητα.

Ξηρά εκτέλεση του αλγορίθμου

Στο δίκτυο στα αριστερά (15 κόμβοι), εκχωρούμε πρώτα μια μοναδική κοινότητα σε κάθε κόμβο. Στη συνέχεια, αξιολογούμε το Modularity κάθε κόμβου και εκχωρούμε εκ νέου την κοινότητα με βάση το κέρδος. Αυτό ονομάζεται Modularity Optimization .

Στην επόμενη φάση, δημιουργούμε κόμβους συγχωνεύοντας όλους τους κόμβους σε αυτήν την κοινότητα σε έναν μόνο κόμβο. Στην πράσινη κοινότητα, έχουμε συνολικά 5 κόμβους και υπάρχει συνολικά 7 άκρα μεταξύ τους.

Επομένως, μετά από τη Συγκέντρωση κοινότητας , το βάρος του αυτο-βρόχου του πράσινου κόμβου θα είναι 14 (7 * 2 καθώς είναι ένας αμφίδρομος σύνδεσμος). Ομοίως, το βάρος του αυτο-βρόχου του κόκκινου κόμβου θα είναι 16, ο μπλε κόμβος θα είναι 4 και ο ανοικτός μπλε κόμβος θα είναι 2.

Το βάρος της άκρης μεταξύ πράσινου και μπλε κόμβου θα είναι 4, καθώς υπάρχουν συνολικά 4 άκρα μεταξύ της πράσινης και της μπλε κοινότητας μετά τη Βελτιστοποίηση Modularity.

Στο επόμενο βήμα, επανεξετάζουμε το Modularity για τους νέους κόμβους και κάνουμε την ίδια διαδικασία ξανά.

Τέλος, έχουμε δύο κοινότητες, το πράσινο και το γαλάζιο. Η Πράσινη κοινότητα έχει 26 αυτο-βρόχους καθώς υπάρχουν συνολικά 13 άκρα μεταξύ των κόμβων της πράσινης κοινότητας. Και έχουμε 12 άκρα στην ανοιχτή μπλε κοινότητα, συνολικά 24 αυτο-βρόχους.

Πλεονεκτήματα του αλγορίθμου

  1. Τα βήματά του είναι διαισθητικά και εύκολα στην εφαρμογή και το αποτέλεσμα είναι χωρίς επίβλεψη.
  2. Ο αλγόριθμος είναι εξαιρετικά γρήγορος. Οι προσομοιώσεις υπολογιστών σε πολύ τεράστια αρθρωτά δίκτυα υποδηλώνουν ότι η πολυπλοκότητά του είναι γραμμική στα τυπικά και αραιά δεδομένα. Αυτό μπορεί να συμβαίνει επειδή το κέρδος στην αρθρωτότητα είναι εύκολο να υπολογιστεί και ο αριθμός των κοινοτήτων μειώνεται δραστικά μετά από λίγα περάσματα.

Περιορισμοί του αλγορίθμου

  1. Η βελτιστοποίηση modularity αποτυγχάνει να εντοπίσει κοινότητες μικρότερες από μια συγκεκριμένη κλίμακα. Έτσι, προκαλεί ένα όριο επίλυσης στην κοινότητα που υπολογίζεται χρησιμοποιώντας μια καθαρή προσέγγιση βελτιστοποίησης αρθρωτότητας.
  2. Για μικρά δίκτυα, η πιθανότητα συγχώνευσης δύο ξεχωριστών κοινοτήτων μετακινώντας κάθε κόμβο είναι πολύ χαμηλή.

συμπέρασμα

Αν έχετε μείνει εκεί πολύ… ευχαριστώ! Ελπίζω να υπάρχουν πολύτιμες πληροφορίες για εσάς.

Τώρα ξέρετε πώς λειτουργεί ο αλγόριθμος Fast Unfolding και ότι είναι εξαιρετικά αποτελεσματικό να εντοπίζετε κοινότητες σε πολύ μεγάλα δίκτυα.

Ο τρόπος υπολογισμού του Gain in Modularity κάνει τον αλγόριθμο να ξεπερνά κάθε άλλο αλγόριθμο εκεί έξω. Αφήστε μου ένα σημείωμα εάν το βρείτε χρήσιμο ή έχετε περαιτέρω ερωτήσεις.

Ευχαριστώ για την ανάγνωση!