Vorhersage des sozialen Status in vorzeichenbehafteten Netzwerken (1)

Abstract

„Sage mir, mit wem du umgehst, so sage ich dir, wer du bist; weiß ich, womit du dich beschäftigst, so weiß ich, was aus dir werden kann“ - Johann Wolfgang von Goethe.

Gemeinschaften haben lange Zeit Menschen mit gemeinsamer Interessen, Verwandts- und Geschäftsbindungen zusammenvereint. Die Menschheit kann nach verschiedenen Kriterien immer noch in viele verschiedene Gruppen, Gemeinschaften und Gesellschaften unterteilt werden. Dieses Konzept liegt jedem fortschrittlichen und erfolgreichen Unternehmen, Projekt oder Start-up zugrunde. Viele Wissenschaftler, Soziologen und Psychologen haben ein erstaunliches Phänomen untersucht, das auf den ersten Blick absurd erscheint. Es wird verschiedene Namen und Beschreibungen dazu gegeben, aber die meisten kennen es als “Sechs Grade der Trennung” oder “Kleine-Welt-Phänomen”. Man kann mit Sicherheit sagen, dass es keinen Menschen auf der Welt gibt, der irgendwie mit keinem verbunden ist. Außerdem ist es nicht notwendig, eine Person persönlich zu kennen, um sich ihrer Hobbys oder Vorlieben bewusst zu machen. Eine hinreichend genaue Analyse der Persönlichkeit kann durchgeführt werden, indem man sich genau auf die Zusammenhänge und Gesellschaften stützt, in denen das Forschungsobjekt aufgenommen wurde. Darüber hinaus kann man verschiedene Annahmen treffen und sogar Erreignisse vorhersagen. Im Zeitalter der Netzwerktechnologien sind Informationen zur gefährlichsten Waffe der Welt geworden. Durch die Vorhersage des Status von Knoten in Netzwerken kann man bestimmte Weltereignisse zum Wohle der Menschheit entscheiden oder verhindern. Ist es nicht bewundernswert?

Inhaltsverzeichnis

1. Einführung
2. Verwandte Arbeiten
3. Setup
4. Methodik
5. Experimente
6. Kollation
7. Referenzen

1. Einführung

Viele komplexe Systeme im wirklichen Leben lassen sich als Netzwerke mit miteinander verbundenen Knoten darstellen. Mit Knoten meinen wir verschiedene Individuen, Objekte, Organisationen, die irgendwie auf unterschiedlichen Grundlagen miteinander verbunden sind. Als diese Grundlagen können gemeinsame Interessen, Verwandtschaft/Freundschaft, Religion, Wissen, Ziele dienen. Dass Netzwerke dazu neigen, sich dynamisch zu verändern, zu verformen oder Linke zu bilden, ist längst kein Geheimnis mehr. Außerdem ist es wichtig, welcher Eigenschaften diese Links besitzen, denn sie können sowohl direkt oder positiv als auch indirekt oder negativ konnotiert sein. Positive Links sind ein Zeichen von Freundschaft oder Vertrauen, während negative Links Feindseligkeit oder Misstrauen zeigen. Es gibt zwei Knotenmetriken, die als Optimismus und Reputation bekannt sind. Diese wiederum werden mit speziellen Knoten-Ranking-Scores Algorithmen berechnet und zur Verfügung gestellt. Dabei handelt es sich um Knotenmetriken von zwei untersuchten Knoten (sogenannte Treugeber und Treuhänder) in verschiedenen Netzwerken. Zusätzlich zu allen, kann der soziale Status eines Knoten in einem vorzeichenbehafteten Netzwerk durch die Relationen zwischen den anderen Knoten und einem gewissen Knoten bestimmt werden. Hierfür spielt der Grad des Optimismus, mit dem sich weitere Knoten auf unseren Knoten beziehen, eine signifikante Rolle. Darauf basierend kann man weitere in naher Zukunft mögliche Knoteninteraktionen höchstwahrscheinlich ermitteln.(Saeed Reza Shahriary, 2015)

2. Verwandte Arbeiten

Für die Vorhersage des sozialen Status in vorzeichenbehafteten Netzwerken findet sich eine Vielzahl an vergangenen sowie aktuellen Forschungsarbeiten. Im Folgenden werden wir vier verwandte Arbeiten im Allgemeine und (Saeed Reza Shahriary, 2015) und (Xiaoming Li, 2018) insbesondere analysieren. Die Autoren erweitern ihre Beiträge mit neuen Erfindungen - wie Link Prediction und Sign Prediction - die beim Vorhersagen des sozialen Status unverzichtbar sind.

Die Arbeit von (Saeed Reza Shahriary, 2015) zeichnet sich dadurch aus, dass die Wissenschaftler neue Algorithmen - wie zum Beispiel “Community-Based Ranking Methods”, “Prestige Ranking Algorithm Based on Community Detection” (kurz “PBCD”) und “HITS Ranking Algorithm Based on Community Detection” (kurz “HBCD”) - für die Vorhersage der Entstehung neuer sogenannten “Links” (Kanten) in einem vorzeichenbehafteten Netzwerk bringen.

Die Link-Vorhersage in vorzeichenbehafteten Netzwerken ist eine Herausforderung aufgrund der Existenz und des Ungleichgewichtes von drei Arten des sozialen Status (positive, negative und leere Beziehung). Außerdem gibt es in der Realität verschiedene Arten der leeren Beziehung (des “no-relation” Status), wie zum Beispiel “strangers” (Fremde), und “frenemies” (eine Mischung zwischen Freund- und Feindschaft), die in den bestehenden Ansätzen nicht von den anderen Verknüpfungen unterschieden werden können. Die Arbeit von (Xiaoming Li, 2018) schlägt eine novelle Betrachtung solcher Verknüpfungen vor, indem auch latente und explizite Merkmale mitbetrachtet werden.

3. Setup

3.1 Vorzeichenbehaftete Netzwerke und Graphen:

Ein Netzwerk ist eine Ansammlung von Punkten, die paarweise durch Linien verbunden sind. In der vorliegenden Arbeit werden vorzeichenbehaftete Netzwerke als eine Erweiterung von Netzwerken gesehen, die zusätzliche Informationen über positive und negative Relationen enthalten und sich als vorzeichenbehaftete Graphen darstellen lassen. Wir formalisieren das wie folgt: man hat einen vorzeichenbehafteten Graph G(V,E), wobei V die Menge der Knoten und E die Menge der Kanten ist. Die vorliegende Arbeit betrachtet verschiedene Individuen, Objekte und Organisationen als Knoten und die sogenannten “Links” als Kanten.

Wir untersuchen unsere Methoden anhand drei online vorzeichenbehafteten Netzwerken: Epinions, Slashdot und Wikipedia.

3.2 Epinions

Epinions ist eine Online-Review-Website, die den Benutzern ermöglicht entweder andere Benutzer oder Artikel zu bewerten. Die Bewertungen können in Form von positiven und negativen Meinungen erfolgen. Die Mitglieder von Epinions können auch diskutieren und sich über verschiedene Arten von Produkten unterhalten. Mit anderen Worten, Epinions ist eine Bewertungs-Website und die Leute entscheiden sich für eine positive oder negative Beziehung zueinander auf der Grundlage ihrer Beobachtungen, Bewertungen und Rezensionen.

3.3 Slashdot

Eine der ersten Technologie-Webseiten mit den Fähigkeiten eines sozialen Netzwerkes ist Slashdot. In Slashdot können Benutzer nicht nur Artikel markieren, sondern auch anderen Benutzern positive (Freundschaft) und negative (Feind) Werte geben. Diese Webseite wurde 1977 gegründet und ermöglicht den Benutzern, Material zu kommentieren, das von Redakteuren/Benutzern veröffentlicht wurde.

3.4 Wikipedia

Wikipedia ist ein bekanntes Onlinelexikon. Die Mitglieder von Wikipedia arbeiten zusammen, eine Enzyklopädie zu erstellen; aus Wartungs- und technischen Gründen benötigt diese Website Administratoren (Managers). Die Administratoren helfen bei der Aufrechterhaltung der Plattform und die Qualifikation der Website zu steigern. Die Manager werden mit Hilfe von positiven und negativen Stimmen der Benutzer durch Online Diskussionen und Gedankenaustausch gewählt.

4. Methodik

Vorzeichenbehaftete Netzwerke wurden in den letzten Jahren in den letzten Jahren von Online-Communities übernommen, da sie zwischenmenschliche Beziehungen besser als unvorzeichenbehaftete Netzwerke widerspiegeln (“A Survey of Signed Network Mining in Social Media,” 2016). Unter dieser Struktur gibt es drei Arten von sozialen Status zwischen zwei Benutzern: positive Beziehung (Vertrauen oder Freundschaft), negative Beziehung (Misstrauen oder Feind) oder leere Beziehung. Zum Beispiel, im Wikipedia Abstimmungsnetzwerk kann ein Benutzer eine kandidierende Entität positiv oder negativ abstimmen und kann auch entscheiden, nicht abzustimmen und und somit keine Beziehung zu der Entität zu haben.

Das zunehmende Interesse an vorzeichenbehafteten Netzwerken hat die Notwendigkeit erhöht, das Problem der Link-Vorhersage (Liben-Nowell und Kleinberg 2007) wieder zu bedenken, da es im Szenario von vorzeichenbehafteten Netzwerken schwieriger wird als bei vorzeichenbehafteten Netzwerken, die nur zwei Arten von sozialem Status berücksichtigen (verbunden oder nicht).

Die alten Studien gehen einfach davon aus, dass bereits bekannt ist, ob eine Kante zwischen zwei Knoten existiert, was in realen Szenarien ungültig ist. In der letzten Zeit wurden einige Methoden vorgeschlagen, die auch die leere Beziehung als bedeutsamen sozialen Status berücksichtigen, um die Link-Vorhersage zu erleichtern. (D. Song, 2015) zeigen zum Beispiel, dass die Nutzung des leeren Beziehungsstatus die Vorhersage von positiven Beziehungen verbessern kann. Allerdings konzentrieren sie sich nur auf die Vorhersage von positiven Beziehungen, können aber die leere Beziehung nicht vorhersagen. (X. Li, 2017) führen den ersten Versuch durch die Link-Vorhersage auf eine realistischere Menge zu erweitern indem sie auch die leere Beziehung vorhersagen. Sie zeigen, dass die leere Beziehungen sich von positiven und negativen Beziehungen unterschieden können, und zwar durch ein merkmalsbasiertes Modell, bei dem die Merkmale aus sozialen Theorien extrahiert werden. Dieses Modell ist jedoch begrenzt durch die Annahme, dass Knoten die gleichen Kriterien haben, um sich mit anderen zu verbinden, was unrealistisch ist. Zum Beispiel könnten einige Knoten eher bereit sein, sich mit anderen zu verbinden während Andere einflussreicher sind und eher von anderen Knoten verbunden werden. In der Tat ist das Problem der Link-Vorhersage in vorzeichenbehafteten Netzwerken ziemlich schwierig, hauptsächlich wegen der Vielfalt der leeren Beziehungen. Es ist denkbar, dass die meisten Paare von Knoten, die keine Beziehung zu einander haben, nur wenige gemeinsame Verbindungen haben (Fremde). Allerdings behalten in der Realität viele Benutzerpaare den leeren Beziehungsstatus, obwohl sie viele gemeinsame Verbindungen haben (frenemies). Zum Beispiel, im Epinions-Datenset, 40.779 aus 94.732 Knoten, die mehr als 100 gemeinsame Nachbarschaften haben, haben noch keine Beziehung zueinander. Es ist sehr einfach, die Benutzer, die viele gemeinsame Nachbarn haben aber nicht verknüpft sind, mit einem verknüpften Status zu bezeichnen.

4.1 Formulierung des Problems

Formal definieren wir das Problem wie folgt: Gegeben ein vorzeichenbehaftetes soziales Netzwerk S \(\in\) \(R^{n*n}\) (n ist die Anzahl der Benutzer im Netzwerk) mit \(S_{ij}\) \(\in\) \({1, 0, -1}\). Wir zielen darauf, alle Benutzerpaare (i, j) mit \(S_{ij}\) = 0 in der Gegenwart, mit der Wahrscheinlichkeit einer Umwandlung in positiven Beziehungen, negativen Beziehungen oder der Aufrechterhaltung einer leeren-Beziehung in die Zukunft zu betrachten. (Xiaoming Li, 2018) argumentiert, dass seine Problemstellung umfassender und realistischer ist als in den bisherigen Studien. Anstatt ein Benutzerpaar als eine spezifische soziale Beziehung zu klassifizieren, verwenden sie einen Ranking-Mechanismus und versuchen eine praktischere Frage zu beantworten: “Von den Benutzerpaaren (i, j) und (i, k), bei welchem Paar ist es wahrscheinlicher, dass sie Freunde (oder Feinde) werden?”. Die erhaltene Rangliste kann direkt in realen Anwendungen wie soziale Empfehlungen verwendet werden.

Frühere Analysen zu Datenmustern in vorzeichenbehafteten Netzwerken (“A Survey of Signed Network Mining in Social Media,” 2016) sind vorläufig und konzentrieren sich nur auf den Vergleich zwischen positiven und negativen Beziehungen. Wir untersuchen nun erneut die Datenmuster, indem wir auch den Status “leere Beziehung” berücksichtigen.

Abbildung 1

4.2 Fremde vs “frenemies”

Die Statistiken in Tabelle 1 zeigen die Existenz von zwei Arten von leeren-Beziehungen, da es eine beträchtliche Anzahl an leeren-Beziehungen mit wenigen gemeinsamen Nachbarn (CN=0, CN steht für Common Neighbors) oder mit vielen gemeinsamen Nachbarn (CN>50) gibt. Im Epinions-Datensatz ist zum Beispiel die Anzahl der gemeinsamen Nachbarn für nicht-relationierende Knotenpaare von 1 bis 2.059. Mit anderen Worten: Selbst ein Knotenpaar mit 2.059 gemeinsamen Nachbarn kann immer noch keine Verbindung zueinander haben. Wir überprüfen weiter, ob diese Paare mit leere-Beziehung über längerer Zeit stabil sind, da der Epinions-Datensatz die Information über den Zeitstempel jeder Linkbildung über 30 Monate enthält. Abbildung 1(y-Achse in \(10^{-3}\) Einheiten) zeigt das sich ändernde Verhältnis der Knotenpaaren mit leerer-Beziehung nach 15 Monaten. Die Y-Achse wird als die Anzahl von Benutzerpaaren ohne Beziehung mit einer bestimmten Anzahl von gemeinsamen Nachbarn, die nach 15 Monaten verknüpft sind, geteilt durch die Anzahl der leeren-Beziehung Benutzerpaare mit einer bestimmten Anzahl von gemeinsamen Nachbarn in der Gegenwart berechnet. Wir beobachten, dass der leere-Beziehungsstatus von Benutzerpaaren über die Zeit stabil sein kann, obwohl sie viele gemeinsame Nachbarn haben, und Benutzerpaare mit mehr gemeinsamen Nachbarn möglicherweise keine höhere Wahrscheinlichkeit haben, in der Zukunft verbunden zu sein. Im Gegenteil, wenn die Anzahl der gemeinsamen Nachbarn größer als 20 ist, wird der Status leere-Beziehung stabiler, je mehr gemeinsame Nachbarn vorhanden sind. Wie wir wissen besteht die Kernaufgabe der Link-Vorhersage darin, die Berechnung eines “Linkbildungs-Scores” für ein Benutzerpaar. Da sowohl Benutzerpaare von “frenemies” als auch Fremde zur derselben Klasse von Knoten mir leerer Beziehung angehören, wird erwartet, dass sie einen ähnlichen Punktzahl haben. Die meisten existierenden Ansätze, die sich auf Netzwerktopologischen Merkmalen beruhen, können dieses einfache Ziel nicht erreichen, da F”frenemies” und Fremde ganz unterschiedliche topologische Merkmale (z. B. die Anzahl der gemeinsamen Nachbarn) haben. Deshalb stellen (Xiaoming Li, 2018) klar, dass die Kernaufgabe der Link-Vorhersage in vorzeichenbehafteten Netzwerken besser explizit definiert wird als “wie man eine Link-Score-Funktion entwirft, um ähnliche Scores für Fremde und “frenemies” zu generieren und gleichzeitig in der Lage zu sein, diese von positiven und negativen Links zu unterscheiden”.

Im Folgenden führen wir eine Beschreibung der latenten und expliziten Merkmale ein, auf denen sich das “FILE”-Modell basiert. Danach präsentieren wir unsere Bauweisen für die Link-Score-Funktion und die Optimisierungsfunktion.

4.3 Latente Eigenschaften

Ein vorzeichenbehaftetes Netzwerk kann durch eine vorzeichenbehaftete Adjazenzmatrix \(S (S \in R^{n×n})\) dargestellt werden, die mit den n Knoten und Verbindungen im Netzwerk assoziiert wird, wobei \(S_{ij}\) = 1 eine positive Verbindung von Knoten i zu j ist, \(S_{ij}\) = -1 eine negative Verbindung von i zu j ist und \(S_{ij}\) = 0 eine leere Beziehung von i zu j (was die Mehrheit der Eintragswerte in S darstellen) zu betrachtet ist. Da diese Art von Matrizen von vorzeichenbehafteten Netzwerken die Low-Rank-Eigenschaft besitzt (C. Hsieh, 2012), kann die Technik der Matrixfaktorisierung eingesetzt werden um die latenten Merkmale der Benutzer zu lernen. Insbesondere kann S in zwei Matrizen mit niedrigem Rang U und V zerlegt werden, wobei \(U^T\)V \(\approx\) S (U, V ∈ \(R^{n×r}\), r\(\ll\)n). Wir nennen sowohl \(u_i\) \(\in\) U und \(v_i\) \(\in\) V als latente Vektoren des Knotes \(i\) und bezeichnen sie als die Aktivität bzw. die Popularität. Für einen bestimmten Knotenpaar i und j hängt die Wahrscheinlichkeit der Linkbildung gleichzeitig sowohl von \(u_i\), als auch von \(v_j\) ab, das heißst, ob i aktiv ist und mehr dazu neigt, anderen zu “vertrauen” (oder zu misstrauen), und ob j beliebt ist und eher dazu neigt, anderen zu vertrauen (oder zu misstrauen). Ein höherer Wert von \({u^T}_iv_j\) zeigt eine höhere Wahrscheinlichkeit, eine positive Verbindung zu bilden. Umgekehrt bedeutet ein niedrigerer Wert von \({u^T}_iv_j\) eine höhere Wahrscheinlichkeit, eine negative Verknüpfung zu bilden. Zusammenfassend lässt sich sagen, dass bei einem Paar von Knoten (i, j) und den r-dimensionalen Eigenschaften \(u_i\) (Aktivität von Benutzer i) und \(v_j\) (Popularität von Benutzer j), definieren wir die Linkbildungswahrscheinlichkeit wie folgt:

Abbildung 2

4.4 Explizite Merkmale

Explizite Merkmale erfassen soziale Einflüsse aus der umliegenden Nachbarschaften um ein Knotenpaar und können aus der Netzwerktopologie formuliert werden. Wir behaupten, dass alle wertvollen und sinnvolle Merkmale aus der Literaturin das FILE-Framework integriert werden können, da sie neue Informationen zu sozialen Einflüssen beitragen. In (Xiaoming Li, 2018) Framework, um die Effektivität der expliziten Merkmale zu zeigen, entwerfen wir zwei explizite Merkmale durch Erweiterung der Gleichgewichtstheorie und der Statustheorie. Gemäß den beiden sozialen Theorien bringt jeder gemeinsame Nachbar entweder einen positiven oder einen negativen Einfluss. Wie in Abbildung 2. gezeigt wird, gibt es insgesamt insgesamt 16 Arten von Triaden, die von einem Benutzerpaar und seinem gemeinsamen Nachbarn gebildet werden (p und n bezeichnen die positiven und negativen Vorzeichen, und f und b stehen für die Verbindungsrichtungen (vorwärts bzw. rückwärts). Wie in der Gleichgewichtstheorie angegeben, bringt jeder gemeinsame Freund einen positiven Einfluss, der die Wahrscheinlichkeit erhöht, dass zwei Knoten eine positive Beziehung entwickeln, während ein Nachbar einen negativen Einfluss hat wenn er das Freund des Einen, aber der Feind des Anderen ist. Daher überprüfen wir, ob der positive oder negative Einfluss in der Gleichgewichtstheorie dominant ist, und zwar über:

In der Statustheorie kann ein Nachbar den Statusunterschied zwischen einem Knotenpaar diktieren. Zum Beispiel, für ppff, gegeben ein Benutzer Paar (i, j) und deren Nachbar w, kommen die Verbindungen i \(\rightarrow\) w und w \(\rightarrow\) j beide positiv heraus. Wenn man sich auf der Statustheorie basiert, bedeutet das, dass der Status von j höher als der von w ist, während der Status von w höher ist als den Status von i. Daher ist die Verknüpfung i \(\rightarrow\) j mit größerer Wahrscheinlichkeit positiv, da der Status von j höher ist als der von i. Wir quantifizieren also den gesamten Einfluss in der Statustheorie über:

Für diese beiden Eigenschaften gilt, dass ein höherer positiver (oder negativer) Wert eine höhere Wahrscheinlichkeit anzeigt, eine positive (oder negative) Verbindung zu bilden. Ein Wert nah an 0 deutet darauf hin, dass sie mit größerer Wahrscheinlichkeit die leere Beziehung behalten. Wir führen den “One-Way ANOVA-Test” auf explizite Merkmale durch, um ihre Effektivität zu bewerten, und beide Merkmale bestehen den Test auf dem Signifikanzniveau von 0,01 (p-Wert < 0,01), was darauf hindeutet, dass sie in der Lage sind, die drei Arten des sozialen Status unterscheiden zu können.

4.5 Die Link-Score-Funktion

\(\mathcal{L}(i,j) = N({u^T}_i*v_j) + \sum_{k} \alpha_\mathbf{w}*N({f_{ij}^w}) (2)\)

wobei \(N({u^T}_i*v_j)\) latente Merkmale und \(\sum_{k}\) \(\alpha_\mathbf{w}*N({f_{ij}^w})\) explizite Merkmale darstellen Wie bereits erwähnt, sind sowohl latente als auch explizite Merkmale unerlässlich, da das Fehlen eines dieser Merkmale zu einer falschen Vorhersage einer leeren Beziehung führt. In Anbetracht dessen definieren wir zunächst eine Schwellenregel für die Linkbildung: Ein positiver Link liegt vor, wenn der Link-Score größer als 1 ist, und ein negativer Link liegt vor, wenn der Link-Score kleiner als -1 ist. Wir begrenzen den Wert jedes Teils (latent oder explizit) durch (-1, 1), was indirekt einschränkt, dass nur die Kombination von zwei Teilen erfolgreich eine entweder positive oder negative Verknüpfung bildet. In Gleichung (2) ist \(u_i\) das latente Aktivitätsniveau von Benutzer i, \(v_j\) ist das latente Merkmal der Popularität von Benutzer j, \({f_{ij}}^w (w \in\) \(\{1, 2\}\) ist ein explizites Merkmal für das Benutzerpaar {i, j}, \(\alpha_w\) ist das entsprechende Gewicht mit \(\sum_w \alpha_w\) = 1 und N(-) die Funktion ist, die die entsprechenden Werte der Merkmale im Interval (-1, 1) normalisiert. Daher ist die Link-Score-Funktion beschränkt und \(L_{ij}\) \(\in\) (-2, 2). Wenn man sich auf der vorherigen Analyse basiert, so beobachtet man, dass wenn \(L_{ij}\) innerhalb von (-1, 1) liegt, es keinen Link von i nach j gibt. Wenn \(L_{ij}\) \(\geq\) 1, dann gibt es eine positive Verbindung von i nach j, und wenn \(L_{ij}\) \(\leq\) -1, dann gibt es eine negative Verknüpfung von i nach j.

4.6 Die Normalisierungsfunktion

Die Normalisierungsfunktion normalisiert die Werte der Merkmalen im Bereich (-1,1). (Xiaoming Li, 2018) formuliert sie wie folgt:

Die Sigmoid-Verteilung erfasst gut die Eigenschaft der Link-Bildung (dass der Wert mit geringerer Geschwindigkeit ansteigt, wenn i und j bereits eine hohe Wahrscheinlichkeit aufweisen, eine Verbindung herzustellen). Die Auswahl von $\omega$ hängt hauptsächlich von der Skala des entsprechenden Eigenschaft ab. In dieser Arbeit normalisieren (Xiaoming Li, 2018) die beiden expliziten Merkmale, indem sie sie innerhalb der gleichen Größenordnung skalieren. Zu diesem Zweck setzen wir \(\omega\) als den Kehrwert des Medianwertes des entsprechenden Merkmals.

4.7 Optimisierung

Der traditionelle quadratische Verlust ist für (Xiaoming Li, 2018)s Problem nicht geeignet, denn anstatt sich um den absoluten Vorhersagefehler zu kümmern, konzentrieren sie sich auf die Ranking-Leistung. Das heißt, dass zum Beispiel bei einem möglicherweise positiven Link \(S_{ij}\) = 1 sollte kein Verlust entstehen, wenn die Vorhersage \(L_{ij} \geq\) 1 ist. Daher ist im Hinblick auf Gleichung 2 die Verlustfunktion definiert als:

wobei I(-) die 0/1-Indikatorfunktion ist, die, wenn die Bedingung in (-) zutrifft, erhalten wir 0 Verlust, sonst 1 Verlust. Wir versuchen eine Ersatzfunktion zu finden, die I(-) ersetzt, da sie nicht konvex ist. Unter Berücksichtigung unserer Link-Score-Funktion in Gleichung 2 kann das Endziel der Zielfunktion so interpretiert werden, \(L_{ij}\) so groß wie möglich zu machen, wenn \(S_{ij}\) = 1 ist, während \(L_{ij}\) so klein wie möglich zu machen, wenn \(S_{ij}\) = -1 ist. Wie für \(S_{ij}\) = 0, machen wir \(|L_{ij}|\) näher an 0. In Anbetracht dieser Überlegung entwerfen wir die Zielfunktion wie folgt: \(min \sum_{S_{ij=1}}(1- L_{ij}) + \sum_{S_{ij=0}}(L^2_{ij} - 1) + \sum_{S_{ij}=-1}(L_{ij} + 1) (5)\)

Um die äquivalente reduzierte Form für Gleichung (5) zu konstruieren und Regularisierer hinzuzufügen, um Overfitting zu vermeiden, kann die Verlustfunktion F wie folgt umgeschrieben werden:

Wir verwenden dann den stochastischen Gradientenabstieg (SGD) zum Herausfinden der Werte von Parametern und Variablen. Insbesondere machen wir zuerst x = 1/(1+\(e^{-u^T_iv_j}\)), \(\Delta_1\) = 2x+ \(\sum_{w} \alpha N(f^w_{ij}\))-1, und \(\Delta_2\) = 2x(1-x). Dann werden die entsprechenden partiellen Ableitungen wie folgt berechnet:

4.8 Prozess der Optimisierung

Input: Matrix S, Lernenrate β, Iterationszeit T und Konvergierungsgrenze c Initialisierung: t = 0, Berechnung \(f_{ij}\) \(\in\) E, Generierung \(U_0\), \(V_0\) loop

    t = t + 1; 
    $U_{t+1}$ = $U_t$ − $\beta$ $\frac{\gamma F}{\gamma U_t}$ (Gleichung 7);
    $V_{t+1}$ = $V_t$ − $\beta$ $\frac{\gamma F}{\gamma V_t}$ (Gleichung 8);

bis Konvergierung Output: U, V — Algorithmus 1 fasst das Optimierungsverfahren der der SGD zusammen. Die Zeitkomplexität des Algorithmus ist O(trn), wobei t die Anzahl der Iterationen, r die Anzahl der latenten Merkmale, n die Anzahl der Beobachtungen im Netzwerk.(Xiaoming Li, 2018)

5. Experimente

5.1 Setting

(Xiaoming Li, 2018) führen Experimente an drei realen Datasets durch und vergleichen den neuen Ansatz mit fünf state-of-the-art Ansätzen in Bezug auf Ranking-Metriken. Wie in Tabelle 1 gezeigt, werden in den Experimenten drei Datasets verwendet, das sind Epinions, Slashdot, Wikipedia RFA. Dazu generieren wir aus jedem Dataset direkt drei Datasets und jeder neu generierte Dataset zeigt eine eindeutige Verteilung von \(\vert P\vert:\vert U\vert :\vert N\vert\), sind die Anzahl der positiven Links, der No-Relation bzw. der negativen Links. Die Statistiken von Datasets sind in Tabelle 2 zusammengefasst. Es wurden für jeden der drei großen Datasets (Epinions, Slashdot, Wikipedia) eine Stichprobe von 10-Prozent der Daten genommen und nach Benutzergrad d (\(\geq10, \geq 25, \geq 50\)) gefilterten Dateneinträge ausgewählt. Datasets sind in folgender Form - “name@degree” eingetragen. (Xiaoming Li, 2018)

5.2 Evaluation von Metrik

Zur Verfügung steht standardmäßige 5-fache Kreuzvalidierung, die man fürs Training, Testen und Verwenden von GAUC (Generalized AUC über +1, 0 and −1)(Song and Meyer 2015), um um die Gesamtrankingleistung zu evaluieren:

Merke: \(L(\cdot)\) ist Link-Score Funktion. GAUC ist eine Erweiterung von AUC und bietet eine Ranking-Metrik, die die drei Arten von Linkstatus berücksichtigt. Die andere Metrik ist precision@top k. In vorzeichenbehafteten Netzwerken, gibt es sowohl positive als auch negative precision@top k, die als das Verhältnis positiver (oder negativer) Links in die oberen (oder unteren) k Vorhersagen definiert sind. Diese zwei Metriken bewerten die Leistung der Linkempfehlung, da die Top-k-Liste für Anwendungen wie Empfehlungssysteme wichtiger ist, während die negative Top-k-Liste für sicherheitsrelevante Anwendungen nützlich ist.(Xiaoming Li, 2018)

5.3 Benchmarking-Ansätze

Laut (Xiaoming Li, 2018) wurden Vergleiche mit fünf state-of-the-art Ansätzen durchgeführt, einschließlich funktionsbasierter Modelle: Common Neighbors (CN) (Liben-Nowell und Kleinberg 2007) und Social Feature Model (SFM); latente Modelle: Low Rank Modeling(LRM) und Rangliste basierend auf latenten Modellen des Bayesianischen personalisierten Rankings(BPRMF) und Optimierung des GAUC (OptGAUC). Für alle oben genannten Benchmark-Methoden gilt: in OptGAUC \(\lambda=20\) und r=50, während \(\lambda=1\) und r=10 in LRM. Beim merkmalsbasierten Modell CN wird die Differenz zwischen der Anzahl positiver und negativer gemeinsamer Nachbarn als Metrik verwendet, um die Rangliste zu erstellen.(Xiaoming Li, 2018)

Im FILE-Framework stehen drei Hyperparameter zur Verfügung: \(\lambda1\), \(\lambda2\) und r. Man setzt \(\lambda1=\lambda2\) und sucht über {0.01, 0.05, 0.1, 0.5}. Ebenso sucht man auch die Anzahl der latenten Merkmale r über {5, 10, 15, 20}. (Xiaoming Li, 2018) führen eine 5-fache Kreuzvalidierung des Trainingssatzes durch und übernehmen die Parameter, die das beste Resultat erzielen. Man überprüfen auch die Parametersensitivität des Ansatzes in Bezug auf bis \(\lambda1\), \(\lambda2\) und r. Über alle Parameterkombinationen hinweg variiert FILE in Bezug auf GAUC in einem Bereich von [0.823, 0.856] in Slashdot@50 und [0.779, 0.823] in Epinions@50. Es ist offensichtlich, dass die Leistungsschwankung über verschiedene Parametereinstellungen relativ gering ist. Ähnliche Ergebnisse erhält man in anderen Datasets. Daraus können wir schließen, dass FILE aufgrund seiner Unempfindlichkeit gegenüber den Modellparametern eine gute Flexibilität aufweist.(Xiaoming Li, 2018)

6. Kollation

6.1 Gesamtergebnis

Tabelle 3 zeigt die Vergleiche zwischen verschiedenen Modellen in Bezug auf die Ranking-Metrik GAUC. Es ist zu sehen, dass die Modell andere Benchmarks für die meisten Datensets übertrifft. CN sieht am schlechtesten aus in allen Szenarien, weil es die Zeichen von Nachbarn und Verbindungen nicht unterscheidet. Daraus folgt, dass traditionelle Linkvorhersagemethoden nicht direkt auf Linkvorhersage in signierten Netzwerken angewendet werden können. Die latenten Modelle - LRM, BPRMF und OptGAUC funktionieren besser als CN, was die Wirksamkeit der latenten Merkmale aufweist. Darüber hinaus übertrifft OptGAUC sowohl LRM als auch BPRMF, was darauf hindeutet, dass die in OptGAUC verwendeten No-Relation-Informationen dazu beitragen, die Ergebnisse der Verbindungsvorhersage zu verbessern. Dieses Ergebnis stimmt mit dem Ergebnis in (Song und Meyer 2015) überein. Außerdem ist SFM besser als CN, LRM und BPRMF, was darauf hindeutet, dass die expliziten sozialen Merkmale in SFM in vorzeichenbehafteten Netzwerkszenarien gut laufen.(Xiaoming Li, 2018)

Insgesamt erzielt FILE im Vergleich mit anderen Ansätzen über alle Datasets hinweg das beste Resultat, und die Verbesserung beträgt durchschnittlich 3,9-Prozent. Wir führen einen t-Test für den Leistungsunterschied zwischen diesen Ansätzen durch. Somit wird gezeigt, dass die Verbesserung unseres Frameworks statistisch signifikant ist (\(p-Wert < 0,01\)).(Xiaoming Li, 2018)

6.2 Auswirkung von d

Um die Robustheit unseres Ansatzes zu demonstrieren, überprüft man seine Leistung in Bezug auf GAUC als Änderung von d im Bereich [1, 50]. Wenn d klein ist (\(d < 5\)), schneidet FILE ähnlich oder etwas schlechter ab als andere. Mit steigendem d ist Ansatz durchweg besser als andere. Ein Grund dafür ist, dass die Daten mit größerem d wertvollere Informationen bewahren, um latente Merkmale über Matrixfaktorisierung zu lernen. Außerdem ist d in der Realität normalerweise viel größer als 5, daher sind die Robustheit und Überlegenheit des neuen Ansatzes in realen Szenarien viel besser. Eine weitere Beobachtung ist, dass die Leistung mit zunehmendem Grad im Wikipedia-Datasets sinkt, weil der Wikipedia-Dataset sehr klein ist. Wenn der Grad größer als 20 wäre, würde der gefilterte Dataset kleiner. Deshalb verschlechtert sich die Performance aller Ansätze.(Xiaoming Li, 2018)

7. Referenzen

1. Saeed Reza Shahriary, R. M. D. N., Mohsen Shahriari. (2015). A Community-Based Approach for Link Prediction in Signed Social Networks. Scientific ProgrammingVolume 2015, 1–10.
2. Xiaoming Li, J. Z., Hui Fang. (2018). FILE: A Novel Framework forPredicting Social Status in Signed Networks. The Thirty-Second AAAI Conferenceon Artificial Intelligence (AAAI-18).
3. A survey of signed network mining in social media. (2016). ACM Computing Surveys.
4. D. Song, A. D. M. (2015). Recommending positive linksin signed social networks by optimizing a generalized auc. Proceedings of the Twenty-Ninth AAAI Conference on ArtificialIntelligence.
5. X. Li, J. Z., H. Fang. (2017). Rethinking the link prediction problem in signed social networks. Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence.
6. C. Hsieh, I. D., K.-Y. Chiang. (2012). Low rank modeling of signed networks. Proceedings of the 18th ACMSIGKDD International Conference on Knowledge Discovery and Data Mining,