# Structural measures of similarity and complementarity in complex networks

Szymon Talaga1∗ Andrzej Nowak2,3

(1Robert Zajonc Institute for Social Studies, University of Warsaw,
Stawki 5/7, 00-183 Warsaw, Poland.
2Faculty of Psychology, University of Warsaw,
Stawki 5/7, 00-183 Warsaw, Poland.
3Department of Psychology, Florida Atlantic University,
777 Glades Rd, Boca Raton, FL 33431, USA.
∗Corresponding author; E-mail<EMAIL_ADDRESS>)

###### Abstract

The principle of similarity, or homophily, is often used to explain patterns
observed in complex networks such as transitivity and the abundance of
triangles (3-cycles). However, many phenomena from division of labor to
protein-protein interactions (PPI) are driven by complementarity (differences
and synergy). Here we show that the principle of complementarity is linked to
the abundance of quadrangles (4-cycles) and dense bipartite-like subgraphs. We
link both principles to their characteristic motifs and introduce two families
of coefficients of: (1) structural similarity, which generalize local
clustering and closure coefficients and capture the full spectrum of
similarity-driven structures; (2) structural complementarity, defined
analogously but based on quadrangles instead of triangles. Using multiple
social and biological networks, we demonstrate that the coefficients capture
structural properties related to meaningful domain-specific phenomena. We show
that they allow distinguishing between different kinds of social relations as
well as measuring an increasing structural diversity of PPI networks across
the tree of life. Our results indicate that some types of relations are better
explained by complementarity than homophily, and may be useful for improving
existing link prediction methods. We also introduce a Python package
implementing efficient algorithms for calculating the proposed coefficients.

### Introduction

The structure of complex networks commonly reflects their functional
properties as well as mechanisms or processes that created them. Seminal
studies have shown that different systems, from neural networks to the World
Wide Web, tend to be characterized by the presence of statistically over-
represented small subgraphs, known as network motifs [48, 58, 64]. While one
may expect different motifs to be related to particular functions or
properties of a given system, it is often not easy to determine what they are
exactly. In some cases and specific contexts, such as gene regulatory
networks, the roles played by different motifs may be revealed through
experimental studies [58, 3]. However, general principles that would explain
the prevalence of specific motifs across different application domains are
still mostly unknown.

An important exception is the widely-known abundance of triangles (3-cycles)
in many types of real-world networks, which has been shown to be a structural
signature of transitive relations driven by similarity between nodes in some
(possibly latent) metric space [10, 11, 36]. The importance of similarity and
its impact on the structure of social networks has been recognized in
sociology for a long time, as it is linked to homophily and triadic closure
[42, 47, 34, 6, 62]. While it is usually hard to disentangle their effects [4,
5], these two processes are also inherently linked as they lead to high
structural equivalence [49] between connected nodes. In other words, in
similarity-driven systems two adjacent nodes are likely to share a lot of
neighbors (Fig. 1A), and this implies the abundance of triangles and a latent
geometric structure [51, 36].

Figure 1: Intuitive meaning of similarity and complementarity. (A) If three
persons are similar (e.g. they are all scientists) and we know that one of
them (top) knows the other two (bottom) it is quite likely that they know each
other too (dashed line). Thus, the relation is transitive. (B) If one wine
(red) goes well with (is complementary to) bread and cheese and another wine
(white) also goes well with the bread, then it is likely that it is a good
match for the cheese too (dashed line). However, this does not imply that both
wines will be drunk together, so the relation is not transitive.

An alike, even if less known, phenomenon is the connection between the
abundance of quadrangles (4-cycles) and networks with so-called functional
structure [45], in which two nodes interact not because they are similar, but
rather because one of them is similar (in some salient way) to the neighbors
of the other [35]. This linkage principle leads to markedly different local
connectivity structures than those found in networks dominated by triangles
(e.g. typical social networks) and is characteristic for relations driven by
complementarity, or differences and synergies, between the features of
connected elements [35, 45, 31].

This observation is important as many phenomena across different application
domains, from cooperation, business interactions and division of labor [28,
13, 55, 70, 20, 45] to the quality of romantic relationships [41], consumer
choices [63] and at least some types of protein-protein binding [35], may
indeed be better explained by the principle of complementarity than
similarity. For instance, two types of wine may be often bought together with
the same kinds of bread and cheese, but rarely both of them will occur in the
same transaction. In other words, in this situation a wine is complementary to
the bread and cheese, but not to the other wine (Fig. 1B). More generally,
complementarity can be seen as a particular interpretation of the principle of
heterophily, which is a preference for connecting to others who are different
with respect to some salient attributes [55].

Here we show that the principle of complementarity, unlike the more general
notion of heterophily, has a straightforward geometric interpretation which
links it to quadrangles as its characteristic motif, in the same way as the
intrinsic geometry of similarity links it to triangles. We also show that
under a particular quadrangle definition (4-cycle without diagonal shortcuts)
the principle of complementarity is connected to locally dense subgraphs of
high bipartivity [30], which, again, is analogous to how the abundance of
triangles implies the presence of dense unipartite subgraphs. More generally,
we argue that both similarity and complementarity are important relational
principles shaping the structure of networks across different application
domains and provide a generic explanation for some of the prevalent structural
patterns observed in many real-world systems.

In order to formalize our analysis, we first define a general family of
similarity coefficients measuring the abundance of triangles at the levels of
individual nodes and edges as well as entire graphs. The coefficients
generalize the notions of local clustering and closure [67, 71] and therefore
capture the full spectrum of transitive, similarity-driven structures. Then,
starting from a simple geometric model of complementarity we follow the same
logic as in the case of similarity and define an analogous family of
complementarity coefficients measuring the abundance of quadrangles.

We will call the proposed measures structural coefficients because they will
not be defined with respect to node attributes, latent or observed, but to how
different nodes are embedded in the network. Moreover, they will not measure
(dis)similarity between nodes, as this problem is usually addressed by
measures of structural equivalence [49]. Instead, structural coefficients will
measure the extent to which any given edge, node or graph is compatible with
the principle of similarity or complementarity. However, to facilitate the
interpretation we will also show how the proposed notions of structural
similarity and complementarity are related to structural equivalence.

We study the behavior of structural coefficients in some of the most important
random graph models as well as multiple real-world social and biological
networks. We demonstrate that they are related to meaningful domain-specific
phenomena and can be used to distinguish between different types of networks.
In particular, using a collection of comparable real-world networks measuring
friendship and health advice ties, we show that structural coefficients
discriminate effectively between social relations driven by similarity and
complementarity, which provides evidence for the theoretical validity of our
approach. We also demonstrate how the coefficients may be used to measure the
increasing structural diversity of protein-protein interactions (PPI) across
the tree of life based on hundreds of interactome networks of different
organisms.

Our work complements the rich literature on network motifs, network geometry
and local connectivity structures as well as introduces principled theory and
methods linking different types of relations to their observable structural
signatures. We argue that the customary assumption of homophily is not
adequate for some types of social relations, which are better explained by
complementarity, and provide tools for identifying such systems, bringing more
nuance to the field of social network analysis. Moreover, the framework we
propose could be, in principle, used for improving existing link prediction
methods by helping to determine when the assumption of 2-path (L2/triadic) or
3-path (L3/tetradic) closure [35] is more appropriate. Last but not least, all
methods introduced in this paper are implemented in a Python package called
pathcensus (see Materials and Methods).

#### Notation & technical remarks

In this paper we consider simple undirected and unweighted graphs $G=(V,E)$
with no self-loops. We use $n=|V|$ and $m=|E|$ to denote the numbers of nodes
and edges in $G$ respectively. Elements of the adjacency matrix of $G$ will be
denoted by $a_{ij}$ and assumed to be equal to $1$ if the edge $(i,j)$ exists
and $0$ otherwise. For any node $i\in V$ we denote its degree by $d_{i}$ and
its $k$-hop neighborhood by $\mathcal{N}_{k}(i)$, in particular $1$-hop
neighborhood will be denoted by $\mathcal{N}_{1}(i)$ (a $k$-hop neighborhood
consists of nodes connected to $i$ by a shortest path of length $k$).
Moreover, we will use $n_{ij}=|\mathcal{N}_{1}(i)\cap\mathcal{N}_{1}(j)|$ to
denote the number of shared neighbors between nodes $i$ and $j$. Averaged
quantities will be denoted by diamond brackets. For instance, $\langle
d_{i}\rangle$ will denote average node degree.

#### Structural equivalence

We briefly introduce the notion of structural equivalence, to which we will
refer at multiple points throughout the paper. Structural equivalence is a
measure of the extent to which two nodes are similarly embedded in a network.
It can be defined in multiple ways, but all definitions try to quantify
similarity between $1$-hop neighborhoods of two nodes [49]. Here we will
follow a common approach and define structural equivalence in terms of
Sørenson Index or normalized Hamming similarity:

$H_{ij}=\frac{2n_{ij}}{d_{i}+d_{j}}$ (1)

which is also often used as an index for predicting missing links (under the
assumption of triadic closure) [60]. Crucially, the notion of structural
equivalence applies to pairs of nodes (not necessarily connected) and is
concerned with the degree of (dis)similarity of their $1$-hop neighborhoods.
This is in contrast to structural coefficients we propose, which are
descriptors of edges, nodes or graphs capturing the degree to which they are
compatible with the logic of similarity or complementarity.

### Theory and Definitions

Here we present the proposed theory of structural similarity and
complementarity and introduce all the main definitions that will be used
throughout the paper. We first discuss structural similarity and its nodewise
and global coefficients and then define the analogous complementarity
coefficients. In the second part of the section we introduce edgewise measures
and discuss use them to discuss the connection between similarity,
complementarity and structural equivalence.

#### Structural similarity

It is common to think about similarity in terms of distance between different
objects in a feature space. Hence, the motivating geometric model for
similarity-driven relations posits that nodes are positioned in some metric
space and the probability of observing a link between them is a decreasing
function of the corresponding distance. Such a generic model can be seen as an
instance of the class of Random Geometric Graphs (RGG) [11, 62]. The crux is
that this very general formulation is enough to guarantee the abundance of
triangles (3-cycles) (see Fig. 2A).

Thus, a good starting point for our endeavor is local clustering coefficient
[67], of which value for a node $i$ will be denoted by $s^{W}_{i}$. It is a
classical network measure of the density of the $1$-hop neighborhood (ego-
network) of $i$ and is defined as:

$s^{W}_{i}=\frac{2T_{i}}{t^{W}_{i}}=\frac{\sum_{j,k}a_{ij}a_{ik}a_{jk}}{d_{i}(d_{i}-1)}$
(2)

where $T_{i}$ is the number of triangles including $i$ and $t^{W}_{i}$ is the
number of wedge triples centered at $i$ or $2$-paths with $i$ in the middle
(Fig. 2B). Crucially, $s^{W}_{i}\in[0,1]$ and is equal to $1$ if and only if
$\mathcal{N}_{1}(i)$ forms a fully connected network. In sociological terms,
it measures the extent to which my friends are friends with each other. Note,
however, that this is only one side of the triadic closure process as it
corresponds to the closing of the loop between friends of the focal node $i$.
The other part is about the loop between $i$ and friends of its friends and
local clustering coefficient does not capture it.

To address this issue an alternative local closure coefficient [71] has been
proposed more recently:

$s^{H}_{i}=\frac{2T_{i}}{t^{H}_{i}}=\frac{\sum_{j,k}a_{ij}a_{ik}a_{jk}}{\sum_{j}a_{ij}(d_{j}-1)}$
(3)

where $t^{H}_{i}$ is the number of head triples originating from $i$, that is,
$2$-paths starting at $i$ (Fig. 2C). It is also in the range of $[0,1]$ and
attains the maximum value if and only if no neighbor of $i$ is adjacent to a
node which is not already in $\mathcal{N}_{1}(i)$. In other words, when
$s^{H}_{i}=1$ a random walker starting at $i$ will never leave
$\mathcal{N}_{1}(i)$. Thus, local closure coefficient measures the extent to
which friends of my friends are my friends, that is, it is a measure of
triadic closure between the focal node $i$ and neighbors of its neighbors. As
a result, it captures exactly that what local clustering is blind to. Since
the local clustering and closure coefficients are based on triples we will
later refer to them as $t$-clustering and $t$-closure respectively.

Figure 2: Geometric motivation and the main properties of structural
similarity coefficients. (A) Metric structure induced by similarity implies
transitivity of relations and the abundance of triangles. (B and C) Wedge and
head triples. (D) Local clustering can be maximized even when neighbors of the
focal node are very differently embedded within the network, while $s_{i}$ is
sensitive to this kind of non-transitivity. (E) Local closure can be maximized
even for nodes with sparse 1-hop neighborhoods if they are star-like as
neighbors with degree one do not generate any head triples. On the other hand,
$s_{i}$ is sensitive to this violation of transitivity. (F) Necessary and
sufficient conditions for maximum structural similarity.

The two coefficients complement each other, so it is justified to combine them
in a single measure. We now propose such a measure which we will call
structural similarity coefficient:

$s_{i}=\frac{4T_{i}}{t^{W}_{i}+t^{H}_{i}}=\frac{t^{W}_{i}s^{W}_{i}+t^{H}_{i}s^{H}_{i}}{t^{W}_{i}+t^{H}_{i}}$
(4)

Note that $s_{i}$ is equal to the fraction of both wedge and head triples
including $i$ which can be closed to make a triangle. It is also equivalent to
a weighted average of $s^{W}_{i}$ and $s^{H}_{i}$, which implies that
$\min(s^{W}_{i},s^{H}_{i})\leq s_{i}\leq\max(s^{W}_{i},s^{H}_{i})$. As we show
later, this makes $s_{i}$ a more general descriptor of local structure than
$s^{W}_{i}$ or $s^{H}_{i}$ alone (cf. Section: Configuration model). Moreover,
since $s^{W}_{i}=1$ if and only if $\mathcal{N}_{1}(i)$ is fully connected and
$s^{H}_{i}=1$ if there are no links leaving $\mathcal{N}_{1}(i)$ then it must
be that $s_{i}=1$ if and only if $i$ belongs to a fully connected network.
Fig. 2 provides a summary of the motivation and main properties of $s_{i}$,
including examples of when $t$-clustering and $t$-closure coefficients are
maximal while structural similarity is only moderate (Figs. 2D and 2E).
Crucially, unlike local clustering and closure, structural similarity is a
comprehensive measure of the density of triangles around a node $i$ and
therefore captures the full spectrum of local structures implied by the
transitivity of similarity-driven relations. Moreover, it is defined for all
nodes contained within components with at least 3 nodes. This is in contrast
to local clustering which is not defined for nodes with $d_{i}=1$.

##### Global similarity

From the global perspective both local clustering and local closure lead to
the same conclusion that the corresponding global measure is just the fraction
of triples that can be closed to make a triangle [71]. This implies that the
same quantity is also the proper global measure of the extent to which
relations are driven by similarity. In other words, global similarity
coefficient is equal to the standard global clustering coefficient and can be
defined as:

$s=\frac{3T}{\sum_{i}d_{i}(d_{i}-1)}$ (5)

where $T$ is the total number of triangles and the denominator counts the
number of triples.

Note that it is indeed a reasonable measure of similarity-driven relations as
it is maximized only when a network is fully connected, so all nodes are
structurally redundant and each can be removed without affecting the overall
connectivity.

#### Structural complementarity

First, let us consider an intuitive meaning of complementarity. We posit that
two objects are complementary when their features are different but in a well-
defined synergistic way. As we will see, this additional synergy constraint is
crucial. However, before we discuss this further let us note that in the case
of similarity an analogous constraint is built-in by design. For any point
there is always only one point minimizing the distance (maximizing similarity)
and it is the point itself. In other words, any object is most similar to
itself. As a result, there is a well-defined notion of maximal similarity.

On the other hand, the case of difference is more complicated. To make our
argument more concrete, let the feature space be $\mathbb{R}^{k}$ with $k\geq
1$. Now, it is easy to see that for any two points $p$ and $r$ at a distance
$d(p,r)$ we can find a third point $s$ such that $d(p,s)>d(p,r)$. In other
words, for any point $p$ there is no well-defined point at the maximum
distance. Thus, complementarity cannot be defined in terms of arbitrary
differences. Intuitively, defining it in terms of a simple unconstrained
heterophily inevitably leads to the conclusion that for any object there is an
infinite variety of more and more complementary (different) objects, which
clearly does not map well on the common understanding of the notion of
complementarity. Thus, we need a definition with the same property as in the
case of similarity, that is, one yielding a sequence of ever smaller sets of
more and more complementary elements converging to a single well-defined point
in the limit of maximum complementarity.

Note that the above abstract argument can be related to known complementarity-
driven systems in a rather straightforward manner. For instance, a key and a
lock are complementary not because they are just different in an arbitrary
fashion, but because they differ in a very specific way by being structural
negatives of each other. Similarly, division of labor in modern societies is
based on complex synergies between capabilities of different individuals and
organizations.

Thus, we argue that complementarity should be defined in terms of distance
maximization but with additional constraints ensuring that for any point in
the feature space there is only one point at the maximum distance. This can be
achieved in several ways, but to keep things simple we will focus on one
particularly straightforward solution.

We consider nodes as placed on the surface of a $k$-dimensional (hyper)sphere
with $k\geq 1$. In this setting for each point there is only a single point at
the maximum distance and the maximum distance is the same for all points. Now,
if nodes connect preferentially to others who are far away, we obtain a model
analogous to similarity, but the connections of a node are not concentrated in
its vicinity but instead on the other side of the space. From this it follows
that any two connected nodes $i$ and $j$ will not share a lot of neighbors, so
triangles will be rare, but instead the $1$-hop neighborhood of $i$ should be
approximately equal to the $2$-hop neighborhood of $j$ and vice versa, that
is, $\mathcal{N}_{1}(i)\approx\mathcal{N}_{2}(j)$ and
$\mathcal{N}_{2}(i)\approx\mathcal{N}_{1}(j)$. Such a spatial structure
inevitably leads to the abundance of quadrangles (4-cycles) and the presence
locally dense bipartite-like subgraphs (Fig. 3A). There are, of course,
alternative and more general ways in which geometric models of
complementarity-driven relations can be defined (see Ref. [33] for an
excellent example), but distance maximization on a sphere provides a good
minimal model highlighting the connection between complementarity, bipartivity
and quadrangles.

Depending on the context different authors may refer to slightly different
objects when using the term quadrangle. Namely, a quadrangle may contain up to
two chords or diagonal links. Here we will consider only quadrangles without
any chords, which we will call strong quadrangles. This choice follows, of
course, from the proposed geometric model and the fact that only strong
quadrangles are characteristic for dense bipartite-like graphs, which should
not have many odd cycles.

Now we can start defining coefficients measuring relations driven by
complementarity. As previously, we begin with a local clustering coefficient,
which will be called $q$-clustering. It is defined analogously, but this time
in terms of quadrangles and wedge quadruples, that is, $3$-paths with the
focal node $i$ at the second position (Fig. 3B):

$c^{W}_{i}=\frac{2Q_{i}}{q^{W}_{i}}=\frac{\sum_{j\neq i}a_{ij}\sum_{k\neq
i,j}a_{ik}(1-a_{jk})\sum_{l\neq
i,j,k}a_{kl}a_{jl}(1-a_{il})}{\sum_{j}a_{ij}[(d_{i}-1)(d_{j}-1)-n_{ij}]}$ (6)

where $Q_{i}$ is the number of strong quadrangles incident to the focal node
$i$ and $q^{W}_{i}$ is the number of wedge quadruples it belongs to. Note that
we consider only quadruples with $i$ at the second position, such as
$(l,i,j,k)$ but not $(k,j,i,l)$, in order to avoid double counting and make
the number of wedge and head quadruples per quadrangle equal. Intuitively, it
quantifies the extent to which the local environment of $i$ is bipartite-like
and its neighbors are structurally equivalent to each other.

Local $q$-closure coefficient is defined in the same way as the fraction of
head quadruples originating from $i$ (Fig. 3C) that can be closed to make a
(strong) quadrangle:

$c^{H}_{i}=\frac{2Q_{i}}{q^{H}_{i}}=\frac{\sum_{j\neq i}a_{ij}\sum_{k\neq
i,j}a_{ik}(1-a_{jk})\sum_{l\neq i,j,k}a_{kl}a_{jl}(1-a_{il})}{\sum_{j\neq
i}a_{ij}\sum_{k\neq i,j}a_{jk}(d_{k}-1-a_{ik})}$ (7)

where $q^{H}_{i}$ is the number of head quadruples starting at $i$.
Conceptually, it measures the extent to which the local environment of $i$ is
bipartite-like and $i$ is structurally equivalent to its $2$-hop neighbors.

Figure 3: Geometric motivation and the main properties of structural
complementarity coefficients. (A) On the surface of a (hyper)sphere for each
point there is only a single other point at the maximum distance, so
complementarity based on distance maximization must lead to the abundance of
strong (chordless) quadrangles and locally dense bipartite-like subgraphs. (B
and C) Wedge and head quadruples. (D) Local $q$-clustering can be maximized
even when some 2-hop neighbors (node $k$ on the figure) of the focal node
connect to nodes which are not in $\mathcal{N}_{1}(i)$, while the $c_{i}$ is
sensitive to this deviation from the principle of complementarity. (E) Local
$q$-closure can be maximized even for nodes with sparse 1-hop neighborhoods if
they are star-like as neighbors with degree one do not generate any head
quadruples. (F) Necessary and sufficient conditions for maximum structural
complementarity.

We can now define structural complementarity coefficient as the fraction of
quadruples including the focal node $i$ which can be closed to make a (strong)
quadrangle which is equivalent to a weighted average of $q$-clustering and
$q$-closure:

$c_{i}=\frac{4Q_{i}}{q^{W}_{i}+q^{H}_{i}}=\frac{q^{W}_{i}c^{W}_{i}+q^{H}_{i}c^{H}_{i}}{q^{W}_{i}+q^{H}_{i}}$
(8)

Note that again we have that $\min(c^{W}_{i},c^{H}_{i})\leq
c_{i}\leq\max(c^{W}_{i},c^{H}_{i})$, so $c_{i}$ is always bounded between its
constitutive clustering and closure coefficients. This implies that $c_{i}$ is
a more general descriptor than $c^{W}_{i}$ or $c^{H}_{i}$ alone (cf. Section:
Configuration model). Moreover, the interpretations of $q$-clustering and
$q$-closure jointly imply that $c_{i}=1$ if and only if the focal node $i$
belongs to a fully connected bipartite network. Fig. 3 presents a summary of
the most important terms and facts related to $c_{i}$.

The geometric model underlying the definition of $c_{i}$ indeed justifies the
interpretation in terms of complementarity or synergy. Nodes are more likely
to be connected when they are far away in the feature space, meaning that they
have different properties which can be possibly combined in a synergistic
manner. Crucially, the mesoscopic network structure that is implied by this
model is also related to complementarity in a straightforward manner.
Bipartite networks are representations of complementarity-driven systems par
excellence as they consist of two types of nodes and allow only for
connections between them. Thus, $c_{i}$, being a measure of local bipartivity,
is indicative of the degree to which the local environment of a node resembles
such a complementarity-driven system.

However, our measure of structural complementarity, while closely related to
measures of network bipartivity [30, 23], is also different in at least two
important respects. Firstly, unlike bipartivity measures, structural
complementarity captures both local bipartivity and density. This is important
because even a high degree of bipartivity alone is not a signature of
complementarity, since random tree-like structures are also relatively
bipartite-like (as evident in Fig. 3a in Ref. [30] where bipartivity
coefficients, $b_{1}$ and $b_{2}$, are much higher than the minimal value of
$1/2$ even for networks with very low values of $r_{1}$ parameter which are
effectively Erdős–Rényi random graphs). Secondly, bipartivity measures are
typically global [30, 23], while structural complementarity coefficients can
be defined for edges, nodes and entire graphs (we note, however, that spectral
bipartivity can be defined also for individual nodes [22]).

Furthermore, structural complementarity coefficient follows closely the
definitions of i-quad and o-quad coefficients proposed in Ref. [31]. However,
it also differs in two important respects. Firstly, it combines both the
perspective of wedge (i-quad) and head (o-quad) quadruples. As we show later
(Section: Configuration model), this makes $c_{i}$ a more general descriptor
of local structure and the density of quadrangles, even if for some specific
research questions clustering or closure (i-quad or o-quad) coefficients may
still be more appropriate. Secondly, it is based on the notion of strong
(chordless) quadrangles instead of the weaker notion allowing for any number
of chordal edges. This is necessary for ensuring the direct connection to
bipartivity. However, it comes at a cost of making structural complementarity
coefficient more sensitive to noise (as strong quadrangles can be easily
destroyed by a single erroneous chordal edge) and less capable of detecting
structures deviating from the strict assumption of local bipartivity. Of
course, $c_{i}$ can be redefined using weak quadrangles, which would lead to a
measure equivalent to a weighted average of i-quad and o-quad coefficients.
However, developing a proper interpretation of weak quadrangles vis-à-vis the
principles of similarity and complementarity would require a non-negligible
amount of additional theoretical and mathematical work, which is outside the
scope of this paper. Nonetheless, weak quadrangles may have some interesting
applications as, for instance, they seem to be connected to the theory of
large quasirandom graphs, of which structure is determined by the amount of
general 4-cycles [39]. Thus, we plan to address this problem in the future.

When applied to bipartite networks the quadrangle-based measures can be seen
as a generalization of the bipartite clustering coefficient(s) [73, 50].
However, the crux is that our structural complementarity coefficients can be
applied to unipartite networks in order to quantify jointly local bipartivity
and density, which together are indicative of complementarity-driven
relations.

##### Global complementarity coefficient

From the global perspective of an entire network there is of course no
difference between wedge and head quadruples. Hence, the global coefficient
can be defined simply as:

$c=\frac{4Q}{\sum_{i,j}a_{ij}[(d_{i}-1)(d_{j}-1)-n_{ij}]}$ (9)

where $(i,j)\in E$ and $Q$ is the total number of quadrangles with no chords.
The denominator counts the total number of quadruples. Note that $c=1$ if and
only if the graph as such is fully connected and bipartite. This agrees with
the intuition as this is exactly the structure one should expect in a system
composed of two classes of elements in which each element in one class is
perfectly complementary to every element in the other.

#### Edgewise measures and structural equivalence

##### Similarity

Edgewise structural similarity coefficient is equal to the ratio of triangles
including nodes $i$ and $j$ and the total number of $2$-paths traversing the
$(i,j)$ edge (Figs. 2G and 4A). In other words, it is equivalent to the number
of shared neighbors relative to the total number of neighbors of $i$ and $j$,
excluding $i$ and $j$ themselves:

$s_{ij}=\frac{2T_{ij}}{t^{W}_{ij}+t^{H}_{ij}}=\frac{2n_{ij}}{d_{i}+d_{j}-2}$
(10)

where $T_{ij}$ is the number of triangles including $i$ and $j$, $t^{W}_{ij}$
is the number of $(k,i,j)$ and $t^{H}_{ij}$ of $(i,j,k)$ triples. Importantly,
$s_{ij}$ is symmetric since $T_{ij}=T_{ji}$ and $t^{W}_{ij}=t^{H}_{ji}$.

Note that $s_{ij}$ is closely related to Hamming similarity defined in Eq. (1)
and differs only in the $-2$ term in the denominator which accounts for the
fact that $i$ and $j$ are known to be connected. Together with the fact that
nodewise coefficient $s_{i}$ is a weighted average of the corresponding
edgewise coefficients, or $\min_{j}{s_{ij}}\leq s_{i}\leq\max_{j}{s_{ij}}$ for
$j\in\mathcal{N}_{1}(i)$, this implies that $s_{i}$ can be seen as a proxy for
the extent to which $i$ is structurally equivalent to its own neighbors.

More concretely, it can be shown that:

$\min_{j}H_{ij}<s_{i}\leq\max_{j}\left(H_{ij}\frac{d_{i}+d_{j}}{d_{i}+d_{j}-2}\right)$
(11)

In other words, high (low) $s_{i}$ implies the existence of highly (lowly)
structurally equivalent neighbor(s). Crucially, this also explains why
structural similarity is inherently linked to transitivity. If neighbors of
$i$ are highly structurally equivalent to it, then it must be likely that if
$i\sim j$ and $j\sim k$ then $i\sim k$ or if $i\sim j$ and $i\sim k$ then
$j\sim k$. The proof of the above statements is presented in the Supplementary
Information (SI: Similarity and structural equivalence).

Figure 4: Interpretation of the edgewise structural coefficients. Focal edges
are marked with colors (red or blue) and paths starting from the focal $(i,j)$
edge are black and dark grey. Solid lines denote paths (triples or quadruples)
and dashed lines correspond to closing edges that form triangles or
quadrangles. (A) Logic of edgewise similarity and the necessary and sufficient
conditions for maximum $s_{ij}$. If $(i,j)$ edge is driven by similarity then
any neighbor of either $i$ or $j$ ($k$ and $l$ on the figure) should be near
$i$ (or $j$) in the latent space making it likely that it links to the other
member of the $(i,j)$ pair too. On the other hand, $k$ and $l$ may still be
quite far away so the link between them is unlikely to exist. (B) Logic of
edgewise complementarity and necessary and sufficient conditions for maximum
$c_{ij}$. If $(i,j)$ edge is driven by complementarity then any $2$-hop
neighbor of $j$ ($i$), such as $l$ ($k$) on the figure, should be a $1$-hop
neighbor of $i$ ($j$). The quadruple $(i,j,k,l)$ corresponds to such a
situation. On the other hand, any pair of neighbors of $i$ and $j$
correspondingly may be located in the latent space close enough to each other
as to make a tie between them unlikely (as it happens for nodes $m$ and $k$ on
the figure).

##### Complementarity

Edgewise structural complementarity coefficient is defined as:

$c_{ij}=\frac{2Q_{ij}}{q^{W}_{ij}+q^{H}_{ij}}$ (12)

where $Q_{ij}$ is the number of quadrangles including nodes $i$ and $j$,
$q^{W}_{ij}$ is the number of $(j,i,k,l)$ and $q^{H}_{ij}$ of $(i,j,k,l)$
quadruples. Again, $Q_{ij}=Q_{ji}$ and $q^{W}_{ij}=q^{H}_{ji}$ so $c_{ij}$ is
symmetric.

This way $c_{ij}$ can be seen as a joint measure of bipartivity around an
$(i,j)$ edge and structural equivalence between $i$ and $1$-hop neighbors of
$j$ and vice versa. It measures the extent to which
$\mathcal{N}_{2}(i)\approx\ \mathcal{N}_{1}(j)$ and
$\mathcal{N}_{1}(i)\approx\mathcal{N}_{2}(j)$ without requiring dense
connections between the $1$-hop and $2$-hop neighborhoods of $i$ and $j$. This
is in analogy to edgewise similarity which measures only the extent to which
$\mathcal{N}_{1}(i)\approx\mathcal{N}_{1}(j)$ without considering the density
of connections between the neighbors of $i$ and $j$ as this would be a higher-
order property unrelated to whether an edge is driven by similarity or not
(see Fig. 4 for details).

The connection to structural equivalence is slightly more complicated in the
case of complementarity and necessitates an introduction of an additional
quantity. For a connected triple $(k,i,j)$ we define Asymmetric Excess
Sørenson Index:

$H_{kj|i}=\frac{n_{jk}-1}{d_{k}-1-a_{jk}}$ (13)

which measures how many of the connections of $k$ are also shared by $j$ while
disregarding edges $(i,k)$, $(i,j)$ and $(j,k)$. Note that the excess degree
of $k$ is used in the denominator as the $(i,k)$ link needs to be ignored.
Moreover, $a_{jk}$ term accounts for the possible presence of the $(j,k)$
link. Finally, $1$ is subtracted from $n_{jk}$ to account for the fact that
$i$ is a shared neighbor of $j$ and $k$.

Now, using the fact that $c_{i}$ is a weighted average of $c_{ij}$’s, or
$\min_{j}c_{ij}\leq c_{i}\leq\max_{j}c_{ij}$, it can be shown that:

$0\leq c_{i}\leq\max_{j,k,l}\left(H_{kj|i},H_{li|j}\right)$ (14)

where $j\in\mathcal{N}_{1}(i)$, $k\in\mathcal{N}_{1}(i)-\\{j\\}$ and
$l\in\mathcal{N}_{1}(j)-\\{i\\}$ (see the proof in SI: Complementarity and
structural equivalence).

In other words, $c_{i}$ is bounded from above by the maximum Asymmetric Excess
Sørenson Index between any two of its neighbors or itself and any neighbor of
its neighbors. Intuitively, high complementarity can exist only in the
presence of high structural equivalence between neighbors of $i$ as well as
$i$ and neighbors of its neighbors.

Crucially, this explains in what sense complementarity-driven relations are
not transitive but yet localized. The principle of complementarity enforces
both the lack of connections between 1-hop neighbors of $i$ as well as a
degree of structural equivalence between them. This in turn induces a
particular kind of correlations between the connections of $i$ and its 1- and
2-hop neighbors which at the same time do not imply transitivity of relations.

### Results

Here we present the results of four case studies analyzing the behavior of
structural coefficients in random graph models and using them to answer
specific research questions based on several empirical datasets.

#### Structural coefficients in random graphs

##### Erdős–Rényi model

In the Erdős–Rényi (ER) model [21] the expected global similarity, which is of
course equivalent to global clustering, is simply $\mathbb{E}[s]=p$, or equal
to the probability that any edge exists. This is a standard result that
follows from the fact that for any $(i,j,k)$ triple the closing $(i,k)$ edge
always exists with probability $p$ [49].

We can use a similar argument to derive the expected value of global
complementarity coefficient in the ER model. Let $(i,j,k,l)$ be any connected
quadruple. It forms a quadrangle with no chords if and only if the $(i,l)$
edge exists while the $(i,k)$ and $(j,l)$ edges do not. Since all edges in the
ER model exist independently with probability $p$ it means that the expected
value of global complementarity coefficient is $\mathbb{E}[c]=p(1-p)^{2}$.
Crucially, this result implies that global complementarity decays
asymptotically towards 0 in sparse random graphs ($\lim_{n\to\infty}\langle
d_{i}\rangle/n\to 0$). This distinguishes it from global bipartivity measures
which attain non-minimal values for ER random graphs (cf. Fig. 3a in Ref.
[30]).

##### Configuration model

A classical null model for studying nodewise coefficients and their
correlations with node degrees is the configuration model in which a
particular degree sequence is enforced while apart from that connections are
established as randomly as possible [49]. In order to describe the qualitative
behavior of the nodewise structural similarity and complementarity we will use
the fact that in both cases they are bounded by their corresponding clustering
and closure coefficients.

First, note that it is usually conjectured that $t$-clustering should
generally decrease with node degree [49]. More recently, it was analytically
proven for the family of random networks with power law degree distributions
that $t$-clustering is on average roughly constant for low-degree nodes and
then starts to decrease more quickly as node degree grows [66].

On the other hand, it has been shown that local closure coefficient, or
$t$-closure in our terminology, is positively correlated with node degree in
the configuration model [71]. Thus, these two results together imply that
structural similarity $s_{i}$ can display rich, also non-monotonic,
correlations with node degrees depending on the structure of a particular
network.

We leave analytical study of the analogous properties of $q$-clustering and
$q$-closure for future work. However, since both types of clustering and
closure coefficients are based on either wedge or head triples/quadruples and
therefore are very similar by construction, we conjecture that they should
display the same qualitative behavior in the configuration model. Namely, we
expect that $q$-clustering should decrease with node degree, especially for
well-connected nodes, and $q$-closure should increase with node degree. As a
result, we also expect that structural complementarity should vary with
respect to node degree in various, also non-monotonic, ways.

Figure 5: Correlations of clustering, closure and structural coefficients with
node degrees in configuration model ensembles based on degree sequences from 8
real-world social and biological networks. See the SI (Fig. S1) for full
results based on 28 networks and the description of the datasets. Null
distributions of the coefficients were approximated based on 100 samples from
Undirected Binary Configuration Model (UBCM). The plots show values averaged
for different node degrees in logarithmic bins (base 2). As evident in the
figure, structural (similarity and complementarity) coefficients are always
bounded between their corresponding clustering and closure coefficients.
Furthermore, in all networks clustering coefficients tend to decrease for high
degree nodes while closure coefficients grow with respect to degree.

Indeed, our theoretical expectations agree with average trends observed in
randomized networks sampled from Undirected Binary Configuration Model[65]
(UBCM; see Materials and Methods) fitted to degree sequences of 28 real-world
networks. See Fig. 5 for details. The results have two important practical
implications. Firstly, structural coefficients often tend to follow closure
coefficients more closely for low-degree nodes and clustering coefficients for
high degree nodes. In other words, in the configuration model local structure
around low-degree (high-degree) nodes is dominated by head (wedge)
triples/quadruples, that is, clustering/closure coefficients are good
descriptors of the density of triangles/quadrangles only for particular
subsets of the degree spectrum. More generally, the degree to which they are
relevant depends on the relative abundances of wedge and head paths. On the
other hand, structural coefficients are more universal since they are weighted
averages of both clustering and closure coefficients with weights reflecting
the relative dominance of wedge or head paths.

Secondly, structural coefficients depend on node degrees even in random graphs
and therefore, when comparing different networks, their values should be
calibrated based on a plausible null model such as UBCM to account for the
effects induced purely by the first-order structure (degree sequences).

#### Structural coefficients in real networks

We studied structural similarity and complementarity in multiple real-world
social and biological networks measuring different kinds of relations —
friendship, trust and recognition for social networks as well as gene
transcription regulation and general protein-protein interactions
(interactomes) for biological networks (see Fig. 6 for details). The goal was
to see whether structural similarity and complementarity can be related to
some meaningful domain-specific properties of different types of networks.

Figure 6: Structural similarity and complementarity in social (19 cases) and
biological (9 cases) networks. Scatterplots show calibrated average nodewise
coefficients with dashed lines indicating null model expectations based on
UBCM (see Materials and Methods for details on the datasets and calibration).
Colors of the quadrants of the plots indicate configurations of increased
values of similarity and complementarity coefficients — high and low (red),
low and high (blue), both high (violet). (A) Social networks. Almost all
feature high similarity and some also increased complementarity (these are
mostly large online social networks). The only case with low similarity and
relatively high complementarity is the network of Dutch literary criticism
representing relationships of recognition (mentioning other’s work, positively
or negatively, in an essay or an interview) within a set of notable literary
authors [18]. (B) Interpretation of similarity and complementarity in terms of
homophily, preferences and transitivity. Some social relations, especially
those depending on close bonds such as friendship or trust, are often driven
by homophily [42, 47]. This implies transitivity of ties and the abundance of
triangles due to triangle closure. However, other relations such as
recognition or skill-based collaboration [70] are based on preferences
decoupled from the properties of the ego. In this case two nodes with similar
preferences connect to the same neighbors but not necessarily to each other.
This leads to what can be called second-order transitivity, which in turn
implies quadrangle closure. (C) Biological networks. Most of them feature both
increased similarity and complementarity indicating higher structural
diversity than in the case of social networks. This is consistent with
multiple results reporting the abundance of both triangle and quadrangle based
motifs [48, 58, 64]. (D) Examples of the relationship between directed motifs
often reported for biological networks and undirected motifs used for defining
structural similarity and complementarity.

Our results show that similarity and complementarity in social networks are
indeed related to different types of relations. In particular, similarity is
stronger in systems driven by homophily, that is, preference for connecting to
others who are similar to us, which leads to the transitivity of relations.
The importance of similarity seems to be particularly strong for relations
depending on close ties such as friendship or trust. This is consistent with
decades of research on social networks [42, 47, 34, 54]. On the other hand, it
seems that complementarity plays an important role in shaping of relations in
which preferences are decoupled from the properties of the ego, such as
recognition (e.g. of value or importance of others), skill-based collaboration
[70] or trade/business interactions [45]. In this case two agents with similar
preferences should typically connect to the same neighbors (and therefore be
structurally equivalent) but not necessarily to each other, as the preferences
of an agent do not have to match its intrinsic properties. This leads to the
abundance of quadrangles and the presence of locally dense bipartite-like
subgraphs, that is, the structural signatures of complementarity.
Interestingly, even though such preference-based relations are not directly
transitive, they can be considered second-order transitive due to the implied
mechanism of quadrangle closure (see Fig. 6B). We put this tentative
hypothesis to a more direct and systematic test in the next section
(Similarity and complementarity in social relations).

Most of the biological networks feature both relatively high similarity and
complementarity. This is consistent with multiple results concerning network
motifs characteristic for interactomes as well as neural and gene
transcription regulatory networks [48, 58, 64]. Namely, structural similarity
is linked to the presence of feed-back and feed-forward loops which, when edge
directions are unknown or ignored, explains the abundance of triangles. On the
other hand, structural complementarity is connected to motifs such as bi-fan
and bi-parallel [48], which imply the abundance of quadrangles (see Fig. 6D).
Importantly, these structural patterns can be linked to meaningful domain-
specific complementarities between different subsets of elements of a system.
For instance, in gene transcription regulatory networks bipartite-like
subgraphs with high density of bi-fan motifs (quadrangles) represent dense
overlapping regulons (DOR) or groups of operons regulated by similar
combinations of input transcription factors [58].

Our results also point to important differences between social and biological
networks. The former, with some exceptions of course, tend to be dominated by
similarity while the latter are more structurally diverse, which probably
reflects their heterogeneous functional properties and complex evolutionary
history (we study this in more detail in Section: Structural diversity across
the tree of life). However, it seems that large online social networks also
feature increased complementarity relatively often (see Fig. 6A). Thus, it may
be worthwhile to study differences between small and large as well as offline
and online social networks in the future. In particular, to our best knowledge
it is not yet clear what social processes are responsible for significantly
high amounts of quadrangles in large online social networks.

#### Similarity and complementarity in social relations

Here we test the hypothesis that social relations based on homophily are
linked to structural similarity and those based on preference, recognition or
skill-based collaboration to structural complementarity. In other words, here
we assess the theoretical validity of our approach. For this purpose, we used
a set of 34 social networks collected in 17 rural villages in Mayuge District,
Uganda [12]. For each village two networks of relations between households
were measured: (1) a friendship network and (2) a health advice network (see
Materials and Methods for details).

This dataset has the structure of a natural experiment as for each village we
have two different networks representing relations between the same households
in the same period of time which were measured by the same research team(s)
using the same method. Thus, they are very likely to be equivalent with
respect to any possible covariate except for the type of relation that was
measured (friendship or health advice). In other words, they can be compared
to each other as nearly perfect synthetic controls [17] and therefore allow
reliable estimation of the effects specific for friendship and health advice
relations.

Thus, the dataset provides a perfect setting for testing our hypothesis.
Namely, it is sociologically justified to expect the friendship networks to
feature high structural similarity as it is a well documented fact that
friendship relations are to a large extent shaped by homophily [42, 47, 34].
On the other hand, health advice networks should be at least partially driven
by complementarity, as the act of advice is usually based on the recognition
of and preference for one’s knowledge as well as an information differential
between an adviser and an advisee. In other words, advising is based on a
synergy between needs and assets of two agents. Moreover, it can be also seen
as a particular kind of skill-based collaboration, which is known to be linked
to complementarity and heterophily [55, 70]. Thus, it is justified to expect
the health advice networks to feature high structural complementarity.

Figure 7: Comparison of structural coefficients between friendship and health
advice networks in 17 Ugandan villages. Observed values were calibrated based
on 500 samples from UBCM (see Materials and Methods). (A) Univariate
distributions of global and average nodewise coefficients reveal significant
differences between the friendship and health advice networks which are
consistent with the hypothesis. The friendship networks feature significantly
higher structural similarity and the health advice networks higher
complementarity. The average differences between networks from the same
villages are denoted by $\Delta$’s. Statistical significance was assessed
using one-sample $t$-test with two-sided null hypothesis applied to the
differences; $p$-values were adjusted for multiple testing using Holm-
Bonferroni method. (B) Bivariate distribution of the calibrated values of the
average nodewise similarity and complementarity coefficients. The decision
boundary separating the friendship and health advice networks (marked in red)
is based on Quadratic Discriminant Analysis (QDA). The out-of-sample
classification accuracy was estimated with stratified 17-fold cross-validation
(one fold per village).

As evident in Fig. 7A, the results are in clear agreement with the theoretical
expectations. The calibrated similarity coefficients (see Materials and
Methods) in the friendship networks were typically increased relative to the
null model (average log-ratios greater than zero) and significantly higher
than in the health advice networks ($p<0.001$). On the other hand, the results
for the complementarity coefficients were exactly opposite and in this case
the health advice networks featured significantly larger calibrated values
($p<0.01$).

Thanks to the convenient quasi-experimental structure of the dataset and the
calibration accounting for differences in degree sequences the results provide
strong support for the claim that, ceteris paribus, social relations based on
similarity and complementarity leave distinct structural signatures in social
networks which can be detected using structural coefficients. In other words,
we showed that, all else being equal, similarity-based ties are linked to the
abundance of triangles and those based on complementarities to the abundance
of quadrangles. This confirms the theoretical validity of the proposed
framework and shows that patterns captured by structural coefficients are
indeed related to meaningful domain-specific phenomena. Crucially, it also
shows that there are types of social relations which are driven not by
similarity but complementarity, so the default assumption of homophily is not
always adequate.

To gauge the discriminatory power of the coefficients better, we fitted a
supervised classifier based on Quadratic Discriminant Analysis (QDA) [29]. To
facilitate visualization we used only two predictors: average nodewise
similarity and complementarity coefficients. The estimated out-of-sample
accuracy was $85.29\%$ (Fig. 7B), which provides further confirmation of the
theoretical validity of our approach.

#### Structural diversity across the tree of life

Functioning of all biological organisms depends on protein-protein
interactions (PPIs), which themselves are constrained by the presence of
compatible binding sites [35]. Hence, it can be argued that it is not similar
but complementary proteins that are most likely to interact, or that two
proteins sharing a neighbor do not have to be connected but instead are likely
to share other neighbors (and be structurally equivalent). This view is
supported by the statistical over-representation of quadrangle-based motifs in
interactome networks [48, 58] as well as recent advances in PPI prediction,
which showed that models based on 3-paths (L3) and quadrangle closure
outperform those based on 2-paths (L2) and triangle closure [35]. Moreover,
there is substantial evidence that protein neighborhoods in interactome
networks across the tree of life tend to gradually shift from the dominance of
triangles to quadrangles during evolution [74]. Nonetheless, triangle-based
motifs are also prevalent in PPI networks and their presence tend to even
correlate positively with the abundance of quadrangles [64]. Here we study
this problem from the perspective of structural similarity and complementarity
and show that increasing complexity of organisms is associated with higher
structural diversity of PPI networks, meaning that protein neighborhoods tend
to feature increasing numbers of both triangles and quadrangles.

We studied PPI networks, or interactomes, of 1840 species across the tree of
life [74] (see Fig. 8 for details). We used network size (number of proteins)
for a proxy of the biological complexity of an organism, which is arguably
justified as on average interactomes of more complex organisms, such as
animals or green plants, are markedly larger than those of bacteria or
archaea. Moreover, taxa with larger interactomes on average also tend to have
longer average evolution times measured in terms of nucleotide substitutions
per site (Fig. 8B).

Figure 8: Structural diversity of 1840 interactomes across the tree of life
[74] (see Materials and Methods). The analysis was based on proportions of
nodes with significantly high values ($p\leq\alpha=0.01$) of structural
coefficients $s_{i}$ and $c_{i}$ or both of them. We also conducted a
sensitivity analysis for alternative levels $\alpha=0.05,0.10$ (SI: Structural
diversity analysis). Significance was based on null distributions estimated
with 100 samples from UBCM. (A) We followed the division into the domains of
Archaea, Bacteria and Eukaryota [68], but also distinguished three arguably
most complex taxa within eukaryotes: green plants (Viridiplantae), fungi and
animals (Metazoa). The two “other” classes consist of all other eukaryotes.
(B) Evolution time and interactome sizes in groups. (C) Proportions of nodes
with significant values of $s_{i}$ are high in all groups, but tend to be
lower among bacteria, which are the only group that feature relatively large
numbers of proteins with high structural complementarity. Crucially, it is the
more complex eukaryotes, particularly animals and plants, which feature many
nodes with significantly high values of both $s_{i}$ and $c_{i}$. This
suggests that interactomes of more complex organisms tend to be more
structurally diverse. The lower panel shows Spearman $\rho$ correlations
between interactome size and the proportions as well as the diversity index
(16); ${}^{***}p\leq 0.001$,${}^{**}p\leq 0.01$, ${}^{*}p\leq 0.05;$ Holm-
Bonferroni correction for multiple testing was used. Notably, in all groups
except Archaea the correlations between interactome size and the diversity
index as well as the “both” proportion are strongly positive. Moreover,
complementarity increases with network size in plants, fungi and animals but
decreases in bacteria, which means that in both cases the general trend goes
in the direction of greater structural diversity. (D) Structural diversity and
interactome size. The general correlation is positive and relatively strong.

The analysis was focused on the structural diversity of protein neighborhoods
in terms of the local abundance of triangles and quadrangles in relation to
the organism complexity (interactome size). We quantified the structure at the
level of entire networks in terms of fractions of nodes with significantly
high values of $s_{i}$ and $c_{i}$ coefficients or both of them (see Fig. 8
for details). Moreover, we also combined the fractions in a synthetic index of
structural diversity, $\mathbb{S}_{\alpha}(G)\in[0,1]$ (see Materials and
Methods for details on calculating $p$-values and structural diversity).

Our analysis (see Fig. 8 for details) indicates a large amount of variation
between different species and taxa. It suggests that bacteria interactomes
tend to be driven by complementarity, and therefore dominated by quadrangles,
to a larger extent than those of other organisms. On the other hand, more
complex eukaryotes (green plants, fungi and animals) tend to feature nodes
with both high structural similarity and complementarity more often, which
implies that protein neighborhoods in their interactomes are more
heterogeneous and contain both many triangles and quadrangles. Crucially, this
intuition is also confirmed by our structural diversity index which correlates
positively with organism complexity (interactome size) (Fig. 8D). Apart from
the tail composed of species with large PPI networks where the trend seems to
bifurcate into two groups of organisms with unexpectedly high and low
diversity scores (with some notable outliers such as Homo sapiens and
Sarcophilus harrisii, or Tasmanian devil), the model provides a relatively
good representation of the data generating process. We modeled the
relationship using a linear model with logit transform applied to the
diversity index and log transform to the number of nodes. Thus, the
relationship between “odds” of the diversity index and the number of nodes
follows a power law, $\mathbb{S}_{\alpha}(G)/(1-\mathbb{S}_{\alpha}(G))\propto
n^{\gamma}$, with $\gamma=0.48$ (95% CI: $[0.45,0.51]$; $p<0.001$). We discuss
additional details and analyses in the SI (Structural diversity analysis). In
particular, we study the stability of the results for different choices of
$\alpha$ and examine models controlling for the number of publications on
different species (to partially correct for publication bias and resulting
differences in terms of interactome completeness).

The results suggest a general tendency towards greater structural diversity in
PPI networks of more complex organisms. In many cases this implies an
increasing prevalence of quadrangles, which is consistent with the results
reported in Ref. [74] as well as the general importance of complementarity of
binding sites for protein-protein interactions [35]. It is also consistent
with the accounts of gene duplication occurring during evolution, and in
particular whole genome duplication events [69, 19], resulting in the creation
of pairs of similarly wired proteins, which together may form multiple
quadrangles. These are tentative results which needs to be corroborated with
more in-depth analyses before they could have a substantial biological
interpretation. Nonetheless, the general picture painted by structural
coefficients seems to agree with the existing literature on PPI networks,
which suggests that the proposed coefficient may be useful for studying
biological networks.

Our results also indicate that, despite the likely increasing importance of
quadrangles during evolution, triangles are still important, perhaps as a
manifestation of feed-back and feed-forward loops, and interactomes often
feature many triangles and quadrangles at the same time, which is consistent
with the reports of positive correlations between triangle and quadrangle
densities in interactomes [64]. This suggests a way for improving on PPI
prediction models based purely on L2 or L3 [35] measures by using a model
averaging combining the two metrics by somehow using the information on the
local structure provided by structural coefficients. We leave a detailed
exploration of this idea for future work.

### Discussion

Starting from first principles based on simple geometric arguments we
introduced a framework for measuring similarity- and complementarity-driven
relations in networks. We linked both relational principles to their
characteristic network motifs — triangles and quadrangles respectively — and
defined two general families of structural similarity and complementarity
coefficients measuring the extent to which they shape the structure of any
unweighted and undirected network. In other words, we showed that both
similarity and complementarity leave statistically detectable structural
signatures, which opens up new possibilities for studying the structure of
various networked systems explicitly in terms of the impact of these two
relational principles. We also demonstrated, using multiple empirical
examples, that both similarity and complementarity are important for many
kinds of social and biological relations. In particular, our results indicate
that the customary assumption of homophily may not be appropriate for some
social networks, of which structure may be better explained by
complementarity.

Even though the connection between the structure of networks and the principle
of complementarity is still relatively unexplored, our work was informed by
existing studies on quadrangle formation [31], functional structure [45],
geometry of complementarity-driven networks [33] and complementarity-based
link prediction [35]. It extends this branch of the literature by introducing
a set of general graph-theoretical coefficients measuring the density of
quadrangles and proposing a simple, minimalistic geometric model linking the
principle of complementarity to quadrangles as its characteristic motif.

Furthermore, in contrast to previous studies using quadrangle-based
descriptors of local structure [31], our approach is focused specifically on
strong (chordless) quadrangles (cf. Fig. 3A). This makes it, of course, less
general, but at the same time allows making a direct connection between the
principle of complementarity and network bipartivity. As a result, our work
shows that the principle of complementarity induces structures which are both
locally bipartite-like and dense, in the same way as similarity is connected
to locally dense unipartite subgraphs. Moreover, the proposed structural
complementarity coefficients, which measure both bipartivity and density, may
be a useful addition to the existing set of measures of bipartivity [30, 23],
which do not consider local density. In particular, it may be potentially very
useful in studies on systems with so-called functional structure such as
production/trade or PPI networks, which are supposed to be characterized by
both relatively high bipartivity and density of quadrangle motifs [45].

Using structural coefficients applied to a rich empirical material, we
confirmed that typically social relations such as friendship or trust are
driven by similarity and therefore are transitive and linked to the abundance
of triangles. However, we also showed that some types of relations, for
instance advice, recognition or skill-based collaboration, are more likely to
be driven by complementarity, which leads to markedly different local
connectivity structures dominated by quadrangles instead of triangles.
Importantly, this indicates that such relations are not directly transitive
($i\sim j\land j\sim k\Rightarrow i\sim k$), but instead second-order
transitive ($i\sim j\land j\sim k\land k\sim l\Rightarrow i\sim l$), which
implies that the principle of triangle (2-path) closure does not capture the
dynamics of such systems very well. Instead, it is quadrangle (3-path) closure
which is more adequate, so the default assumption of homophily/triadic closure
[47, 34, 6] is not always justified. Thus, our results encourage more nuanced
approaches to social network analysis and potentially can be used to design
novel, more flexible link prediction methods.

We also confirmed that biological networks such as gene transcription
regulatory or general PPI networks are more likely to be driven by
complementarity and feature more quadrangles than typical social networks.
This is consistent with multiple empirical results [58, 64, 35, 74] and the
general mechanism of protein-protein interactions based on complementarity of
binding sites [35]. Using structural coefficients, we demonstrated that
interactome networks of more complex organisms across the tree of life tend to
be more structurally diverse, meaning that they consist of many proteins with
neighborhoods containing significantly high numbers of both triangles and
quadrangles. This indicates a large degree of heterogeneity of structure in
PPI networks and suggests that recent results showing that protein interaction
prediction based on 3-path (L3) closure is more effective than the 2-path (L2)
closure rule [35], could be perhaps further improved by combining the L2 and
L3 principles in a way informed by the local structure around a given pair of
proteins.

An important limitation of our work is the fact that our methods currently can
be applied only to undirected and unweighted networks. However, generalizing
them to the weighted case should be rather straightforward, and we plan to
address this problem in the future. In particular, it should be possible to
define weighted structural coefficients following the approach used for
defining weighted clustering coefficient in Ref. [7]. On the other hand, the
geometric motivation of structural coefficients is inherently undirected, so
it is not immediately clear how directed coefficients should be defined. For
now, we leave it as an interesting open problem.

In summary, we showed that both similarity and complementarity are important
organizational principles shaping the structure of social and biological
networks and can be linked to interpretable, domain-specific phenomena. We
proposed a set of coefficients for measuring the extent to which they shape
the structure of networks and demonstrated the theoretical validity and
practical utility of the proposed framework on a rich empirical material.

### Materials and Methods

#### Computing structural coefficients

Structural coefficients are based on counting triples and triangles
(similarity) as well as quadruples and quadrangles (complementarity). While
the first problem is relatively easy and efficient methods for solving it are
implemented in many popular libraries for graph analysis, the second problem
of counting quadruples and quadrangles is more difficult and corresponding
efficient algorithms are not widely known. Here we solve both problems by
counting all motifs of interest at the level of individual edges and then
aggregate the edgewise counts to nodewise or global counts when necessary. We
propose an algorithm which can be seen as a special case of a highly efficient
exact graphlet counting method proposed in Ref. [2]. We call it PathCensus
algorithm as ultimately it counts different types of paths and cycles.
Pseudocode for the algorithm and other computational details are discussed in
the SI (Structural coefficients and PathCensus).

#### Undirected Binary Configuration Model

We used Undirected Binary Configuration Model (UBCM) [65] for the calibration
and assessment of statistical significance of structural coefficients. UBCM is
a variant of the configuration model that induces a maximum entropy
probability distribution over undirected and unweighted networks with $n$
nodes constrained to have a specific expected degree sequence.

UBCM belongs to the family of Exponential Random Graph Models (ERGM) [59]
which induce maximum entropy distributions over networks satisfying some
constraints in expectation. Crucially, it means that such models are fully
specified by a set of sufficient statistics [38] describing the desired
constraints. Hence, the maximum entropy distributions they induce are as
unbiased as possible with respect to any other property [59].

#### Calibrating values of structural coefficients

In the analyses comparing different networks we calibrated observed values of
structural coefficients against UBCM in order to account for effects induced
purely by the first-order structure (i.e. degree sequences). Such a
calibration may be implemented in many different ways, but all reasonable
approaches should yield qualitatively comparable results. We explain our
method using an example of a calibration of a graph-level statistic such as
average nodewise similarity coefficient, $\langle s_{i}\rangle$.

First, for an observed network $G$ calculate the value of a graph statistic of
interest, $x(G)$. Then, sample $R$ randomized replicates $G_{i}$’s of the
observed network from a chosen null model (e.g. UBCM) and calculate $x(G_{i})$
for $i=1,\ldots,R$. Finally, the calibrated value of $x(G)$ based on $R$
samples from the null model is defined as the average log-ratio of the
observed value and the randomized values:

$\mathcal{C}(x,R)(G)=\frac{1}{R}\sum_{i=1}^{R}\log{\frac{x(G)}{x(G_{i})}}$
(15)

Note that the calibrated values are defined using ratios of $x(G)$ and
$x(G_{i})$’s, which are expressed in the same units (e.g. triangles/2-paths),
and therefore produce a dimensionless quantity, as required by the logarithmic
function [44].

#### Assessing significance of structural coefficients

Statistical significance of nodewise structural coefficients was estimated
using simulated null distributions based on $R$ samples from UBCM. We used the
fact that UBCM is a variant of the class of ERGMs [65] and therefore the
probability distribution it induces is fully determined by a set of sufficient
statistics [38], that is, the expected degree sequence in our case. This
implies that null distributions of any statistics for nodes with the same
degrees are identical, so such nodes are indistinguishable from the vantage
point of the model. Thus, we estimated $p$-values according to the following
procedure:

  1. 1.

Sample $R$ randomized analogues of an observed network $G$ from the
probability distribution induced by UBCM.

  2. 2.

For each graph $G_{i}$ with $i=1,\ldots R$ calculate a vector of nodewise
statistics such as structural similarity coefficient $s_{i}$.

  3. 3.

Group calculated values in buckets defined by unique values of node degrees in
the observed network $G$. Nodes in randomized networks are treated as if they
had the same degrees as their corresponding nodes in $G$.

  4. 4.

Calculate quantiles of the distributions in the buckets.

  5. 5.

Set $p$-value for each node to $p=1-\alpha_{\text{max}}$, where
$\alpha_{\text{max}}$ is the maximum quantile lower than the observed value
for a given node. In all cases we used one hundred quantiles or percentiles.

  6. 6.

Adjust $p$-values for multiple testing using two-stage False Discovery Rate
(FDR) correction proposed by Benjamini, Krieger and Yekutieli (Definition 6 in
Ref. [8]).

Note that the above procedure ensures at least $R$ observations for each node
(and more for those with non-unique degrees) and therefore allows estimation
of $p$-values with a resolution of at least $0.01$ when $R\geq 100$ ($1/R$ in
general).

#### Structural diversity index

Let $p^{\alpha}_{S}(G),p^{\alpha}_{C}(G),p^{\alpha}_{B}(G)$ and
$p^{\alpha}_{N}(G)$ be respectively proportions of nodes with significantly
high values (at $p\leq\alpha$) of $s_{i}$ or $c_{i}$ coefficients or both of
them or neither in a graph $G$. Then, we can define analogous proportions
conditioned on the set of nodes with at least one significant value as
$p^{\alpha}_{X\mid N^{\prime}}(G)=p^{\alpha}_{X}(G)/(1-p^{\alpha}_{N}(G))$ for
$X=S,C,B$. The conditional proportions define a probability distribution
$\mathcal{P}^{\alpha}_{G}$. Finally, structural diversity index of a graph $G$
at a significance level $\alpha$ is defined as:

$\mathbb{S}_{\alpha}(G)=\frac{(1-p^{\alpha}_{N})\mathbb{H}(\mathcal{P}^{\alpha}_{G})}{\log_{2}{3}}$
(16)

where
$\mathbb{H}(\mathcal{P}^{\alpha}_{G})=-\sum_{X}p_{X}^{\alpha}(G)\log_{2}{p_{X}^{\alpha}(G)}$
is Shannon entropy functional [57] and $\log_{2}{3}$ term in the denominator
is a normalizing constant ensuring that $\mathbb{S}_{\alpha}(G)\in[0,1]$. This
measure captures structural heterogeneity of node neighborhoods while being
penalized for networks with mostly random-like structure.

#### pathcensus package

We implemented all the methods and algorithms for calculating structural
coefficients as well as several other utilities including most appropriate
null models and auxiliary methods for conducting statistical inference in
pathcensus package for Python. The core routines are just-in-time compiled to
highly optimized C code using Numba library [37] ensuring high efficiency. The
package has an extensive documentation including several usage examples. It is
currently available at GitHub (https://github.com/sztal/pathcensus) and will
be distributed through Python Package Index upon publication.

### Data availability

This study did not generate any new data. Networks used in this paper are
freely accessible from the Netzschleuder repository:
https://networks.skewed.de. Preprocessed data used in the analyses as well as
the code needed for reproducing the data and all the analyses are available at
GitHub: https://github.com/sztal/scs-paper (the repository will be archived
upon publication).

### Acknowledgements

We thank Shlomo Havlin for an advice on contextualizing our work within the
literature on network motifs as well as Brennan Klein and Ivan Voitalov for an
inspiring conversation on complementarity-driven relations few years ago. We
also thank Maciej Talaga for proofreading and Mikołaj Biesaga for the help
with testing the code. This work was supported by a grant from National
Science Center, Poland (Outline of a network-geometric theory of social
structure, 2020/37/N/HS6/00796).

### Author contributions

S.T. and A.N. conceptualized the project. S.T. formulated the mathematical
formalism and wrote the related proofs, designed the algorithms and developed
their Python implementation in the form of pathcensus package. S.T. conducted
the data analyses and prepared the figures. S.T. and A.N. wrote the main text
together.

### Competing interests

The authors declare no competing interests.

### Additional information

Correspondence and requests for materials should be addressed to S.T.

## References

  * [1]
  * Ahmed et al. [2015] Nesreen K. Ahmed, Jennifer Neville, Ryan A. Rossi, and Nick Duffield. 2015.  Efficient Graphlet Counting for Large Networks. In _2015 IEEE International Conference on Data Mining_. IEEE, Atlantic City, NJ, USA, 1–10.  https://doi.org/10.1109/ICDM.2015.141
  * Alon [2007] Uri Alon. 2007.  Network Motifs: Theory and Experimental Approaches.  _Nature Reviews Genetics_ 8, 6 (June 2007), 450–461.  https://doi.org/10.1038/nrg2102
  * Anagnostopoulos et al. [2008] Aris Anagnostopoulos, Ravi Kumar, and Mohammad Mahdian. 2008\.  Influence and Correlation in Social Networks. In _Proceeding of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining_. ACM Press, Las Vegas, Nevada, USA, 7–15.  https://doi.org/10.1145/1401890.1401897
  * Aral et al. [2009] S. Aral, L. Muchnik, and A. Sundararajan. 2009.  Distinguishing Influence-Based Contagion from Homophily-Driven Diffusion in Dynamic Networks.  _Proceedings of the National Academy of Sciences_ 106, 51 (Dec. 2009), 21544–21549.  https://doi.org/10.1073/pnas.0908800106
  * Asikainen et al. [2020] Aili Asikainen, Gerardo Iñiguez, Javier Ureña-Carrión, Kimmo Kaski, and Mikko Kivelä. 2020\.  Cumulative Effects of Triadic Closure and Homophily in Social Networks.  _Science Advances_ 6, 19 (May 2020), eaax7310.  https://doi.org/10.1126/sciadv.aax7310
  * Barrat et al. [2004] A. Barrat, M. Barthelemy, R. Pastor-Satorras, and A. Vespignani. 2004.  The Architecture of Complex Weighted Networks.  _Proceedings of the National Academy of Sciences_ 101, 11 (March 2004), 3747–3752.  https://doi.org/10.1073/pnas.0400087101
  * Benjamini et al. [2006] Yoav Benjamini, Abba M. Krieger, and Daniel Yekutieli. 2006\.  Adaptive Linear Step-up Procedures That Control the False Discovery Rate.  _Biometrika_ 93, 3 (Sept. 2006), 491–507.  https://doi.org/10.1093/biomet/93.3.491
  * Beuming et al. [2005] T. Beuming, L. Skrabanek, M. Y. Niv, P. Mukherjee, and H. Weinstein. 2005.  PDZBase: A Protein-Protein Interaction Database for PDZ-domains.  _Bioinformatics_ 21, 6 (March 2005), 827–828.  https://doi.org/10.1093/bioinformatics/bti098
  * Boguñá et al. [2021] Marián Boguñá, Ivan Bonamassa, Manlio De Domenico, Shlomo Havlin, Dmitri Krioukov, and M. Ángeles Serrano. 2021.  Network Geometry.  _Nature Reviews Physics_ 3, 2 (Feb. 2021), 114–135.  https://doi.org/10.1038/s42254-020-00264-4
  * Boguñá et al. [2020] Marián Boguñá, Dmitri Krioukov, Pedro Almagro, and M. Ángeles Serrano. 2020.  Small Worlds and Clustering in Spatial Networks.  _Physical Review Research_ 2, 2 (April 2020), 023040.  https://doi.org/10.1103/PhysRevResearch.2.023040
  * Chami et al. [2017] Goylette F. Chami, Sebastian E. Ahnert, Narcis B. Kabatereine, and Edridah M. Tukahebwa. 2017\.  Social Network Fragmentation and Community Health.  _Proceedings of the National Academy of Sciences_ 114, 36 (Sept. 2017), E7425–E7431.  https://doi.org/10.1073/pnas.1700166114
  * Chung et al. [2000] Seungwha Chung, Harbir Singh, and Kyungmook Lee. 2000\.  Complementarity, Status Similarity and Social Capital as Drivers of Alliance Formation.  _Strategic Management Journal_ 21 (2000), 1–22.  https://doi.org/10.1002/(SICI)1097-0266(200001)21:1<1::AID-SMJ63>3.0.CO;2-P
  * Coleman et al. [1957] James Coleman, Elihu Katz, and Herbert Mentzel. 1957\.  The Diffusion of an Innovation Among Physicians.  _Sociometry_ 20, 4 (1957), 253–270.
  * Collins et al. [2007] Sean R. Collins, Patrick Kemmeren, Xue-Chu Zhao, Jack F. Greenblatt, Forrest Spencer, Frank C.P. Holstege, Jonathan S. Weissman, and Nevan J. Krogan. 2007.  Toward a Comprehensive Atlas of the Physical Interactome of Saccharomyces Cerevisiae.  _Molecular & Cellular Proteomics_ 6, 3 (March 2007), 439–450.  https://doi.org/10.1074/mcp.M600381-MCP200
  * Coulomb et al. [2005] Stéphane Coulomb, Michel Bauer, Denis Bernard, and Marie-Claude Marsolier-Kergoat. 2005\.  Gene Essentiality and the Topology of Protein Interaction Networks.  _Proceedings of the Royal Society B: Biological Sciences_ 272, 1573 (Aug. 2005), 1721–1725.  https://doi.org/10.1098/rspb.2005.3128
  * Craig et al. [2017] Peter Craig, Srinivasa Vittal Katikireddi, Alastair Leyland, and Frank Popham. 2017\.  Natural Experiments: An Overview of Methods, Approaches, and Contributions to Public Health Intervention Research.  _Annual Review of Public Health_ 38, 1 (March 2017), 39–56.  https://doi.org/10.1146/annurev-publhealth-031816-044327
  * de Nooy [1999] Wouter de Nooy. 1999\.  A Literary Playground: Literary Criticism and Balance Theory.  _Poetics_ 26, 5-6 (Aug. 1999), 385–404.  https://doi.org/10.1016/S0304-422X(99)00009-1
  * Dehal and Boore [2005] Paramvir Dehal and Jeffrey L Boore. 2005.  Two Rounds of Whole Genome Duplication in the Ancestral Vertebrate.  _PLoS Biology_ 3, 10 (Sept. 2005), e314.  https://doi.org/10.1371/journal.pbio.0030314
  * Dopfer et al. [2016] Kurt Dopfer, Jason Potts, and Andreas Pyka. 2016.  Upward and Downward Complementarity: The Meso Core of Evolutionary Growth Theory.  _Journal of Evolutionary Economics_ 26, 4 (Oct. 2016), 753–763.  https://doi.org/10.1007/s00191-015-0434-4
  * Erdős and Rényi [1959] Paul Erdős and Alfred Rényi. 1959.  On Random Graphs I.  _Publicationes Mathematicae_ 6 (1959), 290–297.
  * Estrada [2006] Ernesto Estrada. 2006\.  Protein Bipartivity and Essentiality in the Yeast Protein-Protein Interaction Network.  _Journal of Proteome Research_ 5, 9 (Sept. 2006), 2177–2184.  https://doi.org/10.1021/pr060106e
  * Estrada and Rodríguez-Velázquez [2005] Ernesto Estrada and Juan A. Rodríguez-Velázquez. 2005\.  Spectral Measures of Bipartivity in Complex Networks.  _Physical Review E_ 72, 4 (Oct. 2005), 046105\.  https://doi.org/10.1103/PhysRevE.72.046105
  * Ewing et al. [2007] Rob M Ewing, Peter Chu, Fred Elisma, Li Hongyan, Paul Taylor, Shane Climie, Linda McBroom-Cerajewski, Mark D Robinson, Liam O’Connor, Michael Li, Rod Taylor, Moyez Dharsee, Yuen Ho, Adrian Heilbut, Lynda Moore, Shudong Zhang, Olga Ornatsky, Yury V Bukhman, Martin Ethier, Yinglun Sheng, Julian Vasilescu, Mohamed Abu-Farha, Jean-Philippe Lambert, Henry S Duwel, Ian I Stewart, Bonnie Kuehl, Kelly Hogue, Karen Colwill, Katharine Gladwish, Brenda Muskat, Robert Kinach, Adams Sally-Lin, Michael F Moran, Gregg B Morin, Thodoros Topaloglou, and Daniel Figeys. 2007.  Large-Scale Mapping of Human Protein–Protein Interactions by Mass Spectrometry.  _Molecular Systems Biology_ 3, 1 (Jan. 2007), 89.  https://doi.org/10.1038/msb4100134
  * Fire and Puzis [2016] Michael Fire and Rami Puzis. 2016.  Organization Mining Using Online Social Networks.  _Networks and Spatial Economics_ 16, 2 (June 2016), 545–578.  https://doi.org/10.1007/s11067-015-9288-4
  * Freeman et al. [1988] L Freeman, S Freeman, and A Michaelson. 1988.  On Human Social Intelligence.  _Journal of Social and Biological Systems_ 11, 4 (Oct. 1988), 415–425.  https://doi.org/10.1016/0140-1750(88)90080-2
  * Freeman et al. [1998] Linton C Freeman, Cynthia M Webster, and Deirdre M Kirke. 1998.  Exploring Social Structure Using Dynamic Three-Dimensional Color Images.  _Social Networks_ 20, 2 (April 1998), 109–118.  https://doi.org/10.1016/S0378-8733(97)00016-6
  * Gulati [1995] Ranjay Gulati. 1995\.  Social Structure and Alliance Formation Patterns: A Longitudinal Analysis.  _Administrative Science Quarterly_ 40, 4 (Dec. 1995), 619.  https://doi.org/10.2307/2393756
  * Hastie et al. [2008] Trevor Hastie, Robert Tibshirani, and Jerome Friedman. 2008\.  _The Elements of Statistical Learning_ (second ed.).  Springer.
  * Holme et al. [2003] Petter Holme, Fredrik Liljeros, Christofer R. Edling, and Beom Jun Kim. 2003.  Network Bipartivity.  _Physical Review E_ 68, 5 (Nov. 2003), 056107\.  https://doi.org/10.1103/PhysRevE.68.056107
  * Jia et al. [2021] Mingshan Jia, Bogdan Gabrys, and Katarzyna Musial. 2021\.  Measuring Quadrangle Formation in Complex Networks.  _IEEE Transactions on Network Science and Engineering_ 9, 5 (2021), 538–551.  https://doi.org/10.1109/TNSE.2021.3123735
  * Joshi-Tope [2004] G. Joshi-Tope. 2004\.  Reactome: A Knowledgebase of Biological Pathways.  _Nucleic Acids Research_ 33, Database issue (Dec. 2004), D428–D432.  https://doi.org/10.1093/nar/gki072
  * Kitsak [2020] Maksim Kitsak. 2020\.  Latent Geometry for Complementarity-Driven Networks.  _arXiv:2003.06665 [cond-mat, physics:physics]_ (March 2020).  arXiv:2003.06665 [cond-mat, physics:physics]
  * Kossinets and Watts [2009] Gueorgi Kossinets and D. J. Watts. 2009.  Origins of Homophily in an Evolving Social Network.  _Amer. J. Sociology_ 115, 2 (Sept. 2009), 405–450.  https://doi.org/10.1086/599247
  * Kovács et al. [2019] István A. Kovács, Katja Luck, Kerstin Spirohn, Yang Wang, Carl Pollis, Sadie Schlabach, Wenting Bian, Dae-Kyum Kim, Nishka Kishore, Tong Hao, Michael A. Calderwood, Marc Vidal, and Albert-László Barabási. 2019.  Network-Based Prediction of Protein Interactions.  _Nature Communications_ 10, 1 (Dec. 2019), 1240\.  https://doi.org/10.1038/s41467-019-09177-y
  * Krioukov [2016] Dmitri Krioukov. 2016\.  Clustering Implies Geometry in Networks.  _Physical Review Letters_ 116, 20 (May 2016), 208302.  https://doi.org/10.1103/PhysRevLett.116.208302
  * Lam et al. [2015] Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. 2015\.  Numba: A LLVM-based Python JIT Compiler. In _Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC - LLVM ’15_. ACM Press, Austin, Texas, 1–6.  https://doi.org/10.1145/2833157.2833162
  * Lehmann and Casella [1998] E. L. Lehmann and George Casella. 1998.  _Theory of Point Estimation_ (second ed.).  Springer, New York.
  * Lovász [2012] László Lovász. 2012\.  _Large Networks and Graph Limits_. Colloquium Publications, Vol. 60.  American Mathematical Society, Providence, Rhode Island.  https://doi.org/10.1090/coll/060
  * Maier and Brockmann [2017] Benjamin F. Maier and Dirk Brockmann. 2017.  Cover Time for Random Walks on Arbitrary Complex Networks.  _Physical Review E_ 96, 4 (Oct. 2017), 042307\.  https://doi.org/10.1103/PhysRevE.96.042307
  * Markey and Markey [2007] Patrick M. Markey and Charlotte N. Markey. 2007.  Romantic Ideals, Romantic Obtainment, and Relationship Experiences: The Complementarity of Interpersonal Traits among Romantic Partners.  _Journal of Social and Personal Relationships_ 24, 4 (Aug. 2007), 517–533.  https://doi.org/10.1177/0265407507079241
  * Marsden [1988] Peter V. Marsden. 1988\.  Homogeneity in Confiding Relations.  _Social Networks_ 10, 1 (March 1988), 57–76.  https://doi.org/10.1016/0378-8733(88)90010-X
  * Massa et al. [2009] Paolo Massa, Martino Salvetti, and Danilo Tomasoni. 2009\.  Bowling Alone and Trust Decline in Social Network Sites. In _2009 Eighth IEEE International Conference on Dependable, Autonomic and Secure Computing_. IEEE, Chengdu, China, 658–663.
  * Matta et al. [2011] Chérif F. Matta, Lou Massa, Anna V. Gubskaya, and Eva Knoll. 2011.  Can One Take the Logarithm or the Sine of a Dimensioned Quantity or a Unit? Dimensional Analysis Involving Transcendental Functions.  _Journal of Chemical Education_ 88, 1 (Jan. 2011), 67–70.  https://doi.org/10.1021/ed1000476
  * Mattsson et al. [2021] Carolina E. S. Mattsson, Frank W. Takes, Eelke M. Heemskerk, Cees Diks, Gert Buiten, Albert Faber, and Peter M. A. Sloot. 2021\.  Functional Structure in Production Networks.  _Frontiers in Big Data_ 4 (May 2021), 666712.  https://doi.org/10.3389/fdata.2021.666712
  * McAuley and Leskovec [2012] Julian McAuley and Jure Leskovec. 2012.  Learning to Discover Social Circles in Ego Networks. In _Advances in Neural Information Processing Systems_ , Vol. 25. Curran Associates, Inc., 1–9.
  * McPherson et al. [2001] J. M. McPherson, L. Smith-Lovin, and J. M. Cook. 2001\.  Birds of a Feather: Homophily in Social Networks.  _Annual Review of Sociology_ 27, 1 (Aug. 2001), 415–444.  https://doi.org/10.1146/annurev.soc.27.1.415
  * Milo et al. [2002] R. Milo, S. Shen-Orr, S. Itzkovitz, N. Kashtan, D. Chklovskii, and Uri Alon. 2002\.  Network Motifs: Simple Building Blocks of Complex Networks.  _Science_ 298, 5594 (Oct. 2002), 824–827.  https://doi.org/10.1126/science.298.5594.824
  * Newman [2010] M. E. J. Newman. 2010\.  _Networks: An Introduction_.  Oxford University Press, Oxford, New York.
  * Opsahl [2013] Tore Opsahl. 2013\.  Triadic Closure in Two-Mode Networks: Redefining the Global and Local Clustering Coefficients.  _Social Networks_ 35, 2 (May 2013), 159–167.  https://doi.org/10.1016/j.socnet.2011.07.001
  * Papadopoulos et al. [2015] Fragkiskos Papadopoulos, Rodrigo Aldecoa, and Dmitri Krioukov. 2015\.  Network Geometry Inference Using Common Neighbors.  _Physical Review E_ 92, 2 (Aug. 2015), 022807\.  https://doi.org/10.1103/PhysRevE.92.022807 arXiv:1502.05578
  * Peixoto [2020] Tiago P. Peixoto. 2020\.  The Netzschleuder Network Catalogue and Repository.  https://networks.skewed.de/.
  * Richardson et al. [2003] Matthew Richardson, Rakesh Agrawal, and Pedro Domingos. 2003\.  Trust Management for the Semantic Web. In _The Semantic Web - ISWC 2003_ _(Lecture Notes in Computer Science)_ , Dieter Fensel, Katia Sycara, and John Mylopoulos (Eds.). Springer, Berlin, Heidelberg, 351–368.  https://doi.org/10.1007/978-3-540-39718-2_23
  * Richters and Peixoto [2011] Oliver Richters and Tiago P. Peixoto. 2011.  Trust Transitivity in Social Networks.  _PLoS ONE_ 6, 4 (April 2011), e18384.  https://doi.org/10.1371/journal.pone.0018384
  * Rivera et al. [2010] Mark T. Rivera, Sara B. Soderstrom, and Brian Uzzi. 2010\.  Dynamics of Dyads in Social Networks: Assortative, Relational, and Proximity Mechanisms.  _Annual Review of Sociology_ 36, 1 (June 2010), 91–115.  https://doi.org/10.1146/annurev.soc.34.040507.134743
  * Rual et al. [2005] Jean-François Rual, Kavitha Venkatesan, Tong Hao, Tomoko Hirozane-Kishikawa, Amélie Dricot, Ning Li, Gabriel F. Berriz, Francis D. Gibbons, Matija Dreze, Nono Ayivi-Guedehoussou, Niels Klitgord, Christophe Simon, Mike Boxem, Stuart Milstein, Jennifer Rosenberg, Debra S. Goldberg, Lan V. Zhang, Sharyl L. Wong, Giovanni Franklin, Siming Li, Joanna S. Albala, Janghoo Lim, Carlene Fraughton, Estelle Llamosas, Sebiha Cevik, Camille Bex, Philippe Lamesch, Robert S. Sikorski, Jean Vandenhaute, Huda Y. Zoghbi, Alex Smolyar, Stephanie Bosak, Reynaldo Sequerra, Lynn Doucette-Stamm, Michael E. Cusick, David E. Hill, Frederick P. Roth, and Marc Vidal. 2005.  Towards a Proteome-Scale Map of the Human Protein–Protein Interaction Network.  _Nature_ 437, 7062 (Oct. 2005), 1173–1178.  https://doi.org/10.1038/nature04209
  * Shannon [1948] Claude Shannon. 1948\.  A Mathematical Theory of Communication.  _Bell System Technical Journal_ 27, 3 (1948), 379–423.
  * Shen-Orr et al. [2002] Shai S. Shen-Orr, Ron Milo, Shmoolik Mangan, and Uri Alon. 2002\.  Network Motifs in the Transcriptional Regulation Network of Escherichia Coli.  _Nature Genetics_ 31, 1 (May 2002), 64–68.  https://doi.org/10.1038/ng881
  * Squartini et al. [2015] Tiziano Squartini, Rossana Mastrandrea, and Diego Garlaschelli. 2015\.  Unbiased Sampling of Network Ensembles.  _New Journal of Physics_ 17, 2 (Feb. 2015), 023052.  https://doi.org/10.1088/1367-2630/17/2/023052
  * Srilatha and Manjula [2016] Pulipati Srilatha and Ramakrishnan Manjula. 2016.  Similarity Index Based Link Prediction Algorithms in Social Networks: A Survey.  _Journal of Telecommunications and Information Technology_ 2 (2016), 87–94.
  * Stelzl et al. [2005] Ulrich Stelzl, Uwe Worm, Maciej Lalowski, Christian Haenig, Felix H. Brembeck, Heike Goehler, Martin Stroedicke, Martina Zenkner, Anke Schoenherr, Susanne Koeppen, Jan Timm, Sascha Mintzlaff, Claudia Abraham, Nicole Bock, Silvia Kietzmann, Astrid Goedde, Engin Toksöz, Anja Droege, Sylvia Krobitsch, Bernhard Korn, Walter Birchmeier, Hans Lehrach, and Erich E. Wanker. 2005.  A Human Protein-Protein Interaction Network: A Resource for Annotating the Proteome.  _Cell_ 122, 6 (Sept. 2005), 957–968.  https://doi.org/10.1016/j.cell.2005.08.029
  * Talaga and Nowak [2020] Szymon Talaga and Andrzej Nowak. 2020.  Homophily as a Process Generating Social Networks: Insights from Social Distance Attachment Model.  _Journal of Artificial Societies and Social Simulation_ 23, 2 (2020), 6.  https://doi.org/10.18564/jasss.4252
  * Tian et al. [2021] Yu Tian, Sebastian Lautz, Alisdair O. G. Wallis, and Renaud Lambiotte. 2021.  Extracting Complements and Substitutes from Sales Data: A Network Perspective.  _EPJ Data Science_ 10, 1 (Dec. 2021), 45\.  https://doi.org/10.1140/epjds/s13688-021-00297-4
  * Tran et al. [2013] Ngoc Hieu Tran, Kwok Pui Choi, and Louxin Zhang. 2013\.  Counting Motifs in the Human Interactome.  _Nature Communications_ 4, 1 (Oct. 2013), 2241\.  https://doi.org/10.1038/ncomms3241
  * Vallarano et al. [2021] Nicolò Vallarano, Matteo Bruno, Emiliano Marchese, Giuseppe Trapani, Fabio Saracco, Giulio Cimini, Mario Zanon, and Tiziano Squartini. 2021.  Fast and Scalable Likelihood Maximization for Exponential Random Graph Models with Local Constraints.  _Scientific Reports_ 11, 1 (Dec. 2021), 15227\.  https://doi.org/10.1038/s41598-021-93830-4
  * van der Hofstad et al. [2018] Remco van der Hofstad, Johan S. H. van Leeuwaarden, and Clara Stegehuis. 2018.  Triadic Closure in Configuration Models with Unbounded Degree Fluctuations.  _Journal of Statistical Physics_ 173, 3-4 (Nov. 2018), 746–774.  https://doi.org/10.1007/s10955-018-1952-x
  * Watts and Strogatz [1998] D. J. Watts and S. H. Strogatz. 1998.  Collective Dynamics of ‘Small-World’ Networks.  _Nature_ 393, 6684 (1998), 440.  https://doi.org/10.1038/30918
  * Woese et al. [1990] Carl R Woese, Otto Kandler, and Mark Wheelis. 1990\.  Towards a Natural System of Organisms: Proposal for the Domains Archaea, Bacteria, and Eucarya.  _Proceedings of the National Academy of Sciences_ 87 (1990), 4576–4579.
  * Wolfe and Shields [1997] Kenneth H. Wolfe and Denis C. Shields. 1997.  Molecular Evidence for an Ancient Duplication of the Entire Yeast Genome.  _Nature_ 387, 6634 (June 1997), 708–713.  https://doi.org/10.1038/42711
  * Xie et al. [2016] Wen-Jie Xie, Ming-Xia Li, Zhi-Qiang Jiang, Qun-Zhao Tan, Boris Podobnik, Wei-Xing Zhou, and H. Eugene Stanley. 2016.  Skill Complementarity Enhances Heterophily in Collaboration Networks.  _Scientific Reports_ 6, 1 (May 2016), 1–9.  https://doi.org/10.1038/srep18727
  * Yin et al. [2019] Hao Yin, Austin R. Benson, and Jure Leskovec. 2019\.  The Local Closure Coefficient: A New Perspective On Network Clustering. In _Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining_. ACM, Melbourne VIC Australia, 303–311.  https://doi.org/10.1145/3289600.3290991
  * Zachary [1977] Wayne W. Zachary. 1977\.  An Information Flow Model for Conflict and Fission in Small Groups.  _Journal of Anthropological Research_ 33, 4 (1977), 452–473.  https://doi.org/10.1086/jar.33.4.3629752
  * Zhang et al. [2008] Peng Zhang, Jinliang Wang, Xiaojia Li, Menghui Li, Zengru Di, and Ying Fan. 2008\.  Clustering Coefficient and Community Structure of Bipartite Networks.  _Physica A: Statistical Mechanics and its Applications_ 387, 27 (Dec. 2008), 6869–6875.  https://doi.org/10.1016/j.physa.2008.09.006
  * Zitnik et al. [2019] Marinka Zitnik, Rok Sosič, Marcus W. Feldman, and Jure Leskovec. 2019.  Evolution of Resilience in Protein Interactomes across the Tree of Life.  _Proceedings of the National Academy of Sciences_ 116, 10 (March 2019), 4426–4433.  https://doi.org/10.1073/pnas.1818013116

### Supplementary Information

### Similarity and structural equivalence

Here we derive the relationship between similarity coefficient $s_{ij}$ and
$s_{i}$ and structural equivalence. First, we show that $s_{i}$ is a weighted
average of the edgewise coefficients $s_{ij}$’s for $j\in\mathcal{N}_{1}(i)$,
that is:

$s_{i}=\frac{4T_{i}}{t^{W}_{i}+t^{H}_{i}}=\frac{\sum_{j}\left(t^{W}_{ij}+t^{H}_{ij}\right)s_{ij}}{\sum_{j}t^{W}_{ij}+t^{H}_{ij}}$
(S1)

Note that Eq. (10) mplies that
$\left(t^{W}_{ij}+t^{H}_{ij}\right)s_{ij}=2T_{ij}$. Moreover, since each
triangle including $i$ is shared with two other neighbors we have that:

$\sum_{j\in\mathcal{N}_{1}(i)}\left(t^{W}_{ij}+t^{H}_{ij}\right)s_{ij}=\sum_{j\in\mathcal{N}_{1}(i)}2T_{ij}=4T_{i}$
(S2)

On the other hand, $t^{W}_{ij}+t^{H}_{ij}$ is the number of 2-paths traversing
the $(i,j)$ edges so it can be written as
$t^{W}_{ij}+t^{H}_{ij}=d_{i}+d_{j}-2$. Hence, it is easy to see that:

$\begin{split}\sum_{j\in\mathcal{N}_{1}(i)}t^{W}_{ij}+t^{H}_{ij}&=\sum_{j\in\mathcal{N}_{1}(i)}(d_{i}+d_{j}-2)\\\
&=d_{i}(d_{i}-1)+\sum_{j\in\mathcal{N}_{1}(i)}(d_{j}-1)\\\
&=t^{W}_{i}+t^{H}_{i}\end{split}$ (S3)

Finally, substituting (S2) and (S3) into (S1) we confirm the desired equality.

Now, we use a common definition of structural equivalence in terms of Sørenson
Index (normalized Hamming similarity) and note its direct connection to our
notion of edgewise structural similarity $s_{ij}$:

$H_{ij}=\frac{2n_{ij}}{d_{i}+d_{j}}=\frac{2T_{ij}}{d_{i}+d_{j}}=s_{ij}\frac{d_{i}+d_{j}-2}{d_{i}+d_{j}}$
(S4)

The above implies that $H_{ij}<s_{ij}$ for all $(i,j)$ edges for which
$s_{ij}$ is defined. And since we established that $s_{i}$ is a weighted
average of $s_{ij}$’s with $j\in\mathcal{N}_{1}(i)$ we have that:

$\min_{j}H_{ij}<\min_{j}s_{ij}\leq
s_{i}\leq\max_{j}s_{ij}=\max_{j}\left(H_{ij}\frac{d_{i}+d_{j}}{d_{i}+d_{j}-2}\right)$
(S5)

Note that for large values of $d_{i}+d_{j}$ the above is approximately
equivalent to:

$\min_{j}H_{ij}<s_{i}\leq\max_{j}H_{ij}$ (S6)

In other words, we showed that the similarity coefficient of a node $i$ is
approximately bounded between minimum and maximum structural equivalence
(Sørenson Index) between itself and any of its neighbors.

### Complementarity and structural equivalence

Here we derive the relationship between complementarity coefficients $c_{ij}$
and $c_{i}$ and structural equivalence. We start by showing that $c_{i}$ is a
weighted average of the edgewise coefficients $c_{ij}$’s for
$j\in\mathcal{N}_{1}(i)$, that is:

$c_{i}=\frac{4Q_{ij}}{q^{W}_{i}+q^{H}_{i}}=\frac{\sum_{j}\left(q^{W}_{ij}+q^{H}_{ij}\right)c_{ij}}{\sum_{j}q^{W}_{ij}+q^{H}_{ij}}$
(S7)

Using Eq. (12) we can write
$2Q_{ij}=\left(q^{W}_{ij}+q^{H}_{ij}\right)c_{ij}$. Moreover, each strong
quadrangle including a node $i$ is shared with exactly two other neighbors.
Hence, we have that:

$\sum_{j\in\mathcal{N}_{1}}\left(q^{W}_{ij}+q^{H}_{ij}\right)c_{ij}=\sum_{j\in\mathcal{N}_{1}(i)}2Q_{ij}=4Q_{i}$
(S8)

Next, note that each $3$-path starting at an $(i,j)$ edge defines a unique
ordered quadruple of the form $(i,j,k,l)$ or $(j,i,k,l)$. The first form is
counted as a head quadruple of the node $i$ and a wedge quadruple of the node
$j$ and in the second case the order is reversed. And since
$q^{W}_{ij}+q^{H}_{ij}$ is the number of $3$-paths starting at the $(i,j)$
edge it must hold that:

$\sum_{j\in\mathcal{N}_{1}(i)}\left(q^{W}_{ij}+q^{H}_{ij}\right)=q^{W}_{i}+q^{H}_{i}$
(S9)

Finally, note that (S8) and (S9) jointly mean that (S7) must be true. As a
result, for $j\in\mathcal{N}_{1}(i)$ we have that:

$\min_{j}c_{ij}\leq c_{i}\leq\max_{j}c_{ij}$ (S10)

Now, in order to derive the connection between complementarity coefficients
and structural equivalence we need first to introduce one additional quantity.
For a connected triple $(k,i,j)$ we define Asymmetric Excess Sørenson Index:

$H_{kj|i}=\frac{n_{jk}-1}{d_{k}-1-a_{jk}}$ (S11)

which measures how many of the connections of $k$ are also shared by $j$ while
disregarding edges $(i,k)$, $(i,j)$ and $(j,k)$.

Next, we also need to use the notion of weak quadrangles allowing for any
number of chordal edges. Let $W_{ij}\geq Q_{ij}$ be the number of quadrangles
with any number of chords incident to the $(i,j)$ edge. We also define weak
edgewise complementarity to be $h_{ij}=W_{ij}/(q^{W}_{ij}+q^{H}_{ij})\geq
c_{ij}$. It is easy to see that:

$W_{ij}=\sum_{k\in\mathcal{N}_{1}(i)-\\{j\\}}n_{jk}-1$ (S12)

On the other hand, the number of $3$-paths starting at the $(i,j)$ edge is:

$\begin{split}q^{W}_{ij}+q^{H}_{ij}&=\sum_{k\in\mathcal{N}_{1}(i)-\\{j\\}}(d_{k}-1)+\sum_{l\in\mathcal{N}_{1}(j)-\\{i\\}}(d_{l}-1)-2n_{ij}\\\
&=\sum_{k\in\mathcal{N}_{1}(i)-\\{j\\}}(d_{k}-1-a_{jk})+\sum_{l\in\mathcal{N}_{1}(j)-\\{i\\}}(d_{l}-1-a_{il})\end{split}$
(S13)

since $q^{W}_{ij}$ is the number of $(j,i,k,l)$ and $q^{H}_{ij}$ of
$(i,j,k,l)$ quadruples. The second equality comes from the fact that
$n_{ij}=\sum_{k}a_{jk}=\sum_{l}a_{il}$. Now, we can use (13), (S12) and (S13)
to rewrite the weak edgewise complementarity as:

$h_{ij}=\frac{\sum_{k}(d_{k}-1-a_{jk})H_{kj|i}+\sum_{l}(d_{l}-1-a_{il})H_{li|j}}{\sum_{k}(d_{k}-1-a_{jk})+\sum_{l}(d_{l}-1-a_{il})}$
(S14)

As a result, for $k\in\mathcal{N}_{1}(i)-\\{j\\}$ and
$l\in\mathcal{N}_{1}(j)-\\{i\\}$ we have that:

$\min_{k,l}(H_{kj|i},H_{li|j})\leq h_{ij}\leq\max_{k,l}(H_{kj|i},H_{li|j})$
(S15)

Using (S10) we can write:

$\min_{j,k,l}(H_{kj|i},H_{li|j})\leq h_{i}\leq\max_{j,k,l}(H_{kj|i},H_{li|j})$
(S16)

Finally, since by definition $c_{ij}\leq h_{ij}$ this implies:

$0\leq c_{ij}\leq\max_{k,l}(H_{kj|i},H_{li|j})$ (S17)

as well as:

$0\leq c_{i}\leq\max_{j,k,l}\left(H_{kj|i},H_{li|j}\right)$ (S18)

In other words, we just showed that $c_{i}$ is bounded from above by the
maximum Asymmetric Excess Sørenson Index between any two of its neighbors or
itself and any neighbor of its neighbors. Moreover, in the weak case we also
have a lower bound of the same nature. We leave a more detailed analysis of
the notion of weak complementarity for future work.

### Structural coefficients and PathCensus

## Formulas and algorithm

Edge-level counts of triples, quadruples, triangles and quadrangles are
computed with the algorithm S1. Node and global counts can be obtained by
aggregating edge counts. The rules of aggregation are summarized in Table S1.
Table S2 presents detailed formulas for all structural coefficients expressed
in terms of the aggregated counts.

Table S1: Formulas for aggregating from edge to node and global counts  | Counting level
---|---
| Edge | Node | Global
Paths |  |  |
Wedge triples | $t^{W}_{ij}$ | $t^{W}_{i}=\sum_{j}t^{W}_{ij}$ | $t^{W}=\frac{1}{2}\sum_{i,j}t^{W}_{ij}$
Head triples | $t^{H}_{ij}$ | $t^{H}_{i}=\sum_{j}t^{H}_{ij}$ | $t^{H}=\frac{1}{2}\sum_{i,j}t^{H}_{ij}$
Wedge quadruples | $q^{W}_{ij}$ | $q^{W}_{i}=\sum_{j}q^{W}_{ij}$ | $q^{W}=\frac{1}{2}\sum_{i,j}q^{W}_{ij}$
Head quadruples | $q^{H}_{ij}$ | $q^{H}_{i}=\sum_{j}q^{H}_{ij}$ | $q^{H}=\frac{1}{2}\sum_{i,j}q^{H}_{ij}$
Cycles |  |  |
Triangles | $T_{ij}$ | $T_{i}=\frac{1}{2}\sum_{j}T_{ij}$ | $T=\frac{1}{6}\sum_{i,j}T_{ij}$
Quadrangles | $Q_{ij}$ | $Q_{i}=\frac{1}{2}\sum_{j}Q_{ij}$ | $Q=\frac{1}{8}\sum_{i,j}Q_{ij}$
Table S2: Formulas for structural coefficients based on path and cycle counts

|  | Relational principle
---|---|---
Level | Coefficient | Similarity | Complementarity
Edges | Structural | $s_{ij}=\frac{2T_{ij}}{t^{W}_{ij}+t^{H}_{ij}}$ | $c_{ij}=\frac{2Q_{ij}}{q^{W}_{ij}+q^{H}_{ij}}$
Nodes | Structural | $s_{i}=\frac{4T_{i}}{t^{W}_{i}+t^{H}_{i}}$ | $c_{i}=\frac{4Q_{i}}{q^{W}_{i}+q^{H}_{i}}$
| Clustering | $s^{W}_{i}=\frac{2T_{i}}{t^{W}_{i}}$ | $c^{W}_{i}=\frac{2Q_{i}}{q^{W}_{i}}$
| Closure | $s^{H}_{i}=\frac{2T_{i}}{t^{H}_{i}}$ | $c^{H}_{i}=\frac{2Q_{i}}{q^{H}_{i}}$
Global1 | Structural | $s=\frac{6T}{t^{W}+t^{H}}$ | $c=\frac{8Q}{q^{W}+q^{H}}$
| Clustering | $s^{W}=\frac{3T}{t^{W}}$ | $c^{W}=\frac{4Q}{q^{W}}$
| Closure | $s^{H}=\frac{3T}{t^{H}}$ | $c^{H}=\frac{4Q}{q^{H}}$

  * •

1All global measures are equivalent.

Algorithm S1 PathCensus algorithm. It takes an undirected graph $G=(V,E)$ with
$|V|=n$ and $|E|=m$ as input and returns an array of edgewise counts of wedge
and head triples and quadruples as well as triangles and (strong) quadrangles.
For better performance $E$ can be defined (without loss of generality) to
ensure that for all edges $(i,j)$ it holds that $d_{i}\leq d_{j}$.

1:Initialize empty $C$ $\triangleright$ $m\times 8$ array for storing path
counts

2:Initialize $R$ such that $R_{i}=0\quad\forall i\in V$ $\triangleright$
$n\times 1$ array for keeping track of node roles

3:Let $D$ be the degree sequence of $G$ $\triangleright$ $n\times 1$ array

4:Initialize $u=0$

5:for $e=(i,j)\in E$ do $\triangleright$ the loop may be parallelized

6: Set $u=u+1$

7: Initialize $T_{ij},t^{W}_{ij},t^{H}_{ij}=0$ $\triangleright$ counts of
triangles and wedge and head triples

8: Initialize $Q_{ij},q^{W}_{ij},q^{H}_{ij}=0$ $\triangleright$ counts of
strong quadrangles and wedge and head quadruples

9: Initialize $\text{Star}_{i},\text{Star}_{j},\text{Tri}_{ij}=\emptyset$
$\triangleright$ Empty sets for keeping track of nodes with different roles

10: for $(k\neq j)\in\mathcal{N}_{1}(i)$ do

11: Add $k$ to $\text{Star}_{i}$ and set $R_{k}=1$

12: Set $t^{W}_{ij}=t^{W}_{ij}+1$

13: for $(k\neq i)\in\mathcal{N}_{1}(j)$ do

14: if $R_{k}=1$ then

15: $T_{ij}=T_{ij}+1$

16: Remove $k$ from $\text{Star}_{i}$, add $k$ to $\text{Tri}_{ij}$ and set
$R_{k}=3$

17: else

18: Add $k$ to $\text{Star}_{j}$ and set $R_{k}=2$

19: $t^{H}_{ij}=t^{H}_{ij}+1$

20: for $k\in\text{Star}_{i}$ do $\triangleright$ This internal nested loop
determines computational complexity

21: for $(l\neq i)\in\mathcal{N}_{1}(k)$ do

22: if $R_{l}=2$ then

23: $Q_{ij}=Q_{ij}+1$

24: for $k\in\text{Star}_{i}$ do

25: Set $q^{W}_{ij}=q^{W}_{ij}+D_{k}-1$ and $R_{k}=0$

26: for $k\in\text{Star}_{j}$ do

27: Set $q^{H}_{ij}=q^{H}_{ij}+D_{k}-1$ and $R_{k}=0$

28: for $k\in\text{Tri}_{ij}$ do

29: Set $q^{W}_{ij}=q^{W}_{ij}+D_{k}-2$

30: Set $q^{H}_{ij}=q^{H}_{ij}+D_{k}-2$

31: Set $R_{k}=0$

32: Set
$C_{u}=\left(T_{ij},t^{W}_{ij},t^{H}_{ij},Q_{ij},q^{W}_{ij},q^{H}_{ij}\right)$
$\triangleright$ Set $u$-th row of $C$

33:return $C$

## Calculating counts for reversed edges

Note that in our implementation $t^{W}_{ij}$ counts the number of $(k,i,j)$
and $t^{H}_{ij}$ tracks $(i,j,k)$ triples. Thus, we have that
$t^{W}_{ij}=t^{H}_{ji}$. Similarly, $q^{W}_{ij}$ counts $(j,i,k,l)$ and
$q^{H}_{ij}$ $(i,j,k,l)$ quadruples, so again we have that
$q^{W}_{ij}=q^{H}_{ji}$. On the other hand, counts of triangles and
quadrangles are symmetric. As a result, for the purpose of counting we can
assume that all edges are of the form $i<j$ and still be able to count
everything correctly. In other words there is no need to consider each
undirected edge twice.

## Computational complexity

It is clear from the structure of the three nested loops that the asymptotic
worst-case computational complexity of both algorithms is
$O(m\Delta{}Sd_{\text{max}})$ where $m$ is the number of edges, $\Delta{}S$ is
the maximum size of a $\text{Star}_{i}$ set (see Algorithm S1) and
$d_{\text{max}}$ is the maximum node degree. This agrees with the analysis
presented by the authors of the more general graphlet counting method [2],
which inspired our PathCensus algorithm. However, in practice the runtime can
be reduced by enforcing that edges are defined to satisfy the condition
$d_{i}\leq d_{j}$ (note that this can always be done without loss of
generality). The impact of this optimization can be quite significant for
networks with highly heterogeneous degree distributions. For instance, in the
case of the PGP web of trust network [54] ($n=39796,\langle
d_{i}\rangle=9.91,d_{\text{max}}=1696$) it yields almost 4 times shorter
runtime on average.

### Degree correlations in configuration model

Figure S1: Correlations of clustering, closure and structural coefficients
with node degrees in configuration model ensembles based on degree sequences
from 28 real-world social and biological networks (see Section: Network
datasets). Null distributions of the coefficients were approximated based on
100 samples from Undirected Binary Configuration Model (UBCM). The plots show
values averaged for different node degrees in logarithmic bins (base 2).

### Structural diversity analysis

Here we provide additional details for the corresponding analysis in the Main
Text (Section: Structural diversity across the tree of life). We present
results for three different choices of significance level,
$\alpha=0.01,0.05,0.10$ used for detecting nodes with high structural
similarity and complementarity. We show that qualitative results are stable
for all values of $\alpha$, even though quantitative details change in some
cases.

Figure S2:  General characteristic of the structure of interactomes in
different domains/groups. Apart from some minor details the results for all
values of $\alpha$ are the same.

## Linear model stability and diagnostics

We described the relationship between structural diversity,
$y=\mathbb{S}_{\alpha}(G)$, defined in Eq. (11) in the Main Text, and
interactome size $n$ (number of proteins) using a transformed linear model of
the form:

$\eta(\hat{y})=c+\gamma{}\log{n}$ (S19)

where $\eta(x)=x/(1-x)$ is the logit transformation. This parametric form
ensured model predictions bounded in $(0,1)$, which was necessary as the
structural diversity index ranges from $0$ to $1$. On the other hand, since
the logit transformation is not defined for $0$’s and $1$’s we had to drop
some part of the observations, namely, 119, 94 and 88 cases for
$\alpha=0.01,0.05,0.10$ respectively. These observations corresponded almost
exclusively to organisms with small interactomes as indicated by small average
numbers of nodes ($35.07$, $30.98$ and $28.15$) as compared to the overall
average of $544.06$ nodes. Moreover, all of them were dropped because of
$\mathbb{S}_{\alpha}(G)=0$, which is consistent with the hypothesis that less
complex organisms tend to have less structurally diverse interactomes.

As evident in Fig. S3 the qualitative trend is the same for all values of
$\alpha$. However, the goodness-of-fit of the model is highest for
$\alpha=0.01$. This is not surprising. Higher values of $\alpha$ correspond to
higher type I error rates, meaning that the estimated fractions of nodes with
significantly high values of $s_{i}$ and $c_{i}$ are more noisy. Table S3
presents estimated parameters and other numerical details.

Moreover, since the accuracy of interactome networks may depend on the extent
to which a given species has been studied, we also fitted extended models
including the logarithm of the number of publications about a given species as
the second predictor. This enabled a partial control for possible biases
induced by differences in terms of the incompleteness of the data available
for more and less frequently studied organisms. As Table S3 shows, the effects
of publication count ($b$) were insignificant in all cases.

Figure S3:  Model fit and residual diagnostics for $\alpha=0.01,0.05,0.10$. In
all cases the qualitative trend is similar but $R^{2}$ drops for higher values
of $\alpha$. Moreover, in all cases residuals are approximately normal apart
from larger fluctuations in the region of high fitted values. This is an
effect of the apparent bifurcation of the conditional distribution of
structural diversity index for species with large interactomes discussed in
the Main Text.  Table S3: Estimated parameters of the linear models1

|  $\alpha=0.01$ $(N=1721)$ |  $\alpha=0.05$ $(N=1746)$ |  $\alpha=0.10$ $(N=1752)$
---|---|---|---
| Value | SE | $z$ | $p$ |  | Value | SE | $z$ | $p$ |  | Value | SE | $z$ | $p$ |
$c$ | -3.562 | 0.075 | -47.476 | ¡ 0.001 |  | -2.595 | 0.133 | -19.477 | ¡ 0.001 |  | -2.139 | 0.164 | -13.048 | ¡ 0.001 |
$\gamma$ | 0.481 | 0.015 | 32.256 | ¡ 0.001 |  | 0.353 | 0.023 | 15.299 | ¡ 0.001 |  | 0.292 | 0.027 | 10.817 | ¡ 0.001 |
| R2 = 0.290, F(1719,1) = 1040, p ¡ 0.001 |  | R2 = 0.188, F(1744,1) = 234, p ¡ 0.001 |  | R2 = 0.290, F(1750,1) = 117, p ¡ 0.001 |
| Skew = -0.296, Kurtosis = 3.728 (residuals) |  | Skew = -0.134, Kurtosis = 3.135 (residuals) |  | Skew = -0.129, Kurtosis = 3.234 (residuals) |
| Models accounting for publication count ($b$) |  |  |
|  $\alpha=0.01$ $(N=1662)$ |  $\alpha=0.05$ $(N=1685)$ |  $\alpha=0.10$ $(N=1752)$
| Value | SE | $z$ | $p$ |  | Value | SE | $z$ | $p$ |  | Value | SE | $z$ | $p$ |
$c$ | -3.563 | 0.079 | -44.918 | ¡ 0.001 |  | -2.591 | 0.143 | -18.175 | ¡ 0.001 |  | -2.129 | 0.172 | -12.369 | ¡ 0.001 |
$\gamma$ | 0.481 | 0.017 | 28.633 | ¡ 0.001 |  | 0.353 | 0.026 | 13.730 | ¡ 0.001 |  | 0.290 | 0.029 | 9.971 | ¡ 0.001 |
$b$ | -0.0003 | 0.011 | -0.026 | 0.979 |  | 0.0014 | 0.009 | -0.155 | 0.876 |  | 0.0005 | 0.009 | 0.062 | 0.951 |

  * •

1Standard errors robust to cluster correlation (within taxa) were used.

### Network datasets

All network datasets were downloaded from the Netzschleuder repository [52].
In all analyses only largest connected components were used and networks were
simplified by removing multilinks and self-loops. Moreover, in the case of
directed or weighted networks edge directions and weights were ignored.

Individual network datasets are described below and their unique names within
the repository are provided in the following subsection headings. Each dataset
can be accessed via a generic link of the form: networks.skewed.de/net/<name>
where <name> is a placeholder which should be substituted with the name of a
specific dataset.

Below we list datasets in groups corresponding to the three empirical analyses
presented in the Main Text. Each section ends with a table with most important
descriptive statistics for all networks. The statistics were calculated for
the largest connected component.

## Networks used in “Structural coefficients in real networks”

##### Within-organization Facebook friendships (facebook_organizations)

Six undirected and unweighted networks of friendships among users on Facebook
who indicated employment at one of the target corporations (S1, S2, M1, M2,
L1, L2) [25]. Companies range in size from small to large. Only edges between
employees at the same company are included in a given snapshot.

##### Maier Facebook friends (facebook_friends)

A small anonymized Facebook ego network (undirected and unweighted), from
April 2014 [40]. Nodes are Facebook profiles, and an edge exists if the two
profiles are “friends” on Facebook.

##### Facebook ego-network (ego_social)

The network is a combination of $10$ ego-nets sampled from Facebook [46]. The
network is undirected and unweighted.

##### Zachary Karate Club (karate)

Undirected and unweighted network of friendships among members of a university
karate club [72]. We used the corrected version with 78 instead of 77 edges.

##### ANU Residence Hall network (residence_hall)

A network of friendships among students living in a residence hall at
Australian National University [27]. The original network is directed and
weighted with edges indicating that resident $i$ named resident $j$ as a
friend, and weight indicating the level of friendship: 5 (best friend), 4
(close friend), 3 (friend), 2, 1.

##### Windsurfers network (windsurfers)

A network of interpersonal contacts among windsurfers in southern California
during the Fall of 1986 [26]. The original network is weighted with weights
indicating the perception of social affiliations majored by the tasks in which
each individual was asked to sort cards with other surfer’s name in the order
of closeness.

##### Dutch literacy criticism (dutch_criticism)

A network of criticisms among Dutch literary authors in 1976 [18]. The
directed edge $(i,j)$ denotes that an author $i$ passed judgment on author
$j$’s work in an interview or review. The original network is also signed and
have positive and negative edges (representing positive and negative
judgements). The edge signs were ignored in our analyses.

##### Advogato trust network (advogato)

A network of trust relationships among users on Advogato, an online community
of open source software developers [43]. Edge directions indicate that node
$i$ trusts node $j$, and edge weight denotes one of four increasing levels of
declared trust from $i$ to $j$: observer (0.4), apprentice (0.6), journeyer
(0.8), and master (1.0).

##### Epinions trust network (epinions_trust)

A who-trusts-whom social network of the general consumer review site
Epinions.com [53]. Members can decide whether to “trust” each other. These
trust relationships are combined with review ratings to determine which
reviews are shown to the user.

##### PGP web of trust (pgp_strong)

Strongly connected component of the Pretty-Good-Privacy (PGP) web of trust
among users, circa November 2009 [54].

##### Physician trust network (physician_trust)

A network of trust relationships among physicians in four midwestern (USA)
cities in 1966 [14]. Edge directions indicate that node $i$ trusts or asks for
advice from node $j$. Each of the four components represent the network within
a given city. We analyzed four (disconnected) components corresponding to
different cities as separate networks.

##### E. coli transcription network (ecoli_transcription)

Directed network of operons and their pairwise interactions, via transcription
factor-based regulation, within the bacteria Escherichia coli [58]. In our
analyses we used v1.1 version and did not distinguish between different
regulation types.

##### Yeast transcription network (yeast_transcription)

Directed network of operons and their pairwise interactions, via transcription
factor-based regulation, within the yeast Saccharomyces cerevisiae [48]. We
did not distinguish between different regulation types.

##### Collins yeast interactome (collins_yeast)

Undirected and unweighted network of protein-protein interactions in
Saccharomyces cerevisiae (budding yeast), measured by co-complex associations
identified by high-throughput affinity purification and mass spectrometry
(AP/MS) [15].

##### Coulomb yeast interactome (interactome_yeast)

An undirected and unweighted network of protein-protein binding interactions
among yeast proteins [16]. Nodes represent proteins found in yeast
(Saccharomyces cerevisiae) and an edge represents a binding interaction
between two proteins.

##### Figeys human interactome (interactome_figeys)

A directed unweighted network of human proteins and their binding interactions
[24]. Nodes represent proteins and an edge represents an interaction between
two proteins, as inferred using a mass spectrometry-based approach.

##### PDZ-domain interactome (interactome_pdz)

An undirected and unweighted network of PDZ-domain-mediated protein-protein
binding interactions, extracted from the PDZBase database [9]. Nodes represent
proteins and an edge represents a binding interaction between two proteins.

##### Joshi-Tope human protein interactome (reactome)

An undirected and unweighted network of human proteins and their binding
interactions, extracted from Reactome project [32]. Nodes represent proteins
and an edge represents a binding interaction between two proteins.

##### Stelzl human interactome (interactome_stelzl)

A directed unweighted network of human proteins and their binding interactions
[61]. Nodes represent proteins and an edge represents an interaction between
two proteins, as inferred via high-throughput Y2H experiments using bait and
prey methodology.

##### Vidal human interactome (interactome_vidal)

An undirected and unweighted network of human proteins and their binding
interactions [56]. Nodes represent proteins and an edge represents a binding
interaction between two proteins, as tested using a high-throughput yeast two-
hybrid (Y2H) system.

Table S4: Descriptive statistics ($N=28$)

|  |  | $s$ | $c$ | $n$ | $S$ | $\rho$ | $\langle{d_{i}}\rangle$ | $\sigma_{d_{i}}$ | $d_{\text{max}}$
---|---|---|---|---|---|---|---|---|---|---
domain | dataset | network |  |  |  |  |  |  |  |
biological | collins_yeast |  | 0.62 | 0.01 | 1004 | 0.62 | 0.02 | 16.57 | 1.12 | 127
| ecoli_transcription | v1.1 | 0.02 | 0.05 | 328 | 0.78 | 0.01 | 2.78 | 1.86 | 72
| interactome_figeys |  | 0.01 | 0.14 | 2217 | 0.99 | 0.00 | 5.79 | 2.95 | 314
| interactome_pdz |  | 0.00 | 0.21 | 161 | 0.76 | 0.02 | 2.60 | 1.12 | 21
| interactome_stelzl |  | 0.01 | 0.12 | 1615 | 0.95 | 0.00 | 3.85 | 1.85 | 95
| interactome_vidal |  | 0.04 | 0.03 | 2783 | 0.89 | 0.00 | 4.32 | 1.63 | 129
| interactome_yeast |  | 0.05 | 0.01 | 1458 | 0.78 | 0.00 | 2.67 | 1.29 | 56
| reactome |  | 0.61 | 0.05 | 5973 | 0.94 | 0.01 | 48.81 | 1.39 | 855
| yeast_transcription |  | 0.02 | 0.19 | 664 | 0.72 | 0.00 | 3.21 | 1.79 | 71
social | advogato |  | 0.09 | 0.02 | 5042 | 0.77 | 0.00 | 15.56 | 2.07 | 803
| dutch_criticism |  | 0.16 | 0.22 | 35 | 1.00 | 0.13 | 4.57 | 0.65 | 12
| ego_social | facebook_combined | 0.52 | 0.02 | 4039 | 1.00 | 0.01 | 43.69 | 1.20 | 1045
| epinions_trust |  | 0.07 | 0.02 | 75877 | 1.00 | 0.00 | 10.69 | 4.02 | 3044
| facebook_friends |  | 0.51 | 0.02 | 329 | 0.91 | 0.04 | 11.88 | 0.92 | 63
| facebook_organizations | L1 | 0.26 | 0.04 | 5793 | 1.00 | 0.00 | 10.62 | 1.73 | 320
|  | L2 | 0.22 | 0.02 | 5524 | 1.00 | 0.01 | 34.11 | 0.93 | 417
|  | M1 | 0.26 | 0.03 | 1429 | 1.00 | 0.02 | 27.09 | 1.06 | 339
|  | M2 | 0.23 | 0.02 | 3862 | 1.00 | 0.01 | 45.22 | 0.65 | 328
|  | S1 | 0.29 | 0.03 | 320 | 1.00 | 0.05 | 14.81 | 0.96 | 113
|  | S2 | 0.33 | 0.03 | 165 | 1.00 | 0.05 | 8.80 | 0.95 | 63
| karate | 78 | 0.26 | 0.06 | 34 | 1.00 | 0.14 | 4.59 | 0.83 | 17
| pgp_strong |  | 0.25 | 0.01 | 39796 | 1.00 | 0.00 | 9.91 | 2.46 | 1696
| physician_trust | 1 | 0.17 | 0.05 | 117 | 1.00 | 0.07 | 7.95 | 0.50 | 26
|  | 2 | 0.28 | 0.06 | 48 | 1.00 | 0.16 | 7.46 | 0.62 | 28
|  | 3 | 0.32 | 0.08 | 41 | 1.00 | 0.17 | 6.93 | 0.42 | 15
|  | 4 | 0.42 | 0.07 | 35 | 1.00 | 0.23 | 7.83 | 0.48 | 15
| residence_hall |  | 0.30 | 0.04 | 217 | 1.00 | 0.08 | 16.95 | 0.46 | 56
| windsurfers |  | 0.56 | 0.03 | 43 | 1.00 | 0.37 | 15.63 | 0.42 | 31

  * •

$s$ \- global similarity (clustering)

  * •

$c$ \- global complementarity

  * •

$n$ \- number of nodes in the giant component

  * •

$S$ \- relative size of the giant component

  * •

$\rho$ \- edge density

  * •

$\langle{d_{i}}\rangle$ \- average node degree

  * •

$\sigma_{d_{i}}$ \- coefficient of variation of node degrees

  * •

$d_{\text{max}}$ \- maximum node degree

## Networks used in “Similarity and complementarity in social relations”

##### Ugandan village networks (ugandan_village)

The dataset consists of unweighted and undirected networks of friendship and
health advice relations between households in 17 rural villages bordering Lake
Victoria in Mayuge District, Uganda. It has been originally studied in Ref.
[12]. Relations were measured using the name generator approach in which a
representative of each household was asked to indicate up to 10 persons
considered friends or trustworthy in regard to health issues. Resulting ties
were symmetrized.

Table S5: Descriptive statistics ($N=34$)

|  |  | $s$ | $c$ | $n$ | $S$ | $\rho$ | $\langle{d_{i}}\rangle$ | $\sigma_{d_{i}}$ | $d_{\text{max}}$
---|---|---|---|---|---|---|---|---|---|---
domain | dataset | network |  |  |  |  |  |  |  |
social | ugandan_village | friendship-1 | 0.06 | 0.03 | 202 | 1.00 | 0.03 | 5.42 | 0.72 | 32
|  | friendship-2 | 0.11 | 0.05 | 181 | 0.99 | 0.04 | 7.60 | 0.77 | 44
|  | friendship-3 | 0.13 | 0.06 | 192 | 1.00 | 0.06 | 11.04 | 0.74 | 53
|  | friendship-4 | 0.09 | 0.05 | 320 | 1.00 | 0.04 | 12.97 | 0.66 | 50
|  | friendship-5 | 0.12 | 0.05 | 184 | 1.00 | 0.04 | 7.83 | 0.69 | 30
|  | friendship-6 | 0.14 | 0.07 | 139 | 1.00 | 0.07 | 9.09 | 0.68 | 42
|  | friendship-7 | 0.17 | 0.09 | 121 | 1.00 | 0.11 | 12.73 | 0.52 | 32
|  | friendship-8 | 0.06 | 0.04 | 369 | 1.00 | 0.03 | 9.50 | 0.70 | 58
|  | friendship-9 | 0.16 | 0.06 | 178 | 1.00 | 0.07 | 12.02 | 0.78 | 80
|  | friendship-10 | 0.10 | 0.07 | 207 | 1.00 | 0.05 | 10.55 | 0.64 | 44
|  | friendship-11 | 0.09 | 0.04 | 250 | 1.00 | 0.03 | 8.50 | 0.70 | 44
|  | friendship-12 | 0.08 | 0.05 | 229 | 1.00 | 0.03 | 7.62 | 0.86 | 58
|  | friendship-13 | 0.10 | 0.06 | 183 | 1.00 | 0.05 | 8.84 | 0.68 | 34
|  | friendship-14 | 0.15 | 0.06 | 124 | 1.00 | 0.07 | 8.47 | 0.64 | 36
|  | friendship-15 | 0.07 | 0.04 | 120 | 1.00 | 0.04 | 4.57 | 0.70 | 17
|  | friendship-16 | 0.05 | 0.03 | 372 | 1.00 | 0.02 | 7.38 | 0.72 | 43
|  | friendship-17 | 0.25 | 0.07 | 65 | 1.00 | 0.12 | 7.91 | 0.70 | 31
|  | health-advice_1 | 0.05 | 0.04 | 187 | 0.98 | 0.02 | 4.61 | 1.31 | 60
|  | health-advice_2 | 0.06 | 0.06 | 170 | 1.00 | 0.03 | 4.64 | 1.66 | 70
|  | health-advice_3 | 0.08 | 0.05 | 185 | 1.00 | 0.04 | 6.90 | 1.43 | 78
|  | health-advice_4 | 0.06 | 0.04 | 316 | 1.00 | 0.02 | 6.61 | 0.96 | 72
|  | health-advice_5 | 0.09 | 0.02 | 166 | 0.99 | 0.03 | 4.65 | 1.45 | 70
|  | health-advice_6 | 0.06 | 0.02 | 131 | 0.98 | 0.03 | 4.34 | 1.93 | 75
|  | health-advice_7 | 0.14 | 0.06 | 121 | 1.00 | 0.07 | 7.82 | 0.80 | 46
|  | health-advice_8 | 0.05 | 0.03 | 361 | 1.00 | 0.02 | 6.85 | 1.04 | 84
|  | health-advice_9 | 0.10 | 0.05 | 173 | 1.00 | 0.04 | 7.20 | 1.42 | 98
|  | health-advice_10 | 0.13 | 0.05 | 204 | 1.00 | 0.04 | 8.04 | 0.98 | 71
|  | health-advice_11 | 0.05 | 0.04 | 234 | 0.97 | 0.02 | 4.50 | 1.67 | 85
|  | health-advice_12 | 0.04 | 0.04 | 218 | 0.99 | 0.02 | 4.90 | 1.30 | 79
|  | health-advice_13 | 0.06 | 0.03 | 157 | 0.91 | 0.02 | 3.64 | 1.25 | 51
|  | health-advice_14 | 0.11 | 0.05 | 120 | 1.00 | 0.05 | 5.43 | 0.80 | 26
|  | health-advice_15 | 0.06 | 0.05 | 117 | 1.00 | 0.03 | 3.35 | 1.36 | 34
|  | health-advice_16 | 0.04 | 0.01 | 349 | 1.00 | 0.01 | 4.94 | 2.21 | 152
|  | health-advice_17 | 0.13 | 0.06 | 63 | 1.00 | 0.07 | 4.63 | 0.95 | 28
|  | Average | 0.09 | 0.05 | 197.29 | 0.99 | 0.04 | 7.21 | 1.01 | 56.09

  * •

$s$ \- global similarity (clustering)

  * •

$c$ \- global complementarity

  * •

$n$ \- number of nodes in the giant component

  * •

$S$ \- relative size of the giant component

  * •

$\rho$ \- edge density

  * •

$\langle{d_{i}}\rangle$ \- average node degree

  * •

$\sigma_{d_{i}}$ \- coefficient of variation of node degrees

  * •

$d_{\text{max}}$ \- maximum node degree

## Networks used in “Structural diversity across the tree of life”

For this analysis we used a dataset of 1840 interactomes of different species
across the tree of life published originally in Ref. [74]. The interactomes
represent only physical protein-protein interactions that are experimentally
supported or manually curated. Detailed description of the dataset and its
underlying methodology, including the list of types of interactions that were
considered, can be found in the Supplementary Information appendix of Ref.
[74]. In particular, information on phylogenetic taxonomy information, the
source of publication counts per species and evolution time estimates defined
in terms of the number of nucleotide substitutions per site are discussed in
sections S1.2, S2.2 and S3.

Due to the large number of networks we do not present a table with descriptive
statistics here. The data and code used for conducting the analysis is
available from the Github repository listed in the Main Text (Data and
materials availability).

###  Experimental assessment of the performance of PathCensus algorithm

We assessed the performance of our implementation of PathCensus algorithm by
measuring the average runtime for each of the 1840 interactome networks
studied in the paper as well as their randomized counterparts sampled from
UBCM. For each network an average runtime over 5 runs was calculated for the
observed network and a corresponding randomized version sampled from UBCM (see
Fig. S4).

Our analysis shows that the runtime scales approximately linearly with respect
to $|E|\Delta{}Sd_{\text{max}}$, which agrees with the previous theoretical
analysis of the computational complexity of PathCensus algorithm. However, the