Themengebiet
Communities in sozialen Netzwerken sind z.B. Gruppen von Usern, die sich für ein bestimmtes Thema interessieren,
aber auch Freundschaften oder Bekanntschaften.
In realen sozialen Netzwerken überschneiden sich solche Communities z.B. dadurch, dass verschiedene User ähnliche
Freundeskreise besitzen oder aber mehreren Interessensgruppen angehören.
Viele bekannte Algorithmen zur Erkennung von Communities beruhen auf der Annahme, dass jeder Knoten nur einer Community angehört.
Solche Algorithmen bekommen zudem häufig die Anzahl der vorhandenen Communities als Eingabeparameter, welche jedoch bei der Analyse
von realen sozialen Netzwerken im Vorhinein unbekannt ist.
Diese klassischen Algorithmen arbeiten zudem meist auf kleinen Graphen deren Topologie bekannt ist.
Heutige soziale Netzwerke des Web 2.0 bestehen jedoch aus Millionen
von Knoten (Usern) und noch mehr Kanten (Bekanntschaften etc.) untereinander und besitzen eine Topologie, die sich ständig ändert.
Klassische Algorithmen zur Erkennung von Communities, die auf kompletten Graphen arbeiten, sind für die Analyse von realen
sozialen Netzwerken daher ungeeignet. Auch mit heutigen Computer-Ressourcen würde es viel zu lange dauern bzw. ist es unmöglich,
diese Menge an Daten zu analysieren, geschweige denn diese zu visualisieren.
Es werden daher Algorithmen benötigt, die auf lokalen Regeln basieren und verteilt Informationen sammeln und auswerten.
Solche gesuchten neuartigen Algorithmen könnten z.B. von der Natur inspiriert sein (Ameisenalgorithmen etc.) oder an menschliches
Verhalten angelehnt sein.
Aufgabenstellung
Im Rahmen dieser Arbeit soll ein Algorithmus entwickelt werden, der auf geeigneten Datensätzen von sozialen Netzwerken mit Hilfe von
einfachen lokalen Regeln Communities erkennt, die sich zudem überlappen können und hierarchisch aufgebaut sind. Es sollen Hubs gefunden
werden, also Knoten (Individuen), die sich durch eine hohe Popularität bzw. Expertenwissen auszeichnen.
Arbeitsschritte:
- Ermittlung geeigneter Datensätze zum Testen des zu entwickelnden Algorithmus
- Entwicklung eines Algorithmus zur Erkennung von Communities und Hubs in realen sozialen Netzwerken
- Ausführung des Algorithmus auf Datensätzen von realen Netzwerken
- Ausführung des Algorithmus auf geeigneten Benchmark-Graphen und Vergleich mit klassischen Community Detection Algorithmen
- Visualisierung
- Evaluation
- Dokumentation
Voraussetzungen für die Arbeit
Folgende Kenntnisse sind zum erfolgreichen Abschluss dieser Arbeit erforderlich. Es ist wünschenswert, wenn
zumindest grundlegende Kenntnisse vorhanden sind. Zumindest jedoch sollten die Fähigkeit und der Wunsch
vorhanden sein, dieses Wissen autodidaktisch zu erlangen.
- Kenntnisse in Java
- Interesse an der Entwicklung von Graphenalgorithmen
Das Kleingedruckte
Nach Einarbeitung und Umsetzung ist die geleistete Arbeit in der eigentlichen Arbeit sorgfältig zu
dokumentieren. Der implementierte Code ist selbstverständlich vollständig zu kommentieren.
Es sind die Regeln zur Erstellung von wissenschaftlichen Arbeiten des Instituts
zu beachten.
