Clustering Large Evolving Networks

01.01.2018 bis 31.12.2020

One of the most significant problems in network sciences is clustering or community detection. It is a principle tool for exploratory data analysis and is also crucial for applications such as image processing, server load balancing, and several other areas. Theoretical guarantees on network clustering show that many popular methods are statistically accurate for very large networks. However, one often overlooks the fact that such methods are quite inefficient for large scale applications, and hence, practically efficient clustering algorithms deviate significantly from the theoretically studied methods. The purpose of this project is to blend theory with practice by developing efficient network clustering algorithms that have provable theoretical guarantees, and are also efficient for large scale applications. To this end, we explore the problems of:
(1) clustering graphs, where weights or presence of only few edges are computed using sampling strategies,
(2) streamed clustering of evolving graphs, where the nodes and edges of the graph are revealed sequentially, and the aim is to update the communities in real time, and
(3) extension of the above methods and results to more complex networks that can be represented as hypergraphs.