论文标题
来自模拟退火的实际网络的树木分解
Tree decompositions of real-world networks from simulated annealing
论文作者
论文摘要
网络的分解不仅对结构探索有用。它们还具有在给定网络上运行的过程的分析和计算解决方案（例如ISING模型，渗透，SIR模型）的含义和使用。在此考虑的树和分支分解直接代表网络结构作为网络属性递归计算的树。与在社区结构或群体方面的粗晶近似不同，宽度足够小的树木分解可以在平衡过程中获得精确的结果。在这里，我们使用模拟退火来找到一组中型经验网络的狭窄宽度的树分解。我们没有直接优化树的分解，而是采用了由所谓的消除订单构成的搜索空间，即网络节点集中的排列。对于具有多达1000个边缘的经验网络数据库中的每个数据库，我们发现了一个低宽度的树分解。
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.
