Το Facebook μπορεί να μας κατασκοπεύει, αλλά δημιουργεί όμορφα γραφήματα

Γραφήματα, θεωρία γραφημάτων, Euler και Dijkstra

Καθώς οι εργασίες καθίστανται πιο καθορισμένες, οι δομές των δεδομένων που χρησιμοποιούνται για τον καθορισμό τους αυξάνονται σε πολυπλοκότητα. Ακόμη και τα μικρότερα έργα μπορούν να αναλυθούν σε ομάδες μικρότερων εργασιών, που αντιπροσωπεύουν ακόμη μικρότερες επιμέρους εργασίες. Τα γραφήματα είναι μια δομή δεδομένων που μας βοηθά να αντιμετωπίσουμε μεγάλες ποσότητες πολύπλοκων αλληλεπιδράσεων, με στατικό, λογικό τρόπο. Χρησιμοποιούνται ευρέως σε όλα τα είδη προβλημάτων βελτιστοποίησης, συμπεριλαμβανομένης της κυκλοφορίας και της δρομολόγησης δικτύου, χαρτών, θεωρίας παιγνίων και λήψης αποφάσεων. Είτε το γνωρίζουμε είτε όχι, οι περισσότεροι από εμάς είχαμε εμπειρίες με γραφήματα όταν αλληλεπιδρούμε με τα μέσα κοινωνικής δικτύωσης. Αποδεικνύεται ότι τα γραφήματα είναι η τέλεια δομή δεδομένων για την περιγραφή, την ανάλυση και την παρακολούθηση πολλών αντικειμένων, μαζί με τις σχέσεις τους μεταξύ τους. Ωστόσο, παρά την πανταχού παρουσία των γραφημάτων, μπορεί να είναι αρκετά τρομακτικά στην κατανόηση. Προς το συμφέρον της περιέργειας και της επιστήμης, σήμερα είναι η μέρα που θα αντιμετωπίσουμε τα γραφήματα και θα παλέψουμε με αυτό το άβολο συναίσθημα που νιώθουμε όταν δεν έχουμε την παραμικρή ιδέα πώς λειτουργεί κάτι μπροστά μας.

Για να εξερευνήσουμε γραφήματα, θα ρίξουμε μια ματιά στο τι κάνει ένα γράφημα, θα καλύψουμε μερικά από τα μαθηματικά πίσω από αυτό, θα δημιουργήσουμε ένα απλοποιημένο γράφημα και θα αρχίσουμε να εξερευνούμε ένα πιο σύνθετο κοινωνικό γράφημα από τα δεδομένα του Facebook. Οι κόμβοι ή οι κορυφές ενός γραφήματος είναι σαν τις γωνίες ενός σχήματος, ενώ οι άκρες είναι σαν τις πλευρές. Οι άκρες συνδέονται με γωνίες προς όλες τις κατευθύνσεις, δίνοντας στα γραφήματα τη δυνατότητα να παίρνουν οποιοδήποτε σχήμα. Οποιοδήποτε γράφημα μπορεί να απεικονιστεί με G = (V, E) , όπου E είναι το σύνολο των ακμών και V είναι το σύνολο των κορυφών. Τα μεγαλύτερα γραφήματα έχουν απλώς περισσότερους κόμβους και περισσότερες ακμές σημαίνει περισσότερη συνδεσιμότητα.

Οι υπολογιστές βρίσκουν πιο βολικό να απεικονίζουν γραφήματα ως μήτρα γειτνίασης, αλλιώς γνωστή ως μήτρα σύνδεσης. Ένας πίνακας γειτνίασης αποτελείται από έναν τετράγωνο πίνακα που αποτελείται μόνο από 0 και 1 (δυαδικά). Σε αυτόν τον δυαδικό πίνακα, το 1 αντιπροσωπεύει ένα σημείο στο γράφημα όπου μια άκρη πηγαίνει από κορυφή σε κορυφή. Εάν δεν υπάρχει ακμή που να τρέχει μεταξύ, ας πούμε της κορυφής i και της κορυφής j, θα υπάρχει ένα 0 στον πίνακα. Ένα καλό κομμάτι της θεωρίας γραφημάτων μπορεί να αποδοθεί στον Ελβετό μαθηματικό του 18ου αιώνα Leonhard Euler. Ο Euler είναι γνωστός ως ένας από τους πιο σημαντικούς και παραγωγικούς μαθηματικούς όλων των εποχών, με συνεισφορές στους τομείς της φυσικής, της θεωρίας αριθμών και της θεωρίας γραφημάτων. Το έργο του για το διάσημο Επτά Γέφυρες του Königsberg Το πρόβλημα, όπου κάποιος έπρεπε να αποφασίσει εάν θα μπορούσαν να διασχίσουν κάθε γέφυρα μόνο μία φορά σε ένα ταξίδι μετ‘ επιστροφής πίσω στο σημείο εκκίνησης, οδήγησε σε μια σειρά αποκαλύψεων σχετικά με τη θεωρία γραφημάτων. Μεταξύ αυτών των αποκαλύψεων ήταν η ανακάλυψη της φόρμουλας V-E+F=2 που έχει να κάνει με τον αριθμό των κορυφών, των ακμών και των όψεων ενός κυρτού πολυέδρου.

Σταθμισμένα, κατευθυνόμενα και μη κατευθυνόμενα γραφήματα

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

ΕΝΑ κατευθυνόμενο γράφημα είναι ένα σύνολο αντικειμένων όπου όλες οι ακμές έχουν μια κατεύθυνση που σχετίζεται με αυτά. Θα μπορούσατε να σκεφτείτε τα περισσότερα κοινωνικά δίκτυα ως κατευθυνόμενα γραφήματα, επειδή η κατεύθυνση έχει σημασία όταν λαμβάνετε υπόψη τους όρους followers και follow. Η Kim Kardashian σίγουρα δεν ακολουθεί όλους τους followers της, αλλά τα 140 και πλέον εκατομμύρια άκρα της κατευθύνονται προς τον κόμβο της με τρόπο που την κάνει αρκετά επιδραστική. Θα ρίξουμε μια ματιά για να εξερευνήσουμε αυτό το είδος επιρροής δικτύου λίγο αργότερα, όταν δημιουργήσουμε ένα γράφημα.

Dijkstra

Ο Edsger Dijkstra ήταν Ολλανδός επιστήμονας συστημάτων, ο οποίος δημοσίευσε Ο πρώτος αλγόριθμος της συντομότερης διαδρομής της Dijkstra (SPF) το 1956. Ο αλγόριθμος βρίσκει τις συντομότερες διαδρομές από τον κόμβο πηγής (προέλευσης) προς όλους τους άλλους κόμβους. Απλοποιημένος, ο αλγόριθμος λειτουργεί σύμφωνα με αυτούς τους κανόνες:

Για κάθε νέο κόμβο που επισκέπτεστε, επιλέξτε τον κόμβο με τη μικρότερη γνωστή απόσταση/κόστος για επίσκεψη πρώτος.
Μόλις φτάσετε στον νεότερο κόμβο, ελέγξτε κάθε έναν από τους γειτονικούς του κόμβους.
Για κάθε γειτονικό κόμβο, υπολογίστε το κόστος των γειτονικών κόμβων αθροίζοντας το κόστος όλων των ακμών, από την αρχική κορυφή, που οδηγούν σε αυτόν τον κόμβο.
Εάν το κόστος σε αυτόν τον κόμβο είναι μικρότερο από μια γνωστή (επισημασμένη) απόσταση, αυτή είναι η νέα μικρότερη απόσταση σε αυτήν την κορυφή.
Αυτός ο βρόχος συνεχίζει να τρέχει σε όλους τους κόμβους μέχρι να ολοκληρωθεί η εκτέλεση του αλγόριθμου μας.

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

Χάρτης του Μανχάταν

Πριν λίγο καιρό, επισκέφτηκα κάποια οικογένεια στο Μανχάταν. Τις περισσότερες μέρες που ήμουν εκεί, τελείωσα το ταξίδι μου στη γραμμή Lexington Avenue στο σταθμό 125th St. Καθώς περπατούσα (μέσα από το κρύο) από την πηγή μου για να περιμένω το τρένο μου, διέσχισα μια σειρά από ξεχασιάρικες στροφές αριστερά και δεξιά, καλύπτοντας ένα οδοντωτό μονοπάτι, όπου η συνολική απόσταση ήταν η απόλυτη απόσταση μεταξύ των στροφών ή η απόσταση του Μανχάταν. Μόλις ήμουν υπόγεια στο μετρό, το τρένο πήρε κυρίως μια ευθεία γραμμή, και αυτή είναι η Ευκλείδεια απόσταση. γνωστή και ως η απόσταση που πετάει ένα πουλί. Ένα Σαββατοκύριακο αποφασίσαμε να επισκεφτούμε μερικά τουριστικά σημεία και καθώς αποφασίζαμε ποια μέρη να επισκεφτούμε στον χάρτη και με ποια σειρά, φαινόταν κάπως έτσι:

Με αυτό το γράφημα, οι ακμές μεταξύ των σημείων αντιπροσωπεύουν αποστάσεις. Αν θέλαμε να ελαχιστοποιήσουμε το κόστος από το Chelsea Market © στο Χρηματιστήριο της Νέας Υόρκης (S), θα μπορούσαμε να βρούμε τη συντομότερη διαδρομή προς το S. Στην πραγματικότητα, θα θέλαμε να επισκεφτούμε όλες τις τοποθεσίες, αλλά σε αυτό το παράδειγμα απλά πηγαίνουμε για την απόλυτη συντομότερη δυνατή διαδρομή. Φυσικά, αυτή είναι μια άλλη καλή ερώτηση: ποια σειρά διαδρομής σημαίνει τη μικρότερη απόσταση εάν επιθυμείτε και τους πέντε προορισμούς; Μπορεί ή όχι να το αφήσω σε εσάς να το εξερευνήσετε μόνοι σας.

Εξερεύνηση κώδικα

Το μόνο που χρειάζεται να έχετε εγκαταστήσει για να εξερευνήσετε γραφήματα σε αυτό το παράδειγμα είναι η Python (κατά προτίμηση 3+), το Matplotlib και το NetworkX. Οδηγίες για το πώς να εγκαταστήσετε σωστά και να ξεκινήσετε με το NetworkX μπορείτε να βρείτε από την τεκμηρίωσή τους. Αργότερα, θα κατεβάσουμε ορισμένα δεδομένα κοινωνικών δικτύων ως βάση για την ανάλυση πολύ πιο περίπλοκων δικτύων γραφημάτων. Εάν θέλετε να ακολουθήσετε σε ένα διαδραστικό περιβάλλον κωδικοποίησης χωρίς να χρειάζεται να εγκαταστήσετε τα πάντα τοπικά, μπορείτε να βρείτε τον πλήρη κώδικα σε αυτό Περιβάλλον IPython/Jupyter.

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

import networkx as nx import matplotlib.pyplot as plt G = nx.Graph() G.add_node('S') G.add_node('F') G.add_node('W') G.add_node('P') G.add_node('C') G.add_edge('S', 'F', weight=2) G.add_edge('F', 'W', weight=1.2) G.add_edge('F', 'P', weight=1.5) G.add_edge('P', 'C', weight=0.8) G.add_edge('P', 'W', weight=1.1) G.add_edge('W', 'C', weight=0.4)

Τώρα, σχεδιάζουμε το γράφημα και επισημαίνουμε τις άκρες:

pos = nx.spring_layout(G, scale=3) nx.draw(G, pos,with_labels=True, font_weight="bold") edge_labels = nx.get_edge_attributes(G,'r') nx.draw_networkx_edge_labels(G, pos, labels = edge_labels) plt.show() print(nx.shortest_path(G,'C','S',weight="weight")) print(nx.nx.shortest_path_length(G,'C','S',weight="weight" )) all = (nx.nx.floyd_warshall(G)) print(all)

Φθείρων: Σας έχω ήδη δώσει μια ιδέα για τον προσδιορισμό των αποστάσεων από οποιοδήποτε σημείο από την πηγή, χρησιμοποιώντας το floyd_warshall μέθοδος. Το επιστρεφόμενο αντικείμενο είναι ένα λεξικό με κόμβους ως κλειδιά και αποστάσεις ως ακμές από τον κόμβο πηγής. Θα πρέπει να παρατηρήσετε ότι αυτό θα έλυνε μόνο μέρος του προβλήματός μας εάν θέλουμε να εντοπίσουμε πραγματικά τη διαδρομή που θα μπορούσε να ακολουθήσει ένας ταξιδιώτης εάν ήθελε να διασχίσει ολόκληρη τη διαδρομή. Αντίθετα, μας δίνει την απόσταση κάθε σημείου από την πηγή, όχι την απόσταση μεταξύ κάθε σημείου. Ας συνεχίσουμε.

Ρίξε μια ματιά στο nx.nx.spring_layout(G) . Το έχουμε ξαναδεί αυτό όταν ρυθμίζαμε και σχεδιάζαμε το γράφημά μας, αλλά το αποθηκεύσαμε σε μια μεταβλητή, επομένως φέρει εξήγηση. Όπως μπορείτε να δείτε, το επιστρεφόμενο αντικείμενο είναι ένα λεξικό θέσεων που πληκτρολογείται με κόμβο. Αχα! Αυτό θα ήταν το κλειδί για την εύρεση των σχετικών θέσεων των κόμβων σε ένα καρτεσιανό επίπεδο συντεταγμένων. Καθώς κοιτάμε πίσω, μπορούμε να δούμε ότι στην πραγματικότητα αποθηκεύσαμε αυτές τις θέσεις στη μεταβλητή pos πριν σχεδιάσαμε το γράφημα. Εάν σχολιάσετε το βήμα θέσης ή παραμελήσετε την παράμετρο pos στο βήμα σχεδίασης, θα διαπιστώσετε ότι οι θέσεις των κόμβων θα ήταν τυχαίες αντί για σταθερά σημεία. Ουσιαστικά, απλώς μια ομάδα συνδεδεμένων σημείων που επιπλέουν στο διάστημα, αλλά όχι εδώ. έχουμε σταθερούς κόμβους.

Με τη μέθοδο shortest_path, έχουμε τον αλγόριθμο που προέρχεται από την Dijkstra να μας λέει την τελική σειρά του νικητή της συντομότερης πρώτης αναζήτησης, από τον κόμβο C στον κόμβο S. Θα μπορούσατε να αλλάξετε αυτές τις παραμέτρους για να βρείτε μια εναλλακτική διαδρομή, εάν θέλατε τόσο. Αν αυτό δεν είναι αρκετό, εκτυπώνουμε το μήκος αυτής της διαδρομής, το οποίο αθροίζεται όταν κάνετε την αριθμητική.

Και τώρα παίζουμε λίγο με κάποιες άλλες λειτουργίες για να εξοικειωθούμε περισσότερο με τα δίκτυα γραφημάτων. Όσον αφορά τον βαθμό «συνδεσιμότητας» που έχει κάθε κόμβος, θα χρησιμοποιήσετε βαθμός . Αυτό απλώς θα μας πει πόσες άκρες βγαίνουν από έναν κόμβο. Οσον αφορά ομαδοποίησηορίζεται ως:

Η τοπική ομαδοποίηση κάθε κόμβου μέσα σολ είναι το κλάσμα των τριγώνων που υπάρχει στην πραγματικότητα πάνω από όλα τα πιθανά τρίγωνα στη γειτονιά του. (πηγή)

Ουσιαστικά, πόσοι κόμβοι καταλαμβάνουν τον άμεσο χώρο σε σχέση με άλλα clusters. Όταν εξερευνάτε τη δύναμη και την επιρροή σε ένα δίκτυο, μπορείτε να δείτε κεντρικότητα. Ιδιοδιάνυσμα_κεντρικότητα δίνει μια ένδειξη όχι μόνο του πόσο συνδεδεμένος είναι ένας κόμβος, αλλά και πόσο σημαντικές είναι αυτές οι εισερχόμενες συνδέσεις. Το P και το W φαίνεται να είναι οι πιο ισχυροί κόμβοι στο μικρό μας δίκτυο. Ένα ακόμη μέτρο δικτύου είναι μεταξύ κεντρικότητας , που προσπαθεί να μετρήσει αυτούς τους κόμβους που βοηθούν στο σχηματισμό συνδέσεων από μακρινούς κόμβους. Στο παράδειγμά μας, δεν αποτελεί έκπληξη το γεγονός ότι ο κόμβος F κρατά τον θρόνο ενδιάμεσα, γεφυρώνοντας αποτελεσματικά το χάσμα μεταξύ του Γκρίνουιτς Βίλατζ και του κέντρου του Κάτω Μανχάταν.

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

Δεδομένα Facebook

Το Facebook σημαίνει πολλά πράγματα για πολλούς ανθρώπους, αλλά ένα πράγμα που δεν μπορεί να αμφισβητηθεί είναι ο τεράστιος όγκος δεδομένων που μπορεί να βρεθεί εκεί. Αν είσαι ψάχνοντας το, σίγουρα μπορείς να το βρεις, και το Stanford καθάρισε δημιουργήστε κάποια κοινωνικά δεδομένα για να τα χρησιμοποιήσουμε. Θα χρειαστεί να κατεβάσετε το zip αρχείο με ετικέτα facebook_combined. Όταν εκτελείτε τον κώδικα στο σημειωματάριο και ανεβάζετε σωστά το ληφθέν αρχείο σας (διαγράφεται σε κάθε περίπτωση) θα πρέπει να μοιάζει κάπως έτσι: