Computing layer similarities is an important way of characterizing multiplex networks because various static properties and dynamic processes depend on the relationships between layers. We provide a taxonomy and experimental evaluation of approaches to compare layers in multiplex networks. Our taxonomy includes, systematizes and extends existing approaches, and is complemented by a set of practical guidelines on how to apply them.

1. Introduction

Multiplex networks provide a simple yet expressive way to model a wide range of physical and social systems as sets of entities connected by multiple types of relationships, that in this paper we also call layers following the terminology in [1]. For example, a transport network can be modelled as a set of locations, such as cities or streets, connected by different types of public transport like airplanes, trains and buses. Several studies have investigated the connection between layer similarity and other properties of the network. For example, we known from previous research that the relationships between layers have an impact on dynamic processes such as behaviour and information diffusion [2].

Being able to measure relationships between layers is also essential to validate models aimed at explaining the formation of empirical multilayer networks [3,4]. While the problem of comparing different networks has been thoroughly investigated in the literature [5–13], the problem of quantifying layer similarity where the same nodes can be present in multiple layers (which characterizes multiplex networks) has not been studied in a systematic and comprehensive way so far.

In the literature, we can find a large number of works using layer similarity measures, but most use them as a tool to study other phenomena such as multiplex network generation [3,4,14], link prediction [15] and spreading processes [2]. As a result, different works use the same or very similar approaches presented with different names, the relationships between several of these similarity measures have not been explored, and there are no guidelines on how to quantify layer similarity in multiplex networks, e.g. how to choose the appropriate measure given a specific dataset. In addition, various potentially useful layer comparison measures have not been considered yet.

Therefore, in this paper we provide the following contributions: (i) a systematic study of approaches and measures to compute the similarity between layers in multiplex networks, based both on a literature study and on a theoretical framing of the problem; (ii) a set of measures that have not been used yet to compare layers, complementing those already defined in the literature; (iii) an empirical study of the relationships between different measures, compared on several real datasets; and (iv) a set of guidelines on how to choose and use these measures.

In §2, we present the definitions, concepts and notation used in the paper. In §3, we present an organized set of existing and new layer similarity measures. Section 4 provides the results of an empirical study where the main similarity measures are applied to several real datasets from different domains, such as genetic networks, social networks, co-authorship networks and transport networks. Section 5 discusses guidelines to be used to select the most appropriate measure.

2. Concepts, terminology and notation

In this section, we define the basic concepts needed to provide a systematic coverage of layer similarity measures. We start with the standard definition of multiplex network, followed by an alternative representation called property matrix allowing us to define similarity functions based on different types of network structures and different ways to look at them.

In this paper, we use the following definition of multiplex network:

Definition 2.1 (Multiplex network).

Given a set of nodes $N$ and a set of layers $L$ , a multiplex network is defined as a quadruple $M = (N, L, V, E)$ , where (V, E) is a graph, $V \subseteq N \times L$ , and if (n₁, l₁, n₂, l₂)∈E, then l₁ = l₂.

An example of multiplex network is shown in figure 1, where $L = {l_{1}, l_{2}}$ , $N = {n_{1}, \dots, n_{6}}$ and (n₁, l₁, n₂, l₁) is an example of an edge in E. In the literature, alternative terminologies are used, and here we adopt the one in [1], according to which we would say that node n₁ is present in both layer l₁ and layer l₂. In the literature, some extended multiplex models have also been proposed, allowing multi-dimensional layers [1] and one-to-many relationships between nodes in different layers [16], but we do not consider these extensions here.

Note that the original definition of multiplex network introduced in the field of Social Network Analysis was more restrictive than the one adopted in this paper. In particular, our definition allows some of the nodes not to be present in some layers. For example, (n₅, l₂)∉V in figure 1. In some cases, when the term multiplex is used, it is assumed that all nodes are present in all layers, and this assumption will often affect the result of layer comparisons. To avoid confusion, in this case we explicitly talk about a node-aligned multiplex network [1] and when it is not clear from the context we will call a multiplex network that is not node-aligned a generalized multiplex network.

Definition 2.2 (Node-aligned multiplex network).

A node-aligned multiplex network is a multiplex network $(N, L, V, E)$ where $\forall n \in N, l \in L : (n, l) \in V$ .

Multiplex networks have usually been represented as a set of adjacency matrices A_l, one for each layer l, where a_l(n₁, n₂) = 1 if there is an edge between node n₁ and node n₂ in layer l, a_l(n₁, n₂) = 0 otherwise. The adjacency matrices for our working example are shown in figure 2.

Figure 2. Adjacency matrices for both layers of the multiplex network in figure 1.

However, this representation is not the most appropriate to define similarity measures, for two main reasons. First, it is incomplete, because it only allows representing node-aligned multiplex networks. An example of why this is important is the case of online social media, where each layer represents a different service (Twitter, Facebook, etc.), and it makes a difference whether a user has no connections on Twitter or does not even have an account there. In our working example, we would lose the information that nodes n₅ and n₆ are present in different layers.

Second, adjacency matrices present an edge-oriented view over the multiplex network, which might be the reason why most similarity measures in the literature have been limited to edge similarity. If we take a broader look at empirical networks, we can see how other structures can be relevant. As an example, if we look at figure 1, we can see that the triangle {n₂, n₃, n₄} is present in both layers. Unfortunately, this is not obvious from the adjacency matrices and would require checking several disparate entries making definitions more complicated than needed. Therefore, in the following, we use network representation targeted to the specific properties we want to consider when checking the similarity between layers. We call this representation a property matrix.

Definition 2.3 (Property matrix).

A property matrix P is a matrix where:

(i) the columns correspond to a set S of network structures (nodes, edges, triangles, …),
(ii) the rows correspond to a set C of contexts where these structures are observed (layers, groups, snapshots, …), and
(iii) p_s,c is the value of an observational function mapping each pair structure/context into a number (degree, distance, …).

Since in this paper we focus on layer similarity we will only use layers as contexts, that is, $C = L$ . In summary, each cell p_s,c of a property matrix contains the value of the function describing the structure s (for example, a node) on layer c, and different observational functions can be used to define different types of similarity. Examples of property matrices for our working example are shown in figure 3.

Figure 3. Property matrices for our working example in figure 1. Each *property matrix* is defined by a type of structures (nodes, dyads, triads, etc.), the contexts (layers) and an observational function (existence, degree, forming a clique, distance, etc.).

Given a structure s, we can further summarize its presence in the network by summing over all the values in p^s, computing their standard deviation or performing any other kind of aggregation (sum, avg, median, min, max, etc.). As an example, from a node-degree property matrix (figure 3b) we can obtain the total degree of a node in the whole multiplex network (sum) or its so-called degree deviation [17], which is 0 if a node has the same number of connections on all layers and higher when a node is present in different layers with different degrees, and so on. In summary, property matrices provide a more general and informative representation of multiplex networks than adjacency matrices—which are still useful when the objective is just to know about the edges in a node-aligned network. Property matrices also allow us to provide simple and general mathematical definitions of different ways to compare layers, which will instantiate into several existing and new measures when specific property matrices are used. The terminology and notation used in the paper is summarized in table 1.

Table 1.Terminology and notation used in the paper.
Collapse
symbol	name
$N$	set of nodes {n₁, n₂, …, n_\|N\|}
$L$	set of layers {l₁, l₂, …, l_\|L\|}
P	property matrix
C	set of contexts (e.g. network layers, snapshots, groups)
S	set of structures (e.g. nodes, edges, dyads, triangles)
p_c	property vector for context c∈C
p^s	property vector for structure s∈S
p_s,c	property of s in c (e.g. degree of node s on layer c)
p_C′,S′	p restricted to contexts in C′⊆C and structures in S′⊆S

3. Layer similarity functions

Given a property matrix P where each row represents a layer, we can compare two layers in three main ways. The first is to summarize each row using an aggregation function f and compare f(P_l₁) to f(P_l₂). For example, if the property matrix contains node degrees we can compare the layers' average degrees mean(P_l₁) and mean(P_l₂). Comparing the distribution of values in P_l₁ and P_l₂ is the second way to compare layers. As an example, we can compare degree distributions on different layers and find that both fit well a power-law distribution with the same exponent. The third way is to compare p_s,l₁ with p_s,l₂ for all s. As an example, we can compute degree correlation to check whether nodes with a high (respectively, low) degree on one layer tend to have a high (respectively, low) degree also on the other layer.

3.1. Comparing aggregations of layer property vectors

This first class of comparison methods is based on comparing f(P_l₁) to f(P_l₂) using various functions (f) aggregating each layer into a single value. Typical choices are basic statistical summary functions such as mean, max, sum, skewness and kurtosis, combinations of the simple statistics, such as the coefficient of variation (the ratio between the standard deviation and the mean), the Jarque–Bera statistics (a combination of skewness and kurtosis), or the Shannon entropy [18] of the distribution. These methods are summarized in table 2.

Table 2.Summary of common aggregation functions for *property matrices.*
Collapse
name	function
mean(p_l)	$\frac{\sum_{s} p_{s, l}}{card (p_{l})}$
sd(p_l)	$\sqrt{\frac{\sum_{s} {(p_{s, l} - mean (p_{l}))}^{2}}{card (p_{l})}}$
skew(p_l)	$\frac{\sum_{s} {(p_{s, l} - mean (p_{l}))}^{3}}{card (p_{l}) sd {(p_{l})}^{3}}$
kurt(p_l)	$\frac{\sum_{s} {(p_{s, l} - mean (p_{l}))}^{4}}{card (p_{l}) sd {(p_{l})}^{4}}$
entropy(p_l)	$\sum_{k = 1}^{k} f r_{k, l} \log f r_{k, l}$
CV (p_l)	$\frac{sd (p_{l})}{mean (p_{l})}$
Jarque - - Bera(p_l)	$\frac{card (p_{l})}{6} (skew {(p_{l})}^{2} + \frac{{(kurt (p_{l}) - 3)}^{2}}{4})$

where fr_k,l is the relative frequency of the kth value of the property vector p_l in a generic layer l.

Then, given f(P_l₁) and f(P_l₂) we can compare them, and in our experiments we have used their relative difference, i.e. 2 · (|f(P_l₁) − f(P_l₂)|)/(|f(P_l₁)| + |f(P_l₂)|).

Note that depending on the property matrix these measures correspond to various existing network summaries. For example, the mean function may return the average degree (when applied to property matrices about node degrees), or the global clustering coefficient also known as transitivity index (for node clustering coefficients), or the average path length for property matrices about dyads and geodesic distances (which in the field of chemistry coincides with the Wiener index [19]).

Whether the multiplex network is node-aligned or not, does not pose any problems regarding the computation of the functions in table 2. These functions are computed for each layer, only for the nodes existing on the layer, so if some nodes are not present they are just not considered in the computation. Similarly, also the measures in table 3 can be easily computed for node-aligned and for node-non-aligned as the frequency distributions are computed layer by layer. However, the results of the function and of the comparison can be strongly affected by the alignment, as shown and discussed in our experimental results.

Table 3.Main methods to compare distributions across layers.
Collapse
name	notation	function
dissimilarity index	ID(p_l₁, p_l₂)	$\frac{1}{2} \sum_{k = 1}^{K} \| {fr}_{k, l_{1}} - {fr}_{k, l_{2}} \|$
Kullback–Leibler	D_KL(p_l₁, p_l₂)	$\sum_{k = 1}^{K} {fr}_{k, l_{1}} \log \frac{{fr}_{k, l_{1}}}{{fr}_{k, l_{2}}}$
Jensen–Shannon	D_JS(p_l₁, p_l₂)	$\frac{1}{2} (\sum_{k = 1}^{K} {fr}_{k, l_{1}} \log \frac{{fr}_{k, l_{1}}}{{\hat{fr}}_{k}} + {fr}_{k, l_{2}} \log \frac{{fr}_{k, l_{2}}}{{\hat{fr}}_{k}})$
Jeffrey	D_J(p_l₁, p_l₂)	$\sum_{k = 1}^{K} {fr}_{k, l_{1}} \log \frac{{fr}_{k, l_{1}}}{{fr}_{k, l_{2}}} + \sum_{k = 1}^{K} {fr}_{k, l_{2}} \log \frac{{fr}_{k, l_{2}}}{{fr}_{k, l_{1}}}$

where ${\hat{f} r}_{k} = \frac{f r_{k, l_{1}} + f r_{k, l_{2}}}{2}$ .

3.2. Comparing distributions of layer property vectors

While using a single value to compare layers can provide some useful knowledge about the multiplex network, for example, by highlighting the presence of denser or more clustered layers than others, looking at the whole distribution of values in the property matrix can reveal other types of relationships among layers. From a statistical point of view, some ways are open to pursuing this task. The first one consists in comparing the moments of two distributions. For example, it is possible to compare the first four moments, even if from a theoretical point of view this is not completely sufficient. Another possible approach consists in comparing the distributions directly. In this case, we have to apply to each property vector a function fr(P_l) that derives the relative frequency distribution. In the case of discrete distributions, such as the degree distribution, given a property vector P_l we derive the disjoint values p_k,l, k = 1, …, K, and we associate with each value the relative frequency fr_k,l.

In the case of continuous distribution, or in the case of very large networks in which also the discrete distributions take a wide range of values, the function fr(P_l) derives histograms. We first divide the range of values of the property vector into K equal intervals, or bins, [b_(k−1), b_k], with b₀ being the minimum value in the property matrix and b_K,l being the maximum value in the property matrix.¹ Then we associate the relative frequency fr_k with each interval. Note that the bins of all histograms for all layers must be the same. Then we have to compare only the relative frequency distributions. This procedure is very fast and efficient also for very large networks.

Given the frequencies or histograms, in order to compare two layers we can use the distance between observed distributions based on distance between histograms, namely, the dissimilarity index (ID), the Kullback–Leibler divergence D_KL [20], the Jensen–Shannon divergence D_JS or the Jeffrey divergence D_J, as defined in table 3 [21]. In the following, we do not consider the Jeffrey divergence, as the Jensen–Shannon divergence is its smoother version. Note that this kind of comparison can be made both for node-aligned and for not node-aligned multiplexes.

3.3. Comparing individual structures

The main feature of multiplex networks is that the same structure can be present or not, and have different characteristics, on each layer. For example, a node can be present in one layer and not in the other, or the same node may have different degrees depending on the layer. Therefore, a peculiar set of measures to compare layers relies on the comparison of the structures of interest, one by one.

Two main cases are possible. In property matrices indicating the existence of different structures on the different layers, we only have two values: 0 and 1. While represented as numbers, these are in fact just nominal values indicating that the structure is present on the layer. For these binary matrices, specific methods can be used, checking the overlapping or more in general, the common existence (or common absence) of structures across layers. For numerical matrices containing generic numbers, e.g. node degrees, other methods are more appropriate, as described in the following two sections.

3.3.1. Binary properties

When a structure can be present or not on different layers, a basic way to compute the similarity between layers is to quantify the overlapping of these structures, that is, how often the same structure appears or not on more than one layer. This is typically the case when the observation function defining the property matrix checks the existence of the structure.

Measures of overlapping have been defined and redefined many times during the last few years in different papers, but most definitions can be generalized using property matrices as

C p_{l_{1}}^{'} \cdot p_{l_{2}},

3.1

where C is some normalization function. Most (but not all) measures in the literature compare edges across layers, this being the result of the traditional edge-based definitions of multiplex networks such as adjacency matrices. In our definition, the usage of property matrices allows us to apply similar comparisons to various other properties.

Consider two binary property vectors P_l₁ and P_l₂. Following [22] let us denote with:

— a = P′_l₁ · P_l₂ the number of properties that l₁ and l₂ share;
— b = P′_l₁ · (1 − P_l₂) the number of properties that l₁ has and l₂ lacks;
— c = (1 − P_l₁)′ · P_l₂ the number of properties that l₁ lacks and l₂ has;
— d = (1 − P_l₁)′ · (1 − P_l₂) the number of properties that both l₁ and l₂ lack;
— m = a + b + c + d = length(P_l₁) = length(P_l₂).

Then, the binary similarity functions can be summarized as in table 4.

Table 4.Similarity functions for binary property matrices. Column C indicates the normalization function in equation (3.1). For the two functions also considering the non-existence of structures on both layers, we only provide the standard definition not based on the product of property vectors.
Collapse
name	normalization function C	standard notation
Russel–Rao	$\frac{1}{length (p_{l_{1}})}$	$\frac{a}{m}$
Jaccard	$\frac{1}{length (p_{l_{1}}) - {(1 - p_{l_{1}})}^{'} \cdot (1 - p_{l_{2}})}$	$\frac{a}{m - d}$
coverage	$\frac{1}{length (p_{l_{1}})}$
Kulczyński	$\frac{1}{2} (\frac{1}{∥ p_{l_{1}} ∥_{1}} + \frac{1}{∥ p_{l_{2}} ∥_{1}})$	$\frac{a}{2} (\frac{1}{a + b} + \frac{1}{a + c})$
simple matching coefficient (SMC)	n.a.	$\frac{a + d}{m}$
Hamann	n.a.	$\frac{a + d - (b + c)}{m}$

3.3.2. Numerical properties

Depending on the reason why we are computing the similarity between layers, we can use different approaches. As each layer is represented as a vector in a property matrix, one way is to compute vectorial distances such as Euclidean distance or cosine similarity. Another popular way to compare numerical layer property vectors is to compute correlations. An example of this is the so-called inter-layer correlation measure, which is just the Pearson coefficient computed on two node degree property vectors [23,24]. It is interesting to note that in the literature correlations across layers have been almost always computed on node degrees, and in [25] also on clustering coefficients. However, correlations can be in fact be computed on any property matrix (table 5).

Table 5.Similarity functions for numerical property matrices. The function ρ( · ) provides the ranks of the values in the property vectors.
Collapse
name	function
cosine similarity	$\frac{p_{l_{1}}^{'} \cdot p_{l_{2}}}{∥ p_{l_{1}} ∥ \cdot ∥ p_{l_{2}} ∥}$
Pearson correlation coefficient	$\frac{{[p_{l_{1}} - mean (p_{l_{1}})]}^{'} \cdot [p_{l_{2}} - mean (p_{l_{2}})]}{∥ [p_{l_{1}} - mean (p_{l_{1}})] ∥ \cdot ∥ [p_{l_{2}} - mean (p_{l_{2}})] ∥}$
Spearman correlation coefficient	$\frac{{[ρ (p_{l_{1}}) - mean (ρ (p_{l_{1}}))]}^{'} \cdot [ρ (p_{l_{2}}) - mean (ρ (p_{l_{2}}))]}{∥ [ρ (p_{l_{1}}) - mean (ρ (p_{l_{1}}))] ∥ \cdot ∥ [ρ (p_{l_{2}}) - mean (ρ (p_{l_{2}}))] ∥}$

In addition, we would like to stress that Pearson correlation here is used as measure of accordance of numerical vectors, and then it can be used also when usual statistical assumptions are not completely fulfilled. However, in the case of highly skewed distributions, or in the case of severe and numerous outliers, the Spearman rank correlation is a good solution. For this reason, we suggest to use them jointly.

Finally, when computing correlations in generalized multiplex networks a choice must be made on how to handle actors not present in all layers. The choice we adopted in our experiments was to discard pairs where at least one of the two values was missing, which is a typical option in statistical software packages.

4. Empirical comparison of measures

The experiments have been performed using the multinet library² and 23 multilayer networks.³ The input format of the multinet library allows the distinction between nodes without connections and missing nodes, as in our working example, but none of the datasets we have used explicitly makes this distinction.

In the experiments, we have computed 50 different similarity measures (table 6) between all pairs of layers in each dataset and grouped these results by network type (table 7). Figures 4–6 show the properties of distribution of values produced by each measure. Figures 7–10 show the Pearson correlation between values obtained by different measures, where a value of 1 (yellow in the colour figures) indicates that two measures are equivalent up to some constant rescaling. In addition to the results presented in these figures, we have also performed a manual qualitative analysis of the results, to verify our interpretation of the patterns emerging in the plots.

Figure 4. Boxplots for degree-based measures (1–16). Left: generalized multiplex network, right: node-aligned multiplex network. The outliers have been scattered. (a) Genetic networks, (b) social networks, (c) co-authorship networks and (d) transport networks.

Figure 5. Boxplots for clustering coefficient based measures (17–32). Left: generalized multiplex network, right: node-aligned multiplex network. The outliers have been scattered. (a) Genetic networks, (b) social networks, (c) co-authorship network and (d) transport networks.

Figure 6. Boxplots for node-, edge- and triangle-based measures (33–50). Left: generalized multiplex network, right: node-aligned multiplex network. The outliers have been scattered. (a) Genetic networks, (b) social networks, (c) co-authorship network and (d) transport networks.

Figure 7. Correlation between all fifty measures for genetic networks. (a) generalized multiplex network, (b) node-aligned multiplex network. NaN is marked in white.

Figure 8. Correlation between all 50 measures for social networks. Left: generalized multiplex network, right: node-aligned multiplex network. NaN is marked in white.

Figure 9. Correlation between all 50 measures for co-authorship networks. (a) generalized multiplex network, (b) node-aligned multiplex network. NaN is marked in white.

Figure 10. Correlation between all 50 measures for transport networks. (a) generalized multiplex network, (b) node-aligned multiplex network. NaN is marked in white.

Table 6.Fifty measures evaluated during experiments.
Collapse
1	min degree	17	min CC	33	SMC node
2	max degree	18	max CC	34	Jaccard node
3	sum degree	19	sum CC	35	Kulczyński node
4	mean degree	20	mean CC	36	coverage node
5	standard deviation degree	21	standard deviation CC	37	Russel–Rao node
6	skewness degree	22	skewness CC	38	Hamann node
7	kurtosis degree	23	kurtosis CC	39	SMC edge
8	entropy degree	24	entropy CC	40	Jaccard edge
9	CV degree	25	CV CC	41	Kulczyński edge
10	Jarque–Bera degree	26	Jarque–Bera CC	42	coverage edge
11	dissimilarity index degree	27	dissimilarity index CC	43	Russel–Rao edge
12	KL divergence degree	28	KL divergence CC	44	Hamann edge
13	JS divergence degree	29	JS divergence CC	45	SMC triangle
14	cosine distance degree	30	cosine distance CC	46	Jaccard triangle
15	Pearson correlation degree	31	Pearson correlation CC	47	Kulczyński triangle
16	Spearman correlation degree	32	Spearman correlation CC	48	coverage triangle
				49	Russel–Rao triangle
				50	Hamann triangle

Table 7.Twenty-three multilayer networks used during experiments.
Collapse
ID	network	description	no. of layers	ref.
1	Bos Linnaeus	genetic	4	[26]
2	Candida Albicans	genetic	7	[26]
3	Celegans	genetic	6	[26]
4	Danio Rerio	genetic	5	[26]
5	Gallus Gallus	genetic	6	[26]
6	Hepatitus C	genetic	3	[26]
7	Human Herpes Virus	genetic	4	[26]
8	Human HIV Virus	genetic	5	[26]
9	Oryctolagus	genetic	3	[26]
10	Plasmodium Falciparum	genetic	3	[26]
11	Rattus Norvegicus	genetic	6	[26]
12	Xenopus Laevis	genetic	5	[26]
13	Ckm Physicians Innovation	social	3	[27]
14	AUCS	social	5	[28]
15	Florentine Families	social	2	[29]
16	Kapferer Tailor Shop	social	4	[30]
17	Krackhardt High Tech	social	3	[31]
18	Lazega Law Firm	social	3	[32]
19	Vickers Chan 7^thgraders	social	2	[33]
20	Arxiv Network Science	co-authorship	13	[34]
21	Pierre Auger	co-authorship	16	[34]
22	EU Air Transportation	transport	37	[35]
23	London Transport	transport	3	[36]

In the following sections, we highlight some of the results, grouped into four main areas.

4.1. Correlation-based measures

In figures 4 and 5, we can see how correlation measures (15, 16, 31, 32) prove their usefulness by discriminating between, e.g. social networks, where the degrees are correlated—that is, (un)popular people are often (un)popular on more than one layer, while for co-authorship networks where layers indicate different disciplines researchers are often popular only in one or a few of them. Interestingly, transport networks contain different extremes: airports that are hubs for one airline are often not hubs for others (corresponding to anti-correlations, that is, values towards 1 in the figures) while for the London data the same locations are often hubs for different types of transportation, resulting in positive correlations.

In many cases, Pearson and Rank correlations show similar results.

4.2. Overlapping-based measures

Overlapping-based measures have been used multiple times in the literature, mainly applied to edges. In figure 6, we can observe their behaviours on the various datasets used in our experiments.

Measures based on simple matching, Russel–Rao and Hamann degenerate whenever the property vectors become large (that is, m is large) and sparse (that is, d is close to m). In these cases, Russel–Rao tends to 0 while Hamann and SMC tend to 1, as we can see in the plots. However, with node-existence property matrices, these degeneration conditions are often not verified, so these measures can still capture different levels of similarity.

When applied to generalized multiplex networks, node overlapping shows significant differences between different types of networks. For example, in figure 6b we can see that social networks tend to have a high node overlapping (average close to one for measures 34–36), while for example, co-authorship networks show values closer to 0, indicating a significant difference between people working in different disciplines (figure 6c). In practice, we can say that many social networks are naturally node-aligned.

However, in both cases, we can see several outliers, highlighting special relationships between layers and thus showing the usefulness of these measures also to identify special cases. For example for the Arxiv co-authorship network (20 in table 7), the two layers physics.data-an (Physics Data Analysis, Statistics and Probability) and cs.SI (Computer Science Social and Information Networks) are very similar in terms of node overlapping, indicating an interdisciplinary topic which is of interest to both computer scientists and physicists. Another example, this time for social networks, comes from the AUCS network (14 in table 7). Almost all outliers are related to the two layers Facebook and co-author, both having a significantly different number of actors if compared with the other layers in the network, which explains e.g. low overlapping.

Higher-order structures, that is, dyads and triads in our experiments, also show different behaviours in different types of networks. There are several similar layers in collaboration networks, maybe because these networks are often obtained as projections from bipartite networks, but still, the majority of the pairs of layers are not very similar. For social networks, a high overlapping is observed much more frequently, also because of the high presence of triangles, while transportation and genetic networks show the least overlapping.

4.3. Effects of node alignment

The impact of using a node-aligned or generalized multiplex is evident in many experimental results, as expected. Obviously, node-based measures computing the overlapping among nodes in different layers (33–38) become useless if we force all layers to contain all nodes (figure 6, right-hand side plots).

At the same time, using node-aligned networks also affects many other measures. As an example, figure 4d shows the presence of anti-correlated layers (measures 15 and 16, left-hand side, values close to −1), revealing how airports that are hubs for one airline are often not hubs for others. Considering many nodes that would not be present in the layers, and thus having degree 0, makes these anti-correlations less evident (measures 15 and 16, right-hand-side, values now closer to 0).

For edge- and triangle-based overlapping measures the results are the same in the node-aligned and in the non-aligned networks. This, however, is only because we have not made a difference between e.g. a missing triangle and missing triad, which would be computationally demanding. This also shows how the results we obtain may strongly depend on how we modelled the data and on implementation details such as the policy to handle null values.

Correlations between different measures appear more evidently in node-aligned networks. This effect is more evident for genetic networks and co-authorship networks. In these cases, the zeros added by the alignment reinforce the correlation among the measures.

4.4. Correlation between measures

In figures 7–10, the value for each cell on the heat map is calculated in the following way. First layer–layer similarity for each pair of layers is calculated, for each network. For example, if the network has three layers it will have nine values of similarity. Next, for each network type (genetic, social, co-authorship and transport) and each similarity measure a vector containing the layer–layer similarities for all networks of that type is created. For example, if there are two networks of a given type, one with three and one with four layers, each vector will contain 25 entries, nine concerning the first network and 16 concerning the second. Finally, Pearson correlation coefficients are computed for all pairs of vectors, each representing all the similarities computed using one of the measures in one of the groups.

Groups of measures producing highly correlated values can be identified in the figures, appearing as yellow rectangles (colour figures). In the case of social networks and co-authorship networks, we can see a higher correlation between degree-based measures (1–16) and measures based on the clustering coefficient (17–32).

5. Guidelines

From our literature study, theoretical framing and experiments, it appears how layer comparison measures can be very valuable and often succeed in practice to characterize the structure of multiplex networks, but they are not always straightforward to use. Therefore, in this section, we list a set of guidelines motivated by our experience acquired while testing these measures and by the results presented in the previous section.

One important aspect to consider when choosing which function to use is the distribution of values in the property matrix. Among the criteria that can be used to characterize layer property vectors and comparison functions, the following appear to be useful:

— Sparsity: A layer property vector is sparse if the number of 0s is much higher than the number of non-0 values.
— Degeneracy: A layer property vector degenerates if its values are (almost) constant. Sparsity is a special case of degeneracy.
— Linearity: A layer property vector is linear if the values in the vector and their rank are linearly correlated.
— Scale invariance: a similarity function is scale invariant if it does not (significantly) change when one or more layer property vectors are multiplied by a constant.

We now list our guidelines, divided into four main areas.

5.1. Number of measures

The number of available measures is very large, considering that the 50 options used in our experiments are only some of the measures we can obtain using different combinations of property matrices and observation functions. While the choice of the measures to be used for a specific empirical network is of course influenced by what the analyst is interested in, e.g. degree-based similarity, betweenness-based, or specific motifs that are motivated by the application context, our experiments show that different measures highlight different types of similarities.

At the same time, even during exploratory analyses where it is often useful to compute several measures to get a good overview of the data, it can be practically preferable to identify a small number of measures. This can be due to time constraints, if the data are large, but also to the need of producing results that are easy to interpret and present. The choice of which measures to use can be simplified using the correlation plots in figures 7–10. Groups of measures producing highly correlated values can be identified, and one measure for each group can be chosen. In particular, JS, KL and D divergences are similar, and JS divergence can be used from this group. Jaccard, coverage and Kulczyński are similar, and Jaccard or coverage can be used—with the latter highlighting how the non-overlapping structures are distributed across the two layers, e.g. if one layer is containing the other.

When comparing layers by comparing a single value, particular attention should be paid to the so-called discriminative power or uniqueness of the measure, i.e. the capability of a measure of taking different values on non-isomorphic networks [37]. For example, while mean is not a representative measure for non-regular distributions, it can still be used to compare two distributions, such as degree distributions. But not alone, because the same degree does not imply the same topology.

While min can be useful in general to characterize a distribution if used together with other statistical summaries, it does not appear to be very useful to compare layers where there is typically at least one node having value 0. For example, min degree is 0 for all layers for most networks. On the contrary, max can be useful, e.g. to include the size of the layers in the comparison.

5.2. Node-alignment

The choice of whether a node-aligned or generalized multiplex model should be used is often clear from the context. For example, we would typically not align nodes when layers represent different social network sites, to represent the fact that users may not have accounts on some sites, while we would typically align nodes in a multirelational network about people interacting in multiple ways, where not having edges on a layer does not imply that the person cannot interact in that specific way.

However, the choice may have a significant influence on the results of our analysis as highlighted by our experiments.

Node-alignment may lead to some degeneracy. As expected, node-existence measures become useless, but also other cases are affected, such as measures 11–16 (degree) and 27–32 (clustering coefficient).

Measures based on node existence may also help us interpreting the results of other measures. So, before using link-based measures (such as edge Jaccard) it is important to check node overlapping to understand whether comparing higher-order structures is meaningful, or whether the results will just be a consequence of the limited amount of node overlapping across layers.

Rank correlation can suffer from node-alignment because of false tie resolution, and also Pearson correlation results may become less evident, as shown by the experiments where positive and/or negative correlations are lost or decreased depending on the type of networks.

5.3. Sparsity

SMC and Hamann are only useful for non-sparse, non-degenerated cases, which in our experiments correspond to node existence on generalized networks. Russel–Rao also suffers if property vectors are sparse. As an example, these measures do not work well for triangle-existence property matrices in general.

5.4. Linearity

Having nonlinear distributions of values in the property vectors, as is the case for degree property matrices, is not problematic when computing linear correlation. Linear correlation (Pearson) is often preferable to rank correlation, which can be problematic in the case of generalized networks (because of null values) and also for node-aligned networks (because of the many nodes with the same values).

6. Conclusion

A summary of our guidelines is that there are many ways to compare layers, but (i) not all methods are always appropriate and (ii) some are often correlated, which means that if we only want a small number of layer similarities we can give priority to one for each group of related measures.

As we mentioned in the Introduction, our framework captures several measures that appeared in the literature: node activity overlapping [24], global overlapping of edges [38] and absolute binary multiplexity [39] are applications of the Russel–Rao function to node and edge existence property vectors; average edge overlaps from [25] and from [40] are, respectively, the Jaccard and coverage functions applied to edge existence. A general recommendation is to use the original names, as we do in this article: all the measures used in this work and mentioned in this paragraph are applications of existing proximity measures, most of them well known to data analysts. Calling them by their name, such as edge Jaccard, makes it simpler to understand when it is reasonable to apply them if we already know the original measure.

Also, notice that our framework allows the definition of a large number of other functions not tested in this article, also considering directed/undirected networks, weights and other mesostructures such as motifs. Other network summary functions that are not specific for multiplex networks can also be obtained as combinations of property matrices and observational functions. Examples are order (node existence + sum), size (edge existence + sum), density (edge existence + mean), average path length (dyad distance + mean), etc. We believe that splitting the problem of computing layer similarities into the two problems of (i) deciding what to observe and (ii) deciding how to compare these observations using existing generic comparison functions gives the analyst the ability to easily generate custom layer comparisons that are appropriate for the problem at hand.

Data accessibility

The experiments have been performed using the multinet library available at https://cran.r-project.org/package=multinet and 23 multilayer networks available at https://comunelab.fbk.eu/data.php.

Author's contributions

P.B., A.C. and M.M. created an initial concept for the paper; all authors developed the concept to its current state and designed the experiments; P.B. gathered and prepared all datasets; M.M. implemented and executed all experiments and simulations; all authors analysed data and discussed results, drafted, critically reviewed the manuscript and approved the final version for publication.

Competing interests

We declare we have no competing interests.

Funding

This work was partially supported by National Science Centre Poland, the decisions no. DEC-2016/21/D/ST6/02408 and DEC-2015/18/E/ST2/00560; the European Union‘s Horizon 2020 research and innovation programme under grant agreements nos. 691152 (RENOIR) and 732027 (Virt-EU); and the Polish Ministry of Science and Higher Education fund for supporting internationally co-financed projects in 2016–2019 (agreement no. 3628/H2020/2016/2).

Footnotes

Notes

1 If we only compare two rows, we can also choose the minimum and maximum values in those rows.

2 https://cran.r-project.org/package=multinet.

3 https://comunelab.fbk.eu/data.php.

Published by the Royal Society under the terms of the Creative Commons Attribution License http://creativecommons.org/licenses/by/4.0/, which permits unrestricted use, provided the original author and source are credited.

Comments

VIEW FULL TEXT DOWNLOAD PDF

This Issue

August 2018

Volume 5Issue 8

Article Information

PubMed:30224981
Published by:Royal Society
Online ISSN:2054-5703

History:

Manuscript received02/11/2017
Manuscript accepted04/07/2018
Published online08/08/2018

License:

Citations and impact

Keywords

Subjects

Your password must have 8 characters or more and contain 3 of the following:

Quantifying layer similarity in multiplex networks: a systematic study

Abstract