Linear-Time Graph Triples Census Algorithm Under Assumptions Typical of Social Networks

A graph triples census is a histogram of all possible sets of three vertici (called a triple) from a graph. Graph triples census has been in active use in sociology for over 50 years. The earliest paper using this approach is by Holland and Leinhardt. This gives a general description of the structure of directed graphs in a fixed length vector. Since this time, this analytic tool has been widely used in social network analysis. A summary of important papers using this approach, both as end product and as a component of further analysis, are in.