Static and Dynamic Hierarchical Graph Decompositions

Networks are used to model many real-world objects such as social networks, communication networks such as the internet, road networks, biological networks, and neural networks. In the technical literature networks are frequently also called graphs. The goal of this project is to achieve a better understanding of how to solve various computational problems on networks such as routing traffic through networks, mining the structure of networks such as finding clusters in a social network, or simply analyzing various properties of networks. Many such problems are hard to solve, meaning that no fast algorithm is known for solving them exactly and, thus, the problem is often solved approximately. Hence, our goal is more specifically to design faster and better (with regard to the quality of the approximation) algorithms for a variety of important computational problems on networks. As real-world networks often change dynamically, we will also develop algorithms that can adapt to the changes in the network and after each change quickly recompute the answer, faster than rerun the algorithm on the whole network. Our main approach for designing such algorithms is to partition the graph into subgraphs, solve the problem on each such subgraphs and then combine these solutions. This would be a two-level approach, where all subgraphs belong to level 2 and the complete graph forms level 1. To create a hierarchical graph decomposition we apply this approach recursively to each subgraph, i.e., we split each subgraph into sub-subgraphs etc. For different network properties these hierarchical graph decompositions are different and for some such decompositions do not even exist yet. Our goal is to design such hierarchical graph decompositions, and efficient algorithms to compute them and to maintain them when the network changes.