Efficient orbit-aware triad and quad census in directed and undirected graphs.

Area of Science:

• Graph theory
• Network analysis
• Computational mathematics

Background:

• Subgraph statistics are crucial for network analysis, social network analysis, and systems biology.
• Assessing subgraph prevalence is vital for MCMC sampling and estimation in stochastic network models.
• Existing methods for subgraph counting are often limited in scope or generality.

Purpose of the Study:

• To develop a unified approach for counting all induced and non-induced four-node subgraphs (quad census).
• To enable per-node and per-edge counting of these subgraphs, categorized by their non-automorphic roles.
• To extend the quad census methodology to directed graphs.

Main Methods:

• A novel approach based on a clique-listing subroutine.
• Unified counting of induced and non-induced four-node subgraphs.
• Extension of the quad census to directed graphs, inspired by the triad census.

Main Results:

• The first unified method for comprehensive quad census.
• Demonstrated computational efficiency and superior performance compared to previous methods.
• Development of the asymptotically fastest triad census algorithm as a byproduct.

Conclusions:

• The proposed quad census method offers a simple yet powerful tool for network analysis.
• This approach enhances the study of network effects and stochastic network models.
• The findings provide significant advancements in both subgraph enumeration and network algorithm efficiency.