Erkundung des kleinen Weltdiagramms mit Neo4j / Sudo Null IT News

Als meine Schwester in eine andere Stadt zog und die Nachbarn kennenlernte, stellte sich heraus, dass die Großeltern ihrer Nachbarin und unsere Großeltern gute Freunde waren und sich unterhielten, während sie in einer anderen Stadt in der Nähe lebten – vor zwei Generationen. Es ist interessant, wenn solche unerwarteten Verbindungen entdeckt werden. Nach der Netzwerktheorie sind Wege, die Knoten in einem Netzwerk verbinden, oft kürzer als man denkt.

Wenn es jeder im Netzwerk weiß k andere Personen, dann können wir das, ausgehend von dieser Person, vereinfachend annehmen und vervollständigen n Übergänge von Knoten zu Knoten, werden wir finden kⁿ Mensch. Angesichts des exponentiellen Wachstums würde es sehr wenig Zeit in Anspruch nehmen, einen Pfad von einer bestimmten Person zu einer anderen Person im Diagramm zu erstellen.

Aber in echten sozialen Netzwerken kennen sich viele Personen, die einer bestimmten Person vertraut sind, auch untereinander. Diese Überkreuzung zwischen Freunden von Freunden reduziert die Anzahl neuer Leute, an die ich mich nach jedem Hop in den Pfad vom Startknoten wenden kann. Es kann schwierig sein, Pfade zu finden, die in einer eng verbundenen Community beginnen und sich dann bis in die entferntesten Ecken des Netzwerks verzweigen.

BEI Kapitel 20 des Buches Netzwerke Massen und Märkte seine Autoren David Easley und John Kleinberg liefern einen theoretischen Apparat, der beschreibt, wie Phänomene in der realen Welt entstehen können, die in den Graphen der „kleinen Welt“ passen. Diese Theorie kombiniert die Idee Homophilie, wonach ähnliche Personen zusammengeballt werden, und die Idee der schwachen Bindungen, bei der sich Beziehungen im gesamten Netzwerk verzweigen. Erklärung basierend auf der Arbeit Duncan Watts und Steve Strogatz. Folgen wir diesen Beispielen mit Code, der mit Neo4j geschrieben wurde.

Um den folgenden Code auszuführen, geben Sie ein Sandkasten und wählen Sie „Neues Projekt“. (Neues Projekt). Wählen Sie als Nächstes aus den vorgeschlagenen Projektrohlingen „Graph Data Science“ aus.

Die Sandbox ist mit einer großen Menge an Game of Thrones-Daten geladen, die wir für diese Übung nicht benötigen. Entfernen wir sie.

MATCH (n) DETACH LÖSCHEN n;

Lassen Sie uns nun ein Raster aus Personenknoten erstellen, 30 mal 30. Jeder Personenknoten erhält drei Eigenschaften: eine Zeile, eine Spalte und Koordinaten.

UNWIND RANGE(1,30) AS row UNWIND RANGE(1,30) AS column CREATE (p:Person {Zeile:Zeile, Spalte:Spalte, Koordinaten:toString(Spalte) + ‘, ‘ + toString(Zeile)});

Wir erstellen eine KNOWS-Beziehung zwischen jeder bestimmten Person und der Person, die sich im Raster rechts davon befindet.

MATCH (p1:Person), (p2:Person) WHERE p1.row = p2.row AND p1.column = p2.column – 1 CREATE (p1)-[:KNOWS]->(p2);

Wir erstellen eine KNOWS-Beziehung zwischen jeder bestimmten Person und der Person, die sich im Raster genau unter ihr befindet.

MATCH (p1:Person), (p2:Person) WHERE p1.column = p2.column AND p1.row = p2.row – 1 CREATE (p1)-[:KNOWS]->(p2);

Zwischen jeder bestimmten Person und zwei diagonal neben ihr stehenden Personen, die sich eine Reihe darunter befinden.

MATCH (p1:Person)–>(p2:Person) WHERE p1.row = p2.row-1 WITH (p1), (p2) MATCH (p2)–(p3) WHERE p3.row = p2.row CREATE (p1)-[:KNOWS]->(p3);

Wir haben ein schönes Gittermuster. Wir wählen Person und ihre Nachbarn aus und werden dann sehen, wie diese Beziehungen funktionieren.

MATCH (p:Person {Zeile:5, Spalte:5})-(n) RETURN *;Gesichtsbeziehungen mit Koordinaten 5, 5Gesichtsbeziehungen mit Koordinaten 5, 5

Ich sehe viele Dreiecke in diesem Bild. Lassen Sie uns anhand einer Bibliothek für Data Science auf Graphen ermitteln, wie hoch der Anteil solcher Personen im Bekanntenkreis einer bestimmten Person ist, die sich auch kennen. Lassen Sie uns zunächst einen benannten Graphen im Speicher erstellen.

CALL gds.graph.create(‘base-grid’, ‘Person’, {KNOWS: {orientation:”UNIRECTED”}});

Als nächstes führen wir den Algorithmus zum Zählen von Dreiecken aus.

CALL gds.alpha.triangleCount.stream(‘base-grid’) YIELD-Koeffizient RETURN avg(coefficient) AS averageClusteringCoefficientErgebnisse der Clustering-KoeffizientenErgebnisse der Clustering-Koeffizienten

Ein Ergebnis von 0,44 bedeutet, dass sich im Durchschnitt nur etwa die Hälfte der Bekannten einer bestimmten Person auch kennt. Dieser Grad an Nachbarüberlappung kann zu relativ langen Pfaden führen, verglichen mit dem, was wir in einem Netzwerk erwarten könnten, in dem die meisten Knoten vom Grad 8 sind.

Lassen Sie uns diese Idee testen. Rufen wir die Prozedur allShortestPaths auf, um den kürzesten Pfad zwischen jeweils zwei Knoten im Diagramm zu finden. Als nächstes fassen wir die Ergebnisse zusammen.

CALL gds.alpha.allShortestPaths.stream(‘small-world’) YIELD sourceNodeId, targetNodeId, distance RETURN max(Distanz) AS maxDistance, min(Distanz) AS minDistance, avg(Distanz) AS avgDistance, count(Distanz) AS pathCount;Ergebnisse des allShortestPaths-AlgorithmusErgebnisse des allShortestPaths-Algorithmus

Ich war beeindruckt, dass mein kostenloser Sandbox-Server 809.100 Pfade in etwa einer Sekunde berechnen konnte. Der Durchmesser eines Graphen ist der längste der kürzesten Pfade zwischen Knoten. Der Durchmesser von 29 Übergängen in diesem Diagramm ist ziemlich logisch. Keine zwei Knoten sind weiter voneinander entfernt als diejenigen, die sich an gegenüberliegenden Rändern des Gitters befinden.

Betrachten Sie die Verteilung der Pfadlängen.

CALL gds.alpha.allShortestPaths.stream(‘base-grid’) YIELD sourceNodeId, targetNodeId, distance RETURN distance, count

AS pathCount ORDER BY Distanz;

Hier ist die Tabelle mit den Ergebnissen.Histogramm der Pfadlängen

Histogramm der Pfadlängen

Ändern wir nun das Diagramm, indem wir zufällige Beziehungen zwischen Knoten hinzufügen, die im Gitter nicht benachbart sind. Sie können diese schwachen Bindungen mit solchen Beziehungen vergleichen: Es gibt einige Leute, die Sie kennen, die außerhalb Ihres Hauptfreundeskreises liegen.

Lassen Sie uns die Prozedur apoc.periodic.iterate verwenden, um über alle Knoten zu iterieren und jedem Knoten zwei nicht benachbarte Links hinzuzufügen.[:KNOWS {adjacent:False}]CALL apoc.periodic.iterate( ‘MATCH (p1) RETURN p1’, ‘MATCH (p2) WHERE p1 <> p2 AND NOT EXISTS((p1)-(p2)) WITH p1, p2, rand() AS RAND ORDER BY Rand LIMIT 2 MERGE (p1)-

->(p2)’, {batchSize:1} )

Schauen wir uns noch einmal Person bei den Koordinaten 5, 5 an. Dieser Knoten hat jetzt zehn Links. Acht davon im Raster sind benachbart, und zwei der neuen Verbindungen sind nicht benachbart.MATCH (p:Person {Zeile:5, Spalte:5})-(n) RETURN *;Nachbarn des Knotens mit den Koordinaten 5, 5

Nachbarn des Knotens mit den Koordinaten 5, 5

Lassen Sie uns ein neues Diagramm im Speicher erstellen, das wir mit der Graph Data Science Library analysieren werden.

CALL gds.graph.create(‘small-world’, ‘Person’, {KNOWS:{orientation:”UNIRECTED”}});

Was ist der durchschnittliche Clustering-Faktor für das neue Diagramm?CALL gds.alpha.triangleCount.stream('base-grid') YIELD-Koeffizient RETURN avg(coefficient) AS averageClusteringCoefficientClustering-Koeffizient

Clustering-Koeffizient

In der neuen Spalte finden sich durchschnittlich 18 % der Personen wieder, die die betreffende Person kennen und gleichzeitig einander kennen. Mit zwei neuen Freunden pro Person und weniger Überschneidungen zwischen Freunden sollte es kürzere Pfade zwischen den Knoten geben.

Lassen Sie uns allShortestPaths erneut ausführen und die Statistiken überprüfen.CALL gds.alpha.allShortestPaths.stream('small-world') YIELD sourceNodeId, targetNodeId, distance RETURN max(Distanz) AS maxDistance, min(Distanz) AS minDistance, avg(Distanz) AS avgDistance, count(Distanz) AS pathCount; Ergebnisse des allShortestPaths-Algorithmus

Ergebnisse des allShortestPaths-Algorithmus

Der Durchmesser des Diagramms hat sich von 29 auf 5 stark verringert, und die durchschnittliche Entfernung wurde auf nur 3 reduziert. Tatsächlich ist die Welt klein!

Betrachten Sie eine neue Verteilung von Pfadlängen.

CALL gds.alpha.allShortestPaths.stream(‘small-world’) YIELD sourceNodeId, targetNodeId, distance RETURN distance, count

AS pathCount ORDER BY Distanz;

Es gibt einen sehr kleinen Prozentsatz solcher Menschen, die fünf Schritte voneinander entfernt sind. Die überwiegende Mehrheit der kürzesten Pfade umfasst jetzt drei oder vier Sprünge.

Wir begannen mit einem Netzwerk, in dem jeder nur seinen direkten Nachbarn kannte. Indem wir für jeden Knoten zwei nicht benachbarte Links hinzugefügt haben, haben wir den Diagrammdurchmesser und die durchschnittliche Länge des kürzesten Pfads drastisch reduziert. Sie können den Code mit mehr oder weniger nicht benachbarten Links für jeden Knoten erneut ausführen und sehen, wie sich die Ergebnisse ändern. Easley und Kleinberg zeigen, dass sich das Modell der „kleinen Welt“ auch dann entwickelt, wenn nicht jede Person nicht zusammenhängende Verbindungen hat. Durch Erstellen einer einzelnen nicht benachbarten Verbindung für eine Teilmenge von Knoten ist es immer noch möglich, die Länge von Pfaden zwischen Knoten erheblich zu reduzieren. 

Similar Posts

Leave a Reply

Your email address will not be published.