Ipsen Mads, Mikhailov Alexander S
Fritz-Haber-Institut der Max-Planck-Gesellschaft, Faradayweg 4-6, D-14195 Berlin, Germany.
Phys Rev E Stat Nonlin Soft Matter Phys. 2002 Oct;66(4 Pt 2):046109. doi: 10.1103/PhysRevE.66.046109. Epub 2002 Oct 14.
Can a graph specifying the pattern of connections of a dynamical network be reconstructed from statistical properties of a signal generated by such a system? In this model study, we present a Metropolis algorithm for reconstruction of graphs from their Laplacian spectra. Through a stochastic process of mutations and selection, evolving test networks converge to a reference graph. Applying the method to several examples of random graphs, clustered graphs, and small-world networks, we show that the proposed stochastic evolution allows exact reconstruction of relatively small networks and yields good approximations in the case of large sizes.
能否从动态网络系统产生的信号的统计特性中重建指定该网络连接模式的图？在本模型研究中，我们提出了一种基于拉普拉斯谱重建图的 metropolis 算法。通过突变和选择的随机过程，不断演化的测试网络收敛到一个参考图。将该方法应用于随机图、聚类图和小世界网络的几个示例，我们表明所提出的随机演化能够精确重建相对较小的网络，并且在网络规模较大时也能给出较好的近似结果。
