News

A paper about a new algorithm that counts important patterns in networks, by a team including Marc Roth from the Centre has been accepted by SODA 2026, the Symposium on Discrete Algorithms (the premier venue for foundations of algorithms research).

"Network Motifs" are patterns in the structure of networks. A simple example of a motif is where two points are linked by a series of single hops, but where there is also a direct shortcut link that takes you there in one hop. If this pattern appears more often than expected in a network then it would be a motif of that network.

Motifs are important in real-life networks such as social networks or genetic networks (that control how molecules interact with each other inside cells). Network motifs appear more often in such real-life networks than in random networks.

The number of times certain motifs appear in a network correlates with a variety of important properties of that network as a whole, such as the ways nodes cluster together in communication networks, or how certain types of cancer are more likely in metabolic networks. Consequently, the computational problem of computing the number of times given motifs appears in large networks has received a lot of attention over the last 20 years.

So far, the state of the art applies almost exclusively to networks in which data can be represented as a graph, that is, via individual datapoints that are organised in binary connections where edges of the graph link only two nodes.

In this new paper, a novel algorithm has been developed that operates on "hypergraphs", that is, on data organised in a way where one edge can link between more than two nodes, such as in relational databases.

Moreover, the authors have proved that the newly developed algorithm is optimal with respect to its running time under standard assumptions from complexity theory, related to the P vs NP conjecture. There can be no faster algorithm that does the same thing.

The paper "The Parameterised Complexity of Counting Small Sub-Hypergraphs" can be found at: https://doi.org/10.1137/1.9781611978971.72