An efficient counting method for the colored triad census

Lienert, Jeffrey, Koehly, Laura, Reed-Tsochas, Felix and Marcum, Christopher Steven (2019) An efficient counting method for the colored triad census. Social Networks, 58. pp. 136-142. (Accepted)

[img] PDF - Accepted Version
Restricted to Repository staff only until 24 October 2020.

Download (346kB)


The triad census is an important approach to understand local structure in network science, providing comprehensive assessments of the observed relational congurations 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 mixingmatrix
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.

Item Type: Article
Keywords: triad census, labeled graphs, simulation
Subject(s): Complexity
Centre: CABDyN Complexity Centre
Date Deposited: 09 May 2019 10:58
Last Modified: 09 May 2019 10:58

Actions (login required)

Edit View Edit View