Structural measures for multiplex networks

Many real-world complex systems consist of a set of elementary units connected by relationships of different kinds. All such systems are better described in terms of multiplex networks, where the links at each layer represent a different type of interaction between the same set of nodes rather than in terms of (single-layer) networks. In this paper we present a general framework to describe and study multiplex networks, whose links are either unweighted or weighted. In particular, we propose a series of measures to characterize the multiplexicity of the systems in terms of (i) basic node and link properties such as the node degree, and the edge overlap and reinforcement, (ii) local properties such as the clustering coefficient and the transitivity, and (iii) global properties related to the navigability of the multiplex across the different layers. The measures we introduce are validated on a genuinely multiplex data set of Indonesian terrorists, where information among 78 individuals are recorded with respect to mutual trust, common operations, exchanged communications, and business relationships.

Figure 1

A flattened representation of the three-layer multiplex obtained by considering only trust (T), communication (C), and operations ties (O). For each node $i$ we indicate with a color code the layers in which $i$ is actively involved (i.e., the layers $\alpha$ for which $k_i^{\left[\alpha \right]}>0$). The size of a node is proportional to its overlapping degree $o_i$: node 57 is the node with the largest overlapping degree.

Figure 2

(a) The top row of the panel shows with a color code the degree $k_i$ of each node, from the largest (darkest, leftmost) to the smallest (brightest, rightmost). Keeping fixed the ranking induced by $k_i$, in the other three rows we report, respectively, the degree in the trust layer $k_i^{\left[\mathrm{T}\right]}$, operational layer $k_i^{\left[\mathrm{O}\right]}$, and communication layer $k_i^{\left[\mathrm{C}\right]}$. (b) Same as panel (a) but in the first row nodes are ranked according to their overlapping degree $o_i$. (c) The heat map represents the Kendall $\tau$ correlation coefficient among $k_i$, $o_i$, $k_i^{\left[\mathrm{T}\right]}$, $k_i^{\left[\mathrm{O}\right]}$, and $k_i^{\left[\mathrm{C}\right]}$. Notice that the degree of a node in the operational layer O is poorly correlated with its degree in the communication and trust layers (bright yellow regions in the heat map).

Figure 3

(a) Rank distribution of the participation coefficient $P_i$ for the multilayer network of Noordin Top Indonesian terrorists. $M=3$ layers were considered, namely trust, operational, and communication. The average value $P=0.72$ is shown as a horizontal blue line, while the shaded band indicates the standard deviation. (b) A cartography of the roles of the nodes in a multilayer network can be obtained by plotting, for each node $i$, the multiplex participation coefficient $P_i$ versus the Z score of the total overlapping degree $z\left(o_i\right)$. Even if two nodes have exactly the same value of $z\left(o_i\right)$ (like node 16 and node 34, indicated by the orange and blue circles, respectively), they can have pretty different roles, according to the value of the multiplex participation coefficient. (c) The ego networks of node 16 and 34, in which edges are colored according to the layer to which they belong, respectively green (trust), blue (operational), and red (communication). It is evident that the connectivity pattern of node 16, whose links are homogeneously distributed across the three layers, is “more multiplex” than that of node 34, which is instead focused on the operational layer.

Figure 4

(a) For each layer $\alpha$, we show in the color map the fraction of edges which is also present in each other layer ${\alpha }^{\prime }$. (b) Probability $P^{\mathrm{w}}$ of finding a certain link at layer O (solid blue line), C (dotted green line), and B (dashed red line), conditional to the weight $w_{ij}^{\left[\mathrm{T}\right]}$ of the same link at layer T. (c) The values of $P^{\mathrm{w}}$ computed on real data for layer O (solid blue line) are compared to those obtained by randomizing the edges keeping fixed the total number of links $K^{\left[\mathrm{O}\right]}$ (dashed gray line) or the degree distribution $P\left(k^{\left[\mathrm{O}\right]}\right)$ (dotted magenta line) for the operational layer.

Figure 5

(a) The node clustering coefficient $C_i$ of the aggregated topological network and of the three layers T, O, and C, respectively denoted as $C_i^{\left[\mathrm{T}\right]}$, $C_i^{\left[\mathrm{O}\right]}$, and $C_i^{\left[\mathrm{C}\right]}$. The nodes are ranked according to their value of $C_i$ on the aggregated topological network. (b) The heat map represents the correlation between the rankings of nodes according to their clustering coefficients on the three layers and on the topological aggregated network. Notice that $C_i^{\left[\alpha \right]}$ is weakly correlated with $C_i$ for $\alpha \in \{T,O,C\}$, and that such a correlation might also be negative, as in the case of $C_i^{\left[\mathrm{O}\right]}$. (c) Comparison among the clustering coefficient $C_i$ of the aggregated topological network and the multilayer clustering coefficients $C_{i,1}$ and $C_{i,2}$. The nodes are ranked according to their value of $C_i$. (d) The heat map represents the correlation between the rankings of nodes according to $C_i$, $C_{i,1}$, and $C_{i,2}$.

Figure 6

Scatter plots of (a) $C_{i,1}$ versus $C_{i,2}$ (b) $C_{i,1}$ versus $o_i$ and (c) $C_{i,2}$ versus $o_i$. The values of the Kendall's $\tau$ and of the Pearson's linear correlation coefficient $r$ for any pair of measures are, respectively, $\tau (C_{i,1},C_{i,2})=0.61$, $r(C_{i,1},C_{i,2})=0.76$, $\tau (C_{i,1},o_i)=-0.11$, $r(C_{i,1},o_i)=-0.13$, $\tau (C_{i,2},o_i)=0.01$, $r(C_{i,2},o_i)=0.04$. It is worth noticing that both $C_{i,1}$ and $C_{i,2}$ are almost uncorrelated with the overlapping degree $o_i$, a fact that confirms their truly multiplex nature.

Figure 7

(a) Rank distribution of the node interdependence ${\lambda }_i$ in the Indonesian terrorist multiplex network. (b) Scatter plot of the interdependence ${\lambda }_i$ versus $o_i$ and (c) versus $P_i$. The corresponding value of Kendall's $\tau$ and Pearson's $r$ correlation coefficients are, respectively, $\tau ({\lambda }_i,o_i)=-0.41$, $r({\lambda }_i,o_i)=-0.56$, $\tau ({\lambda }_i,P_i)=-0.41$, and $r({\lambda }_i,P_i)=-0.57$.

Figure 8

(a) Eigenvector centrality of the aggregated topological network $E_i\left(\mathcal{A}\right)$ and of the trust $E_i^{\left[\mathrm{T}\right]}$, operational $E_i^{\left[\mathrm{O}\right]}$, and communication layer $E_i^{\left[\mathrm{C}\right]}$. The nodes are ranked according to their value of $E_i\left(\mathcal{A}\right)$ on the aggregated topological network. (b) Similar to panel (a) but here the nodes are ranked according to their eigenvector centrality computed on the aggregated overlapping network $E_i\left(\mathcal{O}\right)$. (c) Comparison of the rankings of eigenvector centrality computed on the aggregated topological network and on the aggregated overlapping network, respectively, $E_i\left(\mathcal{A}\right)$ and $E_i\left(\mathcal{O}\right)$. (d) The heat map shows the nonparametric correlation between the rankings induces by the different centralities.

Figure 9

Scatter plot of the eigenvector centrality on the aggregated overlapping network $E_i\left(\mathcal{O}\right)$ and the participation coefficient $P_i$. Notice that there is indeed a slightly positive correlation between these metrics ($\tau (E_i\left(\mathcal{O}\right),P_i)=0.31$, $r(E_i\left(\mathcal{O}\right),P_i)=0.43$).

Figure 10

For each couple of layers (duplex) of the multiplex network of Indonesian terrorists we plot the Kendall correlation coefficient ${\tau }_k$ between the eigenvector centrality of the benchmark case ($b=0.5$, i.e., equal weights on both layers) and the generic case of Eq. (26).

Figure 11

As subsets of the original overlapping network, we consider the three duplex $M^{[\mathrm{T},\mathrm{O}]}=b{A}^{\mathrm{T}}+(1-b)A^{\left[\mathrm{O}\right]}$, $M^{[\mathrm{T},\mathrm{C}]}=b{A}^{\mathrm{T}}+(1-b)A^{\left[\mathrm{C}\right]}$ and $M^{[\mathrm{O},\mathrm{C}]}=b{A}^{\mathrm{O}}+(1-b)A^{\left[\mathrm{C}\right]}$. For each possible duplex, we report the Kendall coefficient ${\tau }_k$ between the centrality of each single layer and the corresponding $\mathcal{M}$ as a function of $b$.