Bootstrapping on undirected binary networks via statistical mechanics.
Bootstrapping on undirected binary networks via statistical mechanics.
复制标题
DOI：
10.1007/s10955-014-1043-6
复制
发表时间：
2014-09-01
影响因子：
1.6
通讯作者：
Koehl, Patrice
中科院分区：
文献类型：
--
作者：
Hsieh Fushing;Chen Chen;Liu, Shan-Yu;Koehl, Patrice
我们提出了一种新的方法，从统计力学的启发提取几何信息的无向二进制网络和生成随机网络，符合这种几何。在这种方法中，一个无向二进制网络被视为一个热力学系统的置换邻接矩阵的集合作为其状态。从网络中提取信息的任务，然后重新制定为一个离散的组合优化问题，寻找其基态。为了解决这个问题，我们应用多个温度调节马尔可夫链的合奏，建立一个超度量几何的网络。这种几何结构配备了一个树形层次结构，可以捕获网络的多尺度社区结构。我们将这种几何结构转化为Parisi邻接矩阵，它具有相对较低的能级，并且处于基态附近。Parisi邻接矩阵，然后进一步优化，使块排列的超度量几何。最优矩阵对应于原始网络的宏观状态。然后生成随机网络的集合，使得这些网络中的每一个都符合这个宏状态;相应的算法还提供了这个集合的大小的估计。通过在网络的超度量几何的不同尺度上重复这一过程，就有可能计算其演化熵，也就是说，当我们从几何结构的粗略描述转向新描述时，可以估计其复杂性的演化。我们证明了这种方法的性能模拟以及真实的数据网络。
We propose a new method inspired from statistical mechanics for extracting geometric information from undirected binary networks and generating random networks that conform to this geometry. In this method an undirected binary network is perceived as a thermodynamic system with a collection of permuted adjacency matrices as its states. The task of extracting information from the network is then reformulated as a discrete combinatorial optimization problem of searching for its ground state. To solve this problem, we apply multiple ensembles of temperature regulated Markov chains to establish an ultrametric geometry on the network. This geometry is equipped with a tree hierarchy that captures the multiscale community structure of the network. We translate this geometry into a Parisi adjacency matrix, which has a relative low energy level and is in the vicinity of the ground state. The Parisi adjacency matrix is then further optimized by making block permutations subject to the ultrametric geometry. The optimal matrix corresponds to the macrostate of the original network. An ensemble of random networks is then generated such that each of these networks conforms to this macrostate; the corresponding algorithm also provides an estimate of the size of this ensemble. By repeating this procedure at different scales of the ultrametric geometry of the network, it is possible to compute its evolution entropy, i.e. to estimate the evolution of its complexity as we move from a coarse to a ne description of its geometric structure. We demonstrate the performance of this method on simulated as well as real data networks.
登录
查看更多内容
影响因子：
32.8
作者：
Goldenberg, Anna;Zheng, Alice X.;Airoldi, Edoardo M.
通讯作者：
Airoldi, Edoardo M.
影响因子：
5.7
作者：
Barabasi, Albert-Lashlo
通讯作者：
Barabasi, Albert-Lashlo
影响因子：
2.4
作者：
Chen, Chen;Fushing, Hsieh
通讯作者：
Fushing, Hsieh
影响因子：
2.4
作者：
Bianconi, Ginestra
通讯作者：
Bianconi, Ginestra
影响因子：
56.9
作者：
ANDERSON, PW
通讯作者：
ANDERSON, PW