1. An efficient counting method for the colored triad census
- Author
-
Laura M. Koehly, Jeffrey Lienert, Felix Reed-Tsochas, and Christopher Steven Marcum
- Subjects
FOS: Computer and information sciences ,SocArXiv|Social and Behavioral Sciences|Sociology|Ethnomethodology and Conservation Analysis ,050402 sociology ,Theoretical computer science ,Sociology and Political Science ,Computer science ,Ethnomethodology and Conservation Analysis ,SocArXiv|Social and Behavioral Sciences|Sociology|Methodology ,Network science ,Social and Behavioral Sciences ,Homophily ,SocArXiv|Social and Behavioral Sciences|Sociology|Comparative and Historical Sociology ,SocArXiv|Social and Behavioral Sciences|Sociology ,Sociology ,0504 sociology ,Computer Science - Data Structures and Algorithms ,bepress|Social and Behavioral Sciences|Social Statistics ,050602 political science & public administration ,Data Structures and Algorithms (cs.DS) ,Social network analysis ,Categorical variable ,General Psychology ,Statistical hypothesis testing ,Social and Information Networks (cs.SI) ,Social Statistics ,Mathematical Sociology ,Comparative and Historical Sociology ,05 social sciences ,Methodology ,General Social Sciences ,Computer Science - Social and Information Networks ,Directed graph ,SocArXiv|Social and Behavioral Sciences|Sociology|History of Sociology ,SocArXiv|Social and Behavioral Sciences|Social Statistics ,FOS: Sociology ,0506 political science ,bepress|Social and Behavioral Sciences|Sociology ,bepress|Social and Behavioral Sciences|Sociology|Quantitative, Qualitative, Comparative, and Historical Methodologies ,Colored ,SocArXiv|Social and Behavioral Sciences|Sociology|Mathematical Sociology ,Anthropology ,History of Sociology ,bepress|Social and Behavioral Sciences ,Graph (abstract data type) ,SocArXiv|Social and Behavioral Sciences - Abstract
The triad census is an important approach to understand local structure in network science, providing 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 by approximately 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.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 by approximately 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.
- Published
- 2018