Dynamic programming for calculating the triad census

Triad census is a popular static analysis technique that summarizes topology and triadic behavior in a network. However, traditional static methods for counting triad motifs do not scale for dynamic analysis on large event logs of digital trace data increasingly used in computational social science. Further, tracking triad evolution over time can provide insights into behavioral elements such as information brokerage not captured in static analysis. We propose Dynamic Triad Census (DTC), a dynamic programming algorithm to calculate the triad census procedure efficiently over time. Formal analyses of the correctness and computational complexity of the proposed method are supported by numerical experiments that demonstrate its accuracy and improved efficiency over existing static counting methods. We show how efficient computation and storage of census motifs enables dynamic network analysis of triad transition and brokerage behavior in longitudinal networks by using motifs as covariates in other dynamic techniques and as their own objects of inquiry.