Alignment and comparison of directed networks via transition couplings of random walks

• 成果类型: Article
• 署名作者: Yi, Bongsoo; O'Connor, Kevin; McGoff, Kevin; Nobel, Andrew B.
• 署名单位: University of North Carolina; University of North Carolina Chapel Hill; University of North Carolina School of Medicine; University of North Carolina; University of North Carolina Charlotte
• 刊物名称: JOURNAL OF THE ROYAL STATISTICAL SOCIETY SERIES B-STATISTICAL METHODOLOGY
• ISSN/ISSBN: 1369-7412
• DOI: 10.1093/jrsssb/qkae085
• 发表日期: 2024
• 页码: 186-210
• 关键词: protein-interaction networks; global alignment; dbar-distance; graph; algorithm; yeast

摘要

We describe and study a transport-based procedure called network optimal transition coupling (NetOTC) for the comparison and alignment of two networks. The networks of interest may be directed or undirected, weighted or unweighted, and may have distinct vertex sets of different sizes. Given two networks and a cost function relating their vertices, NetOTC finds a transition coupling of their associated random walks having minimum expected cost. The minimizing cost quantifies the difference between the networks, while the optimal transport plan itself provides alignments of both the vertices and the edges of the two networks. Coupling of the full random walks, rather than their marginal distributions, ensures that NetOTC captures local and global information about the networks and preserves edges. NetOTC has no free parameters and does not rely on randomization. We investigate a number of theoretical properties of NetOTC and present experiments establishing its empirical performance.