  The triad census is an important approach to understand local structure in
network science, providing comprehensive assessments of the observed relational
configurations between triples of actors in a network. However, researchers are
often interested in combinations of relational and categorical nodal
attributes. In this case, it is desirable to account for the label, or color,
of the nodes in the triad census. In this paper, we describe an efficient
algorithm for constructing the colored triad census, based, in part, on
existing methods for the classic triad census. We evaluate the performance of
the algorithm using empirical and simulated data for both undirected and
directed graphs. The results of the simulation demonstrate that the proposed
algorithm reduces computational time many-fold over the naive approach. We also
apply the colored triad census to the Zachary karate club network dataset. We
simultaneously show the efficiency of the algorithm, and a way to conduct a
statistical test on the census by forming a null distribution from 1,000
realizations of a mixing-matrix conditioned graph and comparing the observed
colored triad counts to the expected. From this, we demonstrate the method's
utility in our discussion of results about homophily, heterophily, and
bridging, simultaneously gained via the colored triad census. In sum, the
proposed algorithm for the colored triad census brings novel utility to social
network analysis in an efficient package.
