Community Tracking mit Hilfe von Link Prediction in sozialen Graphen

Abstract

Die Beobachtung von Gruppen in sozialen Graphen ist eine komplexe Aufgabe. Zunächst werden diskrete Zeitabschnitte des Graphen erstellt. Anschließend wird für jeden Zeitabschnitt, die darin enthaltenen Gruppen gesucht und über die Zeitabschnitte hinweg in Beziehung gebracht. Dabei unterliegen Gruppen Änderungen in ihrer Größe, sowie den internen und externen Verbindungen. Um die Zuordnung zu verbessern, soll mit Hilfe von Link- und Node Prediction, die Änderungen vorhergesagt werden. Die verwendeten Algorithmen werden auf dem Graph Processing System Apache Giraph ausgeführt.

Tracking communities in social graphs requires the detection of communities in each timestep and the matching of communities between these timesteps. Communities change over time, they split or merge and single nodes enter or leave the graph. Link and node prediction shall ease the matching of communities leading to more accurate tracking results. The used algorithms are implemented on top of the Apache Giraph framework.