Modeling Higher-Order Interactions in Complex Networks by Edge Product of Graphs. (22nd June 2021)

• Record Type: Journal Article
• Authors: Wang, Yucheng; Yi, Yuhao; Xu, Wanyue; Zhang, Zhongzhi
• Is Part Of: Computer journal. Volume 65:Number 9(2022)
• Page Start: 2347
• Page End: 2359
• Publication Date: 2021-06-22
• Subjects: graph product -- edge corona product -- complex network -- random walk -- graph spectrum -- hitting time -- mixing time; Computers -- Periodicals; 005.1
• DOI: 10.1093/comjnl/bxab070
• Languages: English
• ISSNs: 0010-4620

Abstract

Abstract: Many graph products have been applied to generate complex networks with striking properties observed in real-world systems. In this paper, we propose a simple generative model for simplicial networks by iteratively using edge corona product. We present a comprehensive analysis of the structural properties of the network model, including degree distribution, diameter, clustering coefficient, as well as distribution of clique sizes, obtaining explicit expressions for these relevant quantities, which agree with the behaviors found in diverse real networks. Moreover, we obtain exact expressions for all the eigenvalues and their associated multiplicities of the normalized Laplacian matrix, based on which we derive explicit formulas for mixing time, mean hitting time and the number of spanning trees. Thus, as previous models generated by other graph products, our model is also an exactly solvable one, whose structural properties can be analytically treated. More interestingly, the expressions for the spectra of our model are also exactly determined, which is sharp contrast to previous models whose spectra can only be given recursively at most. This advantage makes our model a good test bed and an ideal substrate network for studying dynamical processes, especially those closely related to the spectra of normalized Laplacian matrix, in order to uncover the influences of simplicial structure on these processes.