Higher-order random network models

Abstract

Most existing random network models that describe complex systems in nature and society are developed through connections that indicate a binary relationship between two nodes. However, real-world networks are so complicated that we can only identify many critical hidden structural properties through higher-order structures such as network motifs. Here we propose a framework in which we define higher-order stubs, higher-order degrees, and generating functions for developing higher-order complex network models. Then we develop higher-order random networks with arbitrary higher-order degree distributions. The developed higher-order random networks share critical structural properties with real-world networks, but traditional connection-based random networks fail to exhibit these structural properties. For example, as opposed to connection-based random network models, the proposed higher-order random network models can generate networks with power-law higher-order degree distributions, right-skewed degree distributions, and high average clustering coefficients simultaneously. These properties are also observed on the Internet, the Amazon product co-purchasing network, and collaboration networks. Thus, the proposed higher-order random networks are necessary supplements to traditional connection-based random networks.

Keywords

• random graphs
• higher-order structure
• complex networks
• network motif