Datensätze für signierte soziale Netzwerke

Abstract

Bei der Modellierung von sozialen Netzwerken werden oft nur positive Beziehungen zwischen Individuen betrachtet. Um die Komplexität eines sozialen Netzwerkes besser darzustellen kann es jedoch sinnvoll sein auch negative Beziehungen zu betrachten. Dies ermöglichen vorzeichenbehaftete soziale Netzwerke, die zwischen positiven und negativen Beziehungen unterscheiden. Wir wollen uns im folgenden mit Datensätzen für vorzeichenbehaftete soziale Netzwerke beschäftigen. Dafür werden wir einige Datensätze sowie Datenformate vorstellen und deren Kompabilität mit dem WebOCD-Tool sowie einigen OCD-Algorithmen prüfen. Es ist einfach Datensätze für vorzeichenbehaftete Netzwerke zu finden. In der Realität wird man fast überall wo man positive Beziehungen zwischen Menschen beobachten kann, auch negative Beziehungen beobachten können. So können insbesondere auch gängige soziale Medien wie Facebook, Twitter, etc als Datensätze benutzt werden. Es ist jedoch schwierig aus den Datensätzen ein vorzeichenbehaftetes Netzwerk zu modellieren, da wenige Soziale Medien explizit negative Interaktions-Features besitzen.

Inhaltsverzeichnis

1. Einleitung
2. Methodik
3. Related Works
4. Anwendung/Experimente
   1. Vorstellung der Datensätze
   2. Anwendung mit dem WebOCD
5. Zusammenfassung
6. Referenzen

1. Einleitung

Jeder, der in den sozialen Netzwerke aktiv ist, kennt den „Freund hinzufügen“ Button. Dadurch kann man sich ganz leicht mit anderen Menschen vernetzen. Ebenso leicht können die Soziale Netzwerke dadurch herausfinden, wo in dem Netzwerk sich Communities befinden. Auch wenn es in den Sozialen Netzwerke meist keine Interaktion für Feindschaften gibt, können trotzdem die Soziale Netzwerke herausfinden, wo in dem Netzwerke sich Feindschaften befinden, indem sie z.B. Sprachanalyse text-basierte Interaktionen auswerten und klassifizieren. Solche Netzwerke nennt man auch „signed networks“. Solche Netzwerke lassen sich durch einen gewichteten Graphen modellieren. Jeder Nutzer des Netzwerks ist dabei ein Knoten im Graphen. Die Kanten zwischen zwei Knoten haben entweder das Gewicht 1, falls eine Freundschaft vorliegt, oder das Gewicht -1, falls eine Feindschaft vorliegt. die Graphen lassen sich durch Datensätze beschreiben. In dieser Arbeit solle es darum gehen, ob man öffentlich zugänglicheDatensätze von unsigned social networks an die OCDA Algorithmen anpassen kann, und wie gut die Algorithmen dann darauf laufen können

2. Related Works

Algorithmen zur Findung von Gemeinschaften waren schon Bestandteil von vielen wissenschaftlichen Arbeiten. So wurde der Signed DMID Algorithm schon im Beitrag „DMID“ aus Auflage 1 erklärt. Auf dem Signed Probablistic Mixture Algorithm ist (Chen et al., 2014) genaustens drauf eingegangen. Im Beitrag „Neue OCDA für vorzeichenbehaftete Netzwerke“ aus Auflage 4 wurde auf evolutionäre Algorithmen eingegangen, zu denen auch der Evolutionary Algorithm based on Similarity gehört. Außerdem haben sich (Esmailian & Jalili, 2015) mit einem Algorithmus beschäftigt, welcher auf dem Constant Potts Model basiert.

3. Methodik

Datensätze

Das Stanford Network Analysis Project (SNAP) ist ein Projekt der Stanford Universität zur Analyse von Netzwerken und Graph Mining (Stanford Large Network Dataset Collection, 27.06.2021). Das Projekt wurde 2004 gegründet und wird seit dem entwickelt. Neben Werkzeugen zur Netzwerkanalyse umfasst das Projekt auch eine Sammlung von verschiedenen Netzwerk Datensätzen, die Stanford Large Network Dataset Collection. Wir haben aus dieser Sammlung 4 Datensätze zu signierten (vorzeichenbehafteten) sozialen Netzwerken ausgewählt, um diese mit dem WebOCD zu analysieren:

• WikiElections: Ein Datensatz zu den Wahlen von Wikipedia Administratoren
• Epinions: Ein Datensatz zu den User-Beziehungen auf dem sozialen Netzwerk Epinions
• Slashdot: Ein Datensatz zu den User-Beziehungen auf der Webseite Slashdot
• Reddit: Ein Datensatz zu den Interaktionen zwischen Communities auf dem sozialen Netzwerk Reddit

WebOCD

Das WebOCD ist ein Projekt der RWTH zur Anwendung von OCD Algorithmen (Overlapping Community Detection). Das Projekt ist open-source und bietet einen Web-Client als Interface für Benutzer an. Zur Analyse von Netzwerken wird eine Vielzahl von Algorithmen angeboten, die man auf Datensätzen, die man zuvor hochgeladen hat, anwenden kann. Außerdem können verschieden Metriken für die jeweilgen Ergebnisse eines Algorithmus berechnet werden.

Für die Analyse der Datensätze, die wir ausgewählt haben, haben wir diese zunächst für das WebOCD angepasst und dort hochgeladen. Da es sich bei unseren Datensätzen um signierte Netzwerke handelt, haben wir für die Analyse Algorithmen verwendet, die mit negativen Kantengewichten kompatibel sind. Im WebOCD sind dies folgende Algorithmen:

• Signed DMID Algorithm: Um eine Community in einem Netzwerk zu finden, arbeitet der DMID in zwei Phasen auf dem Netzwerk. In Phase 1 versucht der Algorithmus die Anführer in dem Graphen zu finden. Ein Anführer ist ein stark vernetzter Knoten, der mit anderen Knoten kommuniziert, die nicht sehr stark vernetzt sind. Dazu berechnet der Algorithmus jeweils den Grad der Knoten. Wenn ein Knoten einen hohen Grad hat, werden die Knoten, mit denen er vernetzt ist untersucht, ob sie einen niedrigen Grad haben. Ist dem so, wurde ein Anführer gefunden. In der zweiten Phase wird überprüft, welchen Einfluss der Anführer auf die Knoten in seiner Umgebung hat. Dazu überprüft der Algorithmus wie lange die Knoten in der Umgebung brauchen, um das Verhalten des Anführers zu übernehmen. Im Beitrag „DMID “ von Auflage 1 wurde näher auf den Algorithmus eingegangen.
• Signed Probablistic Mixture Algorithm: Der Signed Probablistic Mixture Algorithmus ist eine Variante des probabilistic mixture model. Er basiert auf der Erwartungsmaximierungsmethode und kann überlappende Communities in ungerichteten signierten Netzwerken erkennen. Der Algorithmus übertrifft andere Algorithmen beim Erkennen von Communities in synthetic signed networks (Chen et al., 2014).
• Evolutionary Algorithm based on Similarity: Der Evolutionary Algorithm based on similarity ist ein evolutionärer Algorithmus. Evolutionäre Algorithmen sind an der Natur orientierte Optimierungsverfahren. Dazu werden im Graph eine Gruppen von Lösungskandiaten, auch Chromosome genannt, ausgewählt, die vielleicht Commmunitys bilden. Eine Fitnessfunktion weist durch Evaluation den Chromosomen einen Wert zu. Für die Rekombination werden dann Chromosome ausgewählt und kombiniert. Falls es zu einer zufälligen Änderung, Mutation genannt, der Nachfahren kommt, werden die dadurch neu entstandenen Generationen nochmal evaluiert und ausgewählt.

Weitere Analyse

Zusätzlich zu den Algorithmen die im WebOCD implementiert sind analysieren wir die Datensätze mit einem Algorithmus der auf dem Constant Potts Model basiert. Der Algorithmus wurde von Pouya Esmailian und Mahdi Jalili für das Finden von Communities in signierten Netzwerken entworfen (Esmailian & Jalili, 2015).

Anpassung der Datensätze

Die ausgewählten Datensätze liegen in der Stanford Large Network Dataset Collection in unterschiedlichen Formaten vor und haben eine Größe von 100.000 bis über 800.000 Kanten. Um die Datensätze für die Analyse mit dem WebOCD vorzubereiten, haben wir die Datensätze in ein einheitliches Format gebracht und deren Größe auf <10.000 Knoten und ~50.000 Kanten reduziert. Für die Anpassung der Datensätze haben wir Python verwendet.

Zunächst haben wir die unbearbeiteten Datensätze ausgelesen und daraus eine Liste von Knoten und Kanten generiert. Die Vorgehensweise haben wir dabei jeweils an das Format des ursprünglichen Datensatz angepasst. Bei der Verkleinerung der Datensätze haben wir die Datensätze auf ihre “wichtigsten” Knoten (die Knoten mit den meisten Interaktionen) reduziert. Dafür haben wir den Grad der jeweiligen Knoten berechnet, also die Anzahl der ein- und ausgehenden Kanten (Interaktionen), und eine minimalen Grad festgelegt. Damit haben wir den Teilgraph über den Knoten, deren Grad größer gleich dem von uns festgelegten Schwellenwert war, berechnet. Zusätzlich haben wir isolierte Knoten und Self-Loops sowie Kanten mit Gewicht 0 entfernt. Die reduzierten Graphen haben wir dann im Format Weighted Edge List (Liste gewichteter Kanten) abgespeichert, um die reduzierten Datensätze zu erhalten.

Zusätzlich haben wir auch den Teilgraphen der reduzierten Datensätze berechnet, welcher nur positive Kanten enthält. Damit können wir vergleichen wie die Anwesenheit bzw Abwesenheit von negativen Kanten die Ergebnisse der Algorithmen beeinflusst.

4. Anwendung/Experimente

4.1 Vorstellung der Datensätze

WikiElections

Der WikiElections Datensatz umfasst das Abstimmungsverhalten von Nutzern in Administrator Wahlen für Wikipedia bis zum 3.1.2008. Wikipedia ist eine Online-Enzykopädie, deren Inhalt kollaborativ von Nutzern verwaltet wird. Um Administrator zu werden muss ein Nutzer von anderen Nutzern in einer Wahl bestätigt werden. Dabei können die Nutzer der Wahl zustimmen (1), sich neutral verhalten (0) oder ablehnen (-1). Der Datensatz umfasst die Daten zu ~2.500 Wahlen mit ~100.000 Stimmen von ~7.000 Nutzern. Der Datensatz befindet sich in einem Format, das den Kontext der Wahlen wiederspiegelt:

   E: did the elector result in promotion (1) or not (0)
   T: time election was closed
   U: user id (and screen name) of editor that is being considered for promotion
   N: user id (and screen name) of the nominator
   V: vote(1:support, 0:neutral, -1:oppose) user_id time screen_name

Für uns sind dabei relevant der Nutzer über den abgestimmt wird (U) und die Stimmen der anderen Nutzer (V). Beim Auslesen der Daten haben die Stimme eines Nutzers in einer Wahl über einen Nutzer als Kante vom abstimmenden Nutzer zum kanidierenden Nutzer mit dem Kantengewicht, das dem jeweiligen Abstimmungsverhalten entspricht, behandelt. Die Menge der Knoten ist die Menge der Nutzer die im Datensatz vorkommen. Der vollständige Datensatz hat folgende Eigenschaften:

Um den Datensatz zu verkleinern haben wir nun den Schwellenwert 60 genutzt. Da wir den Graphen auf die Knoten mit hohem Grad reduzieren, muss der Schwellenwert relativ weit über dem Median und auch dem Durchschnitt gesetzt werden, weil beim entfernen der Kanten mit niedrigem Grad die Anzahl der Kanten nur gering sinkt. Der reduzierte Graph, den wir berechnet haben, hat folgende Eigenschaften:

Epinions

Epinions.com ist ein wer-vertraut-wem online Soziales-Netzwerk in der man generelle Konsumentenbewertungen schreiben kann. Die Mitglieder können sich gegenseitig vertrauen und damit zeigen wie vertrauenswürdig Bewertungen sind ,um am Ende zu bestimmen welche Bewertungen dem Nutzer gezeigt werden. Der Epinions Datensatz zeigt die Vertrauensbeziehungen zwischen den Mitgliedern um ihren Bewertungen zu vertrauen. Dadurch entsteht das Web of Trust(Netz des Vertrauens).

Im Folgenden sehen wir die Nutzer/Mitglieder die als Knoten dargestellt sind und die Kanten stehen für das Vertrauen untereinander.

Um den Datensatz zu verkleinern haben wir nun den Schwellenwert 400 genutzt. Der reduzierte Graph, den wir berechnet haben, hat folgende Eigenschaften:

Slashdot

Slashdot ist eine technologiebezogene Nachrichten Website und ist bekannt für ihre spezielle User-Community. Die Website enthält die von Mitgliedern selbst geschriebenen aktuellen Nachrichten rund um Technologie. 2002 hat Slashdot eingeführt, dass Mitglieder sich gegenseitig als Freunde oder Feinde markieren können. Dieser Datensatz enthält die Freundschafts-/Feindschaftsverbindungen zwischen den Mitgliedern von Slashdot. Die Daten wurde im Februar 2009 erhoben.

Im Folgenden sehen wir die Nutzer/Mitglieder die als Knoten dargestellt sind und die Kanten stehen für die Freundschafts-/Feindschaftsverbindungen untereinander.

Um den Datensatz zu verkleinern haben wir nun den Schwellenwert 150 genutzt. Der reduzierte Graph, den wir berechnet haben, hat folgende Eigenschaften:

Reddit

Reddit ist eine Website mit mehreren Communities, die wiederum Mitglieder haben, die da rein posten können zu bestimmten Themen. Die Communities bei Reddit nennt man Subreddit. Im Datensatz Reddit Hyperlink Netzwerk werden die direkten Verbindungen zwischen 2 Subreddits aufgefasst. Es werden auch Subreddit Einbettungen zur Verfügung gestellt. Das Netzwerk wird aus den öffentlichen Redditdaten entnommen von 2,5 Jahren( von Januar 2014 bis April 2017).

Die Hyperlink Netzwerke zwischen 2 Subreddits sind extrahiert von Posts die einen Hyperlink erstellen von einem Subreddit zum anderen. Man sagt ein Hyperlink stammt vom Post aus der Quellen-Community und verbindet einen Post aus der Ziel-Community. Das Netzwerk ist gerichtet, signiert, zeitlich und zugeschrieben. Die Knoten stehen für die einzelnen Communities und die Kanten für die Hyperlinks zwischen den Subreddits die einen Wert von 1 oder -1 annehmen können.

Um den Datensatz zu verkleinern haben wir nun den Schwellenwert 400 genutzt. Zusätzlich haben wir nach dem reduzieren des Graphen parallele Kanten verschmolzen. Dabei haben wir die Gewichte der Kanten summiert, so dass eine große Zahl positiver bzw negativer Interaktionen auch zu einer entsprechend stärkeren Gewichtung führt. Der reduzierte Graph, den wir berechnet haben, hat folgende Eigenschaften:

4.2 Anwendung mit dem WebOCD

WikiElections

Die Anwendung der Algorithmen auf dem reduzierten WikiElections Datensatz hat ergeben:

Sowohl der SDMID Algorithmus, als auch der MEA Algorithmus liefern nur eine Community als Ergebnis. Die beiden Algorithmen liefern also für den Datensatz kein sinnvolles Ergebnis, zusätzlich hat der MEA Algorithmus eine sehr hohe Laufzeit. Der SPM Algorithmus und der CPM Algorithmus liefern 6 bzw 35 Communities als Ergebnis. Allerdings mit einer Modularität von 0,1662 bzw 0,1221. Die Qualität der Ergebnisse ist also auch nicht besonders gut.

Ergebnisse auf dem Subgraph der positiven Kanten:

SDMID liefert wie aud dem signierten Datensatz nur eine Community als Ergebnis. MEA liefert 5 Communities, allerdings mit Modularität 0,0110, also einer sehr schlechten Qualität.

Für den WikiElections Datensatz liefert keiner der Algorithmen ein gutes Ergebnis. Der Datensatz lässt sich mit unseren Methoden also nicht gut analysieren. SPM und CPM liefern noch die besten Ergebnisse.

Epinions

Die Anwendung der Algorithmen auf dem reduzierten Epinions Datensatz hat ergeben:

Auch hier liefern sowohl der SDMID Algorithmus, als auch der MEA Algorithmus nur eine Community als Ergebnis. Der SPM Algorithmus liefert 6 Communities mit einer Modularität von 0,1721. Die Qualität ist also relativ schlecht. Der CPM Algorithmus liefert 16 Communities mit einer Modularität von 0,4649. Der CPM Algorithmus ist an dieser Stelle also am besten um den Datensatz zu analysieren.

Ergebnisse auf dem Subgraph der positiven Kanten:

Der SDMID und SPM Algorithmus laufen auf dem positven Graphen sehr ähnlich wie auf dem signierten. Im Gegensatz zum signierten Graphen liefert der MEA Algorithmus hier 3 Communities. Allerdings ist die Modularität sehr gering, so dass man das Ergebniss als nicht sinnvoll betrachten kann.

Der Epinions Datensatz lässt sich mit den Algorithmen im WebOCD nicht gut analysieren. Der CPM Algorithmus liefert hier allerding ein gutes Resultat.

Slashdot

Die Anwendung der Algorithmen auf dem reduzierten Slashdot Datensatz hat ergeben:

Der MEA Algorithmus liefert 5 Communities als Ergebnis mit der Modularität 0,0061. Außerdem hat der ALgorithmus eine sehr hohe Laufzeit. Das Ergebnis ist also nicht sinnvoll. Der SPM Algorithmus und der CPM Algorithmus liefern 6 bzw 89 Communities mit Modularität 0,1842 bzw 0,2922. Die Ergebniss sind also sinnvoll, haben jedoch mittelmäßige Qualität. Das beste Ergebnis liefert der SDMID Algoritmus mit 9 Communities mit Modularität 0,3788.

Ergebnisse auf dem Subgraph der positiven Kanten:

Der MEA Algorithmus liefert hier 3 Communities mit Modularität 0,0388, ist also ähnlich schlecht wie auf dem signierten Datensatz. Der SDMID Algorithmus liefert 3 Communities mit Modularität 0,3776. Der Algorithmus läuft also ähnlich gut wie auf dem signierten Datensatz.

Für den Slashdot Datensatz können wir feststellen, dass dieser besonders mit dem SDMID Algorithmus kompatibel ist und sich auch mit dem SPM und CPM analysieren lässt, während der MEA Algorithmus keine vernünftigen Resultate liefert.

Reddit

Die Anwendung der Algorithmen auf dem reduzierten Reddit Datensatz hat ergeben:

Der SDMID Algorithmus liefert hier nur eine Community. Das Ergebnis ist also nicht sinnvoll. Der MEA Algorithmus und der CPM Algorithmus liefern 4 bzw 8 Communitiers mit einer Modularität von 0,0089 bzw 0,0268. Beide Ergebnisse haben also schlechte Qualität. Der SPM Algorithmus liefert das beste Ergebnis mit 6 Communities und Modularität 0,1749. Auch dieses Ergebnis ist also nicht besonders gut.

Ergebnisse auf dem Subgraph der positiven Kanten:

Alle Algorithmen verhalten sich hier ähnlich wie auf dem signierten Datensatz: SDMID liefert eine Community und SPM 6 mit ähnlicher Modularität. MEA liefert hier 6 Communities, aber die Modularität ist ähnlich gering.

Der Reddit Datensatz lässt sich mit keinem der im WebOCD angebotenen Algorithmen gut analysieren und auch mit dem CPM Algorithmus nicht. Der SPM Algorithmus liefert die besten Resultate, die allerdings auch geringe Qualität haben.

5. Zusammenfassung

Die Ergebnisse der Algorithmen auf den Datensätzen sind sehr unterschiedlich. Der WikiElections und der Reddit Datensatz lassen sich mit keinem der Algorithmen gut analysieren. Der Epinions Datensatz lässt sich besonders gut mit dem CPM Algorithmus analysieren, der nicht im WebOCD implementiert ist. Der Slashdot Datensatz lässt sich am besten mit dem SDMID Algorithmus analysieren.

Der SPM Algorithmus liefert für alle Datensätze stabile Ergebnisse, allerdings ist die Qualität meist mittelmäßig. Der SDMID Algorithmus und der MEA Algorithmus liefern meist schlechte Ergebnisse, bis auf die Ausnahme Epinions mit SDMID. Dazu kommt die extrem hohe Laufzeit von MEA. Der CPM Algorithmus liefert mittelmäßige bis gute Resultate, ist allerdings nicht im WebOCD implementiert. Starke Unterschiede der Algorithmen auf rein positiven Datensätzen sind nicht zu finden.

Generell ist es schwierig Datensätze von signierten Sozialen Netzwerken zu analysieren. Außerdem sind die Datensätze aufgrund ihrer Größe nicht kompatibel mit dem WebOCD. Bei der Verkleinerung der Datensätze gehen Eigenschaften der orginalen Datensätze verloren.

6. Referenzen

1. Chen, Y., Wang, X. L., Yuan, B., & Tang, B. Z. (2014). Overlapping community detection in networks with positive and negative links. Journal of Statistical Mechanics: Theory and Experiment, 2014(3), P03021. http://stacks.iop.org/1742-5468/2014/i=3/a=P03021
2. Esmailian, P., & Jalili, M. (2015). Community Detection in Signed Networks: the Role of Negative ties in Different Scales. SCIENTIFIC REPORTS, 5, 14339. https://doi.org/10.1038/srep14339
3. Stanford Large Network Dataset Collection. (27.06.2021). https://snap.stanford.edu/data/#signnets