Effiziente Algorithmen für Group Centrality (EAGR)

• Antragsteller: Professor Dr. Christian Komusiewicz
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2021 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 450925233

Group Centrality-Probleme dienen der Identifikation wichtiger Gruppen von Akteuren in sozialen Netzwerken. Die Berechnung optimaler Lösungen für Group Centrality-Probleme ist algorithmisch schwierig. Daher werden diese Probleme bisher ausschließlich heuristisch gelöst. In EAGR soll untersucht werden, ob es effiziente Algorithmen gibt, die diese Probleme auf typischen Eingabenetzwerken optimal lösen. Dabei sollen sowohl Algorithmen mit besseren theoretischen Worst-Case-Laufzeiten als auch effiziente Implementierungen entwickelt werden.Zur Entwicklung der verbesserten Algorithmen soll analysiert werden, wie die Struktur des Eingabenetzwerks die Schwierigkeit von Group Centrality-Problemen beeinflusst: Gibt es Netzwerkeigenschaften, die sich algorithmisch ausnutzen lassen oder bleiben Group Centrality-Probleme selbst auf sehr eingeschränkten Netzwerken schwer? Auf praktischer Seite soll untersucht werden, ob ein existierendes Software-Framework zur Lösung schwerer Teilgraphprobleme so erweitert werden kann, dass auch die algorithmisch anspruchsvolleren Group Centrality-Probleme effizient gelöst werden können.

• DFG-Verfahren: Sachbeihilfen