Manuel Sorge started his two-year Feodor Lynen postdoctoral fellowship on October 1, 2020, and will be part of his host’s Martin Nöllenburg’s research unit, Algorithms and Complexity. Together, they will develop new efficient algorithms that help to understand complex networks. The new project is being funded for two years by the Alexander von Humboldt Foundation. The particular focus shall lie on two aspects: the so-called structural sparsity and overlapping clusterings.

The Structure of Networks

Complex networks are all around us, be it Twitter users that follow each other, protein complexes that interact with each other, or foodstuffs that share ingredients. The analysis of such networks is, without a doubt, immensely useful; it can be used to increase political influence or to identify healthy foodstuffs. To better analyze and visualize such networks, it is essential to know their structure.

A network is called structurally sparse if certain dense substructures are not contained in the network. Roughly speaking, such a structure is a collection of parts of the networks such that, when looking from a coarse “zoom level” onto it, then all parts are interacting with each other. This means that there are strong dependencies in the network. Such dependencies lead to high worst-case running times for many computational problems that arise in analyzing complex networks. Thus it is crucial to know whether they are structurally sparse.

Overlapping Clusters

On the other hand, when clustering networks, we usually try to decompose them into disjoint cohesive groups, called clusters, representing communities in social networks or functional units of cells in protein interaction networks. However, some recent studies give evidence that the underlying ground-truth clusters may have substantial overlaps. Thus, it is important to study new concepts of clusterings in which the clusters may overlap and how such clusterings can be computed. This is much more demanding from an algorithmic perspective, but the information gained through such clusterings may better elucidate how agents use social networks, for example.

The two researchers want to employ a mix of theoretical and practical approaches that give each other new impulses in both aspects. The theoretical part encompasses a fine-grained analysis of the underlying algorithmic problems to identify the computationally hard parts as precisely as possible. The resulting knowledge shall be put to use in concrete implementations of the algorithms and their performance tested. The congruence or dissonance between practice and theory then stimulates the theoretical analysis, starting the feedback loop anew.

About The Feodor Lynen Research Fellowship

Named after the former president of the Alexander von Humboldt Foundation, biochemist and Nobel Laureate Feodor Lynen, the Feodor Lynen research fellowship enables researchers with above-average qualifications from Germany at all career levels and in all disciplines to research with members of the Humboldt Network around the world. TU Wien covers a third of the prestigious fellowship.

Curious about our other news? Subscribe to our news feed, calendar, or newsletter, or follow us on social media.