Abstraktionsunterstütztes Clustering in sozialen Online-Netzwerken und Interaktionsströmen

• Antragstellerinnen / Antragsteller: Professor Dr. Ulrik Brandes; Professorin Dr. Dorothea Wagner
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2014 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 254952906

In dem vorgeschlagenen Projekt entwickeln wir neue Methoden zum Clustern großer sozialer Online-Netzwerke, und zwar sowohl für den statischen als auch für den dynamischen Fall. Dazu werden wir Netzwerkgerüste entwerfen, welche die lokal unterschiedliche Kohäsion in sozialen Netzen repräsentieren und verstärken. Um diese effizient berechnen zu können, sollen sie selbst lokal definiert werden. Sie sollen nicht nur als Vereinfachungs- und Vorverarbeitungsschritt für das Clustern dienen, sondern auch zu einem neuen Verständnis der Evolution sozialer Gruppen beitragen, bei dem die Handlungen der beteiligten sozialen Akteure deutlicher zum Tragen kommen.Muster in sozialen Online-Beziehungen aufzuspüren und zu nutzen ist zu einem der wesentlichen Anwendungsfelder von Big Data geworden. Dies liegt an dem relativ einfachen Zugang zu solchen Daten und wird verstärkt durch den immensen wirtschaftlichen und politischen Wert, den derartige Daten darstellen. Zwar haben diese prozessgenerierten Daten einen riesigen Umfang, sie entstehen allerdings aus den Aktionen von Einzelpersonen, die nur ein sehr begrenztes Wissen über das Gesamtsystem haben. Daher ist unsere Arbeitshypothese, dass für die Gruppierung von Akteuren durch Partitionierung oder durch Überdeckung des sozialen Netzes lokale Informationen bereits ausreichend informativ sind. Zudem gehen wir davon aus, dass eine zusätzliche Berücksichtigung von Attributen die empirische Relevanz von berechneten Gruppen weiter erhöhen wird. Schließlich wird die Verallgemeinerung auf zeitlich stabile Netzwerkgerüste zu verlässlicheren Abbildungen der Dynamik von Gruppenzugehörigkeiten führen.Durch die Kombination von Ausdünnung mit Imputation und Knotenattributen wollen wir neu eingeführte Konzepte lokal definierter Abstraktionen von Graphen weiterentwickeln und ihre Tauglichkeit als Vorverarbeitung für neue Graphen-Clusterverfahren mit guten Skalierungseigenschaften untersuchen. Dabei werden wir die Strukturmerkmale sozialer Netze ausnutzen um annähernd lineare Laufzeiten zu erzielen. Asymptotische Laufzeiteffizienz stellt für uns zwar ein wichtiges Kriterium dar, gleichwohl werden wir besonderes Augenmerk auf die Ausnutzung von Lokalitätseigenschaften und die Praktikabilität unserer Verfahren legen. Die Berücksichtigung von algorithmischen Techniken für den Umgang mit Datenströmen ist ohnehin geboten, da soziale Online-Netzwerke typischerweise Folgen dyadischer Interaktionen generieren. Um auch riesige Graphen bearbeiten zu können werden wir einen neuen Fokus auf External-Memory-Algorithmen legen. Andererseits werden wir der Generierung von Graphen besondere Aufmerksamkeit schenken, da synthetische Benchmark-Graphen für die Unterstützung der experimentellen Evaluation von Algorithmen unerlässlich sind.Schließlich erwarten wir, dass die im Projekt entwickelten Werkzeuge auch für die Analyse von Big Data in anderen Anwendungsbereichen verwendet werden können.

• DFG-Verfahren: Schwerpunktprogramme
• Teilprojekt zu: SPP 1736: Algorithmen für große Datenmengen
• Internationaler Bezug: Schweiz