Tree decompositions of real-world networks from simulated annealing

Abstract

Decompositions of networks are useful not only for structural exploration. They also have implications and use in analysis and computational solution of processes (such as the Ising model, percolation, SIR model) running on a given network. Tree and branch decompositions considered here directly represent network structure as trees for recursive computation of network properties. Unlike coarse-graining approximations in terms of community structure or metapopulations, tree decompositions of sufficiently small width allow for exact results on equilibrium processes. Here we use simulated annealing to find tree decompositions of narrow width for a set of medium-size empirical networks. Rather than optimizing tree decompositions directly, we employ a search space constituted by so-called elimination orders being permutations on the network's node set. For each in a database of empirical networks with up to 1000 edges, we find a tree decomposition of low width.