Malte Säuberlich		Natalia Slowikowska
RWTH Aachen University		RWTH Aachen University
malte.saeuberlich@rwth-aachen.de		natalia.slowikowska@rwth-aachen.de

Abstract

Ein großer Teil, der heutigen Gesellschaft wird durch soziale Medien definiert. Vor allem die Jugend ist durch Soziale Medien vernetzt und verbindet sich über gemeinsame Interessen. Diese Verbindungen zwischen unterschiedlichen Personen lassen sich durch soziale Netzwerke darstellen, dazu bewertet man Verbindungen unter Kriterien, wie Vertrauenswürdigkeit und Freundschaft. Diese Verbindungen werden in Gemeinschaften mit gleichen Präferenzen sortiert. Diese Gemeinschaften überlappen sich, da eine Person häufig mehreren Gemeinschaften angehört. Mit diesen Gemeinschaften kann man Vorhersagen in Bezug auf Wahlen, Kaufverhalten und Verhalten in Freundschaftsgruppe -n machen. Dies überlappenden Gemeinschaften erkennt man mit Hilfe von einem OCDA (Overlapping Community Detection Algorithim). Um diese sozialen Netzwerke besser bewerten zu können, werden Personen als Knotenpunkte gesehen und ihre Verbindungen als Kanten. In dieser Arbeit stellen wir ein Verfahren vor, indem die einflussreichsten Knoten die Rolle eines „Anführers“ erhalten. Anschließend kann man den Rest der Knoten als „Mitglieder“ dieser „Anführer“ betrachten und somit einfacher die überlappenden Gemeinschaften entdecken. Diese Prinzipien von überlappenden Gemeinschaften und derer Bewertung werden wir am Beispiel, des soziale Netzwerks YouTube erläutern. Denn mit einem solchem Verfahren, sollte es möglich sein Rückschlüsse auf den Sozialen Status eines Nutzers und deren Entwicklung zumachen.

Inhaltsverzeichnis

Einleitung

Verwandte Arbeiten

Methodik

Einleitung der Methodik

Zwei-Phasen Algorithmus

HITS

Page-Rank

Sign Prediction

HITS Vorhersagen

Page-Rank Vorhersagen

Anwendungsbeispiel Youtube

Youtube als Soziales Netzwerk

Der zweistufen Algorithmus am Beispiel Youtube

Möglichkeiten in einem Sozialen Netzwerk

Evaluation

Normalized Mutual Information

Modularity

Frustration

Auswertung

Andere Modelle für Sign Prediction

Prestige

Page Trust

Bias und Diverse

Vergleich von den vorher benutzten Algorithmen

Fazit und Ausblick

Referenzen

Einleitung

In der heutigen Welt dreht sich vieles um Soziale Medien. Diese werde für verschiedene Zwecke benutzt, wie z.B. Werbung oder sogar als ein Arbeitsplatz für Künstler. Die Wichtigkeit von Sozialen Medien wächst mit jedem Tag und somit auch die Notwendigkeit einer Methode die die Analyse und Vorhersage von den sozialen Netzwerken die auf den sozialen Medien entstehen. Um so eine Analyse durchzuführen wird die Graphentheorie benutzt. Dabei wird, mithilfe von verschieden Mitteln aus dieser Theorie, das Verhalten von den Gemeinschaften beobachtet. Dazu sind am hilfreichsten die sogenannten vorzeichenbehafteten Netzwerke bei denen die Kanten positiv oder negativ sind. Dies kann z.B. für die Vorhersage von unglaubwürdigen Nutzern auf sozialen Medien dienen, um sich dann von denen besser schützen zu können.

Die Forschung in dem Bereich hat mit der Entwicklung von Algorithmen für die Entdeckung von Gemeinschaften angefangen. Dazu gehört die Minimum-Cut Methode, die einer der ältesten Algorithmen für die Entdeckung von Gemeinschaften ist. Dabei wird eine Gemeinschaft zerteilt, in eine vorbestimmte Anzahl von kleineren Gemeinschaften. Dies geschieht mithilfe der Minimalisierung von Kanten zwischen den neu bestimmten Gemeinschaften. Jedoch wird man mit dieser Methode immer Gemeinschaften in sozialen Netzwerken finden, ohne Rücksicht auf deren eigentliche Existenz. Es wird auch nur eine vorgegebene Anzahl der Gemeinschaften gefunden. Da die Anzahl nicht immer vorher bekannt ist und dadurch entweder zu viele oder zu wenige Gemeinschaften gefunden werden, ist dies nicht anwendbar für die Entdeckung der Gemeinschaften. Ein weiterer weitverbreiteter Algorithmus ist die Modularity Maximization bei der nach partiellen Gemeinschaften mit großer Modularität, also mit einer großen Anzahl von Kanten, gesucht wird. Diese werden dann als die neuen Gemeinschaften erkannt.

Allerdings wird bei diesen Algorithmen nicht berücksichtigt, dass im echtem Leben Personen zu mehreren Gemeinschaften gehören können. Ein gutes Beispiel dafür wäre das Abonnentenprinzip auf Youtube, da es sehr selten vorkommt, dass ein Nutzer nur einen Kanal abonniert hat. Diese überlappende Gemeinschaften sind ein viel realistischeres Modell. Jedoch gibt es bisher weniger Forschung, die vorzeichenbehaftete Netzwerke mit überlappenden Gemeinschaften verbindet, obwohl es sehr wichtig für die Zukunft scheint.

In der folgenden Arbeit beschreiben wir eine der ersten Ansätze für Algorithmen, die überlappende Gemeinschaften und die Vorhersage von vorzeichenbehafteten Kanten berücksichtigen. Diese besteht aus SPM (Signed Pobabilistic Mixture Model) und MEAs-SN (Multi-objective Evolutionary Algorithm in Signed Networks), die für die Entdeckung überlappenden Gemeinschaften dienen, und beide OC-HITS und OC-PageRank die als Algorithmen für die Vorhersage der vorzeichenbehafteten Kanten. Schließlich werden wir die Algorithmen für Vorhersage der vorzeichenbehafteten Kanten mit anderen vergleichen und erläutern warum genau diese benutzt wurden.

Methodik

Einleitung in die Methodik

Im folgendem wird die für uns am praktischste Methode vorgestellt um den Sozialen Status in einem sozialen Netzwerk hervor zusagen. Wir haben uns für diese Methode entschieden weil sie überlappende Gemeinschaften und vorzeichenbehafteten Kanten berücksichtigt. Diese Methode wurde “The Significant Effect of Overlapping Community Structures in Signed Networks” (Shahriari et al., 2017) von Mohsen Shahriari, Zing Li und Ralf Klammer vorgestellt.
Zunächst werden wir die benutzten Begrifflichkeiten und Variablen erläutern. Soziale Netzwerke sind Graphen $G(V,E)$, mit $V$ also Knoten und $E$ als Kanten, mit zwei verschieden Werten entweder -1 oder +1 . Wir bezeichnen Knoten, welche auf einen Knoten $i$ zeigen, mit $indeg(i)$ und Knoten auf die ein Konten$i$ zeigt mit $outdeg(i)$. Da diese Verbindungen weiter auch als positiv oder negativ gewertet werden sollen. Beschreiben wir positive Verbindungen $indeg(i)^+$, $indeg(i)^-$ und negative $outdeg(i)^+$, $outdeg(i)^-$. Alle Nachbarn eines Knoten $i$ wird mit $Nei(i)$ beschrieben. Also: $Nei(i) = deg(i) = indeg(i)^+ \cup indeg(i)^-\cup outdeg(i)^+\cup outdeg(i)^-$ Damit werden alle Knoten die mit $i$ verbunden sind beschrieben. Diese verbundenen Konten sind weiter in Gemeinschaften, welche eine Gemeinschaft von Knoten beschreibt, eingeteilt. Welche mit dem vorgestellten Algorithmus gefunden und bewertet werden sollen. Diese Gemeinschaften werden dargestellt mit $C$.Zusätzlich wird die Verbindung zwischen Knoten $i$ und $j$ nun erweitert, es wird nun nicht mehr nur $indeg(i)^+$, $indeg(i)^-$, $outdeg(i)^+$ und $outdeg(i)^-$ benutzt, sondern werden diese weiter mit $intra, extra, Ovl.$ ausgestattet. Wobei der zusätzliche Wert die Art der Verbindungen beschreibt. Hierbei steht $intra$ für eine Verbindung innerhalb einer Gemeinschaft, $extra$ für eine Verbindung mit einem Knoten von einer anderen Gemeinschaft und $Ovl.$ mit einer Verbindung die über eine überlappenden Gemeinschaft geht. Um im weiteren Verlauf Verbindungen zwischen Knoten bewerten zu können, unterteilen wir Knoten in zwei Verhaltensgruppen, einmal Knoten, die anderen Knoten vertrauen $u$ und Knoten denen von anderen Knoten vertraut $v$ wird.

Zwei Phasen Algorithmus

Nun wird der Algorithmus erläutert. Für diesen wollen wir die Knoten mit dem größten Einfluss finden, also Anführer. Dabei sollen unsere Anführer nicht nur einen großen Einfluss, sonder auch eine große Differenz zu ihren Nachbarn haben. Da wir beim Einfluss auch noch negativen Einfluss betrachten müssen beschreiben wir, $ED(i)$ den Einfluss eines Knotens mit:

\[ED(i)= \frac{indeg^+(i)-indeg^-(i) }{indeg^+(i) +indeg^-(i)}\]

Unsere Anführer müssen in jedem Fall einen positiven $ED(i)$ haben. Um nun den Unterschied mit den Nachbarn zu bewerten schauen wir uns die Verbindungen der Nachbarn an.

\[DASS(i)= \frac{\sum _{j\in Nei(i)} (deg(j)-deg(i))}{\sum _{j\in Nei(i)} (deg(j)+deg(i))}\]

Dabei werden die negativen und positiven Verbindungen gleichwertig behandelt. Um lokale Anführer zu bestimmen können $DASS(i)$ und $ED(i)$ verwenden werden um $LLD(i)$ zu berechnen

\[LLD(i) = \alpha \cdot DASS(i) +(1-\alpha) \cdot ED(i)\]

$LLD(i)$ beschreibt nun das Potential für lokale Anführer. $\alpha$ ist hierfür ein Parameter der die Wichtung zwischen Einfluss und der Größe, der Unterschiede mit den Nachbarn beschreibt, dieser wird auf 0,5 angesetzt, da beide Faktoren sehr wichtig sind. Nun kann man lokale Anführer $LL$ bestimmen in dem sagt, ein Knoten $i$ ist ein lokaler Anführer $LL$, wenn für diesen gilt:

$\forall j \in Nei(i)$
$LLD(i)>LLD(j)$

Nun kann man unter den lokalen Anführern $LL$ globale Anführer finden, welche um einiges mehr Verknüpfungen haben. Ein lokaler Anführer ist ein globaler, wenn gilt:

\[LL(i) > AFD\]

$AFD$ steht für die Durchschnitts Anzahl an Anhängern. $AFD$ kann folgend berechnet werden:

\[AFD= \frac{\sum_{i\in LL}|FL(i)|}{|LL|}\]

dafür gilt $FL$ sind die Anhänger vom Knoten $i$.

Nun da die erste Phase für das Netzwerk abgeschlossen wurde, geht es nun darum zu erkennen zu welchem Grad ein Knoten zu einem Anführer gehört. Dies kann man mithilfe eines Network Coordination Game ermitteln. Dafür nimmt man an, dass alle Knoten die gleiche Meinung A haben und nun wollen wir uns anschauen was passiert, wenn von einem Knoten die Meinung sich in B ändert. Umso mehr sich Knoten von einem bestimmtem Knoten beeinflussen lassen umso höher ist die Chance das dieser ein Anführer ist und der Knoten in dessen Gemeinschaft ist. Dafür müssen wir uns die Wahrscheinlichkeit, dass sich die Meinung eines Knoten ändert anschauen, dafür gilt:

\[PayOff(i)=\frac{(j_a\in Nei^+(i))-(j_a\in Nei^-(i))}{(j_a\in Nei^+(i))+(j_a\in Nei^-(i))}\]

In dieser Formel hat $j_a$ die Meinung A welches eine andere Meinung als die des aktuellen Knotens i ist. Wenn der PayOff Wert von $i$ größer als der Schwellwert der Knoten ist, so wechselt $i$ ihre Meinung. Der Schwellenwert eines Knotens ist sein $LLD(i)$, also sein Anführer Potential, so ist sicher gestellt das Anführer Anhänger beeinflussen. Weiter gehen wir davon aus, dass es genauso viele lokale Anführer wie Gemeinschaften gibt. Um festzustellen, ob ein Knoten zu einer Gemeinschaft gehört ändern wir die Meinung eines verbundenem lokalen Anführer. Anschließen kann die Veränderung in der Meinung des Knoten beobachtet werden. Falls eine Veränderung auftritt kann man davon ausgehen, dass dieser Knoten zur Gemeinschaft von dem lokalen Anführer gehört. Für den Knoten $i$ wird die Zugehörigkeit $M_{ij}$ in der sich die Meinung zur der Gemeinschaft $C_j$ folgend berechnet:

\[M_{ij}=\frac{1}{t^2_{ij}}\]

hier ist $t_{ij}$ die Zeitspanne in der sich die Meinung vom Knoten $i$ in die des Gemeinschaft Anführers $j$ ändert. Damit ist es auch möglich die Zugehörigkeit zu mehreren Gemeinschaften zu beschreiben. Nun haben wir einen vollständigen zwei-Phasen Algorithmus welcher eine überlappende Gemeinschaft Struktur darstellt. Nun muss ein solches Netzwerk auch bewertet werden. Dazu sind ein erweiterter Page-Rank Algorithmus, sowie ein erweiterter HITS Algorithmus nützlich.

HITS

Der HITS benutzt grundlegend zwei verschiedene Vektoren genannt hubs und authorities. Jeder Knoten besitzt diese beide Vektoren zunächst enthalten die Vektoren zufällige Werte. Im Laufe des Algorithmus werden die Werte dann aktualisiert. Da der originale Algorithmus nicht sehr präzise arbeitet wird hier eine verbesserte Version präsentiert, welche vorzeichenbehaftete Kanten berücksichtigt:

$a^+_i =\alpha \times \sum_{j\in indeg^+_{intra}(i)}h^+_j+\beta \times \sum_{j\in indeg^+_{ovl}(i)}h^+_j+\gamma \times \sum_{j\in indeg^+_{extra}(i)}h^+_j$ $a^-_i =\alpha \times \sum_{j\in indeg^-_{intra}(i)}h^-_j+\beta \times \sum_{j\in indeg^-_{ovl}(i)}h^-_j+\gamma \times \sum_{j\in indeg^-_{extra}(i)}h^-_j$ $h^+_i =\alpha \times \sum_{j\in outdeg^+_{intra}(i)}h^+_j+\beta \times \sum_{j\in outdeg^+_{ovl}(i)}h^+_j+\gamma \times \sum_{j\in outdeg^+_{extra}(i)}h^+_j$ $h^-_i =\alpha \times \sum_{j\in outdeg^-_{intra}(i)}h^-_j+\beta \times \sum_{j\in outdeg^-_{ovl}(i)}h^-_j+\gamma \times \sum_{j\in outdeg^-_{extra}(i)}h^-_j$

Nun beschreiben $a^+_i$ und $a^-_i$ die positiven und negativen authorities vom Knoten $i$ und $h^+_i$ und $h^-_i$ die positiven und negativen hubs von $i$. Für diesen Algorithmus wird vorgesehen $\frac{1}{V}$ als Startwert zunehmen anstatt einen Zufälligen. $\alpha, \beta, \gamma$ sind Werte um die Wichtigkeit der Kanten zu verändern, damit ist der Algorithmus anpassbar.

Page-Rank

Die Idee hinter PageRank ist die Durchquerung des Graphen entlang der Kanten, dabei erhält jeder besuchte Knoten einen Rang. Am Anfang vom Algorithmus erhält jeder Knoten einen zufälligen Wert, welcher dann anschließend durch den Algorithmus aktualisiert wird. Um zu verhindern das der Algorithmus stoppt kann er sich zur Wahrscheinlichkeit $\zeta$ teleportieren. Dabei wird der Originale Algorithmus folgend beschrieben:

\[(PR_i = \zeta \times( \sum _{j\in outdeg(i)} (\frac{PR_j}{outdeg(j)})+(1-\zeta ) \cdot ( \frac{1}{V} ))\]

Dieser Soll nun auch für überlappende Gemeinschaften erweitert werden:

\[PR^+_i = \zeta (\alpha \times \sum_{j\in indeg^+_{intra}(i)}(\frac{PR^+_j}{OUTDEG^+_{intra(j)}})+\beta \times \sum_{j\in indeg^+_{ovl}(i)}(\frac{PR^+_j}{OUTDEG^+_{ovl(j)}})+\gamma \times \sum_{j\in indeg^+_{extra}(i)}(\frac{PR^+_j}{OUTDEG^+_{extra(j)}}))+(1- \zeta )\cdot (\frac{1}{V})\] \[PR^-_i = \zeta (\alpha \times \sum_{j\in indeg^-_{intra}(i)}(\frac{PR^-_j}{OUTDEG^-_{intra(j)}})+\beta \times \sum_{j\in indeg^-_{ovl}(i)}(\frac{PR^-_j}{OUTDEG^-_{ovl(j)}})+\gamma \times \sum_{j\in indeg^-_{extra}(i)}(\frac{PR^-_j}{OUTDEG^-_{extra(j)}}))+(1- \zeta )\cdot (\frac{1}{V})\]

$PR^+_i$ und $PR^-_i$ sind postive und negative PageRank Werte für den Knoten $i$. Der Originale Wert für $\zeta$ ist 0,85. $\alpha, \beta, \gamma$ sind Werte um die Wichtigkeit der eingehenden Verbindung zu verändern, damit ist der Algorithmus anpassbar.

Sign Prediction

Wir sind daran interessiert, den Effekt von überlappenden Gemeinschaften in Netzwerken zu erkennen. Weiter wollen wir wissen wie sich mithilfe dieser die Verbindungen zwischen zwei Knoten bewerten lassen und wie wir solche voraussagen können. Wie sich Netzwerke bewerten lassen haben wir bereits mit dem Page-Rank Algorithmus und dem HITS Algorithmus gezeigt. Nun geht es um das Problem der Vorhersage von Verbindungen. Dabei wollen wir weiter die Knoten entweder in Knoten $u$, die anderen vertrauen oder in Knoten $v$, welchen vertraut wird, einteilen. Zur Analyse und Vorhersage stehen uns folgende Werte zur Verfügung:

Intra	Ovl	Extra
$indeg_{intra}(u)$	$indeg_{Ovl}(u)$	$indeg_{extra}(u)$
$outdeg_{intra}(u)$	$outdeg_{Ovl}(u)$	$outdeg_{extra}(u)$
$indeg_{intra}(v)$	$indeg_{Ovl}(v)$	$indeg_{extra}(v)$
$outdeg_{intra}(v)$	$outdeg_{Ovl}(v)$	$outdeg_{extra}(v)$

Um nun die Vorhersage für einen Knoten zu ermitteln schreiben wir:

\[indeg_{type}(i)= \frac{indeg^+_{type}(i)-indeg^-_{type}(i) }{indeg^+_{type}(i) +indeg^-_{type}(i)}\]

wobei $type\in \{intra, extra ,Ovl\}$, und weiter:

\[outdeg_{type}(i)= \frac{outdeg^+_{type}(i)-outdeg^-_{type}(i) }{outdeg^+_{type}(i) +outdeg^-_{type}(i)}\]

Somit sollte es möglich sein Knoten die Rolle eines Knotens dem vertraut wird oder die Rolle eines Knoten der vertraut zuzuschreiben.

HITS Vorhersagen

Um nun diese Knoten Vorhersage mit dem HITS Algorithmus zu benutzen benutzen wir finale positive und negative Vektoren für authority und hubs. Die mit diesem Algorithmus ermittelten finalen Werte $a^+_u$,$a^-_u$,$h^+_u$,$h^-_u$ für den Knoten. Wenn man diese finalen Werte mit Knoten den anderer Knoten vergleicht ist eine Verhaltens Vorhersage möglich. Die Werte $\alpha,\beta,\gamma$ können hier für angepasst werden, um zum Beispiel überlappenden Kanten mehr Beachtung zu schenken, dafür wählt man die Werte etwa so:$\alpha=0,3,\beta=0,4,\gamma=0,4$.

Page-Rank Vorhersagen

Damit auch mit Hilfe des Page-Rank Algorithmus eine Vorhersage möglich ist, wird $PR^+_u$ und $PR^-_u$ werden wieder die finalen Werte sich angeschaut und daraufhin Vergleiche vorgenommen. Auch können die Werte $\alpha,\beta,\gamma$ hier angepasst werden um das Modell zu verändern.

Anwendungsbeispiel YouTube

Unser Thema ist die Vorhersage des Sozialen Status in sozialen Netzwerken. Dies ist ohne Problem möglich, da man den sozialen Status durch den vom Algorithmus umstrukturiertem Netzwerk einfach entnehmen kann, denn die Faktoren in unserem Netzwerk einen lokalen Anführer ausmachen sind auch Faktoren die Im Bezug auf sozialen Status relevant sind. So ist unser wert $LLD(i)$ sehr ähnlich zur Definition von Sozialem Status. Nun im Algorithmus wird der Einfluss auf andere Menschen(Knoten), sowie deren Attribut aus der Menge herauszuragen benutzt. Diese zwei Kriterien sollten ausreichen und weiter sind sie in der Lage sozialen Status möglichst simpel zu beschreiben. Dies ist auch mit dem HITS oder dem PAGE Rank Algorithmus möglich, da mit diesen die Rollen der Person der Vertraut wird, sowie der Person welcher Vertrauen schenkt beschrieben werden kann. So ist es möglich Personen, welchen ein großes Vertrauen geschenkt wird, anschließend einen hohen sozialen Status zuzuschreiben.

Youtube als Soziales Netzwerk

Im folgenden wird an einem Beispiel, am Sozialen Netzwerk Youtube die Funktion des Algorithmus gezeigt. Zunächst muss nun die Frage beantworte werden, wieso Youtube ein Soziales Netzwerk ist und wie man in diesem Sozialen Status bestimmen kann. Um zuerkennen das Youtube ein Soziales Netzwerk ist, weisen wir auf folgende drei Themen und deren Datensätze hin.(Mirjam Wattenhofer Roger Wattenhofer Zack Zhu, 2012) Zunächst einmal Sozialer Graph welcher die Anzahl der Abonnenten zeigt, ein sozialer Graph welcher die Kommentar Aktivitäten zeigt und eine Zusammenfassung der sozialen Daten welche auf Youtube hoch geladen werden. Aus diesen drei Datensätzen kann ein Vergleich zu realen Sozialen Netzwerken gebildet werden. Dabei fällt auf, dass im Falle von Youtube im Gegensatz zu nicht online Sozialen Netzwerken der Unterschied zwischen einzelnen Knoten und Knoten mit einem hohen Sozialen Status, die Differenz in deren Kanten Anzahl signifikant größer ist. Trotzdem kann gesagt werden das Youtube ein modernes Soziales Netzwerk. Die monatlich aktiven YouTube-Nutzer beläuft sich auf weltweit 1,9 Milliarden (Stand: Januar 2019). Nun da bestätigt wurde das Youtube als ein Beispiel zur Anwendung nützlich ist wird nun überprüft ob die Umsetzung des Algorithmus möglich ist und ob diese sinnvoll geschieht. Das grundlegende Prinzip des zweistufigen Algorithmus zur Gemeinschaften Findung, besteht zunächst aus der Identifizierung von Anführen und im zweiten Teil dann aus der Zuweisung einzelner Knoten zu einer oder mehreren Gemeinschaften. Weiter muss zunächst, betrachtet werden wie sich in Youtube der soziale Status beschreiben lässt. Nämlich Knoten, welche im Youtube Partner Programm sind. Diese Personen wurden von Youtube selber ausgelesen, um diese und deren Gemeinschaft als gesamtes zu repräsentieren. Personen in diesem Programm besitzen eine hohe Anzahl an Abonnenten, sowie Ansprechpartner innerhalb der Firma und werden auch auf der Homepage unter Vorgeschlagenen Beiträgen normalen Nutzer häufiger Vorgeschlagen. Damit sollte eine Vergleich möglich sein ob der beschriebene Algorithmus implementierbar ist und ob dieser Sinnvoll funktioniert.

Der zweistufen Algorithmus am Beispiel Youtube

Hier zu kann man sich erneut die Formel zur Entdeckung von Anführen anschauen:

\[LLD(i) = \alpha \cdot DASS(i) +(1-\alpha) \cdot ED(i)\]

$ED$, also der Einfluss eines einzelnes Knotens ist einfach zu berechnen, da:

\[ED(i)= \frac{indeg^+(i)-indeg^-(i) }{indeg^+(i) +indeg^-(i)}\]

Hier für ist $indeg(i)$ die Verbindung der Abonnenten zu einem einzelnen Nutzers(i) von Youtube. Daraufhin sind diese noch in $indeg^+(i)$ und $indeg^-(i)$ aufzuteilen, dafür muss die Verbindung zwischen einem Nutzer und dessen Abonnenten bewertet werden. Dies kann recht einfach durch das Like und Dislike Systems in Youtube realisiert werden. Denn nun sagen wir:

\[Verbindung_j(i) = Li_j(i) - Di_j(i)\]

Dafür werden alle Like´s($Li$) und alle Dislike´s($Di$) vom Knoten $i$ die an Beiträge von $j$ ausgeteilt wurden von einander abgezogen. Wenn der Erhaltene Wert $Verbindung_j(i)$ den Wert $\alpha$ überschreitet, so besteht eine positive Verbindung ($indeg^+(i)$) zwischen $i$ und $j$. Wenn der Wert unterschritten wird, dann besteht eine negative Verbindung ($indeg^-(i)$). Dabei ist der Wert$\alpha$ ein Richtwert, welcher für ein Modell angepasst werden müsste. Ich würde als Wert 0 vorschlagen, da so auch Abonnenten, die weder liken noch disliken als positive Verbindung gelten. Zum zweiten muss für den Algorithmus die Differenz zu anderen Knoten große genug sein:

\[DASS(i)= \frac{\sum _{j\in Nei(i)} (deg(j)-deg(i))}{\sum _{j\in Nei(i)} (deg(j)+deg(i))}\]

Diese Differenz zu den Nachbarn wird realisiert, wenn die Kanten zwischen Knoten mithilfe der Abonnenten Funktion deklariert wird. Weiter können auch lokale Anführer nun beschrieben werden:

$\forall j \in Nei(i)$ $LLD(i)>LLD(j)$

Daraufhin können wir auch die Globalen Anführer Identifizieren mit:

\[LL(i) >AFD\]

und

\[AFD= \frac{\sum_{i\in LL}|FL(i)|}{|LL|}\]

$FL$ ist hier bei die Anzahl der Abonnenten von $i$. Unsere Globalen Anführer sollten unter denen des YouTube Partner Programms sein. Nun geht es darum auch zu zeigen das der zweite Part des Algorithmus funktioniert, damit mit diesem Algorithmus auch etwa die Algorithmen zur Verbindungsbewertung benutzt werden können. Dazu muss überprüft werden ob, dass Network coordination game wie angedacht funktioniert, dazu muss nur eine Bedingung zu treffen, nämlich das die Meinung eines Anführer eine Änderung in der Meinung der Anhängers bewirken kann. Welches gegeben ist, wie man unter anderem an Produktplatzierungen erkennt. Nun kann der PayOff, wie oben im Algorithmus gezeigt berechnet werden. Anschließend ist es auch möglich zu berechnen ob ein Knoten zu einer Gemeinschaft gehört oder nicht wie oben gezeigt. Damit ist der Algorithmus zur Strukturierung eines sozialen Netzwerk mit dem oben genannte, Algorithmus möglich.

Möglichkeiten in einem sozialen Netzwerks

Nun stellt sich die Frage was ein solcher Algorithmus für Vorteile bringt. Nun ist es möglich verschiedene Algorithmen wie den vorgestellten HITS und den Page-Rank Algorithmus zu benutzen. Außerdem ist es möglich auf den Sozialen Status eines einzelnen Individuums aufgrund ihrer Stellung im sozialen Netzwerk zurück zuschließen, so kann man davon Ausgehen das ein globaler Anführer einen sehr hohen Sozialen Status hat. Dies könnte man auch mit Hilfe von HITS oder PAGE Rank initialisieren, da man nur nach Knoten denen überdurchschnittlich häufig vertraut wird suchen müsste. Als weiteres Beispiel ist nun mit Hilfe von einem Solchem Netzwerk aufgrund von überlappenden Gemeinschaften auf das Verhalten und die Meinung eines einzelnes Individuums zurück zuschließen. Als Beispiel gibt es bei Youtube eine Seite mit vorgeschlagenen Videos die für das Individuum interessant seien sollen. Nun weiß der Betreiber des Netzwerkes Youtubes, dass das Individuum der Gemeinschaft A eines Youtubers angehört, da dieser dort abonniert hat. Daraufhin kann sich der Betreiber, dass Verhalten anderer Anhänger des Youtubers A, sowie die des Youtubers A selber anschauen und anhand derer Verbindung zu einer anderen Gemeinschaft und deren Video Beiträgen, dem Individuum Beiträge vorschlagen.

Evaluation

Normalized Mutual Information

Mit der NIM wird der Fokus hauptsächlich auf die richtige Mitgliedschaft der einzelnen Knoten, also ob die Knoten sich in der richtigen Gemeinschaft befinden, gelegt. Dabei werden Aspekte wie Grad oder Gewicht der Kanten ignoriert. Das Verfahren Vergleich die Mitgliedschaft Matrix, die das Mitgliedschaftverhalten der einzelnen Knoten beschreibt, mit der vorausgesetzten Grundwahrheit Matrix. Die Ähnlichkeiten werden dann in einer Zahl von 0 bis 1 beschrieben, wobei je größer die Zahl desto mehr Ähnlichkeiten.(Shahriari et al., 2017) Dies ist der NIM Wert.

Modularity

Die Modularität eins Netzwerks beschreibt, im Allgemeinen, die Anzahl der Kanten. Bei der Evaluation mithilfe von diesem Aspekt wird eine erwartete Kantenanzahl von den Gemeinschaften ausgerechnet, die dann kleiner als die tatsächliche Kantenanzahl sein soll. Diese Idee wird dann zu dem Vergleich von verschiedenen Algorithmen hilfreich.

Frustration

Bei der Frustration handelt es sich um die Balance von den Knoten des Netzwerkes. Das Auswerten des Algorithmus verläuft hier mithilfe der Anzahl von den nicht balancierten Kanten, die so niedrig wie möglich sein soll. Ein balanciertes Netzwerk bedeutet im Allgemeinen viele positive Kanten in den Gemeinschaften und negative Kanten zwischen verschiedenen Gemeinschaften.

Auswertung

Im Weiteren werden die Algorithmen SPM, MEA und SDMID unter verschiedenen Aspekten und mit den vorher erklärten Methoden ausgewertet wird. Eine weitere Methode die benutzt wurde ist die Ausführzeit, die eher selbsterklärend ist. Die verschiedenen Aspekte sind zum Beispiel die Große des Netzwerks, der durchschnittliche Grad der Knoten, maximaler Grad der Knoten, die Anzahl der Knoten die sich überlappen und maximale Anzahl an Gemeinschaften.

Im Allgemeinen schneidet der SDMID in den meisten Aspekten, vor einigen in der Ausführzeit, am besten ab. Dagegen hat MEA die schlechteste Leistung von den drei Algorithmen indem es sehr oft schlechte Werte im Bereich der Modularität und Frustration erbringt, vor einigen in den verschiedenen Netzwerk Großen, der maximalen Anzahl der Knoten, der maximalen Anzahl der Knoten die sich überlappen und der maximalen Anzahl von Gemeinschaften. Es schneidet auch schlecht in der Ausführzeit ab. Auch SPM hat mehrmals schlechtere Ausführzeit als SDMID, z.B. in dem Aspekt von der Anzahl von überlappenden Knoten und der maximalen Anzahl von Gemeinschaften. Jedoch er ist fast nie schlechter als MEA.(Shahriari et al., 2017)

Andere Modelle für Sign Prediction

Prestige

Einer der einfachsten Algorithmen für die Vorhersage der vorzeichenbehafteten Netzwerke ist Prestige. Dabei wird das Konzept von dem Prestige vorgestellt, was schließlich ausdrückt wie viele positive Verbindungen ein Knoten erhält. Je mehr positive Verbindungen, desto höher sein Prestige und je mehr negative Verbindungen, desto niedriger das Prestige. Die Anzahl der positiven Verbindungen für den Knoten i wird durch $|IN_i^{(+)}|$ dargestellt und die Anzahl der Negativen durch $|IN_i^{(-)}|$. Damit wir Prestige für den Knoten i wie folgt errechnet:[2]

\[Pr_i=\frac{|IN_i^{(+)}|-|IN_i^{(-)}|}{|IN_i^{(+)}|+|IN_i^{(-)}|}\]

Page Trust

Ein Algorithmus das, im Gegensatz zu dem Originalen Page Rank, für vorzeichenbehaftete Netzwerke geeignet ist, wäre Page Trust. Dieser ist eine Erweiterung von dem vorher erwähnten Page Rank geeignet für Vorhersage der vorzeichenbehafteten Netzwerke. Was diese Algorithmen unterscheidet ist das Page Trust annimmt, dass knoten mit negativen Verbindungen weniger besucht werden. Genauso wie Page Rank verläuft Page Trust rekursiv. Dabei wie ein zufälliger Lauf auf das Netzwerk ausgeführt und es wir eine Matrix die die Wahrscheinlichkeit für den Läufer darstellt, dass i eine negative Verbindung zu j hat. Diese ist die Misstrauen Matrix $P_{ij}$, wobei für die vorher erwähnte Knoten gilt $P_{ij} (i \neq j)$ . Für den Ranking wird dann, mithilfe von Page Rank gewonnener, Einordnungswert von i, dargestellt mit $PT_i$:(Shahriari & Jalili, 2014)

\[PT_i(t+1)=(1-Q_{ii}(t))[\alpha \sum_{j,(j,i) \in G^+}\frac{PT_j(t)}{OUT_j^{(+)}}+(1-\alpha)\frac{1}{N}]\]

Dabei ist $\alpha$ der Vergessenfaktor und Q die Matrix durch $Q(t+1)=T(t)P(t)$ bestimmt. T(t) ist in diesem Fall die Transitionsmatrix, die auch eine normalisierte Form von $A^+$ ist. Mit jedem Schritt wird P nach folgenden Regeln korrigiert:(Shahriari & Jalili, 2014)

\[P_{ij} (t+1)= \begin{cases} 1 \qquad if \: (i \neq j);(i,j) \in G^- \\ 0 \qquad if \: (i = j);(i,j) \in G^-\\ Q_{ij} (t+1) \qquad andernfalls \end{cases}\]

Die initiale Werte, die vorbestimmt werde müssen, werden auf $P(0)=Q(0)=A^-$. $A^+$ ist in diesem Fall die Nachbarschaftsmatrix mit nur negativen Kanten.

Bias und Diverse

Weiterer Algorithmus basiert auf der Idee von Bias und Diverse. Dabei beschreibt Bias das erwartete Gewicht von einer ausgehenden Kante von einem knoten und Diverse, oder auch Prestige genannt, das erwartete Gewicht von den Kanten die ein Knoten bekommt von Knoten die keinen hohen Bias haben. Bias ist in diesem Fall mit der Voreingenommenheit vergleichbar, da sie Meinung von den biased Knoten von einem Vorurteil bestimmt wird und somit auch nicht so hoch angesehen wird als die von den nicht biased Knoten, die keine Vorurteile haben. Diverse wird in den Rechnungen mit $DES_i(t)$ notiert und Bias mit $BIAS_i(t)$ an dem Zeitpunkt t. Diverse wird dann durch folgende Formel ausgerechnet:(Shahriari & Jalili, 2014)

\[DES_i(t+1)=\frac{1}{|IN_i|}\sum_{k\in OUT_i}[a_{ki}(1-X_{ki}(t))]\]

Vergleichbar berechnet man den Bias mit:(Shahriari & Jalili, 2014)

\[BIAS_i (t+1) = \frac{1}{2\lvert OUT_i \rvert} \sum_{k \in OUT_i} [a_{ik} - DES_k (k)]\]

Wobei $\mid IN_i \mid$ die Anzahl von Knoten in $IN_i$ repräsentiert, $a_{ki}$ des zugehörigen Eintrags aus der Nachbarschaft Matrix $A^-$, die aus 1 und 0 Einträgen, für positiv und negativ, besteht. Die Stärke von dem Bias eines Knotens k wird dann wie folgt bestimmt:

\[X_{ki} (t) = max\{0,BIAS_k \times a_{ki}\]

Vergleich von den vorher benutzten Algorithmen

In dem Algorithmus werden angepasste Versionen von HITS und Page Rank gebraucht. Sogar der originale HITS, der eigentlich nicht für vorzeichenbehaftete Netzwerke dient, ist einer der genausten von den Algorithmen mit diesem Zweck. Aus diesem Grunde ist die Wahl von HITS verständlich, da die Anpassung die noch geeigneter macht. Jedoch gibt es keinen Algorithmus der immer am besten abschneidet. Deswegen kann man nicht vorhersagen welche Wahl die beste wäre ohne die Algorithmen vorher auszuprobieren.

Fazit und Ausblick

In dieser Arbeit, haben wir die Verbindung von Algorithmen für überlappende Gemeinschaften und vorzeichenbehaftete Netzwerke. Als erstes haben wir das Modell des zwei-Phasen-Algorithmus vorgestellt, mit welchem man ein Netzwerk beschreiben kann. Für diesen wurde anschließend der HITS und der Page Rank Algorithmus optimiert. Mit diesen ist es möglich ein Netzwerk auszuwerten. Um nun Vorhersagen in diesem Netzwerk treffen zu können haben wir, die Knoten als einen Knoten dem Vertraut wird und einem Knoten welcher vertraut unterteilt. Diese konnte man nun im Netzwerk erkennen, auch mithilfe des HITS und des Page Rank Algorithmus. Anschließend haben wir am Beispiel Youtube gezeigt das ein Solches Netzwerk auch innerhalb eines Sozialen Netzwerkes funktioniert und welche Vorteile einer solcher bietet. Vorteile sind unter anderem die Erkennung von Personen mit einem hohem Sozialen Status, sowie auch Verhaltens-vorhersage einzelner Knoten. Als nächstes haben wir die Ergebnisse des Modells ausgewertet mithilfe von NMI, Modularity und Frustration. Daraus konnte man folgern, dass der SDMID am besten aus den drei abschneidet. Schließlich stellten wir andere, für vorzeichenbehaftete Netzwerke geeignete, Algorithmen vor und vergleichen die mit HITS und Page Ranks. Wir spekulieren auch welcher von den Algorithmen besser für den zwei-Phasen-Algorithmus sein könnte.
Für die Zukunft hoffen wir, dass der zwei-Phasen-Algorithmus weiter überprüft wird und dadurch noch erweitert wird. Dieser Algorithmus kann nämlich in vielen Feldern gebraucht werden. Beispielsweise für die Vorhersage von zukünftigen Berühmtheiten auf sozialen Medien. Dadurch konnten viele Werbegelegenheiten entstehen oder man konnte sogar das Wachstum, von Personen ohne das richtige Image für die sozialen Medien, verhindern. Wir erwarten auch mehr Forschungen die mehrere Aspekte von den sozialen Netzwerken, wie der zwei-Phasen-Algorithmus, verbinden. Dies scheint eine offensichtliche Zukunft der Forschung in dem Feld der sozialen Netzwerke sein. Algorithmen dieses Typs sind den heutigen sozialen Medien sehr ähnlich und stellen dadurch viele Gelegenheiten das Verhalten von sozialen Medien, die heutzutage nicht mehr zu ignorieren sind, zu analysieren und daraus Verbesserungen für das System zu erläutern. Forschung dieser Art konnte vieles in der heutigen Welt für besseres verändern.

Referenzen

Shahriari, M., & Jalili, M. (2014). Ranking Nodes in Signed Social Networks. Social Network Analysis and Mining (SNAM), 4. https://doi.org/10.1007/s13278-014-0172-x
Shahriari, M., Li, Y., & Klamma, R. (2017). The Significant Effect of Overlapping Community Structures in Signed Social Networks. In J. Kawash, N. Agarwal, & T. Özyer (Eds.), Prediction and Inference from Social Networks and Social Media (pp. 51–84). Springer International Publishing. https://doi.org/10.1007/978-3-319-51049-1\textunderscore 3
Mirjam Wattenhofer Roger Wattenhofer Zack Zhu. (2012). The YouTube Social Network (Sixth International AAAI Conference on Weblogs and Social Media, Ed.). https://research.google/pubs/pub37738/

Intra	Ovl	Extra
\(indeg_{intra}(u)\)	\(indeg_{Ovl}(u)\)	\(indeg_{extra}(u)\)
\(outdeg_{intra}(u)\)	\(outdeg_{Ovl}(u)\)	\(outdeg_{extra}(u)\)
\(indeg_{intra}(v)\)	\(indeg_{Ovl}(v)\)	\(indeg_{extra}(v)\)
\(outdeg_{intra}(v)\)	\(outdeg_{Ovl}(v)\)	\(outdeg_{extra}(v)\)