Wie der Fast-Unfolding-Algorithmus Communities in großen Netzwerken erkennt

Bei der Analyse sozialer Netzwerke werden Muster in großen realen Netzwerken untersucht, die aus Millionen von Knoten bestehen. Wenn Sie über Grundkenntnisse in der Graphentheorie verfügen, können Sie diese Analysen durchführen.

Die digitale Welt hat eine völlig andere Art der Beziehungsbildung eröffnet. Es wird auch ein Ozean von Daten freigesetzt, die wir analysieren können, um ein besseres Verständnis des menschlichen Verhaltens zu erhalten.

Social-Media-Daten beziehen sich auf alle rohen Erkenntnisse und Informationen, die aus den Social-Media-Aktivitäten einer Person stammen. Wir können aus diesen Social-Media-Aktivitäten Netzwerke erstellen, um eine bessere Wahrnehmung dieser Person zu erhalten.

Diese Netzwerke können sehr unterschiedlich sein und Ihre Facebook-Freunde, die Produkte, die Sie kürzlich bei Amazon gekauft haben, die Tweets, die Sie mochten oder retweeteten, Ihr Lieblingsessen, das Sie bei Zomato bestellt haben, die Suche, die Sie bei Google durchgeführt haben, oder das Bild, das Sie kürzlich bei Instagram mochten, umfassen .

Unternehmen verwenden diese Netzwerke, um ihre Benutzer in verschiedene Gruppen einzuteilen. Das hilft ihnen

  • Marktforschung durchführen
  • Leads generieren
  • besser ihren Kunden dienen
  • Fotos und Videos finden und teilen
  • Entdecken und diskutieren Sie Trendinhalte
  • Informationen über Dienstleistungen und Restaurants austauschen
  • Verbinde dich mit anderen um ein gemeinsames Interesse oder Hobby
  • und mehr.

Die Liste ist so ziemlich endlos.

Bevor wir uns zu sehr mit dem Unkraut befassen, wollen wir die Unterscheidung zwischen verschiedenen Komponenten eines Netzwerks schnell auflösen.

Was ist ein Netzwerk?

Ein Netzwerk ist ein Netz miteinander verbundener persönlicher Beziehungen. Beispielsweise können verschiedene Personen in einer Social-Media-Gruppe über ein dynamisches Beziehungsgeflecht miteinander kommunizieren.

Ein Netzwerk besteht aus Knoten (einzelne Akteure, Personen oder Dinge innerhalb des Netzwerks) und den Bindungen , Kanten oder Verknüpfungen (Beziehungen oder Interaktionen), die sie verbinden.

Was ist eine Gruppe?

Reicher SD in Die Bestimmung des kollektiven Verhaltens beschreibt eine Gruppe als eine Sammlung von Personen, die sich als Gruppe betrachten. Mitglieder derselben Gruppe haben eine Reihe gemeinsamer Überzeugungen und Verhaltensweisen.

Was ist eine Gemeinschaft?

Laut David W. McMillan ( Gemeinschaftsgefühl: Eine Definition und Theorie ) kann die Gemeinschaft wie folgt definiert werden:

„Das Gemeinschaftsgefühl ist ein Gefühl der Zugehörigkeit der Mitglieder, ein Gefühl, dass die Mitglieder einander und der Gruppe wichtig sind, und ein gemeinsamer Glaube, dass die Bedürfnisse der Mitglieder durch ihr Engagement für das Zusammensein erfüllt werden.

Communities oder Untereinheiten sind die Teilnetzwerke in einem Netzwerk, bei denen es sich um stark miteinander verbundene Knoten handelt.

Die Community weist auf interne Strukturen hin, die besondere Merkmale aufweisen oder in einem Netzwerk dieselbe Rolle spielen.

Stark verbundene Gruppen von Personen oder Objekten innerhalb dieser Netzwerke sind Gemeinschaften. Es liegt normalerweise am Schnittpunkt des Netzwerks und der Gruppe.

Nachdem wir eine klare Vorstellung davon haben, was ein Netzwerk, eine Gruppe und eine Community ist, wollen wir uns eingehender mit der Aufteilung dieser Netzwerke in kleine Communities befassen.

Wir werden uns den beliebten Fast Unfolding-Algorithmus ansehen . Vincent C. Blondel und die Co-Autoren des Papiers verglichen diesen Algorithmus mit anderen Community-Erkennungsalgorithmen. Sie entdeckten, dass dieser Algorithmus jeden anderen Algorithmus in großen Netzwerken übertrifft.

Was ist der Fast Unfolding-Algorithmus?

Der Fast Unfolding-Algorithmus wurde verwendet, um Sprachgemeinschaften in einem belgischen Mobilfunknetz mit 2,6 Millionen Kunden zu identifizieren.

Es wurde auch verwendet, um ein Webdiagramm von 118 Millionen Knoten und mehr als einer Milliarde Links zu analysieren.

Die Identifizierung von Communities in einem so großen Netzwerk dauerte nur 152 Minuten. Dieser Algorithmus ist also schnell und effizient.

Wie der Algorithmus funktioniert

Der Algorithmus arbeitet in zwei Phasen:

Phase 1

  1. Weisen Sie jedem Knoten in einem Netzwerk eine andere Community zu.
  2. Dann betrachtet i für jeden Knoten den Knoten j und bewertet den Modularitätsgewinn, indem der Knoten i aus seiner Community entfernt und in die Community von j eingefügt wird.
  3. Der Knoten i befindet sich in der Community, für die er maximale Modularität erhält, aber der Gewinn sollte positiv sein. Wenn die Verstärkung negativ ist, bleibt der Knoten i in derselben Gemeinschaft.

Phase 2

  1. Die zweite Phase des Algorithmus besteht darin, ein neues Netzwerk aufzubauen, dessen Knoten nun die in der ersten Phase gefundenen Communities sind. Wir erstellen also Knoten, indem wir alle Knoten in der Community als einen einzigen Knoten zusammenführen.
  2. Die Gewichte der Verbindung zwischen den Knoten ergeben sich aus der Summe der Gewichte der Verbindungen zwischen den Knoten in den entsprechenden zwei Gemeinschaften.
  3. Die Verknüpfung zwischen Knoten derselben Community führt zu Selbstschleifen für die Community im neuen Netzwerk.
  4. Wiederholen Sie Phase 1, bis keine weitere Verbesserung erreicht werden kann.

Wie der Gewinn an Modularität berechnet wird

Die Qualität der Partition ( Q ) wird anhand der Modularität (auch als Modularität der Partition bezeichnet) gemessen . Es ist ein skalarer Wert zwischen -1 und 1 und misst die Dichte von Links innerhalb von Communities im Vergleich zu Links zwischen Communities.

Der Gewinn an Modularität (∆Q), der durch Verschieben eines isolierten Knotens i in eine Community C erhalten wird, kann leicht berechnet werden durch:

Σin ist die Summe der Gewichte der Glieder innerhalb von C.

Σtot ist die Summe der Gewichte der Verbindungen, die auf Knoten in C einfallen.

ki ist die Summe der Gewichte der Verbindungen von i zum Knoten in C.

m ist die Summe der Gewichte aller Verbindungen im Netzwerk.

Der Gewinn an Modularität wird bewertet, indem i aus seiner Community entfernt und dann in eine benachbarte Community verschoben wird . Wenn der Gewinn positiv ist, wird dieser Knoten in die Nachbargemeinde gestellt.

Trockenlauf des Algorithmus

Im linken Netzwerk (15 Knoten) weisen wir jedem Knoten zunächst eine eindeutige Community zu. Anschließend bewerten wir die Modularität jedes Knotens und weisen die Community basierend auf dem Gewinn neu zu. Dies wird als Modularitätsoptimierung bezeichnet .

In der nächsten Phase erstellen wir Knoten, indem wir alle Knoten in dieser Community zu einem einzigen Knoten zusammenführen. In der grünen Community haben wir insgesamt 5 Knoten und es gibt insgesamt 7 Kanten zwischen ihnen.

Nach der Community-Aggregation beträgt das Gewicht der Selbstschleife des grünen Knotens 14 (7 * 2, da es sich um eine bidirektionale Verbindung handelt). In ähnlicher Weise beträgt das Gewicht der Selbstschleife des roten Knotens 16, der blaue Knoten 4 und der hellblaue Knoten 2.

Das Gewicht der Kante zwischen dem grünen und dem blauen Knoten beträgt 4, da nach der Modularitätsoptimierung insgesamt 4 Kanten zwischen der grünen und der blauen Community vorhanden sind.

Im nächsten Schritt bewerten wir die Modularität für die neuen Knoten neu und führen den gleichen Vorgang erneut durch.

Schließlich erhalten wir zwei Gemeinschaften, Grün und Hellblau. Die grüne Community hat 26 Selbstschleifen, da sich zwischen den Knoten der grünen Community insgesamt 13 Kanten befinden. Und wir haben 12 Kanten in der hellblauen Community, insgesamt 24 Selbstschleifen.

Vorteile des Algorithmus

  1. Die Schritte sind intuitiv und einfach zu implementieren und das Ergebnis ist unbeaufsichtigt.
  2. Der Algorithmus ist extrem schnell. Computersimulationen in sehr großen modularen Netzwerken legen nahe, dass die Komplexität der typischen und spärlichen Daten linear ist. Dies kann daran liegen, dass der Gewinn an Modularität einfach zu berechnen ist und die Anzahl der Communitys bereits nach wenigen Durchgängen drastisch abnimmt.

Einschränkungen des Algorithmus

  1. Bei der Modularitätsoptimierung können keine Communities identifiziert werden, die kleiner als ein bestimmter Maßstab sind. Dies führt zu einer Auflösungsbeschränkung für die Community, die mit einem rein modularen Optimierungsansatz berechnet wird.
  2. Bei kleinen Netzwerken ist die Wahrscheinlichkeit sehr gering, dass zwei separate Communities durch Verschieben jedes Knotens zusammengeführt werden können.

Fazit

Wenn Sie so lange dort geblieben sind ... danke! Ich hoffe, es gab wertvolle Informationen für Sie.

Jetzt wissen Sie also, wie der Fast Unfolding-Algorithmus funktioniert und dass es äußerst effizient ist, Communities in sehr großen Netzwerken zu erkennen.

Durch die Berechnung des Gewinns an Modularität übertrifft der Algorithmus jeden anderen Algorithmus. Schreiben Sie mir eine Nachricht, wenn Sie diese nützlich finden oder weitere Fragen haben.

Danke fürs Lesen!