Transitivity and degree assortativity explained: The bipartite structure of social networks

Dynamical processes, such as the diffusion of knowledge, opinions, pathogens, “fake news,” innovation, and others, are highly dependent on the structure of the social network in which they occur. However, questions on why most social networks present some particular structural features, namely, high levels of transitivity and degree assortativity, when compared to other types of networks remain open. First, we argue that every one-mode network can be regarded as a projection of a bipartite network, and we show that this is the case using two simple examples solved with the generating functions formalism. Second, using synthetic and empirical data, we reveal how the combination of the degree distribution of both sets of nodes of the bipartite network—together with the presence of cycles of lengths four and six—explain the observed values of transitivity and degree assortativity coefficients in the one-mode projected network. Bipartite networks with top node degrees that display a more right-skewed distribution than the bottom nodes result in highly transitive and degree assortative projections, especially if a large number of small cycles are present in the bipartite structure.

Figure 1

Schematic drawing of the three projection methods we discuss here: simple graph, multigraph, and weighted graph projections.

Figure 2

Diagram with examples of structures that inhibit the formation of (simple) triangles. The six-cycles are embedded in subgraphs containing top nodes with degree $d\ge 3$. In panel (a) we have a complete subgraph with an overlapping of nodes with $d_v=3$ that results in only one triadic closure in the projected network, for instance, three papers coauthored by the same three authors. In panel (b) the addition of the dashed link breaks the six-cycle into four-cycles.

Figure 3

Degree distributions (CCDF, complementary cumulative distribution function) of top and bottom node sets for (a) arXiv Biology, (b) arXiv Mathematics, (c) Physical Review E (PRE), and (d) Norwegian directors. The heavy-tailed top degree distributions of arXiv Biology, and PRE, supported by the high presence of small cycles (Table 2), result in high projected transitivity and degree assortativity. This is so even with both cases displaying heavy-tailed bottom distributions, which create large numbers of open triplets and high relative branching. On the other hand, peaked distributions of the Norwegian board-of-directors network result in comparatively small projected degree assortativity, but high transitivity as the top distribution is more shifted to the right than the bottom distribution. In this case, transitivity is driving assortativity.

Figure 4

Correlation between the bottom degree $k$ and the projected degree $q$ for (a) arXiv Biology with Person's coefficient $r=0.23$, (b) arXiv Mathematics with $r=0.68$ (c) – Physical Review E with $r=0.56$, and (d) Norwegian directors with $r=0.73$. Although many low degree bottom nodes have high projected degree (i.e., connected to high top degree nodes), especially in panel (a), we see a positive correlation between $k_u$ and $q_u^{\mathrm{s}}$. That is, the higher $k_u$ is, the more likely that $u$ will have high $q_u^{\mathrm{s}}$.

Figure 5

Correlation between the bottom degree $k$ and the number of four-cycles in $B$ a node is part of for (a) arXiv Biology with Person's coefficient $r=0.61$, (b) arXiv Mathematics with $r=0.51$, (c) – Physical Review E with $r=0.66$, and (d) Norwegian directors with $r=0.52$. The positive correlations mean that high degree bottom nodes are more likely to be part of several four-cycles (to have several common neighbors with other bottom nodes).

Figure 6

Evolution of PRE network topology until 2015. (a) Top and (b) bottom degree distribution; (c) four- and six-cycles, triangles, and triplets; and (d) transitivity, assortativity, relative branching, and modular connectivity. The highest-degree top node enters the network (snapshot of the year 2000), increasing transitivity and assortativity as it favors triangles and intermodular connectivity, respectively. As only the bottom degree distribution gets shifted to the right with time, open triplets and relative branching are favored, reducing transitivity and assortativity as the network grows.

Figure 7

Evolution of APS network topology until 1991. (a) Top and (b) bottom degree distribution; (c) four- and six-cycles, triangles, and triplets; and (d) transitivity, assortativity, relative branching, and modular connectivity. Initially the network is dissortative, due to the combination of a peaked top degree distribution, a broader bottom distribution than the top one, and the low presence of four- and six-cycles. As the network evolves, the top distribution becomes broader and the frequency of small cycles grows substantially, resulting in large transitivity and degree assortativity.