Periodic reordering
Periodic reordering
复制标题
DOI：
10.1093/imanum/drp047
复制
发表时间：
2010-01-01
影响因子：
2.1
通讯作者：
Kalna, Gabriela
中科院分区：
文献类型：
--
作者：
Grindrod, Peter;Higham, Desmond J.;Kalna, Gabriela
对于自然界、科学和技术中的许多网络，可以对节点进行排序，使大多数链接是短程的，连接近邻，而相对较少的远程链接或捷径。给定一个网络作为一组观察到的链接（相互作用），找到揭示这种范围依赖结构的节点排序的任务与科学计算中出现的一些稀疏矩阵重新排序问题密切相关。稀疏矩阵重新排序的谱或Fiedler向量方法已成功地应用于生物数据集，揭示了有用的结构和子模式。在这项工作中，我们认为，定期模拟的标准重新排序任务也是高度相关的。在这里，而不是鼓励非零只躺在一个适当有序的邻接矩阵的对角线附近，我们还允许他们居住在非对角线的角落。事实上，对于Watts & Strogatz（1998）的经典小世界模型，“小世界”网络的集体动力学。Nature，393，440-442）这种类型的周期性结构是固有的。因此，我们设计和测试一个新的频谱算法定期重新排序。通过推广Grindrod（2002，Range-dependent random graphs and their application to modeling large small-world proteome datasets.物理评论E，66，066702-1-066702-7）到周期性的情况下，我们也可以构建一个可计算的似然比，表明一个给定的网络是固有的线性或周期性的。对合成数据的测试表明，新算法可以检测周期性结构，即使在噪声的存在。在真实的生物数据集上的进一步实验表明，一些网络更好地被视为周期性的而不是线性的。因此，我们发现了生物网络周期性的定性（重新排序的网络图）和定量（似然比）证据。
For many networks in nature, science and technology, it is possible to order the nodes so that most links are short-range, connecting near-neighbours, and relatively few long-range links, or shortcuts, are present. Given a network as a set of observed links (interactions), the task of finding an ordering of the nodes that reveals such a range-dependent structure is closely related to some sparse matrix reordering problems arising in scientific computation. The spectral, or Fiedler vector, approach for sparse matrix reordering has successfully been applied to biological data sets, revealing useful structures and subpatterns. In this work we argue that a periodic analogue of the standard reordering task is also highly relevant. Here, rather than encouraging nonzeros only to lie close to the diagonal of a suitably ordered adjacency matrix, we also allow them to inhabit the off-diagonal corners. Indeed, for the classic small-world model of Watts & Strogatz (1998, Collective dynamics of 'small-world' networks. Nature, 393, 440-442) this type of periodic structure is inherent. We therefore devise and test a new spectral algorithm for periodic reordering. By generalizing the range-dependent random graph class of Grindrod (2002, Range-dependent random graphs and their application to modeling large small-world proteome datasets. Phys. Rev. E, 66, 066702-1-066702-7) to the periodic case, we can also construct a computable likelihood ratio that suggests whether a given network is inherently linear or periodic. Tests on synthetic data show that the new algorithm can detect periodic structure, even in the presence of noise. Further experiments on real biological data sets then show that some networks are better regarded as periodic than linear. Hence, we find both qualitative (reordered networks plots) and quantitative (likelihood ratios) evidence of periodicity in biological networks.