Vorwort

Das vorliegende Online Buch ist das Ergebnis des Proseminars “Algorithmen für die Entdeckung von Communities in sozialen Netzwerken”, welches im Sommersemester 2017 an der Informatik im Bachelor-Studiengang Informatik durchgeführt worden ist. Die Inhalte, das Layout, die Begutachtung wurden von Bachelor-Studenten selbst gestaltet. Dieses Vorwort soll eine kurze Einführung in das Thema des Proseminars, eine Übersicht über die pädagogischen Zielsetzungen des Proseminars und eine kurze Würdigung der studentischen Beiträge geben.

In sozialen Medien interagieren Menschen mit ähnlichen Interessen und Bedürfnissen. Jeder Mensch ist gleichzeitig (überlappend) in verschiedenen Communities aktiv (Freunde, Studium, Beruf, Hobbies usw.) Charakteristisch ist eine hohe Interaktionsdichte innerhalb einer Community. Zusätzlich wird angenommen, dass er weniger Interaktionen zwischen Communities gibt. Menschen werden in der sozialen Netzwerkanalyse durch Knoten, soziale Interaktionen durch Kanten repräsentiert. Der so entstehende soziale Graph kann algorithmisch untersucht werden, z.B. zur Entdeckung von (überlappenden) Communities. Zur Entdeckung von überlappenden Communities gibt es eine Reihe verschiedener algorithmischer Ansätze. Einige suchen die Knoten mit den meisten Verbindungen in der Annahme, dass dies besonders aktive Mitglieder sind, um die sich andere scharen. Manche Algorithmen suchen Gruppen ähnlicher Knoten. Ähnliche Knoten können beispielsweise in Cliquen, organisiert sind, wo jeder Knoten mit jedem Knoten verbunden sind. Machen Algorithmen suchen gezielte Knotengebiete im sozialen Graphen mit hoher Kantendichte, weil sie davon ausgehen, dass dort besonders viele interagiert wird. Daher untersuchen Algorithmen auch die Inhalte der sozialen Interaktion. Manche Algorithmen konzentrieren sich auf die Wahrnehmung von Veränderungen, beispielsweise die Teilung oder Verschmelzung von Teilgraphen. Damit kommt die Frage auf, wie sich Communities entwickeln? Können Knoten andere beeinflussen, oder finden sich gleichartige Knoten? Können wir vorhersagen, ob zwischen zwei Knoten eine Kante entstehen wird? Können wir vorhersagen, ob eine soziale Interaktion als positiv oder negativ signalisiert wird? Solch identifizierte Communities dienen oft als Basis für Empfehlungs-Systeme, das Vorhersagen von Kanten und Signalen, oder die die Identifizierung von Experten. Angesichts der Vielfalt der Vorgehensweisen und der damit verbundenen Ziele ist es kein Wunder, dass es schwierig ist die Algorithmen nur nach einem oder wenigen Kriterien zu beurteilen. Vielmehr muss eine Vielzahl von Kriterien angewendet werden, um einen guten Algorithmus für den zugrundeliegenden sozialen Graphen und den Einsatzzweck zu finden. Kriterien fragen danach, wie der Algorithmus sich auf dynamischen oder statischen Netzwerken arbeitet, wie gut er sich dezentral im Sinne von verteil ausführen lässt, wie der Algorithmus mit Ausreißern umgeht und ob es besser auf gerichteten oder ungerichteten Graphen, beziehungsweise dünn oder dicht besetzten Graphen arbeitet. Somit ist dieses Buch auch eine Quelle für Praktiker der Analyse von sozialen Graphen.

Neben der Einführung in das klassische, wissenschaftliche Arbeiten, also die Literaturrecherche, das Anfertigen von wissenschaftlichen Texten und das Halten einer wissenschaftlichen Präsentation sollte das Proseminar moderne Formen der Kollaboration in wissenschaftlichen Prozessen vermitteln. Dazu kommen immer öfters Werkzeuge und Techniken aus dem Bereich der agilen Softwareentwicklung zum Einsatz, Jekyll, GitLab, Slack, Web-Sprachen. Der agile Entwicklungsprozess mit mehreren, ineinander übergreifenden Milestones verschiedener Teamaufgaben ist dabei die Blaupause für den wissenschaftlichen Kooperationsprozess und bringt damit zwei aus der Informatik bekannte Praktiken in Einklang. Der Vorteil für den Studenten besteht darin, weniger Werkzeuge lernen zu müssen und Erfahrungen aus beiden Praktiken einfacher übertragen zu können.

Konkrete Aufgaben des Proseminars waren das Erstellen eines Online-Buches über OCD-Algorithmen, das Kollaboratives Arbeiten in Gruppen, als auch zwischen Gruppen. Dazu wurden vertikale und horizontale Teams geschaffen. Die vertikale Teams waren für das Erstellen von Buchkapiteln verantwortlich, die horizontale Teams für das Editieren und Organisieren des Prozesses. Jeder Teilnehmer des Proseminars war Mitglied in einem vertikalen und einem horizontalen Team. Folgende horizontalen Teams wurden gebildet: Design und & Layouting-Team verantwortlich für die Gestaltung des Buchs, das Algorithmus- und Visualisierungs-Team verantwortlich für die Einbettung einer externen Web-basierten Schnittstelle zu den Implementierungen der Algorithmen und die Einbettung einer Javascript-Bibilothek für dir Visualisierung der Kriterien in Form von Spiderweb-Diagrammen, das Präsentations-Team verantwortlich für die Gestaltung der Präsentationsfolien, das Dokumentations- und PR-Team für die Öffentlichkeitsarbeit und das Herausgeber- und Begutachtungs-Team für die Organisation der internen Begutachtung miitels easychair.

Disassortative Degree Mixing and Information Diffusion for Overlapping Community Detection in Social Networks (DMID) von Christian Hoyer, Marc Osterberg, Cedrik Albrecht und Julian Düstersiek beschäftigt sich mit einem zweiphasigen Algorithmus, der in der ersten Phase eine dissassortive Matrix Zur Berechnung von besonders interessanten Knoten berechnet und in der zweiten Phase diese Knoten gegeneinander zur Formation der Communities antreten lässt.

Link Communities (LC) von Kevin Schwarz, Lennard Heller, Xuan Thanh Nguyen und Minh Vu Ngo befasst sich mit einem fast schon klassischen Alfgorithmus, der auf hierarchischer Clusterbildung beruht.

Speaker-listener Label Propagation Algorithm (SLPA) von Axel Thill, Manuel Drazyk und Frederic Kerksieck beschreibt einen Algorithmus, der aufgrund der Nutzung lokaler Informationen dynamisch in drei Phasen die Communities erzeugt, dabei aber unter verschiedenen Startbedingungen zu verschiedenen Ergebnissen kommt. Dafür ist er einer der schnellsten Algorithmen.

Der Algorithmus von Stanoev, Smikov and Kocarev (SSK) von Daniel Höppe ist ebenfalls ein auf lokalen Informationen beruhender Algorithmus in mehreren Phasen, der zunächst eine Einflussmatrix zur Bestimmung der einflussreichsten Knoten und dann stochastische Mitgliedschaftsvektoren für die verbleibenden Knoten berechnet.

Merge Overlapping Natural Communities (MONC) von Sezin Maden, Stephanie Kinderreich und Ali Al-Abaidi untersucht einen parameterfreien, lokalen Algorithmus, der auf gewichteten Graphen arbeitet und eine fortlaufende Optimierung der gefundenen, sich überlappenden Communities auf verschiedenen Auflösungsebenen durchführt.

Identifying overlapping communities in social networks using multi-scale local information expansion (CLIZZ) von David Klüner, Lukas Ochse, Manuel Giel und Yannik Korzikowski der mittels topologischer Entropie optimiert.

Alle Beiträge ordnen sich in die existierende Literatur ein, haben den Algorithmus auch mittels vorhandener sozialer Graphen ausgeführt und die Ergebnisse bewertet. Als Fazit lässt sich festhalten, dass diese Proseminar ein Experiment für alle Beteiligten war. Die Motivation war auf Seiten der Lehrenden und Lernenden gleichermaßen hoch, was über einige organisatorische und auch technische Klippen hinweg half. Leider wird in der aktuellen Prüfungsordnung nur die Ausarbeitung und der mündliche Vortrag als Bestandteile eines Proseminars zur Bewertung herangezogen, sonstige Aktivitäten sind somit freiwillig. Das Thema war sicherlich anspruchsvoll und verlangt mathematische und informatische Kenntnisse, die nicht immer vorausgesetzt werden konnten. Wir haben Workshops durchgeführt, um z.B. Random Walks zu erklären. Das heißt, die Grundlagen der linearen Algebra und Stochastik wurden zusätzlich vermittelt. Dazu kamen noch weitere Workshops für das Lesen und Schreiben wissenschaftlicher Arbeiten, zu den Werkzeugen, zu der Benutzung von Javascript-Bibliotheken zu Visualisierung und zur Organisation eines Peer Review Prozesses. Zu Beginn wurden uns doppelt so viel Studenten zugewiesen wie Plätze zur Verfügung standen. Dadurch wurden die Gruppen auch doppelt so groß, was zusätzliche Komplexität durch die notwendigen Abstimmungen innerhalb der Gruppen mit sich brachte. Kleinere Teams wären unserer Meinung nach deutlich effektiver gewesen. Manche horizontale Teams haben wir während der Veranstaltung zusammengelegt, teilweise bedingt durch abspringende Studenten, teilweise wegen großer inhaltlicher Ähnlichkeit der Aufgaben. Eine vertikale Gruppe bestand am Ende nur noch aus einem Studenten. Insgesamt waren wir mit der Struktur der Durchführung des Proseminars sehr zufrieden und werden im nächsten Jahr auch fast alles wieder so durchführen. Als technische Neuerung sehen wir das gleichzeitige Verfassen wissenschaftlicher Texte über das Web und inhaltlich können wir uns vorstellen, das bestehende Buch mit weiteren Kapiteln auszubauen, aber auch so bestehende Kapitel zu erweitern.

Aachen, im August 2017 Ralf Klamma, Peter De Lange, Mohsen Shahriari