Tree decompositions of real-world networks from simulated annealing

Konstantin Klemm

Research output: Contribution to journalArticlepeer-review

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.

Original languageEnglish
Article number035003
JournalJPhys Complexity
Volume1
Issue number3
DOIs
Publication statusPublished - Dec 2020

Keywords

  • Density of states
  • Exact algorithm
  • Network decomposition
  • Simulated annealing
  • Tree decomposition

ASJC Scopus subject areas

  • Artificial Intelligence
  • Computer Networks and Communications
  • Computer Science Applications
  • Information Systems

Fingerprint Dive into the research topics of 'Tree decompositions of real-world networks from simulated annealing'. Together they form a unique fingerprint.

Cite this