Alex Thill Manuel Drazyk Frederic Kerksieck
RWTH Aachen RWTH Aachen RWTH Aachen
alex.thill@rwth-aachen.de manuel.drazyk@rwth-aachen.de frederic.kerksieck@rwth-aachen.de


Struktur

  • Abstract
  • Einleitung
    • Motivation
    • Bedeutsamkeit des Algorithmus
  • Verwandte Arbeiten
    • LPA
  • Methodik
    • Vorstellung des Algorithmus
    • Darstellung der drei Phasen
      1. Initialisierung der Label
      2. Austausch der Labels zwischen Sprecher und Zuhörer
      3. Nachbearbeitung basierend auf den Labels der Knoten
    • Implementierung
    • Laufzeit
    • Animation
  • Experimente/Resultate
  • Zusammenfassung und Ausblick
  • Referenzen

Abstract

Personenspezifisches Marketing wird in Zeiten des Internets immer wichtiger, weshalb das erkennen von Communitys, also von Personengruppen mit vielen gleichen Interessen, auch immer wichtiger wird. Dabei befinden sich Personen meist in meherern Communitys gleichzeitig, wodurch diese sich überlappen.
Deshalb benötigen wir eine Möglichkeit, so effizient und präzise wie möglich, überlappende Communitys in einem sozialen Netzwerk zu finden.

Der hier vorgestellte Algorithmus ermöglicht genau dies, indem er verbundene Knoten Labels austauschen lässt, wobei sich die Knoten in der Rolle des Zuhörers, der die Labels seiner Nachbarn abfragt, abwecheln. Am Enden bilden dann die Knoten mit gleichen Labels eine Community.
Der Algorithmus hat eine lineare Laufzeit und erbringt ein besseres Ergebnis, als viele andere Algorithmen welchem zum suchen von überlappenden Communitys genutzt werden.

Mit Hilfe dieses Algorithmus wird also nicht nur effizient und effektiv nach überlappenden Communitys in Netzwerken gesucht, sondern es ist ebenfalls möglich die Kriterien und Informationen, die der Zuhörer abfragt, zu verändern und anzupassen, wodurch ein großes Potential für die Nutzung in anderen Forschungen gegeben ist.

Einleitung

Wenn wir den Umkreis beziehungsweise das Netzwerk einer Person betrachten, wird festgestellt, dass die meisten Menschen Kontakt zu mehr als nur einem anderen Menschen oder einer anderen Menschengruppe, wie z.B. Arbeitskollegen, Freunde oder Familie haben. Des Weiteren hat die große Mehrheit der Menschen mehrere Interessen und kann heutzutage mit Hilfe des Internets personalisiert die für Ihn interessanten aktuellen Nachrichten und Ankündigungen verfolgen.
Um dieses Netzwerk einer Person so genau wie möglich mit einem Algorithmus finden und nachstellen zu können, muss dieser also in der Lage sein „overlapping Communitys“, zu Deutsch etwa „übereinanderliegende Communitys“ zu erkennen.
Das Ziel dieser Algorithmen ist es einen Satz von Gruppen zu finden, in welchem jeder Knoten zu mindestens einer Gruppe gehört. In diesem Onlinebuch wird einen effizienter Algorithmus vorgestellt, der nicht nur diese übereinangerliegenden Communitys findet, sondern sogar einzelne übereinanderliegende Knoten, die sogenannten Schnittstellen dieser Communitys.

Verwandte Arbeiten

Die Erfindung eines Algorithmus welcher übereinanderliegende Communitys findet wurde von Palla (Palla et al., 2005) mit dem “clique percolation algorithm” (CPM) gemacht. Dieser liegt den Annahmen zugrunde, dass jede Community aus vollständig verbundenen Untergraphen besteht. In diesen werden die übereinangerliegenden Communitys dadurch gesucht, dass in einem Untergraphen ein Knoten gesucht wird, welcher mindestens mit einer bestimmten Anzahl an Kanten zu einem anderen Untergraphen gehört.
J. Baumes hingegen erfand mit dem “iterative scan alogrithm” (Baumes et al., 2005) einen Algorithmus, welcher sich dem Maximieren der lokalen Dichtefunktion widmete. Bei der Dichtefunktion handelt es sich um eine Funktion, die zeigt in welchen Teilen sich die übergebenen Werte am dichtesten scharen. Dabei werden solange Knoten hinzugefügt oder gelöscht bis die lokale Dichtefunktion nicht mehr weiter verbessert werden kann. Die Qualität der gefundenen Community ist dabei abhängig von dem sogenannten “seed”, der Startwert für einen Pseudozufallszahlenalgorithmus, welcher hier auch zum Erzeugen genutzt wird.
Mit Hilfe von “randomised local fitness maximisation” (LFM) (Lancichinetti et al., 2009) wird die Community eines zufälligen seed-Knoten solange erweitert, bis die Fitnessfunktion ihr lokales Maximum erreicht hat. Dabei ist zu beachten, dass LFM stark von einem Parameter der Fitnessfunktion abhängig ist, welcher die Größe der Community bestimmt.
CONGA (Gregory, 2007) erweitert das divisive Clusterverfahren, auch bekannt als Top-Down-Verfahren, dadurch dass er das Kopieren bzw. vervielfachen eines Knotens zulässt. Das divisive Clusterverfahren ist ein Verfahren, in dem zunächst alle Objekte welche einem Cluster zugehörig sind betrachtet werden und dann schrittweise die bereits gebildeten Cluster in immer kleinere Cluster aufgeteilt werden, bis jeder Cluster nur noch aus einem Objekt besteht. Desweiteren exstiert für jeden Weg zwischen zwei Knoten mindestens ein kürzester Weg, damit am wenigsten Kanten besucht werden. Betweeness ist die Anzahl all dieser kürzesten Wege, die durch den Knoten gehen. Bei Conga sind beide Teilungen der betweenness auf dem kürzesten Pfad der imaginären und der normalen Kante auf welchen betweenness betrachtet werden definiert. In CONGO (Gregory, 2008), einer Verfeinerung von CONGA, wird die lokale betweenness dazu genutzt die Geschwindigkeit des Algorithmus zu optimieren.
Der “label propagation algorithm” (LPA) (Raghavan et al., 2007) wird ebenfalls für die Entdeckung von übereinanderliegende Communitys genutzt und ist außerdem der Algorithmus auf den SLPA basiert. Im Gegensatz zum SLPA besteht dieser jedoch aus fünf Schritten. In den ersten beiden Schritten werden zunächst die Labels aller Knoten initialisiert und die einfache Zählvariable t auf 1 gesetzt. In Schritt 3 werden die Knoten im Netzwerk in einer zufälligen Reihenfolge neu zusammengesetzt und in Schritt 4 gibt jeder Knoten das häufigste Label seiner neuen Nachbarn zurück. Im fünften Schritt wird geprüft, ob das Label von jedem Knoten gleich dem Label von der maximalen Anzahl seiner Nachbarn ist. Sollte dies der Fall sein, wird der Algorithmus abgebrochen, ansonsten wird t um eins erhöht.
Copra (Gregory, 2010) ist ebenfalls eine Erweiterung von LPA, in welchem eine Anzahl von kleinen Communitys in einigen Netzwerken erstellt wird.
Mit “Fuzzy clustering” von Zang (Zhang et al., 2007) werden übereinangerliegende Communitys gefunden, dadurch dass die Spektralmethode genutzt wird um den Graphen in einen k-1 dimensionalen euklidischen Raum einzubinden, in welchem dann die Knoten vom “fuzzy c-mean algorithm” geclustered werden.
Auch wurde von Nepusz (Nepusz et al., 2008) versucht übereinangerliegende Communitys zu finden, dadurch dass er es als nichtlineares zeitabhängiges Optimierungsproblem modelliert und von Psorakis et al. (Psorakis et al., 2010) durch eine Modellierung basierend auf der bayesischen nichtnegativen Matrixfaktorisierung.
Das Benutzen von Links statt Knoten wurde ebenfalls analysiert (Ahn et al., 2010) (Evans & Lambiotte, 2010), jedoch führt die Knotenteilung in einem Link-Graph dazu, dass eine Kantenteilung des Originalgraphen entsteht.

Methodik

Vorstellung des Algorithmus

Wie in “Verwandte Arbeiten” bereits erwähnt wurde, handelt es sich bei dem Algorithmus um eine Erweiterung von LPA. Während jedoch beim LPA jeder Knoten nur ein Label hat, welches nach den am häufigsten vorkommenden Labeln seiner Nachbarn aktualisiert wird, wird bei SLPA jedem Knoten erlaubt alle nötigten Knoten auszulesen.
Jeder Knoten ist dabei entweder ein Zuhörer („listener“), wenn er Informationen sammelt bzw. nutzt oder ein Sprecher („speaker“), wenn er Informationen weitergibt. Dabei gilt, je öfter ein Knoten ein Label bei seinen Nachbarn einliest, desto wahrscheinlich wird dieses an andere Knoten weitergegeben. Dies geschieht durch die folgenden drei Schritte:

Darstellung der drei Phasen

1. Initialisierung der Knoten

Zu Beginn wird der Speicher jedes Knotens mit einem eindeutigen Label initialisiert, das einfach aus der ID des jeweiligen Knoten besteht.

2. Austausch der Labels zwischen Sprecher und Zuhörer

Die Knoten werden nacheinander in einer zufälligen Reihenfolge ausgewählt, wobei der ausgewählte Knoten zum Zuhörer („listener“) wird und alle seine Nachbarn zu Sprechern („speakers“). Alle Sprecher wählen jeweils aus ihrem Speicher ein Label nach einer Sprecher-Regel aus und senden dieses an den Zuhörer. Danach wählt der Zuhörer aus den empfangenen Labels ein Label nach einer Zuhörer-Regel aus und speichert dieses Label in seinem Speicher. Dies wird solange wiederholt, bis dass das Halte-Kriterium erfüllt ist.

Die Sprecher-Regel wählt ein zufälliges Label aus dem Speicher, wobei die Wahrscheinlichkeit, dass ein Label ausgewählt wird, proportional zu seiner Häufigkeit im Speicher ist.
Die Listener-Regel wählt aus den im aktuellem Schritt empfangenen Labels das aus, das am häufigsten empfangenen wurde.
Als Halte-Kriterium dient eine Anzahl an Iterationen T, die ausgeführt werden müssen.

3. Nachbearbeitung basierend auf den Labels der Knoten

Erst in der Nachbearbeitung wird entschieden, zu welchen Communitys ein Knoten gehört. Dazu wird für jeden Knoten aufgrund seines Speicherinalts eine Wahrscheinlichkeitsverteilung der Label aufgestellt. Je häufiger ein Label im Speicher vorkommt, desto größer die Wahrscheinlichkeit, dass der Knoten zu dieser Community gehört.
Die relative Häufigkeiten der Labels können nun für eine schwammige („fuzzy“) Community-Detektion (Gregory, 2011) benutzt werden, die angibt, wie stark ein Knoten zu einer Community gehört. In der Regel will man aber klare („crisp“) Communitys finden, daher eindeutig feststellen, ob ein Knoten zu einer Community gehört oder nicht. Dazu werden alle Labels aus dem Speicher eines Knoten entfernt, deren relative Häufigkeit unter einem Grenzwert r ∈ [0, 1] liegt. Verbundene Knoten, die dann noch über ein gleiches Label verfügen, werden zu einer Community gezählt. Hat ein Knoten meherere verschiedene Labels, liegt er in mehreren Communitys. Ineinander verschachtelte Communitys werden noch entfernt, damit die resultierenden Communitys maximal sind, daher keine kleineren entahlten. Da diese Phase unabhängig von der 2. Phase ist, kann die Berechnung für verschiedene Grenzwerte r ausgeführt werden, ohne dass Phase 2 neu berechnet werden muss. Abhängig von r liefert der Algorithmus unterschiedlich gute Ergebnisse.

Abbildung 1. Verhältnis der gefundenen Communitys zu den tatsächlich vorhandenen für verschiedene Werte von r auf einem Graphen mit 1000 Knoten und 44 Communitys, erstellt mit LFR.

Wird r zu klein gewählt, werden zu viele Communitys gefunden, die nicht vorhandenen sind und wenn r zu groß ist, werden nicht alle Communitys entdeckt (Abbildung 1). In der Praxis liefert ein Wert zwischen 0.1 und 0.15 gute Ergebnisse.

Implementierung

1.  Algorithm 1: SLPA(T,r)
2.  [n, Nodes] = loadnetwork;
3.  // Stage 1: Init
4.  for i = 1:n do
5.      Nodes(i).Mem = i;
6.  // Stage 2: Evolution
7.  for t = 1: T do
8.      Nodes.ShuffleOrder();
9.      for i = 1:n do
10.         Listener = Nodes(i);
11.         Speakers = Nodes(i).getNbs();
12.         for j = 1:Speakers.len do
13.             LabelList(j) = Speakers(j).speakerRule();
14.         w = Listener.listenerRule(LabelList);
15.         Listener.Mem.add(w);
16. // Stage 3: post-processing
17. for i = 1:n do
18.     remove Nodes(i) labels seen with probability < r;

Algorithmus 1, wie vorgestellt in (Xie et al., 2011)

Wie in Algorithmus 1 sichtbar wird (z.B. Zeile 5), hat jeder Knoten seinen eigenen Speicher, in dem alle bisher aufgenommenen Labels stehen. Jeder Knoten ist beim SLPA also in der Lage, auch ältere, gespeicherte Informationen zu nutzen, anstatt diese wie beim LPA (Raghavan et al., 2007) nach jeder Iteration zu verwerfen. Falls die Speichergröße nur ein Label umfasst und die Anzahl der Iterationen T groß genug gewählt ist, reduziert sich der SLPA jedoch auf den LPA.

Der SLPA durchläuft – im Gegensatz zum LPA, der nach einer gewissen Laufzeit konvergiert - eine feste Anzahl T an Iterationen. Aufgrund der zufälligen Reihenfolge der Listener (Zeile 8) ist der SLPA nicht deterministisch, jedoch wird ab T ≥ 20 eine gewisse Stabilität erreicht, unabhängig von der Netzwerkgröße und Struktur (Xie et al., 2011).

Die Speaker- und Listener-Rules (Zeilen 13-14) sind sehr wichtig für den Algorithmus, da diese die Weitergabe und Speicherung von Informationen in den einzelnen Knoten bestimmen. Eine beispielhafte Implementierung könnte hierbei so aussehen, dass die Speaking-Rule ein zufälliges Label aus dem Speicher eines Speakers liest und dieses an den Listener sendet, wobei die Wahrscheinlichkeit der Weitergabe eines Label hierdurch von dessen relativer Häufigkeit im Speicher des Speakers abhängt. Die Listener-Rule wählt anschließend ein Label aus allen Empfangenen aus (Hier beispielhaft: das häufigste empfangene Label), das dann in den Speicher des Listeners geschrieben wird.

Nachdem die ersten beiden Phasen abgeschlossen sind, erhält man ein Netzwerk, in dem jeder Knoten einen Zugehörigkeitsgrad (Stärke (Xie et al., 2011)) zu angrenzenden Communitys hat, der durch die relative Häufigkeit des Labels der jeweiligen Community definiert wird. Diese Stärke der Assoziation mit einer Community kann anschließend für Fuzzy Community Detection (Gregory, 2011) verwendet werden. Alternativ (Zeilen 17-18) kann man durch das Post-Processing schwache Assoziationen aus dem Netzwerk herausfiltern, damit die Mitgliedschaft jedes Knotens in einer Community binär wird. In der Praxis wählt man dann einen Schwellenwert r ∈ [0, 1] und löscht alle Labels mit relativer Häufigkeit kleiner r aus dem Speicher der jeweiligen Knoten. Enthält ein Knoten nach dem Post-Processing mehrere Labels, so ist dieser überlappend, jedoch ist beim SLPA die Anzahl der Mitgliedschaften eines Knotens nur beschränkt durch den selbst gewählten Parameter r und dem Grad dieses Knotens.

Laufzeit

(Im folgenden wird explizit von der oben beschriebenen Implementierung gesprochen.)

Die Initialisierung des SLPA liegt für n Knoten in O(n), da jeder Knoten nur mit seiner eigenen ID als erstes Label beschriftet wird. Der Großteil der Laufzeit fällt jedoch auf die 2. Phase des Algorithmus: Während die äußere Schleife (Zeile 7 ff.) T mal durchlaufen wird (s.o.), wird die innere Schleife (Zeile 9 ff.) n mal ausgeführt, wobei diese die Speaker-Rule für jeden Nachbarn des gerade behandelten Knotens aufruft und anschließend einmal die Listener-Rule.

Das zu sendende Label des Speakers wird zufällig aus allen Labels des Knotens ausgewählt, also liegt die Laufzeit der Speaker-Rule in O(1) und die Speaker-Rule wird für jeden Nachbarn des behandelten Knotens aufgerufen. Die Gesamtheit aller ausgeführten Speaker-Rules liegt also in O(K), mit K als Durschnittsgrad aller Knoten. Die Listener-Rule hat die Laufzeit O(K), da alle empfangenen Labels überprüft werden müssen.

Das Post-Processing überprüft für jeden der n Knoten bis zu T verschiedene Labels auf ihre relative Häufigkeit und liegt damit in O(Tn).

Insgesamt liegt die Laufzeit des Algorithmus also in O(TnK), oder auch O(Tm) für die Anzahl aller Kanten m (Xie & Szymanski, 2012), im Falle dünn besetzter Netzwerke verringert sich die Laufzeit auf O(Tn).

Experimente/Resultate

A. Benchmarks

Um das Verhalten von SLPA zur Erkennung von überlappenden Communitys zu untersuchen, haben wir ein paar Experimente auf synthetischen Netzen durchgeführt, die mit LFR generiert wurden. Außerdem haben wir SLPA mit zwei anderen Algorithmen zur Erkennung von überlappenden Communitys verglichen.

Für die folgenden Experimente haben wir Netzwerke der Größe n = 1000 genutzt mit folgenden Parametern:

  • durchschnittlicher Knotengrad: k = 20
  • maximaler Knotengrad: kmax = 50
  • Communitygröße: 10 < c < 50
  • Mixing-Parameter: 0.1 < μ < 0.2
  • Anzahl überlappender Knoten: On = 100
    Die Anzahl an Communitys zu denenen ein überlappender Knoten gehört Om, haben wir von 2 bis 8 varieren gelassen.

Zum Vergleichen haben wir die Algorithmen MONC (Havemann et al., 2011) und CLIZZ (Li et al., 2012) genommen.
Für SLPA haben wir die Parameter Anzahl der Iteration T = 100 und Grenzwert r = 0.15 gewählt.

Abbildung 2. Laufeit der 3 Algorithmen für verschiedene Werte Om

Abbildung 3. Omega Index der von den 3 Algorithmen generierten Cover für verschiedene Werte Om

Abbildung 4. ENMI der von den 3 Algorithmen generierten Cover für verschiedene Werte Om

B. Resultate

Von der Laufzeit her, sind SLPA und CLIZZ wesentlich besser, als MONC. CLIZZ ist allerdings noch ein Stück schneller, als SLPA.
Die generierten Cover der Algorithmen haben wir bezüglich des Extended Normalized Mutal Information (ENMI), vorgeschlagen von Lancichinetti (Lancichinetti et al., 2009) und des Omega Index (Murray et al., 2012) verglichen. Im Falle des Omega Index prodzieren alle drei gute Werte nahe 1, wobei SLPA zwischen MONC und CLIZZ liegt. Für den ENMI sind die Resultate nicht so gut, allerdings liegen die drei Algorithmen wieder nahe beieinander, wobei SLPA und MONC gleichauf liegen und CLIZZ der beste ist.

Zusammenfassung/Ausblick

Dieses Paper beschreibt den SLPA und erklärt dessen Idee, menschliches Sozialverhalten zu imitieren, um so Communitys in Graphen zu entdecken. Die hier vorgestellte Implementierung ist leicht zu modifizieren, was die Speaker-/Listener-Rules oder das Post-Processing angeht. Dies erleichtert es, den Algorithmus an die jeweiligen Bedürfnisse anzupassen. Zudem bietet der Algorithmus große Vorteile in seiner, je nach Netzwerk, fast linearen Laufzeit, Nachteile liegen jedoch bei der Stabilität: Da der SLPA keine einzelne Lösung findet, sondern eine Menge an Lösungen, ist der Algorithmus auf manchen Graphen nicht dazu geeignet, über längere Zeit Veränderungen in Netzwerken festzustellen. Eine mögliche Lösungsstrategie dafür wurde beim Labelrank (Xie & Szymanski, 2013) diskutiert. Zudem ist es vorstellbar, in Zukunft die Daten der ersten zwei Phasen bezüglich unscharfen Communitys zu untersuchen (Gregory, 2011).

Referenzen

  1. Palla, G., Derényi, I., Farkas, I., & Vicsek, T. (2005). Uncovering the overlapping community structure of complex networks in nature and society. Nature, 435(7043), 814–818.
  2. Baumes, J., Goldberg, M. K., Krishnamoorthy, M. S., Magdon-Ismail, M., & Preston, N. (2005). Finding communities by clustering a graph into overlapping subgraphs. IADIS AC, 5, 97–104.
  3. Lancichinetti, A., Fortunato, S., & Kertész, J. (2009). Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3), 033015.
  4. Gregory, S. (2007). An algorithm to find overlapping community structure in networks. Knowledge Discovery in Databases: PKDD 2007, 91–102.
  5. Gregory, S. (2008). A fast algorithm to find overlapping communities in networks. Joint European Conference on Machine Learning and Knowledge Discovery in Databases, 408–423.
  6. Raghavan, U. N., Albert, R., & Kumara, S. (2007). Near linear time algorithm to detect community structures in large-scale networks. Physical Review E, 76(3), 036106.
  7. Gregory, S. (2010). Finding overlapping communities in networks by label propagation. New Journal of Physics, 12(10), 103018.
  8. Zhang, S., Wang, R.-S., & Zhang, X.-S. (2007). Identification of overlapping community structure in complex networks using fuzzy c-means clustering. Physica A: Statistical Mechanics and Its Applications, 374(1), 483–490.
  9. Nepusz, T., Petróczi, A., Négyessy, L., & Bazsó, F. (2008). Fuzzy communities and the concept of bridgeness in complex networks. Physical Review E, 77(1), 016107.
  10. Psorakis, I., Roberts, S., & Sheldon, B. (2010). Efficient bayesian community detection using non-negative matrix factorisation. ArXiv Preprint ArXiv:1009.2646.
  11. Ahn, Y.-Y., Bagrow, J. P., & Lehmann, S. (2010). Link communities reveal multiscale complexity in networks. Nature, 466(7307), 761–764.
  12. Evans, T. S., & Lambiotte, R. (2010). Line graphs of weighted networks for overlapping communities. The European Physical Journal B-Condensed Matter and Complex Systems, 77(2), 265–272.
  13. Gregory, S. (2011). Fuzzy overlapping communities in networks. Journal of Statistical Mechanics: Theory and Experiment, 2011(02), P02017.
  14. Xie, J., Szymanski, B. K., & Liu, X. (2011). Slpa: Uncovering overlapping communities in social networks via a speaker-listener interaction dynamic process. Data Mining Workshops (ICDMW), 2011 IEEE 11th International Conference On, 344–349.
  15. Xie, J., & Szymanski, B. (2012). Towards linear time overlapping community detection in social networks. Advances in Knowledge Discovery and Data Mining, 25–36.
  16. Havemann, F., Heinz, M., Struck, A., & Gläser, J. (2011). Identification of overlapping communities and their hierarchy by locally calculating community-changing resolution levels. Journal of Statistical Mechanics: Theory and Experiment, 2011(01), P01023.
  17. Li, H.-J., Zhang, J., Liu, Z.-P., Chen, L., & Zhang, X.-S. (2012). Identifying overlapping communities in social networks using multi-scale local information expansion. The European Physical Journal B-Condensed Matter and Complex Systems, 85(6), 1–9.
  18. Murray, G., Carenini, G., & Ng, R. (2012). Using the omega index for evaluating abstractive community detection. Proceedings of Workshop on Evaluation Metrics and System Comparison for Automatic Summarization, 10–18.
  19. Xie, J., & Szymanski, B. K. (2013). Labelrank: A stabilized label propagation algorithm for community detection in networks. Network Science Workshop (NSW), 2013 IEEE 2nd, 138–143.