2018/04/09 by Samir Chowdhury, Chowdhury, Samir, Facundo Mémoli +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Neuroscience · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Gene Regulatory Network Analysis #Metric Geometry (math.MG) #Neural dynamics and brain function #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1804.02820
openalex publication_date 2018/04/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the question of reconstructing a weighted, directed network up to isomorphism from its motifs. In order to tackle this question we first relax the usual (strong) notion of graph isomorphism to obtain a relaxation that we call weak isomorphism. Then we identify a definition of distance on the space of all networks that is compatible with weak isomorphism. This global approach comes equipped with notions such as completeness, compactness, curves, and geodesics, which we explore throughout this paper. Furthermore, it admits global-to-local inference in the following sense: we prove that two networks are weakly isomorphic if and only if all their motif sets are identical, thus answering the network reconstruction question. Further exploiting the additional structure imposed by our network distance, we prove that two networks are weakly isomorphic if and only if certain essential associated structures---the skeleta of the respective networks---are strongly isomorphic.