Efficient Algorithms for Group Centrality (EAGR)

群体中心性问题用于识别社交网络中的重要参与者群体。 计算群体中心性问题的最优解在算法上是困难的，因此这些问题通常通过启发式方法来解决。研究项目EAGR调查是否有有效的算法，最佳地解决这些问题的现实世界的情况。 为此，该项目旨在开发具有改进的最坏情况运行时间和有效实现的算法。为了达到改进的算法，应研究输入网络的结构如何影响问题的算法难度：是否存在可以在算法上利用的网络属性，或者即使在非常有限的情况下，组中心性问题仍然很难解决？在实践方面，它应调查，是否现有的软件框架解决硬子图问题可以扩展到组中心性问题，这是算法上更具挑战性。

Group Centrality problems are used to identify groups of important actors in social networks. Computing optimal solutions for Group Centrality problems is algorithmically hard an thus these problems are usually solved by heuristic methods. The research projectEAGR investigates whether there are efficient algorithms that solve these problems optimally on real-world instances. To this end, the project aims at the development of algorithms with improved worst-case running times and efficient implementations.To reach improved algorithms, it shall be investigated how the structure of input networks influences the algorithmic difficulty of the problem: Are there network properties that can be exploited algorithmically or do Group Centrality problems remain hard even on veryrestricted instances? On the practical side it shall be investigated, whether an existing software framework for solving hard subgraph problems can be extended to Group Centrality problems which are algorithmically even more challenging.