Interlayer link prediction in multiplex social networks: an iterative degree penalty algorithm

In several works, features have been extracted from profiles and contents. These studies have adopted machine learning techniques to predict the interlayer links across multiple OSNs [2]. Profile attributes include the username, gender, birthday, address, experience, and image, among others [44]. The username has been found to be the most important attribute in the profile and has been explored extensively. Zafarani and Liu [45] formalized the problem of mapping among identities across multiple websites, and conducted similar empirical tests on thousands of usernames across 12 social networks, thereby empirically validating several hypotheses. They further developed a supervised methodology for the same problem in Ref. [46], which extracted behavioral features of usernames based on the priori knowledge of linguistics and human behavior according to three aspects: human limitations, exogenous factors, and endogenous factors. Perito et al. [47] determined that a significant portion of the users can be linked by means of their usernames, and identified users with binary classifiers. Liu et al. [48] differentiated among users with the same usernames and proposed an unsupervised approach to match users. Among usernames, the recognition of photographs may provide a means of mapping users. Although usernames can be used to predict the interlayer links of the multiplex social network, it is difficult to use them in large-scale situations because some users may have the same username. Acquisti et al. [49] used publicly available photos for large-scale individual re-identification. However, users tend to publish different pieces of information in different OSNs  [50]. Only a handful of users may put their personal photos on different OSNs. Therefore, using photos for identification is appropriate for these specific users.

Apart from usernames and images, several researchers have focused on considering various profile attributes to improve the prediction performance [51, 52, 53, 54, 55, 56]. A heuristic approach based on using the username, e-mail, and birth city attributes was proposed by Carmagnola et al. [51]. Iofciu et al. [52] divided profile information into two types: usernames and tags. They determined that users can be identified by analyzing their tagging, and the performance can be improved by combining tags and usernames. Mu et al. [56] explored the concept of latent user space to describe the user profiles in different social platforms, so that two individuals with greater similarities would have closer profiles in the latent user space. Similar areas were also studied in Refs. [53, 54, 55]. Leveraging more profile attributes could improve the prediction performance effectively, but profile attributes may contain information which are null or are not sufficiently strong to indicate user identity.

Content attributes for individuals can reveal their activities, such as posting, mentioning, and commenting in OSNs [2]. These properties can capture unique characteristics for the interlayer link prediction of multiplex OSNs. Zheng et al. [57] extracted four types of writing-style features (syntactic, lexical, structural, and content) to identify authorship. Goga et al. [58] exploited the geo-location, timestamp, and writing style of user posts to identify accounts on different OSNs. Zafarani and Liu [59] extracted trajectory-based content features to capture the unique footprints of user activities for linking the same user accounts across platforms. Nevertheless, the methods based on content attributes often face the problem of data sparsity, because the amount of location data or posted content of different users varies significantly. These approaches are usually confined to some specific OSN applications, which makes it harder to leveraged them on a general multiplex social network.

Personal data available on OSNs are usually anonymized owing to privacy concerns, with users often removing their profile and attribute information or replacing these with fake information [40]. Therefore, using network structures to predict the interlayer links has been the focus of substantial research. Narayanan and Shmatikov [60] assumed that a natural person usually has a similar social network in the virtual world. Based on this assumption, Zhou et al. [36] developed a network structure-based method known as the Friend Relationship-based User Identification (FRUI) algorithm. The FRUI algorithm identifies the same user across different OSNs by leveraging the shared friend cycle, and requires several priori matched pairs. They subsequently proposed an approach that did not require priori matched pairs in Ref. [33]. Interlayer link prediction in a multiplex network consisting of multiple OSNs formed the maximum common subgraph problem in Ref. [61], which maximized the number of standard links to obtain one-to-one mapping. The maximum common subgraph problem is an NP-hard problem, and is therefore hardly used in real scenarios. Tan et al. [41] leveraged a hypergraph to model user relationships and correlate accounts across different OSNs by projecting the manifolds of two networks onto a commonly embedded space. Moreover, neighborhood-based network features were used for account alignment in [62]. Zhang et al. [63] proposed a joint link fusion algorithm to predict the social links and anchor links of two OSNs simultaneously. This algorithm transferred information relating to social links from one network to another. Its time complexity is approximately $O(n^{3})$. Numerous researchers have used network embedding [64], also known as representation learning [65], to predict interlayer links in recent years. Liu et al. [37] adopted a network embedding approach to align users across multiple directed OSNs. Their method embedded two OSNs into a common space to capture the social links of user accounts. Man et al. [38] proposed a supervised model to learn cross-layer mapping for interlayer link prediction, which leveraged network embedding to capture the underlying structural regularities. Zhou et al. [31] proposed an unsupervised algorithm for user identification, using network embedding and scalable nearest neighbors. A deep reinforcement learning-based framework was developed in Ref. [32], which could embed the global network structure, thereby achieving higher correlation accuracy than other network embedding methods. Similar studies can also be found in Refs. [26, 27, 28, 29, 31, 34, 35, 39]. Most of the network embedding-based methods implicitly assume that the input networks are complete without missing edges, and it is not easy to add user attribution into the representation vectors.

Other relevant approaches have combined the feature-based and structure-based methods for interlayer link prediction; for example, searching the same username from the friend lists of seed users across Facebook and Twitter [66]. Nunes et al. [67] introduced a binary classification method to classify account pairs as belonging to the same person or not. The feature vectors of the classifier were constructed by profile information, descriptions of interests, and friend lists. Kong et al. [68] studied two fully aligned OSN datasets collected from Foursquare and Twitter to determine the correspondence between different user accounts. They extracted multiple features and formulated the correspondence problem as a stable matching problem. The network structure features were one type among multiple features. Zhang et al. [69] explored a probabilistic approach for mapping individuals, in which the user friend or connection count was used as a feature. Lu et al. [24] introduced a methodology to identify customers between customer accounts, e-commerce sites, and OSN applications. The network structure was used to extract user interest features.

In the majority of combination approaches, the problem of attempting to obtain user profile features for the sake of privacy protection exists. Our study focuses on structure-based prediction. Numerous real-world OSNs exhibit a scale-free degree distribution [43]. Common matched neighbors with different degrees may have different influences on the matching degrees of nodes across two OSNs. In this study, we developed an IDP algorithm to address this issue.

To distinguish the different OSN platforms, we represent the relationship between nodes in one OSN as the graph $G^{\alpha}(V^{\alpha},E^{\alpha})$, where $V^{\alpha}$ and $E^{\alpha}\subseteq V^{\alpha}\times V^{\alpha}$ are the sets of nodes and edges of the graph $G^{\alpha}$. The elements of $E^{\alpha}$ are referred to as intralayer links. The scenario of multiple OSNs is represented by the multiplex network $\mathcal{M}=(g,c)$, where $g={\{G^{\alpha}|\alpha\in\{1,\cdots,m\}\}}$ is the set of graphs and $c={\{E^{\alpha\beta}\subseteq V^{\alpha}\times V^{\beta}|\alpha,\beta\in\{1,\cdots,m\},\alpha\neq\beta\}}$ is the set of connections between the nodes of graphs $G^{\alpha}$ and $G^{\beta}$. If there exists an edge $e^{\alpha\beta}_{ij}$ between node $v^{\alpha}_{i}$ in graph $G^{\alpha}$ and node $v^{\beta}_{j}$ in graph $G^{\beta}$, the accounts represented by the two nodes belong to the same user. The elements of $E^{\alpha\beta}$ are known as interlayer links. Each subnetwork in $g$ is referred to as a layer in multiplex network $\mathcal{M}$. An illustration of multiplex networks is provided in Fig. 1.

Prior to introducing the details of our proposed method, we present the formal definitions of various important concepts in this paper.

Definition 1: Interlayer node pair (INP). Given a multiplex network $\mathcal{M}$, if an interlayer link exists between a node $v^{\alpha}_{i}$ in layer $\alpha$ and a node $v^{\beta}_{j}$ in layer $\beta$, we refer to the pair consisting of these two nodes as an INP, which is represented by INP$(v^{\alpha}_{i}$ ,$v^{\beta}_{j})$. Moreover, the nodes belonging to the INP are known as interlayer nodes.

Definition 2: Matched interlayer node pair (MINP). Given a multiplex network $\mathcal{M}$, if a node pair consisting of node $v^{\alpha}_{i}$ in layer $\alpha$ and node $v^{\beta}_{j}$ in layer $\beta$ is matched as an INP, we refer to this pair as an MINP and denote it by MINP $(v^{\alpha}_{i}$ ,$v^{\beta}_{j})$. An MINP is not necessarily an INP, because the results calculated by the algorithm may be incorrect.

Definition 3: Priori interlayer node pair (PINP). Given a multiplex network $\mathcal{M}$, if several INPs are provided in advance, we refer to these INPs as PINPs. Furthermore, the nodes belonging to the PINP are known as priori interlayer nodes.

Definition 4: Unmatched node pair (UNP). Given a multiplex network $\mathcal{M}$, if a node $v^{\alpha}_{i}$ in layer $\alpha$ and a node $v^{\beta}_{j}$ in layer $\beta$ have not been matched, we refer to the pair consisting of these two nodes as a UNP, which is represented by UNP$(v^{\alpha}_{i}$ ,$v^{\beta}_{j})$.

Definition 5: Common matched neighbor (CMN). Given a PINP($v^{\alpha}_{i}$,$v^{\beta}_{j}$), if node $v^{\alpha}_{a}$ in layer $\alpha$ has an intralayer link with node $v^{\alpha}_{i}$, and node $v^{\beta}_{b}$ in layer $\beta$ has an intralayer link with node $v^{\beta}_{j}$, we can state that the PINP($v^{\alpha}_{i}$,$v^{\beta}_{j}$) is the CMN of nodes $v^{\alpha}_{a}$ and $v^{\beta}_{b}$.

It is worth noting that the terms graph and layer, link and connection, and interlayer node pair and interlayer link are used interchangeably in this paper.

Supposing that we have a two-layer multiplex network $\mathcal{M}$ with a small set of priori interlayer links, the purpose of the interlayer link prediction problem is to predict which node pairs are most likely to have the interlayer links.

Given a UNP $(u^{\alpha}_{i},u^{\beta}_{j})$ in the multiplex network $\mathcal{M}$, the objective function of the interlayer link prediction can be defined as follows:

where $r_{ij}$ represents the matching degree of the unmatched nodes $v^{\alpha}_{i}$ and $v^{\beta}_{j}$. The interlayer link prediction problem is converted into the calculation of $r_{ij}$ and the definition of the objective function $J$.

In a real scenario, certain people may possess two or more accounts in the same OSN application. For simplicity, we assume that these multiple accounts belong to different users. This means that the interlayer link prediction problem in this study is a one-to-one matching problem; that is, no two interlayer links share the same node.

Researchers have established that numerous natural and artificial networks exhibit certain common topological characteristics, such as small world, scale free, and core periphery [70]. The scale-free property is valuable in that the degree distribution of a scale-free network follows a power law. Zhou et al. analyzed four leading OSN sites (Delicious, Flickr, Twitter, and YouTube), and found that these sites all exhibit scale-free degree distributions [43]. This means that there exist large nodes with a small degree, as well as several nodes with a large degree. The CMNs with different degrees will have different weights for the UNP matching degrees. For example, if a person has only one friend and he or she follows an account $v^{\alpha}$ on OSN $G^{\alpha}$ and an account $v^{\beta}$ on OSN $G^{\beta}$, it is highly likely that $v^{\alpha}$ and $v^{\beta}$ belong to the same person, namely his or her friend. In contrast, if this person has many friends, it is difficult to determine whether or not the accounts that he or she follows on different OSNs belong to the same person.

Based on the above statements, we propose the principle of the degree penalty of CMNs for calculating the matching degree of the unmatched nodes, which assigns more weights to smaller-degree CMNs. We define

as the matching degree of UNP $(u^{\alpha}_{i},u^{\beta}_{j})$. In Eq. (2), $\Phi$ represents the set of PINPs, $\Gamma(u^{\alpha}_{i})$ and $\Gamma(u^{\beta}_{j})$ represent the neighbor sets of nodes $u^{\alpha}_{i}$ and $u^{\beta}_{j}$, respectively, $k$ represents the node degree, and the constraints in the equation indicate that the PINP $(v^{\alpha}_{a},v^{\beta}_{b})$ is the CMN of UNP $(u^{\alpha}_{i},u^{\beta}_{j})$. It is noteworthy that, if $k_{v^{\alpha}_{a}}=1$, $\log(k_{v^{\alpha}_{a}})$ will be equal to 0, and $\log^{-1}(k_{v^{\alpha}_{a}})$ becomes meaningless. To overcome this problem, we add 1 to each log by means of Laplace smoothing.

The degree penalty principle has the following characteristics:

(i) It can reflect the contribution of the number of CMNs to the matching degree. For any two unmatched nodes $u^{\alpha}_{i}$ and $u^{\beta}_{j}$, a greater number of CMNs results in their matching degree $r_{ij}$ being larger.

(ii) It can reflect the influence of the degree of CMNs on the matching degree. For any CMNs, a smaller degree results in the weights of these CMNs making a greater contribution to the matching degree of the UNPs connected to them.

The matching degree of each UNP can be calculated by the degree penalty principle proposed above. Given all of the nodes, interlayer links, and priori interlayer links, the question is how to obtain all matching degrees of the UNPs efficiently. We propose an approach based on matrix operation, inspired by Ref. [71].

Given a multiplex network $\mathcal{M}$, $n^{\alpha}$ and $n^{\beta}$ are denoted as the number of nodes in layers $\alpha$ and $\beta$, respectively, while $n$ is the number of PINPs. The number of unmatched nodes in layer $\alpha$ can be represented by $n^{\alpha}-n$, while the number of unmatched nodes in layer $\beta$ can be represented by $n^{\beta}-n$.

For a node $v^{\alpha}_{a}\in\varphi^{\alpha}$, where $\varphi^{\alpha}$ represents the set of priori interlayer nodes in layer $\alpha$, the degree of $v^{\alpha}_{a}$ can be expressed as

where $e^{\alpha}_{ab}$ is equal to 1 if an intralayer link exists between nodes $v^{\alpha}_{a}$ and $v^{\beta}_{b}$, and 0 otherwise.

By $h^{\alpha}_{a}=\log^{-1}(k_{v^{\alpha}_{a}}+1)$, we can rewrite Eq. (2) as

This equation will facilitate the subsequent introduction of matrix operations.

It is clear that, if PINP $(v^{\alpha}_{a},v^{\beta}_{b})$ is the CMN of UNP $(u^{\alpha}_{i},u^{\beta}_{j})$, $e^{\alpha}_{ia}$ and $e^{\beta}_{jb}$ will be equal to 1; thus, $e^{\alpha}_{ia}\cdot h^{\alpha}_{a}\cdot e^{\beta}_{jb}=h^{\alpha}_{a}$ and $e^{\alpha}_{ia}\cdot h^{\beta}_{b}\cdot e^{\beta}_{jb}=h^{\beta}_{b}$. In contrast, if PINP $(v^{\alpha}_{a},v^{\beta}_{b})$ is not the CMN of UNP $(u^{\alpha}_{i},u^{\beta}_{j})$, $e^{\alpha}_{ia}$ or $e^{\beta}_{jb}$ will be equal to 0; thus, $e^{\alpha}_{ia}\cdot h^{\alpha}_{a}\cdot e^{\beta}_{jb}=0$ and $e^{\alpha}_{ia}\cdot h^{\beta}_{b}\cdot e^{\beta}_{jb}=0$. Therefore, Eq. (4) can be replaced with

If node $v^{\alpha}_{a}$ is a matched interlayer node in layer $\alpha$, a counterpart node must exist in layer $\beta$, and vice versa. Naturally, it is possible to make the PINPs uniform, as follows: $(v^{\alpha}_{1}$, $v^{\beta}_{1}),(v^{\alpha}_{2}$, $v^{\beta}_{2}),\cdots,(v^{\alpha}_{n}$, $v^{\beta}_{n})$. Therefore, Eq. (5) can be rewritten as

Using the vector form, Eq. (6) can be represented as

It is known that the Hadamard product of $A\equiv[a_{ij}]$ and $B\equiv[b_{ij}]$ with the same dimensions is the matrix $A\circ B=[a_{ij}b_{ij}]$. Therefore, $[h^{\alpha}_{1}\cdot e^{\alpha}_{i1},h^{\alpha}_{2}\cdot e^{\alpha}_{i2},\cdots,h^{\alpha}_{n}\cdot e^{\alpha}_{in}]$ can be represented as $[h^{\alpha}_{1},h^{\alpha}_{2},\cdots,h^{\alpha}_{n}]\circ[e^{\alpha}_{i1},e^{\alpha}_{i2},\cdots,e^{\alpha}_{in}]$. Denoting $\bm{h}^{\alpha}_{i}=[h^{\alpha}_{1},h^{\alpha}_{2},\cdots,h^{\alpha}_{n}]^{T}$, $\bm{h}^{\beta}_{j}=[h^{\beta}_{1},h^{\beta}_{2},\cdots,h^{\beta}_{n}]^{T}$, $\bm{e}^{\alpha}_{i}=[e^{\alpha}_{i1},e^{\alpha}_{i2},\cdots,e^{\alpha}_{in}]^{T}$, $\bm{e}^{\beta}_{j}=[e^{\beta}_{1j},e^{\beta}_{2j},\cdots,e^{\beta}_{nj}]^{T}$, where $(\cdot)^{T}$ is the transposition of $(\cdot)$, Eq. (7) can be rewritten as

Using Eq. (8), the matching degree of UNP $(u^{\alpha}_{i},u^{\beta}_{j})$ is represented by the form of the vector operation. Then, we can express the matching degree of all UNPs in the matrix operation form. In a similar manner, we denote $\bm{H}^{\alpha}=[\bm{h}^{\alpha}_{1},\quad\bm{h}^{\alpha}_{2},\quad\cdots,\quad\bm{h}^{\alpha}_{n^{\alpha}-n}]$, $\bm{E}^{\alpha}=[\bm{e}^{\alpha}_{1},\bm{e}^{\alpha}_{2},\cdots,\bm{e}^{\alpha}_{n^{\alpha}-n}]$, $\bm{H}^{\beta}=[\bm{h}^{\beta}_{1},\bm{h}^{\beta}_{2},\cdots,\bm{h}^{\beta}_{n^{\beta}-n}]$, $\bm{E}^{\beta}=[\bm{e}^{\beta}_{1},\bm{e}^{\beta}_{2},\cdots,\bm{e}^{\beta}_{n^{\beta}-n}]$. The matching degree of all UNPs can be calculated as follows:

It is worth noting that $\bm{H}^{\alpha}$ consists of $n^{\alpha}-n$ copies of $\bm{h}^{\alpha}_{i}$, because $\bm{h}^{\alpha}_{1}=\bm{h}^{\alpha}_{2}=\cdots=\bm{h}^{\alpha}_{n}=[h^{\alpha}_{1},h^{\alpha}_{2},\cdots,h^{\alpha}_{n}]^{T}$. Similarly, $\bm{H}^{\beta}$ consists of $n^{\beta}-n$ copies of $\bm{h}^{\beta}_{j}$. Moreover, $\bm{E}^{\alpha}$ and $\bm{E}^{\beta}$ are the submatrices of the adjacency matrix of $G^{\alpha}$ and $G^{\beta}$, respectively. Each row of the submatrix represents one of the matched interlayer nodes, while each column represents one of the unmatched nodes.

Based on the above statements, the four matrices $\bm{H}^{\alpha}$, $\bm{E}^{\alpha}$, $\bm{E}^{\beta}$, and $\bm{H}^{\beta}$ can be obtained. The matching degree of all unmatched nodes between the different layers of the multiplex network $\mathcal{M}$ can be calculated efficiently.

After obtaining the values of all elements of the matching degree matrix $\bm{R}$, we need to determine which UNPs can be selected as MINPs. This means that we should formulate the objective function $J$. This function clarifies that a node pair can be selected as an MINP when its matching degree satisfies certain conditions. A larger value of the matching degree $r_{ij}$ indicates a higher probability that the node pair ($u^{\alpha}_{i}$, $u^{\beta}_{j}$) is the MINP. Therefore, we define the objective function as:

where (i) $\mathds{1}(\cdot)$ is an indicator function that takes 1 if the condition inside the parenthesis is true, and zero otherwise; (ii) $\max(\cdot)$ is the maximum function that takes the maximum value inside the parenthesis; (iii) $\psi^{\alpha}$ and $\psi^{\beta}$ are the sets of matched interlayer nodes in layers $\alpha$ and $\beta$, respectively; and (iv) $\delta$ is a control parameter that takes a value from 0 to 1. When $\delta=1$, only the UNPs with the maximum value of the matching degree can be selected as MINPs. When $\delta\in(0,1)$, the UNPs with a matching degree greater than $\delta\cdot\max(\bm{R})$ can be selected as MINPs. Moreover, when $\delta=0$, all of the UNPs can be selected as MINPs. It is obvious that a smaller value of $\delta$ means that additional UNPs are selected as MINPs, and hence, the accuracy is lower. In contrast, a larger value of $\delta$ indicates that less UNPs are selected as MINPs, and hence, the efficiency is lower. The constraints in Eq. (10) are used to ensure that each unmatched node is matched only once.

In the previous steps, the degree penalty principle and matrix operation are leveraged to calculate the matching degree matrix $\bm{R}$ for all unmatched nodes among the different layers in the multiplex network $\mathcal{M}$ and the node pairs with matching degrees greater than $\delta$ times $\max(\bm{R})$ are selected as MINPs. By performing these steps once, only one or several UNPs can be selected as MINPs. Therefore, we propose an iterative strategy, known as the IDP algorithm, to achieve additional MINPs.

Denoting $\Psi$ as the set of MINPs, we can add elements of $\Psi$ to $\Phi$. Moreover, we execute the steps introduced above again to identify more MINPs. This strategy can be executed iteratively until all of the unmatched nodes in one layer are matched or all of the matching degrees of the UNPs are equal to 0.

The details of our suggested IDP algorithm for interlayer link prediction are presented in Algorithm 1. In each iteration, the time complexity of the algorithm mainly depends on the calculation of the matching degree matrix $\bm{R}$ of Algorithm 1, which is matrix multiplication. Provided $n^{\alpha}-n=n^{\beta}-n=m$, the running time of the matrix multiplication is $nm^{2}/q$, where $q$ is the number of compute nodes [72]. For the whole algorithm, provided that $z$ is the average number of selected matched interlayer nodes per iteration, the time complexity of IDP is $O(nm^{3}/zp)$. Moreover, an illustration of the procedure of the IDP algorithm is presented in Fig. 2.

We verify the effectiveness of our proposed IDP algorithm on both artificial scale-free and real-world networks. The steps for constructing the artificial scale-free multiplex networks are as follows:

(i) We create a Barabási-Albett (BA) [73] network, the degree distribution of which follows a power law distribution, according to the generation step proposed in Ref. [73]. This is an original network for the following steps. (ii) Using $G^{org}(V^{org},E^{org})$ to represent the original BA network and $s$ to represent the percentage of remaining nodes, we construct two networks, $G^{\alpha}=G^{org}$ and $G^{\beta}=G^{org}$. (iii) For a node $v^{\alpha}_{i}$ in $G^{\alpha}$, we generate a random value $a_{1}$ with a uniform distribution in [0,1]. If $a_{1}\geq s$, the node $v^{\alpha}_{i}$ is discarded, as are all of the intralayer links connected with node $v^{\alpha}_{i}$. Otherwise, node $v^{\alpha}_{i}$ is preserved in $G^{\alpha}$. (iv) Similarly, for a node $v^{\beta}_{i}$ in $G^{\beta}$, we generate a random value $a_{2}$ with a uniform distribution in [0,1]. If $a_{2}\geq s$, the node $v^{\beta}_{i}$ is discarded, as are all of the intralayer links connected with node $v^{\beta}_{i}$. Otherwise, node $v^{\beta}_{i}$ is preserved in $G^{\beta}$. (v) We determine whether to add an interlayer link between $v^{\alpha}_{i}$ and $v^{\beta}_{i}$. If $a_{1}<s$ and $a_{2}<s$ simultaneously, the counterpart nodes of node $v^{org}_{i}$, namely $v^{\alpha}_{i}$ and $v^{\beta}_{i}$, remain in layers $\alpha$ and $\beta$. Therefore, we add an interlayer link between $v^{\alpha}_{i}$ and $v^{\beta}_{i}$. Otherwise, we do nothing. (vi) Steps (iii) to (v) are repeated until all of the nodes in $G^{\alpha}$ and $G^{\beta}$ are traversed.

The real-world datasets contain eight networks downloaded from the websites Stanford Large Network Dataset Collection [74], Link Prediction Group [75], and Network Analysis of Advogato [76]. In a real scenario, OSN application users are often wary of their privacy. Therefore, it is difficult to obtain complete ground truth. To address this problem, we perform experiments on self-matching real-world networks[77]. The solution for obtaining the self-matching real-world multiplex network is the same as that for the BA multiplex network described above.

After constructing the multiplex networks, we use the FRUI [36], NS [78], and INOE [37] as the baselines for the experiments, where FRUI is the closest to the IDP algorithm for the interlayer link prediction as a state of the art. Each experiment is repeated 500 times. For the sake of reducing computational time in each experiment, the adjacency matrices constructed by the matched nodes and unmatched nodes of layer $\alpha$ and $\beta$ in the $t$th iteration will join to $\bm{E}^{\alpha}$ and $\bm{E}^{\beta}$, respectively. This could avoid reconstructing $\bm{E}^{\alpha}$ and $\bm{E}^{\beta}$ in $(t+1)$th iteration.

The time complexity of the baseline and IDP algorithms is presented in Table 2. In particular, $K$ is the negative sampling number, $D$ is the representation dimension, $|E^{\alpha}|$ and $|E^{\beta}|$ are the number of intralayer links in layer $\alpha$ and $\beta$, respectively. $d^{\alpha}$ and $d^{\beta}$ are the maximal degrees of nodes in layer $\alpha$ and $\beta$, respectively.

We employ the recall, precision, and F1  [2] as the metrics for evaluating the performance of the FRUI and IDP algorithms, which are widely used in information retrieval, machine learning, and data mining, among others. The recall can be formulated as

where TP and FN indicate the number of true positives and false negatives, respectively [48]. In this study, the recall reflects the ratio of INPs that the algorithm correctly predicts to the number of INPs that need to be predicted. The precision can be formulated as

where FP indicates the number of false positives [48]. In this study, the precision reflects the ratio of INPs that the algorithm correctly predicts to all of the results predicted by the algorithm. $F1$ is the harmonic mean between the precision and recall [79]. It can be formulated as

where the range for $F1$ is [0,1]. For these three metrics, a higher value indicates superior performance of the algorithm performance.

In this subsection, we outline the manner in which to determine an optimal value of $\delta$, and demonstrate the comparison results of the baseline and IDP algorithms on different average node degrees, node overlaps, and network sizes.

We use eight real-world networks to construct self-matching real-world multiplex networks, and evaluate the FRUI and IDP algorithms on these multiplex networks. The statistical characteristics of the eight real-world networks are presented in Table 5. Formally, we represent each of the eight real-world networks as an undirected graph. In these experiments, $s=0.5$ and $p$ increases from 0.01 to 0.1 by 0.01.

Figures  6(a) to (f) display the recall, precision, and F1 rates of the FRUI and IDP algorithms of the eight real-world networks. The following observations can be made. The IDP algorithm outperforms the FRUI algorithm. For a given real-world network, the recall, precision, and F1 rates of the FRUI and IDP algorithms increase with $p$. The reasons are the same as those in Figs. 3(a) to (c). For a given $p$, different real-world networks exhibit varying performances, because the network sizes, average degrees, and clustering coefficients of the real-world networks differ.

Figures  6(g) to (l) illustrate the percentages of improvement under the same experimental settings as those in Figs. 6(a) to (f). The following observations can be made. The recall rate increases by a maximum of 36.6% and an average of 7.0%. The precision rate increases by a maximum of 19.0% and an average of 3.8%. The F1 rate increases by a maximum of 25.0% and an average of 5.0%. On real-world network 2, 3, 4, and 8, the percentages of improvement exhibit a trend of first increasing and then decreasing with an increase in $p$. On real-world networks 1, 5, 6, and 7, the percentages of improvement exhibit a trend of first increasing and then decreasing with an increase in $p$. The reasons are the same as those in Figs. 3(d) to (f).