Ground Truth-Datensätze

Florian Bünker		Svetoslav Apostolov
RWTH Aachen University		RWTH Aachen University
florian.buenker@rwth-aachen.de		svetoslav.apostolov@rwth-aachen.de

Abstract

Jedes Netzwerk, egal ob biologisch, technologisch oder sozial, lässt sich als eine Struktur von vielen verbundenen Knoten betrachten. Diese hat in ihrer Basis eine Menge von Informationen, die empirisch bewiesen worden sind und damit stets gültig sind. Diese Datensätze werden Ground Truth-Datensätze genannt. Es gibt aber einen Mangel an Analyse von diesen Datensätzen und besonders davon, wie Overlapping Community Detection Algorithmen auf diesen angewendet werden und was von Ergebnisse zu erwarten sind. Deshalb hat diese Arbeit das Ziel, gewählte Algorithmen auf ein Ground-Truth Datensatz anzuwenden und den Unterschied zwischen diesen zu bestimmen. Bei vorläufigen Resultaten ist zu bemerken, dass verschiedene Communities entdeckt werden. Das deutet darauf hin, dass verschiedene Algorithmen in verschiedenen Anwendungsfällen optimal sind. Es wird also für zukünftige Arbeiten empfohlen, die Effekte dieser Algorithmen im Bezug zu Real World- und Ground-Truth Datensätzen zu analysieren und wie die besser zu Ground Truth Community Detection angepasst werden können.

___

Inhaltsverzeichnis

1. Einleitung
2. Verwandte Arbeiten
3. Methodik
   
   1. Problemstellung
   2. Disassortative Degree Mixing and Information Diffusion Algorithm
   3. SSK Algorithm
   4. CLiZZ Algorithm
   5. Speaker Listener Label Propagation Algorithm
4. Anwendung und Evaluierung
   
   1. Datensatz
   2. Gesamte Evaulierung
   3. Disassortative Degree Mixing and Information Diffusion Algorithm
   4. SSK Algorithm
   5. CLiZZ Algorithm
   6. Speaker Listener Label Propagation Algorithm
5. Zusammenfassung
6. Referenzen

---

1. Einleitung

In Overlapping Community Detection (im Folgenden als OCD abgekürzt) bedeutet das Ground Truth eine dem Community zugrunde liegende Verbindung, die allen Mitgliedern davon betrifft. Es ist eine Beschreibung davon, worauf die Community basiert. Ground Truth lässt sich am häufigsten bei Real World-Datensätze bestätigen, wie diese aus sozialen Netzwerken oder aus der realen Welt. In dem sozialen Netzwerk Facebook zum Beispiel ist das Ground Truth ein gemeinsames Interesse von Nutzern. Ground Truth Communities sind dann die jeweiligen Gruppen, die auf diesem Interesse zentriert sind. Es lässt sich annehmen, dass die Nutzer in einer solchen Gruppe eine Beziehung zueinander haben, entweder indem sie Diskussionen führen, Freunde sind oder dieselben Beiträge kommentieren.

Solche Beziehungen lassen sich als Kanten des Communty-Graphs behandeln. Wegen des Wesens von Ground Truth Communities sind diese oft als eine explizite Expression der Verhältnisse bezeichnet, die oft dem realen Leben entspricht. Häufige Beispiele sind “Freunde” (Facebook), “Subscriber” (Youtube) und “Follower” (Twitter, Instagram, Reddit).

Das Ground Truth spielt eine wichtige Rolle in OCD, weil es stabile Communities bildet und die Analyse die auf denen angewandte Algorithmen erleichtert. Die Verhältnisse zwischen Knoten sind eindeutig und haben eine stetige Interpretation. Es lassen sich aus diesen expliziten Beziehungen realitätsnahe Subcommunities ableiten. Jedoch gibt es keine Algorithmen, die besonders für Ground Truth-Datensätze geeignet sind. Das ist der Fall, weil die Definition von Ground Truth dynamisch ist - bei verschiedenen Datensätzen hat es eine verschiedene Bedeutung. Wegen der Vielfalt in OCD Algorithmen und deren Methodik ist auch das Finden von Ground Truth Communities schwer (Yang & Leskovec, 2012). Deshalb werden in dieser Arbeit vier OCD Algorithmen analysiert, damit ihre Effizienz und Genauigkeit in dem Umgang mit Ground Truth-Datensätzen und Netzwerken bestimmt wird.

2. Verwandte Arbeiten

In Kern dieser Arbeit steht das Papier von (Yang & Leskovec, 2012). Die vorgeschlagene Methodik zur Evaluation und Schlussfolgerungen über die Unterschiede zwischen OCD Algorithmen sind von größter Bedeutung für das Verstehen von Ground Truth Communities und die Schwierigkeiten bei deren Erkennung.

Außerdem haben die Autoren ein anderes, immer noch wichtiges Papier (Yang & Leskovec, 2014), das die Anführerknoten einführt, welche in unseren Schlussfolgerungen wichtig sind.

Alle andere Information wird aus Auflage 1 dieses Buchs entnommen, besonders die Artikel über DMID, SSK, CLiZZ, SLPA.

3. Methodik

3.1 Problemstellung

Zur Notation wird im Folgenden diese Symbole benutzt:

• \(G = (V,E)\) ist ein gerichtetes Graph G mit Knotenmenge V und Kantenmenge E.
• \(n = \vert V \vert\) ist die Anzahl von Knoten in G und \(m = \vert E \vert\) die Anzahl von Kanten.
• Für \(v,w \in V\) ist \((v,w) \in E\) eine gerichtete Kante von \(v\) nach \(w\).
• \(t_x\) ist für \(x \in\) {SDMID, SSK, CLiZZ, SLPA} die Laufzeit des betrachteten Algorithmus.

In dieser Arbeit werden vier ausgewählte Algorithmen, die für soziale Netzwerke geeignet sind, auf einen Datensatz mehrmals angewendet. Solche Algorithmen sind hier gewählt, weil Ground Truth Communities von Menschen natürlich gebildet werden. Um die Effizienz bei dem Umgang mit Ground Truth zu prüfen, müssen wir ein erwartetes Ergebnis definieren, mit dem wir die Ground Truth Communities vergleichen können. Die Vorgehensweise der Algorithmen wird demnächst kurz erläutert, aber für eine detaillierte und tiefe Erklärung davon wird empfohlen, die entsprechenden Kapitel in Auflage 1 dieses Buchs zu lesen.

3.2 Disassortative Degree Mixing and Information Diffusion Algorithm

Der Disassortative Degree Mixing and Information Diffusion Algorithmus (im Folgenden zu DMID gekürzt) basiert auf der Suche von lokalen und globalen Anführer. Knoten werden nach ihrem Anführerpotenzial bewertet, das eine Kombination von dem Grad des Knotens und die lokale Disassortivität, oder die Häufigkeit, dass Knoten von geringem Grad mit Knoten von hohem Grad verbunden sind, ist. Die globalen Anführer sind am wichtigsten, weil sie funktionelle Mittelpunkte der Communities sind. Diese gehen dann durch ein logisches Spiel, das die Knoten den Anführern zuweist.

Trotz seinem Anfang, der von Random Walks abhängt, ist dieser Algorithmus wegen der späteren strengen logischen Vorgehensweise stabil und realitätsnah, was für OCD von Ground Truth Communities bevorzugt wird.

3.3 SSK Algorithm

Der SSK Algorithmus benutzt eine Kombination von Einfluss-Matrizen und Anführern. Die Anführer werden wegen ihrem Einfluss oder Entfernung von anderen Knoten so bezeichnet, nicht wegen dem Grad wie in DMID. Der Algorithmus liefert das Ergebnis in einem Mitgliedschaftsvektor. Er ist somit fähig, nicht nur Anführer zu bestimmen, sondern Hierarchie zu interpretieren.

SSK ist für Ground Truth-OCD gut anwendbar, weil Hierarchien in verschiedenen sozialen Situationen zu finden ist. Ein Beispiel dafür wäre eine LinkedIn Organisation, wobei der Leiter einer Abteilung Verbindungen mit allen Abteilungsarbeiter hat.

3.4 CLiZZ Algorithm

CLiZZ führt einen zu Anführern ähnlichen Begriff - Leaders. Funktionell sind die Leaders dieselben wie SSK’s Anführer - einflussbasiert. Es wird aber auch bei deren Bestimmung der Grad benutzt. Random Walks kommen auch bei Community Detection in Frage.

CLiZZ ist ein Algorithmus, der die schon beschriebene DMID und SSK kombiniert, was sich in einen robusten und im Allgemein fähigen Algorithmus ergibt. Struktur und Hierarchie lassen sich auch mit CLiZZ finden, ohne dass globales Wissen bekannt werden muss. Deshalb betrachten wir auch CLiZZ und werden den Vergleich mit DMID und SSK betonen.

3.5 Speaker Listener Label Propagation Algorithm

Der Speaker Listener Label Propagation Algorithm (im Folgenden zu SLPA gekürzt) ist der einzige in dieser Arbeit betrachtete Algorithmus, der sich nicht mit der Suche von Anführern beschäftigt. Stattdessen werden zufällige Nodes ausgewählt, die als “Listener” bezeichnet sind. Die Nachbarn davon sind die “Speaker”.

Es lässt sich merken, dass dieser Algorithmus im Vergleich zu den anderen drei unstabiler ist, hauptsächlich wegen der Abweichung von dem Anführer als Konzept. Die Zufälligkeit der Listener-Auswahl ermöglicht viele Interpretationen von derselben Struktur. Jedoch ist dieser Algorithmus für unser Ziel nützlich, weil er direkte Nachbarschaften betrachtet, ohne globales Wissen abzurufen, was ähnlich zu der realen zwischenmenschlichen Prozesse des Gemeinschaftbeitretens ist.

4. Anwendung und Evaluierung

4.1 Datensatz

Wir haben uns für einen Datensatz entschieden, bei dem man leicht nicht nur vier Ground Truths erkennen kann, sondern auch einen nicht Ground Truth Datensatz. Der aus konect.cc genommene Datensatz zeigt die Verteilung von Innovationen von 246 ÄrztInnen in den Städten Peoria, Bloomington, Quincy und Galesburg (wobei man nicht weiß welches Cluster welche Stadt darstellt) und wurde 1966 gesammelt. Ein Knoten repräsentiert eine/n Arzt/Ärztin und eine Kante \((v,w)\) zeigt, dass der/die Arzt/Ärztin \(v\) den/die Arzt/Ärztin \(w\) als Freund/Freundin hat oder dass er/sie sich an die Person \(w\) wendet, wenn er/sie Hilfe benötigt oder an einer Diskussion interessiert ist. Es existiert immer nur eine Kante zwischen zwei Knoten auch wenn mehr als eine Bedingung der Wahrheit entsprechen. Der ganzen Datensatz bildet selbst kein Ground Truth, während die Stadtverteilung der vier Teildatensätze vier separate Ground Truths liefert - die Personen werden von ihrem Wohnort verbunden. Unsere Aufteilung der Ground Truths ist sehr simpel, da wir die jeweiligen Städte genommen haben, wobei diese nach Größe sortiert sind. D.h. das erste ist das Größte und das vierte - das kleinste Netzwerk.

Abb. 1 – Ganzes Netzwerk

4.2 Gesamte Evaluierung

Nun testen wir die die vier Algorithmen auf unseren Datensatz. Hierfür benutzen wir den WebOCD Dienst der RWTH Aachen. Die Parameter, die wir für die Algorithmen benutzt haben, sind die folgenden:

• DMID: iterationStep: 4.0, disassortativityEffectiveDegreeWeight: 0.5
• SSK: leadershipIterationBound: 1000, membershipsIterationBound: 1000, leadershipPrecisionFactor: 0.001, membershipPrecisionFactor: 0.001
• CLiZZ: membershipsIterationBound: 1000, membershipPrecisionFactor: 0.001, influenceFactor: 0.9
• SLPA: memorySize: 100, probabilityThreshold: 0.15

Als erstes vergleichen wir die Ergebnisse der vier Algorithmen untereinander und danach vergleichen wir die Ergebnisse der Algorithmen wenn diese nur auf den einzelnen Ground Truths angewendet werden mit den Ergebnissen des gesamten Netzwerkes. Fangen wir also mit dem Vergleich der Ergebnisse der vier Algorithmen auf das ganze Netzwerk an.

Algorithmus		Communities
DMID		6
SSK		32
CLiZZ		12
SLPA		23

Das erste was auffällt ist natürlich die unterschiedliche Anzahl an Communities die gefunden werden. Hierbei hat SSK am meisten Communities gefunden mit 32 und DMID hat am wenigsten gefunden mit nur 6 Communities. CLiZZ hatte hierbei 12 Communities gefunden und SLPA hatte 23 Communities gefunden. Dieses Ergebnis war ungefähr zu erwarten, da die beiden Algorithmen die die meisten Communities gefunden haben für soziale Netzwerke entwickelt wurden und versuchen menschliches verhalten zu imitieren wie bei dem SSK Algorithmus welcher beispielsweise auf der Entdeckung von Anführern basiert oder der SLPA Algorithmus der, wie der Name schon sagt, auf einen Speaker und Listener Prinzip aufbaut. Die beiden Algorithmen die weniger Communities gefunden haben basieren hingegen auf lokale Informationen wie der SSK Algorithmus oder ist eher auf Präzision ausgelegt wie der DMID Algorithmus.

Bei der Ausführungszeit ist SLPA der Langsamste, danach kommt SSK gefolgt von CLiZZ und der schnellste ist DMID.

Nun vergleichen wir die Ground-Truths als einzelne Netzwerke mit dem kompletten Netzwerk nachdem auf diesen die jeweiligen Algorithmen angewendet wurden.

4.3 Disassortative Degree Mixing and Information Diffusion Algorithm

Fangen wir mit dem DMID Algorithmus an. Dieser hatte bei den gesamten Netzwerk 6 Communities gefunden und das gleiche Ergebnis bekommt man auch wenn den Algorithmus einzeln auf die Netzwerke anwendet wobei im ersten Ground Truth 2, im zweiten und dritten jeweils einen und im vierten 2 Communities gefunden wurden, was der Erwartungen entspricht.

4.4 SSK Algorithm

Als nächstes schauen wir uns den SSK Algorithmus an. Wie vorher schon erwähnt hatte dieser beim gesamten Netzwerk die meisten Communities gefunden mit 32. Nachdem man dieses Algorithmus das dann auf die einzelnen Netzwerke anwendet bekommt man als Ergebnis auch 32 verschiedene Netzwerke wie man es auch erwarten würde wobei im ersten Ground Truth 12, im zweiten 6, im dritten 9 und im vierten 5 Communities gefunden wurden. Der Algorithmus verhält sich also wie erwartet.

4.5 CLiZZ Algorithm

Als letztes gucken wir uns den CLiZZ Algorithmus an welcher bei den gesamten Netzwerk 12 Communities gefunden hatte und dies ist hier auch das Ergebnis. Wie man es erwarten würde wobei die Verteilung der Communities auf die Ground Truths wie folgt: Ground Truth 1 hat 3 Communities, Ground Truth 2 hat 1 Communities, Ground Truth 3 hat 5 Communities und Ground Truth 4 hat 3 Communities. Die Zahl und Struktur der Communities sind gleich wie die erwarteten.

4.6 Speaker Listener Label Propagation Algorithm

Als letztes schauen wir uns den SLPA Algorithmus an. Wie schon bei den Vergleich der Algorithmen auf den ganzen Netzwerk gesagt wurde hat der Algorithmus 23 Communities gefunden. Wenn man den Algorithmus hingegen auf die einzelnen Ground-Truths als einzelne Netzwerke anwendet bekommt man aber insgesamt 32 Communities, wobei alleine schon im ersten Ground Truth 22 gefunden wurden. Die restlichen sind wie folgt verteilt - 1 im zweiten Ground Truth, 6 im dritten und 3 im vierten. Dies ist ziemlich interessant, da die 4 Ground-Truths keine Verbindungsknoten haben, weswegen man davon ausgehen würde, dass es zumindest eine ungefähr gleiche Anzahl an Communities finden sollte, wenn man die Anzahl aller einzelnen Netzwerke addiert.

Abb. 2 – Ganzes Netzwerk nach SLPA-Anwendung

Abb. 3 – Alle Teilnetzwerke nach SLPA-Anwendung

5. Zusammenfassung

Die Anzahl der Communities ist meistens das, was erwartet wird, zumindest wenn man sich darauf bezieht, welche Algorithmen mehr und welche weniger Communities finden. Selbes kann auch behaupten werden, nachdem man die Ergebnisse der Tests für die einzelnen Netzwerke im Vergleich zum gesamten analysiert. Die Ausnahme ist SLPA, welcher bei den einzelnen Netzwerken mehr Communities gefunden hat. DMID, SSK und CLiZZ dagegen liefern Ergebnisse, die vorschlagen, dass die drei Algorithmen effizient und präzis bei dem OCD von Ground Truth Communities sind.

6. Referenzen

1. Yang, J., & Leskovec, J. (2012). Defining and Evaluating Network Communities based on Ground-truth. In Y. Ding (Ed.), Proceedings of the ACM SIGKDD Workshop on Mining Data Semantics: Vol. abs/1205.6233 (pp. 1–8). ACM. https://doi.org/10.1145/2350190.2350193
2. Yang, J., & Leskovec, J. (2014). Structure and Overlaps of Ground-Truth Communities in Networks. ACM Transactions on Intelligent Systems and Technology, 5(2), 1–35. https://doi.org/10.1145/2594454