2025/07/23 by Vilhelm Agdur, Jessica Enright, Agdur, Vilhelm +9
Computer Science · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Topological and Geometric Data Analysis
paper · doi:10.48550/arxiv.2507.17541
openalex publication_date 2025/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Modularity is a very widely used measure of the level of clustering or community structure in networks. Here we consider a recent generalisation of the definition of modularity to temporal graphs, whose edge-sets change over discrete timesteps; such graphs offer a more realistic model of many real-world networks in which connections between entities (for example, between individuals in a social network) evolve over time. Computing modularity is notoriously difficult: it is NP-hard even to approximate in general, and only admits efficient exact algorithms in very restricted special cases. Our main result is that a multiplicative approximation to temporal modularity can be computed efficiently when the underlying graph has small treewidth. This generalises a similar approximation algorithm for the static case, but requires some substantially new ideas to overcome technical challenges associated with the temporal nature of the problem.