Praktikum Algorithm Engineering - Graphgeneratoren für soziale Netzwerke

• Betreuung: Dr. rer. nat. Robert Görke, Dr. Marcus Krug, Dr. Andrea Kappes, Prof. Dr. Dorothea Wagner
• Präsenztermine: freitags 9:45–11:15 Uhr, Seminarraum 301 (Informatikgebäude 50.34)
• Vorbesprechung: Die Vorbesprechung wird am Freitag, den 15.04.11, um 9:45 Uhr in Raum 301 stattfinden.
• Teilnahme: Die Teilnehmerzahl ist auf zwölf Personen begrenzt. Anmeldung per E-Mail an Marcus Krug.

• Nähere Informationen werden noch bekanntgegeben.

Hinter vielen Internetportalen wie Facebook, Twitter oder Amazon, die wir heute ganz selbstverständlich benutzen, verbergen sich enorme Datenmengen, die die sozialen Strukturen der Nutzer auf unterschiedlichste Weise beschreiben. Die sozialen Netzwerke, die aus diesen Daten abgeleitet werden können, geben Aufschluss darüber, wer mit wem befreundet ist oder welche Benutzergruppen sich für ähnliche Produkte interessieren und liefern damit auch Erkenntnisse über die sozialen Mechanismen unserer Gesellschaft. Das Auffinden von stark vernetzten Gruppen oder Clustern, die untereinander weniger stark vernetzt sind, spielt dabei eine wichtige Rolle, da der damit verbundene Übergang von einzelnen Individuen zu homogenen Gruppen die Komplexität von Erklärungsmodellen erst beherrschbar macht.

Graphgeneratoren spielen in diesem Kontext aus zwei Gründen eine wichtige Rolle. Zum einen können Graphgeneratoren dabei helfen, die Mechanismen der Entstehung von sozialen Netzwerken zu verstehen, da jeder Generator ein mögliches Modell für das Zustandekommen eines solchen Netzwerkes liefern kann. Je besser die erzeugten Graphen dabei die Eigenschaften sozialer Netzwerke approximieren, desto eher kommen die den Generatoren zugrundeliegenden Mechanismen als Erklärungsmodelle für die Ausprägung sozialer Strukturen infrage. Von besonderem Interesse ist auch hier die Entstehung der oben genannten Cluster. Zum anderen erfüllen Generatoren eine wichtige Funktion bei der Validierung von Algorithmen zur Analyse von sozialen Netzwerken. Da wir die tatsächliche Struktur vieler sozialer Netzwerke aufgrund ihrer Größe und Komplexität nicht kennen können, müssen wir uns darauf verlassen, dass die Algorithmen, die wir zur Analyse von sozialen Netzwerken heranziehen, sinnvolle Ergebnisse liefern. Leider sind viele der Optimierungsprobleme, die sich etwa hinter dem Clustern von Netzwerken verbergen, NP-schwer, so dass man auf Heuristiken zurückgreifen muss. Häufig versucht man daher die Qualität einer solchen Heuristik dadurch zu evaluieren, dass man sie auf ein Netzwerk mit bekannter Struktur anwendet und die gefundenen Strukturen mit den bekannten vergleicht. Graphgeneratoren sind als Quelle von Netzwerken mit bekannten Strukturen dabei häufig unerlässlich.

In diesem Praktikum untersuchen wir unterschiedliche Modelle für die Erzeugung von Graphen zur Simulation von sozialen Netzwerken. Wir gehen dabei von realen Netzwerken aus, die zunächst auf ihre Eigenschaften und Struktur hin analysiert werden sollen. Anschließend werden in kleinen Gruppen unterschiedliche Modelle zur Simulation von sozialen Netzwerken erstellt und implementiert. Dabei sollen, basierend auf bestehenden Modellen, erweiterte Modelle entwickelt werden, die die im Analyseschritt gefundenen Erkenntnisse berücksichtigen. Die entstehenden Generatoren werden schließlich im Vergleich mit den realen Instanzen auf ihre Qualität hin untersucht.

Folien der Vorbesprechung

Réka Albert and Albert-László Barabási, Statistical mechanics of complex networks, Rev. Mod. Phys. 74, 47–97 (2002), PDF

Michał Karoński, Edward R. Scheinerman, Karen B. Singer-Cohen, On Random Intersection Graphs: The Subgraph Problem, Combinatorics, Probability and Computing, Volume 8 Issue 1-2, (1999 )