Gong Xue, Higham Desmond J, Zygalakis Konstantinos
School of Mathematics, University of Edinburgh, Edinburgh EH9 3FD, UK.
The Maxwell Institute for Mathematical Sciences, Edinburgh EH8 9BT, UK.
R Soc Open Sci. 2021 Oct 13;8(10):211144. doi: 10.1098/rsos.211144. eCollection 2021 Oct.
We consider spectral methods that uncover hidden structures in directed networks. We establish and exploit connections between node reordering via (a) minimizing an objective function and (b) maximizing the likelihood of a random graph model. We focus on two existing spectral approaches that build and analyse Laplacian-style matrices via the minimization of frustration and trophic incoherence. These algorithms aim to reveal directed periodic and linear hierarchies, respectively. We show that reordering nodes using the two algorithms, or mapping them onto a specified lattice, is associated with new classes of directed random graph models. Using this random graph setting, we are able to compare the two algorithms on a given network and quantify which structure is more likely to be present. We illustrate the approach on synthetic and real networks, and discuss practical implementation issues.
我们考虑用于揭示有向网络中隐藏结构的谱方法。我们建立并利用了通过（a）最小化目标函数和（b）最大化随机图模型的似然性来进行节点重新排序之间的联系。我们专注于两种现有的谱方法，它们通过最小化挫折感和营养不连贯性来构建和分析拉普拉斯风格的矩阵。这些算法分别旨在揭示有向周期层次结构和线性层次结构。我们表明，使用这两种算法对节点进行重新排序，或将它们映射到指定的晶格上，与新的有向随机图模型类别相关联。在这种随机图设置下，我们能够在给定网络上比较这两种算法，并量化哪种结构更有可能存在。我们在合成网络和真实网络上说明了该方法，并讨论了实际实现问题。
