# Transitivity Correlation: Measuring Network Transitivity as Comparative
Quantity

David Dekker Special thanks go to the participants of the seminar series at
the Center for Business Network Analyses (University of Greenwich)and at the
CASOS seminar(Carnegie Mellon University). Correspondence should be sent to
David Dekker, E-mail<EMAIL_ADDRESS>University of Greenwich  David
Krackhardt  Carnegie Mellon University  Tom A.B. Snijders  University of
Oxford  University of Groningen

###### Abstract

This paper proposes that common measures for network transitivity, based on
the enumeration of transitive triples, do not reflect the theoretical
statements about transitivity they aim to describe. These statements are often
formulated as comparative conditional probabilities, but these are not
directly reflected by simple functions of enumerations. We think that a better
approach is obtained by considering the linear regression coefficient of ties
$i\,\rightarrow\,j$ on the number of two-paths
$i\,\rightarrow\,k\rightarrow\,j$ for the $(n-2)$ possible intermediate nodes
$k$. Two measures of transitivity based on correlation coefficients between
the existence of a tie and the existence, or the number, of two-paths are
developed, and called “Transitivity Phi” and “Transitivity Correlation”. Some
desirable properties for these measures are studied and compared to existing
clustering coefficients, in both random (Erdös-Renyi) and in stylized networks
(windmills). Furthermore, it is shown that under the condition of zero
Transitivity Correlation, the total number of transitive triples is determined
by four underlying features of any directed graph: size, density, reciprocity,
and the covariance between indegrees and outdegrees. Also, it is demonstrated
that plotting conditional probability of ties, given the number of two-paths,
provides valuable insights into empirical regularities and irregularities of
transitivity patterns.

Keywords: Network Transitivity, Transitive Triples, Transitivity Covariance,
Transitivity Correlation, Transitivity Phi, Clustering Coefficient, Balance

##  1 Introduction

Transitivity is the qualitative aspect of the transitive triple configuration
(e.g., Holland & Leinhardt,, 1976) that occurs when there is a tie between an
ordered pair of nodes $i$ and $j$, and there exist at least one node $k$, such
that there are directed ties from $i$ to $k$, and from $k$ to $j$.
Transitivity measures have been developed to measure the frequency or relative
frequency of transitive triples in networks (e.g., Holland and Leinhardt,
1970; Frank, 1980). Newman et al., (2001) write: “Clustering refers to the
increased propensity of pairs of people to be acquainted with one another if
they have another acquaintance in common”[p.026118-12](italics added).
Corresponding to this, but using the more traditional term ‘transitivity’
rather than ‘clustering’, we refer to ”network transitivity” as the network-
level property that captures the increased propensity of pairs of nodes to be
directly connected when they are connected through an intermediary node.

The motivation of this paper resides in the fact that although network
transitivity has been quantified to describe theoretical processes, this
quantification has been separate from those theories. As noted by Holland and
Leinhardt (1976), many theoretical statements in sociology and psychology are
framed in terms of transitive triple configurations. In fact, various strands
of scientific literature (e.g., biology, sociology, social psychology,
physics) assign an important role to this configuration. Yet, theories
explicitly or implicitly using the concept of network transitivity refer to
the frequency of transitive triples being higher relative to some null
situation, e.g. balance theory in psychology, epidemiology or diffusion in
biology, medicine and marketing science. This means it is not enough to
consider the frequency or relative frequency of transitive triples in a
network, but a measure needs to capture the increase in frequency compared to
a situation without transitivity. Here a set of measures is developed,
presented and analyzed that can capture the increased propensity of transitive
triples in networks.

It is important to distinguish this set of measures from other related
concepts, especially, clustering. In social sciences, micro processes are
considered at the basis of many macro social phenomena we can observe (e.g.,
Coleman,, 1990; Faust,, 2010; Schelling,, 1978). A ubiquitous construct in
studying consequences of such processes is the concept of clustering in social
networks. That is, frequently such social structures are not merely random
aggregations of ties, such as modeled in Erdös-Renyi digraphs or expander
graphs. Rather, clustering is the extent to which there are regions in the
network that have a higher density than there is between these regions. A
micro process that has been foundational to clustering is transitivity. A
macro level assessment of transitivity among triples is the global level
property called network transitivity. Clustering has been equated to network
transitivity. For example, in their pivotal paper, Newman et al., (2001,
p.026118-12) state:“…clustering in social networks [is] also sometimes called
network transitivity.” However, the two concepts do differ. While most of the
literature has focused on the global property of clustering, this paper
explores the equally important property of network transitivity.

The ideas in this paper also build on the work of authors (e.g., Holland &
Leinhardt,, 1970; Wasserman,, 1975; Feld & Elmore,, 1982; Faust,, 2007) who
have shown that the triad censuses of networks are highly associated with
lower order properties (nodal and dyadic). This implies that descriptive
network transitivity measures should control for the lower order properties.
The purpose of this paper is to elaborate this.

In this paper, first a theoretical development of network transitivity
measures is presented. Second, existing and new measures of network
transitivity are defined and their properties described. Third, behavior of
different measures is compared in examples (stylized, random, and empirically
observed networks). Subsequently, findings and further research opportunities
are discussed, and conclusions presented.

##  2 Transitivity in Social Sciences

###  2.1 Theory Formalization and Generalization

The importance of network substructures in theory construction is well
exemplified by Heider’s balance theory (1946; 1958). The eminent psychologist,
Fritz Heider, proposes balance theory as an explanation for the valence a
person attributes to objects that she associates to another person. As such,
balance theory demonstrates the importance of transitivity in formalizing
social theory. Furthermore, Cartwright & Harary, (1956) formalize and
generalize Heider’s balance theory from one triple to $n(n-1)(n-2)$ triples in
digraphs.

Such formalizations and generalizations allow us to make statements about
substructures in whole systems, which are essential in allowing to make
empirical descriptions of theoretical processes on a global level. The gap
between local observations and the global nature of much social theory can be
bridged “… by examining local structural properties and determining whether
they hold, on the average, across entire social systems.” (Holland &
Leinhardt,, 1976). Hence, average occurrence of local structures (or sub-
structures) is considered an important descriptive statistic of whole systems
as it allows to link social structure to global theoretical statements.

###  2.2 Network Transitivity as a Comparative Quantity

Transitivity is a property of ordered labeled 3-sub-graphs (Holland &
Leinhardt,, 1971, 1972) or triples. It thus not only plays a role as
conceptual configuration in sociological theory, it is also an attractive
statistical concept for network modeling. It’s theoretical importance in much
of social science stems from a Heiderian view that transitivity occurs in
social interactions at a rate that is in excess of what we would expect by
chance (Davis,, 1967). This has led to statistical modeling of the frequency
of transitive triples under a variety of null models (e.g., Holland &
Leinhardt,, 1971; Frank,, 1988; Karlberg,, 1999).

Another view that shares the same Heiderian roots, yet deviates from the
approach that focuses on enumerating the absolute or relative number of
transitive triples can be derived from Newman et al., (2001). They define
network transitivity as: “… the increased propensity of pairs of people to be
acquainted with one another if they have another acquaintance in common”
[p.026118-12] (italics added). Here, the concept of network transitivity is
not reflected by a mere average measure of transitive triples, but rather an
average increased propensity to form transitive triples. This definition
suggests measuring an intrinsic comparative transitivity quality of a network.
This contrasts, for example, an external comparison of transitive triple
counts or ratios to an assumed network model.

In the literature, transitivity is measured usually as the ratio of transitive
to potentially transitive triples (Harary & Kommel,, 1979; Frank,, 1980;
Karlberg,, 1999) or as the average density of personal networks (Watts &
Strogatz,, 1998; Newman et al.,, 2001). These measures, based on relative
frequencies, do not reveal much about an increased propensity.

“Network transitivity” quantifies a statement about the comparative frequency
of transitive triples among relevant triples in the network. It reflects a
structural hypothesis that refers to an elevated conditional probability of
ties given at least one two-step between pairs of nodes. This is an intrinsic
statement about the occurrence of non-vacuously transitive triples given two-
step paths111This only covers part of the Heiderian view on balance, which
considers also balance in vacuously transitive triples., or two-paths,
compared to triples for which the condition does not hold.

To define such a comparison, for a given observed digraph with $n$ nodes, we
rely on two simple probability mechanisms. In Section 3.1 we use the
probability distribution consisting of the random choice of an ordered triple
$(i,j,k)$ of vertices ($i\,\neq\,j,$ $i\,\neq\,k$, $j\,\neq\,k$) from the
total of $n$ vertices. The probability distribution used in Section 3.2 is the
random choice of a pair of vertices and will be further elaborated in that
section. For the first probability distribution we consider the triplet
(Wasserman & Faust,, 1994) of tie variables $x_{ij},\,x_{ik},\,x_{kj}$, which
are defined as the dichotomous (0/1) indicators of the existence of the ties
$i\,\rightarrow\,j,\ i\,\rightarrow\,k$, and $k\,\rightarrow\,j$,
respectively. Probabilities under the random choice of an ordered triple
$(i,j,k)$ will be denoted by $p$. The basic comparison is given by the
difference between conditional probabilities of a tie, given a two-step path,
and, a tie given no two-step path,

$p(x_{ij}=1\mid x_{ik}x_{kj}=1)\,-\,p(x_{ij}=1\mid x_{ik}x_{kj}=0),$ (1)

where a positive difference demonstrates an increased propensity towards
transitivity. This difference reflects the most relevant alternative to the
configuration central to the definition of Newman et al., (2001), namely, the
configuration where pairs of people are acquainted with one another if they
have no other acquaintance in common.

##  3 Measurement of Transitivity

In this section we define various measures that express the comparative
frequency of transitive triples in a network.

###  3.1 Difference in Conditional Probability and Centered Clustering
Coefficient

For transitivity as a purely descriptive statistic, a common definition is the
ratio of transitive to potentially transitive triples (e.g., Wasserman &
Faust,, 1994), as proposed by Harary & Kommel, (1979):

$\displaystyle C=\frac{\sum\limits_{i}\,\sum\limits_{j\neq
i}x_{ij}\,\sum\limits_{k\neq
i,j}x_{ik}x_{kj}}{\sum\limits_{i}\,\sum\limits_{j\neq i}\,\sum\limits_{k\neq
i,j}x_{ik}x_{kj}}=\frac{\sum\limits_{i}\,\sum\limits_{j\neq
i}\,\sum\limits_{k\neq
i,j}x_{ij}x_{ik}x_{kj}}{\sum\limits_{i}\,\sum\limits_{j\neq
i}\,\sum\limits_{k\neq i,j}x_{ik}x_{kj}}.$ (2)

If the network is non-directed, this is equal to the well-known formula

$C=\frac{3\times\text{number~{}of~{}triangles~{}in~{}the~{}graph}}{\text{number~{}of~{}connected~{}triples~{}of~{}vertices}},$
(3)

coined the clustering coefficient by Newman et al., (2001). This is equal to
the first term in (1),

$C=p(x_{ij}=1\mid x_{ik}x_{kj}=1).$ (4)

Comparing (1) and (4) immediately shows that (4) is only a partial expression
of theoretical statements about network transitivity, because it lacks a
comparative aspect.

Another measure for transitivity is the clustering coefficient defined by
Watts & Strogatz, (1998) as the mean of local transitivity around the nodes.
The version for digraphs is given by

$\displaystyle
LC=\overbracket{LC_{i}}=\frac{1}{n}\sum\limits_{i}\frac{\sum\limits_{j\neq
i}\sum\limits_{k\neq i,j}x_{ij}x_{ik}x_{kj}}{OD_{i}(OD_{i}-1)},$ (5)

where $OD_{i}=\sum_{h}x_{ih}$ is the outdegree of node $i$. Just like (2),
however, this is not a comparative measure.

To develop a measure that does have a comparative nature, just like (1), we
present the two by two table for the two random variables $x_{ij}$ and
$x_{ik}x_{kj}$ under the probability distribution of randomly drawing a triple
$(i,j,k)$. Here $x_{ij}$ indicates the existence of a direct tie between $i$
and $j$ and $x_{ik}x_{kj}$ indicates the existence of a two-path, i.e., an
indirect connection.

|  | $x_{ik}x_{kj}$ |
---|---|---|---
|  | 1 | 0 |
$x_{ij}$ | 1 | $p_{11}$ | $p_{10}$ | $p_{1+}$
0 | $p_{01}$ | $p_{00}$ | $p_{0+}$
|  | $p_{+1}$ | $p_{+0}$ | $1$
Table 1: Transitivity Joint and Marginal Probabilities

The cells in Table 1 contain joint probabilities, while the row and column
sums give marginal probabilities, respectively. The joint probability’s first
index indicates whether $x_{ij}=1$ or 0, while the second index indicates
whether $x_{ik}x_{kj}=1$ or 0. For example, $p_{11}$ is the joint probability
of a tie between the pair $(i,j)$ and a two-step between this pair via $k$. In
the marginal entries, a plus (+) indicates summing over both joint
probabilities. For example, $p_{1+}$ is the marginal probability of a tie,
which is the sum of the joint probabilities of a tie and a two-path, and a tie
and no two-path.

Given that conditional probability is given by the ratio of joint probability
and marginal probability, (1) is equal to
$p_{11}/p_{+1}~{}-~{}p_{10}/(1-p_{+1})$. It is well known that this difference
is the bivariate linear regression coefficient for dichotomous data (see Falk
& Well,, 1997, for an excellent exposition). We use this expression to define
(1) as TPB (Transitivity Phi Beta):

$\displaystyle\textit{TPB}=\frac{p_{11}}{p_{+1}}-\frac{p_{10}}{(1-p_{+1})}.$
(6)

A bivariate regression coefficient is equal to the covariance between the two
variables divided by the variance of the explanatory variable. This implies
that another expression is

$\textit{TPB}=\frac{\text{cov}(x_{ij},x_{ik}x_{kj})}{\text{var}(x_{ik}x_{kj})},$
(7)

where again the variance and covariance are with respect to the probability
distribution of randomly drawing a triple of nodes from the digraph.

This expression emphasizes that centering is the major difference with
existing measures. The numerator in (7), which we shall call Transitivity
Covariance, is by definition a centered measure for the joint occurrence of
ties and two-paths in an observed digraph. The measures in equations (2) and
(5), clearly are not centered. The centering is essential for the comparative
nature of our measure for network transitivity.

A major advantage of centering is that it yields the value of 0 if there is no
network transitivity in the sense that the existence of a two-path is not
associated with the existence of a direct tie. For dichotomous variables a
covariance of 0 is equivalent to independence; therefore, our transitivity
measure TPB is 0 if and only if, in case a triple $(i,j,k)$ is randomly drawn,
the existence of the direct tie $i\,\rightarrow\,j$ is independent of the
existence of the two-path $i\,\rightarrow\,k\,\rightarrow\,j$. A direct
expression for the Transitivity Covariance is the centered joint probability,

$\text{cov}(x_{ij},x_{ik}x_{kj})=\frac{1}{n(n-1)(n-2)}\sum_{i}\sum_{j\neq
i}\sum_{k\neq i,j}x_{ij}x_{ik}x_{kj}-\overbracket{x}\cdot\overbracket{xx},$
(8)

where $\overbracket{x}$ is the proportion of ties, or density in the digraph,
and, $\overbracket{xx}$ is the proportion of two-paths among all triples of
nodes in the digraph.

Another measure can be obtained as the bivariate correlation coefficient
instead of the regression coefficient. For this measure, bounded between $-1$
and $+1$, the Transitivity Covariance is divided not by the variance of the
two-path indicator but by the product of the two standard deviations. As both
variables are dichotomous, the Pearson product-moment correlation coefficient
is also known as the $Phi$ coefficient (Falk & Well,, 1997). Here, we use the
term “Transitivity Phi”,

$\textit{TPhi}=\frac{\text{cov}(x_{ij},x_{ik}x_{kj})}{\sqrt{\text{var}(x_{ij})\text{var}(x_{ik}x_{kj})}}.$
(9)

The obvious further advantage of this measure is that it is bounded between
$-1$ and $+1$.

###  3.2 Correcting for Two-path Autocorrelation

The measures proposed in the preceding section do not take into account the
multi-level issue that for each pair $(i,j)$ there are $n-2$ potential
vertices $k$, which play a different role in the triplet than $i$ and $j$. The
‘clustering’ of two-paths through specific $k$’s for a given $(i,j)$, which
may be called the autocorrelation between different two-paths connecting the
same pair $(i,j)$, is ignored.

Considering the set of all potential ‘third’ vertices $k$ leads to interest in
the relation between the total number of two-paths connecting $i$ and $j$, and
the existence of a direct tie $i\,\rightarrow\,j$. Therefore we now turn to
the second probability model which is defined as the random draw of an ordered
pair $(i,j)$. To distinguish this from the model of the preceding section we
indicate the other nodes by the letter $h$, distinguishing them from the
single third node $k$ in the preceding section. Accordingly we define the
Transitivity Correlation222This measure has been implemented in function
gtrans in the R-package ’sna’ (Butts,, 2016, p.112). by

$\textit{TC}=\frac{\text{cov}\Big{(}x_{ij},\sum\limits_{h\neq
i,j}x_{ih}x_{hj}\Big{)}}{\sqrt{\text{var}(x_{ij})\text{var}\big{(}\sum\limits_{h\neq
i,j}x_{ih}x_{hj}\big{)}}}.$ (10)

The relation between TPhi and TC is derived in Appendix A) and indeed depends
on the two-path autocorrelation.

The other measure, similar to TPB in (7), replaces variance in two-paths for
ordered triples $(i,k,j)$ with the variance of the number of two-paths for
ordered node pairs $(i,j)$. This is the bivariate regression coefficient of
ties on the number of two-paths between ordered pairs $(i,j)$,

$\displaystyle TB=\frac{\text{cov}\Big{(}x_{ij},\sum\limits_{h\neq
i,j}x_{ih}x_{hj}\Big{)}}{\text{var}\Big{(}\sum\limits_{h\neq
i,j}x_{ih}x_{hj}\Big{)}},$ (11)

This slope gives a linear approximation of the conditional probability of a
tie, given the number of two-paths. As such it is more informative about the
increased propensity towards transitivity than for example the clustering
coefficient $C$ in (2), which gives an mean conditional probability over all
two-path counts.

At this point it should be emphasized that the expected values, covariances,
etc., referred to in this paper are those of ties between randomly chosen
vertices in an observed network, not those of possible underlying random graph
processes. A disadvantage of this is that the measures discussed above can not
be used for statistical inference without non-trivial additional assumptions.
What is subtracted in centering is not the expected value under a null model
for networks. As shown in the next section, a necessary condition for
$\textit{TC}=0$ and $\textit{TPhi}=0$ is that the number of two-paths is a
specified function of $n$, density, mutuals, and the covariance between in-
and outdegrees.

However, there are random graph processes that do generate an expected value
of $\textit{TC}=0$ and $\textit{TPhi}=0$. For example, in Erdös-Renyi digraphs
we have

$\displaystyle E\Big{\\{}X_{ij}\sum_{h\neq i,j}X_{ih}X_{hj}\Big{\\}}={}$
$\displaystyle E\\{X_{ij}\\}\,E\Big{\\{}\sum_{h\neq
i,j}X_{ih}X_{hj}\Big{\\}}.$ (12)

This does show that the expected value of the numerator in the covariance
measures under the Erdös-Renyi digraph model is $0$. Since what is subtracted
takes account of the indirect connections, this centering is more subtle than
the null expected value under the Erdös-Renyi digraph.

Further, we note that TC and TPhi differ only in the denominator, i.e., the
standardization. Therefore one way of studying the differences between these
measures is to consider the digraphs for which TC or TPhi are $-1$ or $+1$ if
such digraphs exist.

Digraphs that are unions of complete sub-graphs, to which also isolated points
may be added, are completely transitive in the sense that $C=1$. If all these
sub-graphs have the same size, then also $\textit{TC}=\textit{TPhi}=1$.
However, if the sub-graph sizes are different, then TC and TPhi are less than
1.

##  4 Behavior of Transitivity Covariance Measures

In assessing the utility of these centered measures we look at the behavior in
comparison to existing clustering coefficients. Much of it will depend on the
properties of Transitivity Covariance, when we know it to be zero.

###  4.1 Descriptive Mathematical Properties

Empirical studies find that the frequency of triangles in a network is to a
large extent accounted for by lower order network properties (e.g., Faust,,
2007). If it is totally accounted for by lower order properties it may be
expected that transitivity covariance is close to zero. Then it would be
concluded that there is no “increased” (or decreased) propensity toward
transitivity. The mean number of transitive triples over all ordered pairs
$(i,j)$ is given by

$TT\,=\,\frac{1}{n(n-1)}\sum_{i=1}^{n}\,\,\sum_{\mathclap{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}}^{n}\enskip\,\sum_{\mathclap{\begin{subarray}{c}h=1\\\
h\neq i,j\end{subarray}}}^{n}\enskip x_{ij}\,x_{ih}\,x_{hj}\ .$ (13)

For any digraph, the condition $\textit{TC}=0$ is equivalent to

$TT\,=\,\frac{\big{(}n\,\,\text{cov}(OD,ID)\,+\,n\,d^{2}\,-\,M\big{)}\,d}{n(n-1)}$
(14)

(for a proof see Appendix B). Equation (14) expresses the necessary and
sufficient condition for a zero correlation between $x_{ij}$ and
$x_{ik}x_{kj}$. Therefore, if (14) holds, which is equivalent to
$\textit{TC}=0$, no elevated or decreased propensity to transitivity may be
said to exist in the network. The number of transitive triples then is
determined by a function of four parameters: number of nodes $n$, density
(number of ties), reciprocity (number of mutual ties, $M$), and covariance
between the degree distributions, $\text{cov}(OD,ID)$.

The fact that $\textit{TC}=0$ implies a conditioning on $\text{cov}(OD,ID)$
relates to the observation of Feld and Elmore (1982), who observe that “…
inequality of popularity among individuals implies disproportionate
frequencies of particular types of triads, including transitive triad types”.
They do not make clear how the “increased propensity” of transitive triples
depends on degree. Transitivity covariance does control for such popularity
induced transitivity as it incorporates the covariance between in- and
outdegree.

###  4.2 Telling Problem: Don Quichot Measures and Windmills

An example that illustrates the problems with different measures for an
increased propensity of transitive triples in networks is given by structures
named windmill graphs (see for example Jackson,, 2008). A windmill graph has
one center node connected to all other nodes, while all other nodes are in
’wings’, which are even sized cliques where all nodes are connected within
wings, but not to any other node (except the center node). Windmills
$W_{m}^{r}$ are characterized by two parameters: the size of each wing
$(r>2)$, and the number of wings $(m>1)$ (see for examples Fig. 1).

Figure 1: Windmills ($W^{r}_{m}$) with different values for $r$ and $m$

In such graphs, there are either $1$ or $(r-2)$ two-paths between each pair of
nodes, where the latter are always part of a transitive triple, while the
former are not. Given this morphological constriction, windmills provide an
experimental model that allows to vary the number of non-transitive two-paths
and transitive triples as functions of $r$ and $m$. The number of two-paths in
a windmill is given by

$W_{TS}=m\,r\,(r-1)\,(r-2)\ +\ m\,(m-1)\,(r-1)^{2},$ (15)

where the first part on the right-hand side is the number of transitive
triples, while the second part gives the number of intransitive triples. The
latter increases more strongly in $m$ as it is a quadratic polynomial, while
the former is linear in $m$. The opposite holds for $r$ as the number of
transitive two-paths increases cubically, and the intransitive triples
quadratically, in $r$. Hence, this network model allows to manipulate the
total degree of network transitivity.

To assess the behavior of network transitivity measures on the windmill model
we express them in terms of $m$ and $r$. Table 2 summarizes these expressions,
as well as their behavior in the limit when either or both approach infinity.
It is important to recall that the clustering coefficients in (2) and (5) give
the conditional probability of a transitive triple, and the mean conditional
probability of a transitive triple occurring in a neighborhood, respectively.
The contradictory effects of increases in $m$ and $r$ result in an undefined
value for the clustering coefficient ($C$) in the bivariate limit, while it
behaves as expected in the univariate limits. As $r$ increases it tends
towards $1$, while it tends to $0$ with increasing $m$.

Similarly, the local clustering coefficient ($LC$), in the limits, reflects
that apart for the single central node, all neighborhoods are cliques where
all two-paths are transitive, so that it tends towards $1$. The contradictory
outcome between $LC$ and $C$ as $m\rightarrow\infty$ was first noted in
Jackson, (2008, p.36-37).

In windmills, the transitivity covariance based measures, which are weighted
functions of TPB in (7), illustrate another important distinction. For
increasing wing size $r$, the difference in conditional probabilities (TPB)
still depends on the number of wings, $m$. On the other hand, when $m$ grows,
the difference tends towards $0$ irrespective of $r$. The multivariate limit
is undefined as it will depend on the asymptotic ratio $m/r$.

TPhi is restricted to [$-1,1$] as it is a correlation coefficient. In the
limit in $r$ it becomes a decreasing function of $m$, and approaches $0$ for
increasing $m$. This is the correlation between $x_{ij}$ and $x_{ik}x_{kj}$
for a random triple $(i,j,k)$. For an increasing number of wings $m$ the
conditional probability of the two-path through a random $k$ between a given
pair of nodes, i.e., $P\\{x_{ik}x_{kj}=1\|i,j\\}$, tends to zero for all pairs
$(i,j)$; this implies that the correlation tends to 0. The consideration of a
random third node does not bring out the clustering pattern for windmills with
many wings, and therefore this pattern yields approximately a zero
correlation.

The covariance-based measures that weight on bases of the cumulative number of
two-paths, TC and $TB$, do signal this autocorrelation. First, TC as a bounded
measure on [$-1,1$] is a constant $1$, reflecting the perfect control for the
morphological similarity of different size windmills. It indicates the perfect
correlation that occurs in these structures, where the presence of a tie
implies $(r-2)$ two-paths, while lack of a tie implies $1$ two-path — the
regularity that defines windmills.

In the limit $TB$ in windmills tends to $0$. The decline in the ratio of
transitivity covariance (based on number of two-paths) and the variance of the
number of two-paths is due to the fact that $Var(\sum_{h}x_{ih}x_{hj})$ is a
factor $(r-3)$ larger than $Cov(x_{ij},\sum_{h}x_{ih}x_{hj})$. This shows that
for the value of TC a direct interpretation is more clear than for TB.

Table 2: Transitivity measures for Windmills Measure | $f(m,r)^{*}$ | $\lim_{r\rightarrow\infty}f$ | $\lim_{m\rightarrow\infty}f$ | $\lim_{(r,m)\rightarrow(\infty,\infty)}f$ |
---|---|---|---|---|---
Clustering Coefficients: |
$C$ | $\frac{r(r-2)}{r(r-2)+(m-1)(r-1)}$ | 1 | 0 | Undefined |
$LC$ | $1-\frac{n-r}{n}\frac{1}{n-2}$ | 1 | 1 | 1 |
Composites for covariance based measures: |
$Var(x_{ij})$ | $\frac{r(n-r)}{n^{2}}$ | $\frac{m-1}{m^{2}}$ | 0 | 0 |
$Var(x_{ik}x_{kj})$ | $\frac{((n-1)(n-2)-(r-1)(r-2))(n+r(r-3))}{n^{2}(n-2)^{2}}$ | $\frac{m^{2}-1}{m^{4}}$ | 0 | 0 |
$Var(\sum_{h}x_{ih}x_{hj})$ | $\frac{(m-1)r(r-1)(r-3)^{2}}{n^{2}}$ | $\infty$ | 0 | Undefined |
$Cov(x_{ij},x_{ik}x_{kj})**$ | $\frac{(m-1)r(r-1)(r-3)}{n^{2}(n-2)}$ | $\frac{m-1}{m^{3}}$ | 0 | 0 |
Covariance based measures (triadic probability model): |
TPhi | $\frac{\sqrt{(}r)(r-3)}{\sqrt{(nr+r(r-3))(n+r(r-3))}}$ | $\frac{1}{\sqrt{m+1}}$ | 0 | 0 |
TPB | $\frac{(n-2)r(r-3)}{(n+r-3)(n+r(r-3))}$ | $\frac{m}{m+1}$ | 0 | Undefined |
Covariance based measures (dyadic probability model): |
TC | 1 | 1 | 1 | 1 |
TB | $\frac{1}{r-3}$ | 0 | $\frac{1}{r-3}$ | 0 |
*̂$n=m(r-1)+1$, *̂*Note that $\lim_{(r,m)\rightarrow(\infty,\infty)}(n-2)Cov(x_{ij},x_{ik}x_{kj})$ is undefined. |

###  4.3 Erdös-Renyi Random Digraphs

The stylized example on windmills in the previous section shows that a family
of morphological similar networks can produce measures that are undefined in
the limit, while they may give ambiguous readings for small networks. This is
not a desirable property. However, in practice other families of networks may
be more important to consider.

Figure 2: Means of Transitivity Covariance based measures and means of the
clustering coefficients plotted as a function of density in random Erdös-Renyi
digraphs ($n=100$). It becomes immediately clear that the clustering
coefficients increase with density, while there certainly is no increased
propensity of these random networks to form transitive triples. The
transitivity covariance-based measures remain stable around zero as density
increases. Each point is a mean value of each of the measures based on $100$
random draws of Erdös-Renyi digraphs with given density.

If there is known to be independence between ties and two-paths in a network
there would not be expected any elevation or increased propensity in
transitive triples, or network transitivity. Here we compare the behavior of
different measures for Erdös-Renyi digraphs (Erdös & Renyi,, 1959). In these
networks all ties are independent, and the probability for a tie is constant,
determining the expected density. Hence, within this family of networks on
average we do not expect to find any increased propensity for transitive
triples to occur. Consequently, on average a transitivity measure should be
independent of the density, in other words, control for the density. Through
simulations we first analyze the dependence of different measures on density.
Figure 2 shows the results of these analyses for Erdös-Renyi digraphs. It
shows that the covariance based measures are, as expected, independent of
density; while $C$ and $LC$ are, respectively, linear and non-linear functions
of density (for the latter result see also Newman,, 2003).

We illustrate the measures by considering two networks harvested from our
simulations of Erdös-Renyi digraphs. These networks exhibit transitivity and
intransitivity, respectively. We specifically look at digraphs selected from
simulations with $n=21$ and low mean degree, for graphical clarity.

The cases we consider are depicted in Figure (3). The networks in Figures
(3(a)) and (3(b)) are very similar on many properties, such as density, mean
number of two−step paths, mean degree, and mean path length. Also the
clustering coefficients are similar, at least they wouldn’t lead to very
different conclusions about the networks. Yet, the transitivity covariance
measures indicate positive and negative values for network transitivity,
respectively. TPB shows that the probability of a transitive tie in Figure
(3(a)) is $4.7\%$ higher than the probability of a tie given there is no two-
path, while the probability of transitive ties is $2.5\%$ lower in Figure
(3(b)). This difference in probabilities shows that in these cases, otherwise
very similar, still there are opposite propensities toward the formation of
transitive triples to form, with a large difference of $(7.2\%)$ in the
contrasts of conditional probabilities.

(a)
Positive value for Network Transitivity

(b)
Negative value for Network Transitivity

Figure 3: Examples of positive and negative values for network transitivity in
Erdös-Renyi digraphs ($n=21$)

###  4.4 Observed Networks

The covariance based measures of transitivity can be interpreted as linear
approximations of the relationship between direct ties and two-path ties. In
particular, TB is the linear regression coefficient of the tie indicator on
the number of two-paths between the node pair. Graphical inspection of this
relationship may provide insight about the appropriateness of the linearity
assumption. Due to combinatorial restrictions the relationship may be highly
non-linear, which can be directly assessed from a plot. Example datasets were
obtained via public websites333Data via Opsahl, (2017).,444Data via Freeman,
(2017)..

(a) ”Southern Women”-Data (Davis et al., (1941)), cf. footnote 3.

(b) ”Law Firm Friendships”-Data (Lazega,, 2001), cf. footnote 4.

(c) ”Neural Network of Caenorhabditis elegans worm (C.elegans)”-Data (Watts &
Strogatz,, 1998), Dichotomized, cf. footnote 3.

(d) ”High-Tech Managers Reports To”-Data (Krackhardt,, 1987), cf. footnote 4.

Figure 4: A. Illustrating $10$ descriptive network statistics on 12 datasets.
All reported graphs and descriptives are based on $x_{ij}\in\\{0,1\\}$. In
case data are valued, they are dichotomized by the rule:
$x_{ij}=1~{}\forall~{}y_{ij}>0$ else $x_{ij}=0$, unless differently indicated.
On the vertical axis conditional probabilities for ties are shown, and dot
sizes indicate the number of ordered pairs for each count of two-paths
(horizontal axis). The horizontal line indicates the clustering coefficient
($C$) for that network. It can be interpreted as the weighted mean conditional
probability over all groups of two-path counts. Third, the linear regression
line between ties and number of ordered two-paths is shown. The slope of this
line is given by $TB$ (T. Beta). The digraph plots show the networks without
isolates.

(a) ”Rodriguez Madrid Train Bombing”-Data (Hayes,, 2006), Dichotomized, cf.
footnote 4.

(b) ”Coauthors’ Network”-Data (Newman,, 2006), Dichotomized, cf. footnote 4.

(c) ”R&D Team in Manufacturing Company”-Data (Cross & Parker,, 2004),
Dichotomized $x_{ij}=1~{}\forall~{}y_{ij}>4$, cf. footnote 3.

(d) ”Protein-Protein Interaction”-Data ((Jeong et al.,, 2001)), cf. footnote
4.

Figure 5: B

(a) ”Dolpins Frequently Associating”-Data (Lusseau,, 2003), cf. footnote 4.

(b) ”24 Country Minerals and Fuels Trade”-Data (Smith & White,, 1992;
Wasserman & Faust,, 1994), cf. footnote 4.

(c) ”Florentine Marriage”-Data (Padgett & Ansell,, 1993), cf. footnote 4.

(d) ”Florentine Business”-Data (Padgett & Ansell,, 1993), cf. footnote 4.

Figure 6: C

In Figure (4: A, B, C), $12$ network datasets from different fields are
analyzed. Each figure contains a diagram, an associated graph plot, and
relevant summary statistics. The diagram shows the conditional probability for
a tie given the number of two-paths on the vertical axis, and the number of
two-paths on the horizontal axis. Information in the diagram is based on the
depicted network although for clarity isolate nodes have been excluded.

Number of observations (ordered pairs of nodes) in each category of two-path
counts is indicated by the size of dots. Each dot is connected with a straight
line to emphasize the differences and direction in change of conditional
probabilities between categories.

The horizontal dotted line indicates the clustering coefficient ($C$) for that
network. This can be interpreted as the ’mean conditional probability’ over
all categories of two-path counts. By definition this measure discards all
information about the differences between categories of two-path counts.

The dashed linear regression line between ties and number of ordered two-paths
gives a linear approximation for these differences. The slope of this line is
given by TB, which hence allows for a network level indication of an increased
(decreased) propensity towards transitivity. A down-side is that TB doesn’t
allow for comparison between networks or a direct interpretation. However, TC
is a linear transformation of TB, which serves these purposes.

The relevant summary statistics here are $n$, the number of nodes in the
network, number of isolates (not depicted in the digraph plot), density, and
the mean number of 2-step paths between the $n\,(n-1)$ node pairs, average
degree (Avg. Deg.), Transitivity covariance (Trans. Cov.), Clustering
Coefficient, C (Clus. Coef.), Local Clustering Coefficient, LC (Loc. Clus.
Coef.), transitivity correlation, TC (T. Corr.), and transitivity beta, TB (T.
Beta).

The example networks are from a variety of fields, and differ in size
($\textit{n}=16$ to $\textit{n}=2114$) and structure ($\textit{d}=.001$ to
$\textit{d}=.908$). In most examples there is a positive TB, implying that in
all these networks there is network transitivity. The exception is the formal
organizational ’reports to’ relationship among high-tech managers (Figure
4(d)). The negative value for network transitivity here is induced by the
design of formal organizational networks, which are usually set up as trees.
Although in some examples a low clustering coefficient ($\textit{C}<.2$), such
as for C. elegans (Fig. 4(c)), protein interactions (Fig. 5(d)), and Mediaeval
Florentine Family Weddings (Fig. 6(c)), could be interpreted as no tendency
towards transitivity in the network, this would be a mistake. The positive
regression coefficient TB indicates an elevated propensity towards transitive
triples occuring on average throughout these networks as the number of two-
paths between pairs increases.

It must be emphasized that no inferential claims can be made about the
statistical significance of these descriptive statistics. This would require
further non-trivial assumptions about underlying digraph distributions. What
could be done is to make a case by case comparison. For example, in the
Florentine families data (Fig.’s 6(d) and 6(c)) it would be a valid statement
to say that network transitivity is higher in the observed business network
compared to the marriage network.

Further, this is not restricted to comparing networks on the same group of
nodes, but holds for comparison between any type of network if we would
compare TC. For example, comparing the Southern women club with friendships in
a law firm, the latter has (slightly) lower TC ($.443$ vs. $.445$), and hence
lower network transitivity. In this case the clustering coefficient would have
led to the same conclusion. But, this is not always so.

Comparing the inter country trade of minerals and fuel data (Fig. 6(b)) with
frequent, and, very frequent information exchange (Fig. 5(c)) shows very
similar diagrams. However, the clustering coefficients ($\textit{C}=.417$ and
$\textit{C}=.344$, respectively) would suggest a different conclusion than
when comparison is done on transitivity correlation ($\textit{TC}=.481$ and
$\textit{TC}=.584$, respectively). This is due to differences in density of
the two networks. The conditional probability of a transitive triple is higher
in observed mineral and fuel trade network compared to information exchange,
due to a higher density. The increased propensity towards transitive triples
is more increased in the information exchange network, and in this sense it
shows more network transitivity.

Further, a remarkable finding that illustrates the value of these plots is
that in three cases (Fig.’s 4(c), 5(a), 5(d)) with positive TB the probability
of a tie doesn’t show a monotonic increase with increasing two-path counts.
Most clearly this is shown in the neural network of C. elegans, where beyond
$9$ two-paths between two nodes, the probability for a tie strongly diminishes
(except at $14$ two-paths). Reasons for this could be myriad, but it is
important to consider that it could be indicative of missing, incomplete or
biased data. The example in Figure (5(d)) has been shown to be an incomplete
dataset, which limited conclusions of the study on this dataset (see for
critiques Coulomb et al.,, 2005; Han et al.,, 2005; Stumpf et al.,, 2005). Or,
due to ill defined relationships, for example, interactions could traverse
through different media not considered (e.g., complementary use of email and
phone), so that not all relevant interactions may have been observed.
Similarly, the network in Figure (5(a)) displays a drop in tie probability at
$3$ and $6$ two-paths, while a sharp increase occurs at $7$. As this dataset
is a covert network constructed from secondary sources it could be indicative
of a missing source, or a bias because some sources are irrelevant or receive
too much emphasis. At least, non-monotonicity in the plots deserves a further
theoretical explanation when no data related reasons can be found.

##  5 Discussion

This paper proposed new measures for transitivity based on covariances and
correlations between ties and two-paths, and described some of their numerical
properties. This new set of measures all are expressions of the difference in
conditional probabilities in (1) that define network transitivity.

###  5.1 Statistical Inference

The measures are proposed as descriptives, and not primarily for use in
statistical inference. (For an overview of issues in statistical modeling for
social network analysis see Snijders, 2011.) Statistical inference about
transitivity in networks can be directed at testing the null hypothesis of no
transitivity, or at making statistical network models that do include
transitivity. The former topic is treated by Karlberg, (1999). This author
defines two transitivity indices as potential test statistics, and uses as a
null distribution the U $\mid$ (OD, ID) specification, i.e. the uniform
distribution conditional on given in- and out-degree vectors. His first test
statistic is (2). His second test statistic is an average of local
transitivity indices, where the local transitivity is defined as the density
of the out-neighborhood of the node, divided by the maximal density given the
indegree, outdegree, and number of mutual ties of the node. This reflects the
importance of accounting for outdegrees, indegrees, and number of mutual ties
that we encountered in (14), the condition for the Transitivity Correlation to
be 0. We suggest that our proposed statistic TC could also be a suitable
statistic for testing transitivity, and a suitable null distribution could be
U $\mid$ (OD, ID, M), the uniform distribution conditional on given in- and
out-degree vectors and a given number $M$ of reciprocated ties. (Note that OD
and ID imply the values of $n$ and $d$.) Although generating random networks
from these distributions is not discussed here, it should be noted that
generating samples from the U $\mid$ (OD, ID) as well as from the U $\mid$
(OD, ID, M) distribution faces serious combinatorial restrictions. A computer
program that can simulate samples from these two distributions is ZO
(Snijders,, 2017), based on Snijders, (1991), and obtainable from
http://www.stats.ox.ac.uk/~snijders/socnet.htm. More recently a method for
doing this was proposed by Tao, (2016). Further literature about the
generation of networks with given in- and out-degrees is Rao et al., (1996),
Roberts, (2000), Verhelst, (2008), and Chatterjee et al., (2011).

###  5.2 Absence and Presence of Transitivity

One of our conclusions is that condition (14), depending on outdegrees,
indegrees, and number of mutual ties, expresses absence of transitivity. This
echoes and refines Feld and Elmore’s (1982) observation, extended later by
Faust, (2007), that interpretations of the number of transitive triplets in a
network should take into account the degree distributions. It is also related
to the statement, made by Snijders et al., (2006) and Lusher et al., (2012, p.
70), that the number of independent two-paths (also called dyadwise shared
partners) should be included in specifications of Exponential Random Graph
Models as a ‘prerequisite’, or lower-order configuration, for testing the
transitive closure expressed by $k$-triangles (also called edgewise shared
partners).

In the observed network examples in Section 4.4 we have mainly found positive
values for Transitivity Covariance. This unambiguously shows that there is an
increased propensity towards transitive triplets in these networks, in line
with the predominance of transitive triplets found in a much larger set of
networks already by Davis, (1970). However, in some cases the diagrams that
depict the slope TB, also show that the observed probabilities for ties may
become highly variable for high values of the number of two-paths. This in
itself is thought-provoking theoretically, and might inspire other measures
that express deviations from a linear relation. However, other explanations
are also possible, such as randomness, lack of data quality, or existence of
covert ties.

###  5.3 Extensions

Next to transitivity we may consider balance (Heider,, 1958). When balance is
treated for graphs or digraphs without considering edge signs, it is usual to
treat absent edges as negative ties. Instead of Transitivity Covariance, the
’Balance Covariance’ would then be based on the association between $x_{ij}$
and $x_{ik}\,x_{kj}+x^{c}_{ik}\,x^{c}_{kj}$, where $x^{c}$ is the complement
of digraph $x$, with tie variables $x^{c}_{ij}=1-x_{ij}$. As the values of
$x_{ik}\,x_{kj}+x^{c}_{ik}\,x^{c}_{kj}$ still are in $\\{0,1\\}$ the analyses
will remain similar. The measure can then be further adjusted to accommodate
other statements about triads.

Further refinements could be made regarding, for example, the implicit
assumptions about homogeneity of nodes. In case nodes are explicitly organized
in groups a distinction between different subsets of nodes, or different
blocks of ties, may refine conclusions about increased, or decreased, levels
of a tendency towards transitivity. Adjusted covariance based measures could
be derived in this way, controlling for grouping of nodes.

Further developments could also be made for networks with valued ties. A
generalized form of network transitivity for valued ties was proposed by
Opsahl & Panzarasa, (2009). It is still unknown in which way this would lead
to different conclusions and interpretations than those presented here.

##  6 Conclusion

We defined two new measures for transitivity: Transitivity Phi TPhi, defined
as the observed correlation between the tie variable between two nodes and a
random two-path connection between them; and the Transitivity Correlation TC,
the observed correlation between the tie variable and the number of two-paths
between the two nodes. The foremost advantage of these measures is that they
offer a quantitative expression for the ’increased propensity’ of transitive
triples which is the definition of transitivity as formulated, e.g., by Newman
et al., (2001). By contrast, the clustering coefficient C, one of the basic
measures for transitivity, reflects the observed conditional probability of a
tie, given a two-path, not a comparative quantity. Under the Erdös-Renyi model
the clustering coefficient can have any expected value in $(0,1)$ depending on
the density. Because of their comparative nature these correlation measures
allow for comparison between networks, even networks of unequal size or
density, and from different contexts.

The two measures are both based on considering the tie variable for a random
pair $(i,j)$ of nodes; the difference is that TPhi considers one randomly
selected third node, whereas TC considers all other nodes as potential
intermediates. Both are functions of the ego-networks of all nodes in the
digraph, where the ego-network is defined as the digraph induces by the node
and all nodes in its direct out-neighborhood. Clearly, TC takes into account
much more of the structure of the ego-networks than TPhi, specifically, the
dependence between the different two-paths connecting any two nodes.

The results found in the comparison of measures for windmill graphs led to the
conclusion that the difference between these two measures can imply large
differences in conclusions about transitivity. For windmills with many wings
the consideration of the two-path dependence by TC leads to a value tending to
1, contrasting with the value for TPhi tending to 0. We interpret windmill
graphs as being highly transitive, and find this a strong argument in favor of
TC over TPhi.

Correlations between binary variables are known to have a restricted range.
For graphs that are unions of disconnected complete subgraphs of equal sizes,
both TC and TPhi assume the maximum of 1. This shows that there may be room
for developing other measures for transitivity that assume their maximum value
for all totally transitive graphs, without the restriction of equal-size
components.

A finding that we believe to be new is that the condition that TC is zero, is
equivalent to a condition on the covariance between in- and outdegrees, the
number of mutual ties, the density, and the number of nodes. This leads to
interest in the uniform distribution for digraphs conditional on these four
quantities. This distribution presumably is very difficult to handle; the
distribution of digraphs, for a given number of nodes, conditional on the
vectors of in- and outdegrees and the number of mutual ties may be presumed to
be easier to handle, although this distribution already poses huge problems
(Tao,, 2016; Snijders,, 2017).

## References

  * Butts, (2016) Butts, Carter T. (2016).  Package ‘sna’.  Available at: https://cran.r-project.org/web/packages/sna/sna.pdf.
  * Cartwright & Harary, (1956) Cartwright, Dorwin, & Harary, Frank. (1956).  Structural balance: a generalization of heider’s theory.  Psychological review, 63(5), 277.
  * Chatterjee et al., (2011) Chatterjee, Sourav, Diaconis, Persi, & Sly, Allan. (2011).  Random graphs with a given degree sequence.  The annals of applied probability, 1400–1435.
  * Coleman, (1990) Coleman, James Samuel. (1990).  Foundations of social theory.  Cambridge, Mass.: Harvard University Press.
  * Coulomb et al., (2005) Coulomb, Stéphane, Bauer, Michel, Bernard, Denis, & Marsolier-Kergoat, Marie-Claude. (2005).  Gene essentiality and the topology of protein interaction networks.  Proceedings of the royal society of london b: Biological sciences, 272(1573), 1721–1725.
  * Cross & Parker, (2004) Cross, Robert L, & Parker, Andrew. (2004).  The hidden power of social networks: Understanding how work really gets done in organizations.  Harvard Business Press.
  * Davis et al., (1941) Davis, Allison, Gardner, Burleigh B, Gardner, Mary R, & Warner. (1941).  Deep south: A sociological anthropological study of caste and class.  University of Chicago Press.
  * Davis, (1967) Davis, James A. (1967).  Clustering and structural balance in graphs.  Human relations, 20(2), 181–187.
  * Davis, (1970) Davis, James A. (1970).  Clustering and hierarchy in interpersonal relations: Testing two graph theoretical models on 742 sociomatrices.  American sociological review, 35, 843–852.
  * Erdös & Renyi, (1959) Erdös, Paul, & Renyi, A. (1959).  On random graphs.  Publ math debrecen, 6(290-297), 290–297.
  * Falk & Well, (1997) Falk, Ruma, & Well, Arnold D. (1997).  Many faces of the correlation coefficient.  Journal of statistics education, 5(3), 1–18.
  * Faust, (2007) Faust, Katherine. (2007).  Very Local Structure in Social Networks.  Sociological methodology, 5(2), 148–256.
  * Faust, (2010) Faust, Katherine. (2010).  A puzzle concerning triads in social networks: Graph constraints and the triad census.  Social networks, 32(3), 221–233.
  * Feld & Elmore, (1982) Feld, Scott L, & Elmore, Richard. (1982).  Patterns of Sociometric Choices : Transitivity Reconsidered.  Social psychology quarterly, 45(2), 77–85.
  * Frank, (1980) Frank, Ove. (1980).  Sampling and Inference in a Population Graph.  International statistical review revue internationale de statistique, 48(1), 33.
  * Frank, (1988) Frank, Ove. (1988).  Random Sampling and Social Networks: A Survey of Various Approaches.  Mathematiques informatique et sciences humaines, 26, 19–33.
  * Freeman, (2017) Freeman, Linton C. (2017).  Datasets.  moreno.ss.uci.edu/data.html, Feb. 1st, 2017.
  * Han et al., (2005) Han, Jing-Dong J, Dupuy, Denis, Bertin, Nicolas, Cusick, Michael E, & Vidal, Marc. (2005).  Effect of sampling on topology predictions of protein-protein interaction networks.  Nature biotechnology, 23(7), 839–844.
  * Harary & Kommel, (1979) Harary, Frank, & Kommel, Helene J. (1979).  Matrix measures for transitivity and balance.  Journal of mathematical sociology, 6(2), 199–210.
  * Hayes, (2006) Hayes, Brian. (2006).  Connecting the dots can the tools of graph theory and social-network studies unravel the next big plot?  American scientist, 94(5), 400–404.
  * Heider, (1946) Heider, Fritz. (1946).  Attitudes and cognitive organization.  The journal of psychology, 21(1), 107–112.
  * Heider, (1958) Heider, Fritz. (1958).  The Psychology Of Interpersonal Relations.  New York: John Wiley & Sons.
  * Holland & Leinhardt, (1970) Holland, Paul W., & Leinhardt, Samuel. (1970).  A method for detecting structure in sociometric data.  American journal of sociology, 76(3), 492–513.
  * Holland & Leinhardt, (1971) Holland, Paul W., & Leinhardt, Samuel. (1971).  Transitivity in structural models of small groups.  Small group research, 2(2), 107–124.
  * Holland & Leinhardt, (1972) Holland, Paul W., & Leinhardt, Samuel. (1972).  Holland and leinhardt reply: Some evidence on the transitivity of positive interpersonal sentiment.  American journal of sociology, 77(6), 1205–1209.
  * Holland & Leinhardt, (1976) Holland, Paul W, & Leinhardt, Samuel. (1976).  Local structure in social networks.  Sociological methodology, 7, 1–45.
  * Jackson, (2008) Jackson, Matthew O. (2008).  Social and economic networks.  Vol. 3.  Princeton university press Princeton.
  * Jeong et al., (2001) Jeong, Hawoong, Mason, Sean P, Barabási, A-L, & Oltvai, Zoltan N. (2001).  Lethality and centrality in protein networks.  Nature, 411(6833), 41–42.
  * Karlberg, (1999) Karlberg, Martin. (1999).  Testing Transitivity in Digraphs.  Sociological methodology, 29(1), 225–251.
  * Krackhardt, (1987) Krackhardt, D. (1987).  Cognitive Social Structures.  Social networks, 9, 109–134.
  * Lazega, (2001) Lazega, Emmanuel. (2001).  The collegial phenomenon: The social mechanisms of cooperation among peers in a corporate law partnership.  Oxford University Press on Demand.
  * Lusher et al., (2012) Lusher, Dean, Koskinen, Johan, & Robins, Garry. (2012).  Exponential random graph models for social networks: Theory, methods, and applications.  Cambridge University Press.
  * Lusseau, (2003) Lusseau, David. (2003).  The emergent properties of a dolphin social network.  Proceedings of the royal society of london b: Biological sciences, 270(Suppl 2), S186–S188.
  * Newman et al., (2001) Newman, M E J, Strogatz, S H, & Watts, D J. (2001).  Random graphs with arbitrary degree distributions and their applications.  Physical review e, 64(2), 19.
  * Newman, (2003) Newman, Mark EJ. (2003).  The structure and function of complex networks.  Siam review, 45(2), 167–256.
  * Newman, (2006) Newman, Mark EJ. (2006).  Finding community structure in networks using the eigenvectors of matrices.  Physical review e, 74(3), 036104.
  * Opsahl, (2017) Opsahl, Tore. (2017).  Datasets.  https://toreopsahl.com/datasets/, Feb. 1st, 2017.
  * Opsahl & Panzarasa, (2009) Opsahl, Tore, & Panzarasa, Pietro. (2009).  Clustering in weighted networks.  Social networks, 31(2), 155–163.
  * Padgett & Ansell, (1993) Padgett, John F., & Ansell, Christopher K. (1993).  Robust action and the rise of the medici, 1400-1434.  American journal of sociology, 98(6), 1259–1319.
  * Rao et al., (1996) Rao, A Ramachandra, Jana, Rabindranath, & Bandyopadhyay, Suraj. (1996).  A markov chain monte carlo method for generating random (0, 1)-matrices with given marginals.  Sankhyā: The indian journal of statistics, series a, 225–242.
  * Roberts, (2000) Roberts, John M. (2000).  Simple methods for simulating sociomatrices with given marginal totals.  Social networks, 22(3), 273–283.
  * Schelling, (1978) Schelling, TC. (1978).  Micromotives and macrobehavior.  New York [etc.]: Norton.
  * Smith & White, (1992) Smith, David A, & White, Douglas R. (1992).  Structure and dynamics of the global economy: Network analysis of international trade 1965-1980.  Social forces, 857–893.
  * Snijders, (1991) Snijders, T. A. B. (1991).  Enumeration and simulation methods for 0-1 matrices with given marginals.  Psychometrika, 56(3), 397–417.
  * Snijders et al., (2006) Snijders, T A B, Pattison, P E, Robins, G L, & Handcock, M S. (2006).  New specifications for exponential random graph models.  Sociological methodology, 36, 99–153.
  * Snijders, (2011) Snijders, Tom A. B. (2011).  Statistical models for social networks.  Annual review of sociology, 37, 131–153.
  * Snijders, (2017) Snijders, Tom A. B. (2017).  Manual for ZO version 2.3.  Department of Sociology, University of Groningen, Groningen.  Available at
http://www.stats.ox.ac.uk/~snijders/socnet.htm.

  * Stumpf et al., (2005) Stumpf, Michael PH, Wiuf, Carsten, & May, Robert M. (2005).  Subnets of scale-free networks are not scale-free: sampling properties of networks.  Proceedings of the national academy of sciences of the united states of america, 102(12), 4221–4224.
  * Tao, (2016) Tao, Trevor. (2016).  An improved MCMC algorithm for generating random graphs from constrained distributions.  Network science, 4, 117–139.
  * Verhelst, (2008) Verhelst, Norman D. (2008).  An efficient MCMC algorithm to sample binary matrices with fixed marginals.  Psychometrika, 73(4), 705–728.
  * Wasserman & Faust, (1994) Wasserman, Stanley, & Faust, Katherine. (1994).  Social network analysis: Methods and applications.  Cambridge: Cambridge University Press.
  * Wasserman, (1975) Wasserman, Stanley S. (1975).  Random Directed Graph Distributions in the Triad Census in Social Networks.  Journal of mathematical sociology, 5(1), 61–86.
  * Watts & Strogatz, (1998) Watts, Duncan J, & Strogatz, Steven H. (1998).  Collective dynamics of ‘small-world’networks.  nature, 393(6684), 440–442.

##  Appendix A Relation TPhi and TC

The covariance between directed ties and the number of two-paths is,

$\text{cov}\Big{(}x_{ij},\sum\limits_{h\neq
i,j}x_{ih}x_{hj}\Big{)}=\frac{1}{n\,(n-1)}\sum_{i}\sum_{j\neq
i}x_{ij}\,\big{(}\sum_{h\neq
i,j}x_{ih}\,x_{hj}\big{)}-\overbracket{x}\,\overbracket{xx},$ (16)

The difference between TC and TPhi is in scaling. Consider that covariance in
(16) is a weighted measure of the numerator in (8),

$\text{cov}\Big{(}x_{ij},\sum_{h\neq
i,j}x_{ih}x_{hj}\Big{)}=(n-2)\,\text{cov}(x_{ij},\,x_{ik}x_{kj}).$ (17)

Further, the denominator in (10) differs from that of TPhi only in
$s.e.(\sum_{h}x_{ih}x_{hj})$ (see (9)). The variance of the number of two-
paths between any ordered pair can be rewritten as

$\displaystyle\text{var}\Big{(}\sum_{h}x_{ih}x_{hj}\Big{)}=(n-2)\,\big{[}\text{var}(x_{ik}x_{kj})+(n-3)\,\text{cov}(x_{ik}x_{kj},x_{i\ell}x_{\ell
j})\big{]}$ (18)

Under conditions where $\text{cov}(x_{ik}x_{kj},x_{i\ell}x_{\ell
j})=\text{var}(x_{ik}x_{kj})$, TC reduces to TPhi as

$\displaystyle\text{var}\Big{(}\sum_{h}x_{ih}x_{hj}\Big{)}=(n-2)^{2}\,\text{var}(x_{ik}x_{kj}).$
(19)

But, more generally, we can state

TC $\displaystyle=\alpha\times\textit{TPhi},$ (20)

where $\alpha$ is

$\displaystyle\alpha$ $\displaystyle=\frac{\textit{TC}}{\textit{TPhi}}$
$\displaystyle=\frac{(n-2)\sqrt{\text{var}(x_{ik}x_{kj})}}{\sqrt{((n-2)[\text{var}(x_{ik}x_{kj})+(n-3)\,\text{cov}(x_{ik}x_{kj},x_{i\ell}x_{\ell
j})])}}$ (21)

for $\ell\neq k$. Note that (A) can be rewritten as

$\displaystyle\alpha=\frac{(n-2)}{\sqrt{((n-2)\,[1+(n-3)\rho])}},$ (22)

where

$\displaystyle\rho=\frac{\text{cov}(x_{ik}x_{kj},\,x_{i\ell}x_{\ell
j})}{\text{var}(x_{ik}x_{kj})}$ (23)

is the autocorrelation between two-paths in a digraph. Now $\rho$ is a
correlation so that $\rho\leq 1$; further, rewriting (18),

$\displaystyle 0\,$ $\displaystyle\leq\,\text{var}\Big{(}\sum_{k\neq
i,j}x_{ik}x_{kj}\Big{)}\,=\,(n-2)\,\text{var}(x_{ik}x_{kj})\,+\,(n-2)(n-3)\,\text{cov}(x_{ik}x_{kj})$
(24)
$\displaystyle\,=\,(n-2)\big{(}1+(n-3)\,\rho\big{)}\,\text{var}(x_{ik}x_{kj})\
,$

which implies that $\rho\geq-1/(n-3)$. With (22) this implies that $\alpha\geq
1$ except for $\textit{TPhi}=0$, where $\rho=-1/(n-3)$ and TPhi is undefined.
It can be concluded that $\textit{TC}\geq\textit{TPhi}$. The distinction
between TC and TPhi is about size not direction. Although the relation between
$\alpha$ and $\rho$ is non-linear, $\alpha$ is monotonically decreasing as
$\rho$ increases. The ratio of the two transitivity correlations is a function
of $n$ and the two-path autocorrelation in the digraph. The autocorrelation
between two-paths is itself a Phi-coefficient, expressing the difference in
conditional probabilities of a two-path via a node $k$ given a two-path via
another node $\ell$ exists and of a two-path via $k$ given that no other two-
path exists. As such, it can be interpreted as a measure of network
centrality, where a smaller $\rho$ indicates an elevated uniqueness of nodes
as intermediate in two-paths.

##  Appendix B When is Transitivity Covariance Equal to Zero

We derive an condition equivalent to the property that the Transitivity
Correlation TC, or equivalently the Transitivity Covariance, is zero.

The Transitivity Covariance is defined as the covariance, for a randomly
chosen pair $(i,j)$, between the direct tie $x_{ij}$ and the number
$\sum_{h\neq i,j}x_{ih}x_{hj}$ of directed two-paths between these nodes as
defined in (17). Network density in (di)graphs is the mean tie indicator
variable,

$d=\overbracket{x}=\frac{1}{n(n-1)}\sum_{i=1}^{n}\,\,\sum_{\mathclap{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}}^{n}\,x_{ij}\ .$ (25)

Over all ordered pairs $(i,j)$, the mean number of two-paths is

$\overbracket{xx}=TSP=\frac{1}{n(n-1)}\sum_{i=1}^{n}\,\,\sum_{\mathclap{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}}^{n}\enskip\,\sum_{\mathclap{\begin{subarray}{c}h=1\\\
h\neq i,j\end{subarray}}}^{n}\,x_{ih}\,x_{hj}$ (26)

and the mean number of transitive triples is given by

$TT=\frac{1}{n(n-1)}\sum_{i=1}^{n}\,\,\sum_{\mathclap{\begin{subarray}{c}j=1\\\
j\neq i\end{subarray}}}^{n}\enskip\,\sum_{\mathclap{\begin{subarray}{c}h=1\\\
h\neq i,j\end{subarray}}}^{n}\,x_{ij}\,x_{ih}\,x_{hj}\ .$ (27)

Let

$M=\sum_{i=1}^{n}\,\sum_{\mathclap{\begin{subarray}{c}j=1\\\ j\neq
i\end{subarray}}}^{n}\,x_{ij}\,x_{ji}$ (28)

be the sum of reciprocal or mutual ties (note that reciprocal ties are two-
paths that do not contribute to a transitive triple). The mean number of two-
paths in (26) can be rewritten as

$TSP=\frac{1}{n\,(n-1)}(OD\cdot ID-M)$ (29)

where $ID$ and $OD$ are the vectors of indegrees and outdegree, and $OD\cdot
ID$ is their inner product.

Substitution in (17) gives

$\text{cov}(x_{ij},\sum_{h\neq
i,j}x_{ih}\,x_{hj})=(n-2)\Bigg{(}TT-\frac{(OD\cdot ID-M)\,d}{n(n-1)}\Bigg{)}\
.$ (30)

The inner product of two vectors can be expressed in terms of covariance, in
this case the covariance between indegree and outdegree for the probability
distribution that a node is randomly chosen. This gives

$\text{cov}(OD,ID)=\frac{1}{n}(OD\cdot ID)-d^{2}\ .$ (31)

Substitution gives

$\text{cov}(x_{ij},\sum_{h\neq
i,j}^{n}x_{ih}\,x_{hj})=(n-2)\Bigg{(}TT-\frac{\big{(}n\,\,\text{cov}(OD,ID)+n\,d^{2}-M\big{)}\,d}{n(n-1)}\Bigg{)},$
(32)

which simplifies to equation (14) under the condition of no network
(in)transitivity.