Inhalt

“Identifying communities by influence dynamics in social networks” von Stanoev, Smilkov und Kocarev

Wir analysieren den von Stanoev, Smilkov und Kocarev entwickelten Algorithmus zur Entdeckung von überlappenden Communities und ordnen ihn zu den in diesem Buch vorgestellten Algorithmen ein. Der Algorithmus wurde für soziale Netzwerke entwickelt, lässt sich aber auf beliebige Netzwerke, die sich durch gegenseitige Beeinflussung der Teilnehmer verdichten, anwenden. Einen allgemeingültigen Algorithmus hielten die Autoren für unzureichend, da ein guter Algorithmus sich nicht nur an der Topologie, sondern auch an den dynamischen Prozessen in einem Netzwerk orientieren sollte. Der Algorithmus erlaubt die Entdeckung von Anführern der einzelnen Communities und die Einordnung in Communities als hierarchische Einflussstrukturen. Die Modularitätsfunktion wird nicht verwendet, da diese bekanntermaßen Schwächen bei der Ermittlung verschieden starker Zugehörigkeiten, überlappender Communities, sowie kleiner Communities in großen Netzwerken aufweist. Stattdessen wird eine Einflussmatrix zur Ermittlung und ein stochastischer Zugehörigkeitsvektor zu Ermittlung wie Darstellung der Communities genutzt. Die lokale Vorgehensweise erlaubt eine verteilte Ausführung und erfordert bei Hinzufügen bzw. Entfernen von Knoten bzw. Kanten nur in deren Nachbarschaft Neuberechnungen, er ist also gut für sich wandelnde Netzwerke geeignet. Der Algorithmus zeigte sich tauglich für Repräsentanten verschiedenster Kategorien von Netzwerken.

Struktur

  • Inhalt
  • Motivation
  • Vorstellung des Algorithmus’
    • Einleitung
    • Einflussmatrix
    • Bestimmung der Anführer
    • Mitgliedschaftsvektoren
  • Eigenschaften des Algorithmus’
  • Einordnung des Algorithmus’
  • Anwendungen und Animationen
  • Zusammenfassung
  • Danksagung
  • Quellen

Vorwort

Der folgende Text wurde im Rahmen des Proseminars an der RWTH Aachen im Sommersemester 2017 geschrieben und stellt im Wesentlichen eine deutsche Version des Papers “Identifying communities by influence dynamics in social networks” von Angel Stanoev, Daniel Smilkov und Ljupco Kocarev dar. (Stanoev et al., 2011)

Motivation

Die Komponenten vieler verschiedener Strukturen können als Netzwerke ausgelegt werden. Netzwerke werden so mächtige Werkzeuge um ein Verständnis für die Struktur, die Dynamiken und Entwicklung von komplexen Systemen zu entwickeln. Häufig zeigen diese Netzwerke eine modulare und hierarchische Struktur welche die Entwicklung zu komplexen Systemen unterstützt. Die automatische Erkennung der Struktur - bekannt unter Community Erkennung - kann dabei helfen benachbarte Klassen von Knoten zu identifizieren. Außerdem erleichtert es das Verständnis für die Organisation von komplexen Systemen.

Die derzeitige, auf Community Erkennung, konzentrierte Forschung fokussiert sich auf die Erkennung von Communities in jeder Art von Kontext. Diese allgemeingültige Vorgehensweise hat viele Nachteile, hauptsächlich dabei, dass die Algorithmen die entstandene Partitionierung des Netzwerks nicht erklären kann. Damit die Algorithmen in der Praxis genutzt werden können, muss der Kontext, wie Communities aufgebaut werden und sich entwickeln, berücksichtigt werden. Als Beispiel spielen einzelne Einflussgeber oder Gruppen in sozialen Netzwerken eine große Rolle. In Kommunikationsnetzwerken sind dies gut verbundene Knoten, in Netzwerken für wissenschaftliches Arbeiten sind es wichtige Paper die das Netzwerk stark beeinflussen.

Communities sind zudem nicht statisch, sie entwickeln sich, dabei können sie sich spalten, vereinigen, vergrößern und verkleinern. Sie sind ein Produkt von dynamischen Prozessen die die Entwicklung von Netzwerken beherrschen. Ein guter Algorithmuss muss also nicht nur die Topologie eines Netzwerks beachten, sondern auch die Prozesse die der Formung des Netzwerks dienen. Da es sehr viele verschiedene Prozesse gibt, die Netzwerke formen ist es schwierig einen Algorithmus zu entwickeln, der auf jeder Art von Netzwerk gut funktioniert. Oft schneiden sich Communities in den Netzwerken, so dass ein Knoten zu mehreren Communities gehört. Überraschenderweise wurde diese Eigenschaft, bis vor Kurzem, sehr lange vernachlässigt. Es gibt ein paar Algorithmen, welche die Überlappung von Communities berücksichtigen, die Anzahl derer, die es nicht tun ist jedoch noch größer. Der in diesem Online-Buch vorgestellte Algorithmus von Angel Stanoev, Daniel Smilkov und Ljupco Kocarev (SSK) verfolgt nicht die allgemeingültige Strategie, sondern konzentriert sich auf soziale Netzwerke und die dynamischen Interaktionen die in diesen Netzwerken vorkommen. Dies hilft die Anführer und Communities welche sich um die Anführer entwickeln zu identifizieren. Durch die Zuordnung eines Zugehörigkeitsverktors zu jedem Knoten unterstützt er nativ die Erkennung von sich überlappenden Communities.

Der bedeutsamste Teil eines sozialen Netwerks sind die Verbindungen, welche die Interaktion von zwei sozialen Entitäten darstellt. Die Autoren glauben, dass die simple Quantifizierung von Verbindungen viele Nachteile hat. Eine gute Vorgehensweise zur Erkennung von Communities muss also die sozialen Interaktionen berücksichtigen. In dem Paper wird das soziale Netzwerk von Zachary genutzt um die Nachteile anderer Netzwerke aufzuzeigen. Außerdem erklären sie die Motivation des vorgeschlagenen Algorithmus.

Die meisten Methoden nutzen die Modularitätsfunktion zur Erkennung von Communities. Seit ihrer Einführung gab es viele Algorithmen, welche die Modularitätsfunktion als Basis nutzen. Diese Algorithmen optimieren die Funktion um einen besseren Modularitätswert und so eine bessere Erkennung von Communities zu erreichen. Neulich scheint der Fokus auf die Modularitätsfunktion verloren gegangen zu sein, da viele Nachteile erkannt wurden. Zwei der wichtigsten sind die fehlende Auflösung und die Diversität von stark modularen Partitionen.

Im Paper wurde ein weiterer negativer Aspekt der Modularitätsfunktion an Knoten welche am Rand eines Netzwerks liegen. Am Beispiel des Zachary Netzwerks wird dieser negative Aspekt erläutert. Die Analyse zeigt auf, dass eine Community Zuordnung die Dynamiken und nicht die Topologie in Betracht ziehen sollte. Des Weiteren sollte die Entscheidung der Zuordunung knotenbasiert erfolgen.

Wenn die Einflussnahme einzelner Knoten berücksichtigt wird, wird im gleichen Atemzug auch die Erkennung von Hierarchien unterstützt. Naturgemäß sind Knoten mit großer Einflussnahme auch wichtige Knoten innerhalb der Hierarchie. Somit unterstützt der vorgestellte Algorithmus auch die Hierarchieerkennung.

Vorstellung des Algorithmus’

Einleitung

Die Basis des Algorithmus ist eine dezentrale Herangehensweise. Der erste Schritt ist die Erkennung des Einflusses eines Knotens auf einen anderen. Echte Netzwerke tendieren dazu, Dreiecke von eng zusammengehörenden Knoten zu bilden. An dieser Stelle nutzt der Algorithmus die Tatsache, dass die Verbindungsdichte innerhalb von Communities größer als außerhalb ist. Anführer tendieren dazu Knoten untereinander zu verbinden während normale Knoten eher mit anderen verbunden werden, daraus folgt, dass Knoten welche keine Anführer sind eher Teil eines Ganzen sind. Wenn also für einen Knoten die Verbindungsrichtung bestimmt werden kann, kann bestimmt werden, zu welcher Community ein Knoten gehört. Je dichter die Knoten beieinander liegen, desto näher liegen die Knoten am Kern der Community. Da Dreiecke zwischen zwei Knoten eine bessere Vermittlung als eine direkte Verbindung bieten, folgt, dass je mehr Dreiecke ein Knoten hat, desto mehr Einfluss hat dieser Knoten im Netzwerk.

Im Folgenden liegt der Fokus auf einem simplen, gerichteten und gewichteten Netzwerk \(G\) ohne Mehrfachverbindungen oder Verbindungen von Knoten auf sich selbst. Das Netzwerk wird durch eine \(N\times N\) Adjazenzmatrix \(A\) beschrieben, wobei \(N\) die Anzahl der Knoten ist. Per Definition ist \(A_{ij}\) das Gewicht der Kante von Knoten \(j\) zu Knoten \(i\) und im Allgemeinen ist \(A_{ij}\) ungleich \(A_{ji}\). Da es sich bei \(G\) um ein gerichtetes Netzwerk handelt, interpretieren wir \(A_{ij}\) als den Einfluss von Knoten \(i\) auf Knoten \(j\). Falls das Netzwerk ungerichtet ist, gilt \(A_{ij}=A_{ji}\). \(s_i=\sum_jA_{ij}\) ist die Stärke von Knoten i, wenn das Netzwerk ungewichtet ist, so ist \(s_i\) gleich dem Grad von Knoten \(i\).

Einflussmatrix

Um die Information, die wir aus den Dreiecken gewinnen, zu nutzen, führen wir ein gewichtetes Netzwerk \(G'\) ein, in dessen Kantengewichten der Einfluss der Dreiecke integriert ist, womit wir die Einflussmatrix \(A'\) erhalten. Dafür definieren wir das “transitive” Kantengewicht von Knoten \(i\) über Knoten \(k\) auf Knoten \(j\) als \(C^k_{ji}=\text{min}(A_{ki},A_{jk})\), welches nur für benachbarte Knoten definiert ist, womit \(C^k_{ij}=0\), wenn \(A_{ij}=0\). Es wird das Minimum verwendet, da nicht mehr Einfluss weitergegeben werden kann, als ein Knoten selbst ausübt. Der Einfachheit halber definieren wir \(\Delta_{ji}=\sum_kC^k_{ji}\), den gesamten indirekten Einfluss von \(j\) auf \(i\). Zusammen mit dem direkten Einfluss \(A_{ji}\) erhalten wir den Gesamteinfluss \(A'_{ji}=A_{ji}+\Delta_{ji}\). Wenn es sich bei dem untersuchten Netzwerk um ein ungewichtetes, ungerichtetes handelt, dann ist \(A'_{ji}\) einfach eins mehr als die Anzahl der Dreiecke zwischen Nachbarn \(i\) und \(j\). Für späteren Gebrauch definieren wir \(\Delta_j=\sum_k\Delta_{jk}\), den gesamten indirekten Einfluss von \(j\) auf alle seine Nachbarn. Wenn der ursprüngliche Graph indirekten Einfluss schon einbezieht, dann fällt dieser Schritt weg und \(A=A'\).
Der nächste Schritt ist die Berechnung von \(x_i^*\), des Einflusses eines Knotens \(i\) auf das gesamte Netzwerk. Dafür wird die Ausbreitung von Meinungen als ein Zufallsprozess auf dem Graphen modelliert, in dem bei jedem Schritt ein Marker auf Knoten \(j\) zu einem Nachbarn übergeht, mit einer zu \(A'_{ij}\) proportionalen Wahrscheinlichkeit auf Knoten \(i\) überzugehen. Sei \(\textbf{x}(t)=(x_1(t),x_2(t),...,x_N(t))\) mit \(x_i(t)\) Einfluss des Knotens \(i\) auf das gesamte Netzwerk bei Schritt \(t\), dann entwickelt sich die erwartete Dichte von Markern nach
\(\bf{x}(t+1)=T\bf{x}(t)\),
wobei \(T\) die Transitionsmatrix ist, deren Eintrag \(T_{ij}\) die Wahrscheinlichkeit eines Übergangs von \(j\) nach \(i\) repräsentiert,
\(T_{ij}=\frac{A'_{ij}}{\sum_kA'_{kj}}\).
\(T_{ij}\) beschreibt den relativen Einfluss von Knoten \(i\) auf Knoten \(j\). Wir beginnen mit dem Vektor \(\textbf{x}(0)=(\frac{1}{N},\frac{1}{N},...,\frac{1}{N})\). Der Einfluss auf das gesamte Netzwerk \(x^*_i\) ist eine Lösung der Gleichung \(\textbf{x}(t+1)=\textbf{x}(t)\) und kann für gerichtete Netzerke nur numerisch durch Iteration gefunden werden, also durch numerische Berechnung von \(\text{lim}_{t\to\infty}(\textbf{x}(t))\). Im Sonderfall, dass das Netzwerk ungerichtet und nicht bipartit ist, gibt es eine bekannte analytische Lösung für \(x^*_i\), nämlich
\(x^*_i=\frac{\sum_jA'_{ij}}{\sum_{jk}A'_{kj}}\propto s_i+\Delta_i\).
Wie zu sehen ist, ist das Potenzial eines Knotens Anführer zu werden von seinem Eingangsgrad und der Anzahl an Dreiecken abhängig, wie weiter oben schon erwähnt.

Bestimmung der Anführer

Da wir nun die relativen Einflüsse zwischen den Knoten \(T_{ij}\) und die Einflüsse auf das gesamte Netzwerk \(x^*_i\) kennen, können wir die Anführer identifizieren. Ein Anführer sollte einen großen Einfluss auf das gesamte Netzwerk haben, da dieser repräsentiert, wie nah am Kern seiner Community ein Knoten und wie groß sein tatsächlich Potenzial Anführer zu werden ist. Außerdem sollte ein Anführer mehr Einfluss auf seine Nachbarn haben, als sie auf ihn. Daher definieren wir Anführer als solche Knoten, für die das Produkt aus Einfluss auf das gesamte Netzwerk und relativem Einfluss groß ist. Genauer, wir beschreiben mit \(\Gamma_i=\{j\mid T_{ji}=\text{max}_kT_{ki}\}\) die Menge der Nachbarn mit dem größten relativen Enfluss auf Knoten \(i\). Knoten \(i\) ist Anführer, wenn
\(T_{ij}x^*_i>T_{ji}x^*_j\),
für alle \(j\in\Gamma_i\). Das Produkt \(T_{ij}x^*_i\) der beiden Zahlen \(T_{ij}\) und \(x^*_i\) kombiniert den relativen Einfluss von Knoten \(i\) auf Knoten \(j\) mit dem Einfluss auf das gesamte Netzwerk von Knoten \(i\).
Es ist zu beachten, dass in den seltenen Fällen, in denen zwei oder mehr Anführer auch ihre jeweils einflussreichsten Nachbarn sind (also wenn \(T_{ij}x^*_i=T_{ji}x^*_j\)), sich diese zusammenschließen und Anführer derselben Gruppe werden. In einem vollständigen Graphen z.B. sind alle Knoten Anführer derselben Community, während in einem Ring jeder Knoten Anführer seiner eigenen Community ist. Tatsächlich weist dies darauf hin, dass in Fällen, in denen kaum hierarchische Strukturen vorliegen und damit auch kein ausgezeichneter Anführer in einer Community existiert, sich diese Community in von ihrer Kantendichte abhängige Teilgruppen aufspaltet.

Mitgliedschaftsvektoren

Angenommen wir haben \(L\) Anführer im Netzwerk und damit \(L\) Communities, und sei \(l=\{l_1,l_2,...,l_L\}\) die Menge aller Anführer. Wir berechnen den Mitgliedschaftsvektor \(\textbf{y}_i=(y^1_i,y^2_i,...,y^L_i)^T\), einen stochastischen Vektor der Länge \(L\), der die Beteiligung von Knoten \(i\) in jeder Community beschreibt. Da \(\textbf{y}_i\) ein stochastischer Vektor ist, summieren sich seine Komponenten auf \(1\), also \(\sum^L_{k=1}y^k_i=1\). Für jeden Anführer \(l_i\) ist der anfängliche Mitgliedschaftsvektor bis auf die \(i\)-te Komponente \(y^i_{l_i}=1\) genullt. Für jeden Knoten \(j\), der kein Anführer ist, sind alle Komponenten von \(\textbf{y}_i(0)\) mit \(\frac{1}{L}\) initialisiert, um gleichmäßige Beteiligung an jeder Community zu repräsentieren. Um die Mitgliedschaftsvektoren zu berechnen, nutzen wir Konsensdynamiken,
\(\textbf{y}_i(t+1)=\frac{1}{\sum_jA_{ji}}\sum_jA_{ji}\textbf{y}_j(t)=\sum_jS_{ji}\textbf{y}_j(t)\).
Bei jedem Schritt wird der Mitgliedschaftsvektor jedes Knotens durch einen gewichteten Durchschnitt der Mitgliedschaftsvektoren seiner Nachbarn aktualisiert. Hierbei wird nicht \(A'\) genutzt, da die in \(A'\) eingebetteten indirekten Einflüsse in diesem Prozess natürlich zutage treten und eine Einbeziehung von \(A'\) das Ergebnis verzerren würde. Wenn allerdings \(S\) irreduzibel ist, was in ungerichteten Graphen oft der Fall ist, dann konvergiert das System zu einem Konsens, in dem alle Knoten denselben Mitgliedschaftsvektor haben. Um dies zu vermeiden, behandeln wir die Mitgliedschaftsvektoren der Anführer als unveränderlich, also
\(\textbf{y}_{l_i}(t+1)=\textbf{y}_{l_i}(t)=...=\textbf{y}_{l_i}(0)\).
Auf diese Weise modifizieren wir die Matrix \(A\), indem wir die Anführer nur mit sich selbst verbinden. Nach dieser Änderung bleibt die Matrix \(S\) eine stochastische Matrix, da jede Spalte sich auf \(1\) summiert, womit Konvergenz garantiert ist, da der größte Eigenwert von \(S\) \(1\) ist und seine Vielfachheit \(L\) ist.

Eigenschaften des Algorithmus’

Da der Algorithmus den Mitgliedschaftsvektor für jeden Knoten berechnet, erkennt er sehr leicht, wenn ein Knoten in mehreren Communities enthalten ist. Hierdurch können nicht nur Knoten erkannt werden, welche gut zu einem Anführer passen, sondern auch solche, die keiner Community zugeordnet werden können.

Der Algorithmus verfügt über die Fähigkeit Anführer zu erkennen. Durch die Erkennung des Anführers einer Community gewint man viele Informationen über diese, da Anführer naturgemäß die Community maßgeblich beeinflussen. Beispielsweise wird sich eine Community durch Entfernung eines Anführers sehr stark verändern - beispielsweise wird diese sich in mehrere aufteilen oder sogar komplett auflösen. Der Algorithmus erlaubt nicht nur die Erkennung von Anführern in Communities, sondern auch die Schaffung von Communities um vorher bestimmte Anführer herum.

Ein weiteres markantes Feature des Algorithmus ist die Erkennung von hierarchischen Organisationen. Der Vaterknoten eines Knotens kann einfach durch die Einflussmatrix und die Gesamteinflüsse bestimmt werden. Nachbarknoten können durch die Zuordnung zu gleichen Vaterknoten erkannt werden.

Quellen

  1. Stanoev, A., Smilkov, D., & Kocarev, L. (2011). Identifying communities by influence dynamics in social networks. Physical Review, 84(4). https://doi.org/10.1103/PhysRevE.84.046102