Mixing patterns in graphs with higher-order structure: the role of inter-subgraph correlations

Abstract In this paper, the percolation properties of higher-order networks that have non-trivial clustering and subgraph-based assortative mixing (the tendency of vertices to connect to other vertices based on subgraph joint degree) are examined. Our analytical method is based on generating functions and is exact for the networks we model. We also propose a Monte Carlo graph generation algorithm to draw random networks from the ensemble of graphs with fixed statistics. The proposed model is used to understand the effect that network microstructure has, through the arrangement of inter-subgraph clustering, on the global connective properties of the network. We find that even in k-regular networks, with fixed joint degree distributions and clustering coefficients, the arrangement of clustering has a non-trivial influence on the percolation properties of the network. We find that subgraph disassortativity increases the percolation threshold, whilst assortativity among subgraphs decreases and broadens the transition. Finally, we use an edge disjoint clique cover to represent empirical networks using our formulation, finding the resultant model offers a significant improvement over edge-based theory.