An effective community-based link prediction model for improving accuracy in social networks

Abstract

Link prediction plays a predominant role in complex network analysis. It indicates to determine the probability of the presence of future links that depends on available information. The existing standard classical similarity indices-based link prediction models considered the neighbour nodes have a similar effect towards link probability. Nevertheless, the common neighbor nodes residing in different communities may vary in real-world networks. In this paper, a novel community information-based link prediction model has been proposed in which every neighboring node’s community information (community centrality) has been considered to predict the link between the given node pair. In the proposed model, the given social network graph can be divided into different communities and community centrality is calculated for every derived community based on degree, closeness, and betweenness basic graph centrality measures. Afterward, the new community centrality-based similarity indices have been introduced to compute the community centralities which are applied to nine existing basic similarity indices. The empirical analysis on 13 real-world social networks datasets manifests that the proposed model yields better prediction accuracy of 97% rather than existing models. Moreover, the proposed model is parallelized efficiently to work on large complex networks using Spark GraphX Big Data-based parallel Graph processing technique and it attains a lesser execution time of 250 seconds.

Keywords

Link prediction social network performance evaluation prediction accuracy parallel louvain algorithm

1 Introduction

A social network is an interaction of social objects and a set of connections between these objects. A graph data structure represents the social network in that vertices means actors and edges (links) illustrate the relationships or interactions among actors [1]. The cooperation and interactions among the people have become convenient due to the speedy improvement of the internet. Online social networks like Facebook, WhatsApp, and Twitter play a vital role in our daily lives which provide us a platform to transfer details with each other [2].

The social networks generate vast volumes of data every day and have some distinct characteristics like quality, semi-structure, and direct interaction between real-world entities on social networks. Link prediction is a significant factor in estimating link mining and forecast the information about the links to be formed in the future based on node interactions [3]. It is not solely utilized in social networks however it may be applied in alternative fields. Moreover, it has often accustomed to discover interactions among proteins in the bioinformatics field [4].

Link prediction has been utilized to produce advice systems in electronic commerce. It facilitates to search the hidden terrorist criminal gangs in the security field. Anomaly detection is one of the ways to identify malicious users over the network [5]. This model presented an advanced community detection system to perform link prediction techniques and a Bulk Synchronous Parallel programming model. Subsequently, the information diffusion and influences the network happenings to predict cascade related to viral events. It is associated with several areas and there are many types of correlation algorithms planned to resolve link prediction [6].

A few of the existing link prediction methods developed so far are based on the neighboring nodes considering only the adjacent information rather than the community information of each neighboring node. Even though some of the methods considering the community information, but they have categorized entire communities as inter and intra-communities and they failed to concentrate on each and every community individually. Because of, not considering each community separately, the participation of the individual communities for predicting the new link between the nodes is missed.

Typically, in real-world social networks, the participation of every individual node for predicting the future link between the two nodes is based on the impact of communities of the neighboring nodes. For example, in real-world social networks such as Twitter, Facebook, and LinkedIn, the friend request is not only based on simply nearby locations additionally occupation, interests, working area are also considered and also the friend request may be based on the current trends on social networks. Similarly, the proposed work considering the neighborhood community information to predict the future link among the two nodes, and the node that belongs to the community having the high importance in the entire network can participate more than the other neighboring nodes during the link prediction process. So in this paper, the community-based linkage prediction approach has been proposed by restructuring the existing similarity indices by using every community importance. To find the community importance, the new Community Centrality (CC) measure is proposed based on basic graph measures.

The various novel contribution of this paper is as follows:

A novel CC measure has been proposed which is based on degree, closeness, and betweenness centralities of graph network. Due to this novel consideration, the proposed method achieved a higher precision value for larger datasets.

According to the new CC, each neighboring node’s importance is determined towards their community. This strategy helps to attain maximum accuracy during the evaluation process.

The standard similarity metrics are redefined based on CC and the new parallel community-based link prediction method is proposed. The 13 real-world dataset networks has been employed to evaluate the proposed method.

The structure of this paper is organized as follows: The related work of link prediction is summarized in section 2. The preliminary concept utilized in the proposed method is explained in section 3. Section 4 depicts the proposed methodology. The performance evaluation is described in Section 5. The results and performance analysis are demonstrated in section 6. Finally, the conclusion is enumerated in section 7.

2 Related works

The following section summarizes the various background studies related to link prediction. A novel graph-based convolutional neural network model has been proposed for multi-relative link prediction in multimodal networks [7]. In this model, the side effects of two drugs are identified when they are used together by considering the side effect as the link prediction problem to find the side effect (link), the features of the drugs only utilized rather than neighboring information of the represented graph.

Most of the link prediction techniques are roughly categorized into two sets: probabilistic-based and similarity-based methods. A few of the existing probabilistic methods require the information of vertex attributes that are added to the identified network formation. However, it requires more computational time to derive the link prediction which is applied in massive networks [8]. Next, similarity-based methods usually allocate a score to each pair of nodes to calculate its existing probability. It is a widely unitized technique due to its fairness of prediction and its effectiveness in computation [9]. These methods are often categorized into native data-based (local indices) and global data-based (global indices). Local indices are effective than global indices as lesser calculation complexity, but the local index accuracy is smaller than global indices.

Most of the existing works concentrated on local indices since local indices are easier to implement. It takes lesser time complexity even the given real-world networks are extremely large. Nevertheless, most of the classical local indices except Resource Allocation (RA) and Adamic-Adar (AA) based on familiar neighbours assume that every common neighbour equally participates in fining the link likelihood among the vertex that it constraints the index performance. It is observed from the artificial and real-world network experimentation that the similarity-based index performance enhances due to the growth of the community structural networks [10]. So, the intra-community neighbors alone has been considered for identifying further link among the nodes. The significance of network structure is identified and several researchers have projected numerous link prediction strategies depends on cluster or community information to enhance the prediction accuracy [11, 12].

Another way to improve the prediction accuracy, common neighbors, and RA indices is the utilization of the intra-community information rather than inter-community neighbours of the node pair [13]. This model failed to concentrate on recall metrics in the network which paves the way to attain the lower efficiency. In [14], a new WIC methodology has been developed to enhance the prediction efficiency using data from within cluster common neighbors instead of considering all neighbors from the clusters. This method causes lesser accuracy in the social network.

In [15], a novel model has been introduced to address the link prediction in the social network. It depends on the conditional probability that both the vertices belong to the same cluster by using the neighbors from the given cluster. This model failed to concentrate on the precision metrics in the network. In [16], a novel methodology has been presented that depends on Intra-Com data and RA index with an accuracy of 10 real networks. The model leads to attaining lower prediction accuracy due to higher algorithm complexity. Furthermore, the missing link is not properly identified throughout the network. In [17], the community compliant link prediction has been presented in which the links are divided into an inter-community and intra-community category. By giving more importance to intra-community links with the tuning parameter, the missing link is identified.

Although most of the existing models employed the effect of Intra community familiar neighbors but neglect the impact of inter-community neighbors and also they have used community labels for identifying inter and intra community neighbors. Further, they do not focus on each neighboring node based on their community importance. To overcome this, the proposed model considered both inter-community and intra-community neighborhood nodes of each pair. It also anticipated the significance of the neighboring nodes based on their community importance. The significance of communities will be identified through the CC measurements of their leader node.

3 Preliminaries

Initially, the preliminaries describe the concepts of the link prediction problem and the objective of the proposed work. Then, three commonly utilized centrality measures of the graph and community detection technique have been discussed in this section.

3.1 Link prediction problem

Assume an undirected graph G (V, E) where V and E are the set of vertices and edges. In this graph, the proposed model taking all possible edges $((| V | - 1) * \frac{| V |}{2})$ . among all pairs of vertices which can be represented as Universal Set S. Here, |V| represents the number of vertices. The link prediction problem goal is to predict the future links from given graph G is illustrated in Fig. 1.

Fig. 1

(a). Network Data E.

Fig. 1

(b). Training Set E^T.

Fig. 1

(c). Nonexistent Set E^non.

Fig. 1

(d). (d). Probe Set E^P.

Consider the missing link set E^non, which contains all unavailable (non-existent) links (x, y), where x, y ∈ V are disconnected node pairs. Then, the set of common neighbours between node pairs x, y is denoted by λ_x,y = Γ (x) ∩ Γ (y). Wherever Γ (x) indicates set of x’s neighbours and Γ (y) indicates set of y’s neighbours. To evaluate the probability of forming the new link betwe disconnected nodes, the similarity Score Sx, y is calculated between every pair of vertices by using a link prediction algorithm. Hence, the possibility of linking nodes (x, y) is raised because of the risen score Sx, y. The whole graph links are randomly split into 2 sets to calculate the accuracy of a link prediction technique. One is training set E^T, which is considered know information, and another one is prob set E^P which is utilized for testing the algorithm. Certainly, E^T ∪ E^P = E, E^T ∩ E^P = φ and E^T ∪ E^P ∪ E^non = S. The main objective is to define an efficient technique that generates the similarity score of every edge in E^P greater than the links in E^non.

3.2 Degree centrality

Degree centrality is a simple centrality measure that counts the number of neighbors node. This centrality can be mathematically represented in Equation (1) which can be normalized between 0 and 1 by dividing it by several anticipated links (n-1) of each node [18]. $Cd (v) = \frac{\deg (v)}{n - 1} .$ (1) where deg(v) represents the number of actual links of node v and n-1 indicates the number of anticipated links of each vertex.

3.3 Closeness centrality

In a graph network, the centrality of the closeness of a node is the shortest path with an average length among neighborhood nodes. The central node is closer to other nodes can be illustrated as [19] $C (v) = \frac{N - 1}{\sum_{u} dist (v, u)} .$ (2) where dist (v,u) denotes the shortest path distance among vertices v and u. N implies the total nodes in a given network graph.

3.4 Betweenness centrality

Betweenness centrality establishes the node functions as a bridge among the shortest path between two nodes. It is the measure quantifying control measurement for human enabled communication between the humans. The vertices have a high probability of choosing the random condition of the shortest path among n-linear selected vertices with a consideration of high betweenness.

The betweenness centrality can be mathematically described as follows [20]: ${CB}_{v = S \neq v \neq tV} = \sum ρ_{st} (v) / ρ_{st} .$ (3) where ρ_st is the total available shortest paths from vertex ‘s’ to vertex ‘t’ and ρ_st (v) is the total number of possible paths pass via vertex ‘v’.

3.5 Louvain community detection algorithm

Girvan-Newman algorithm has been introduced for community detection to detect the communities on a large-scalreal-world network graph [21]. It is a greedy optimization method that attempts to enhance the modularity of a partition of the graph. The algorithm consists of two phases, which are repeated until the modularity cannot be improved. During the first phase, every node is observed as an individual cluster.

For each node p (p = 1, …, N) its neighbours q (q = 1, …, N) are examined for whether the modularity improves if p is detached from its cluster and into the cluster of node q is allocated. Then the node p is assigned to the respective cluster, which improves the growth in modularity. Nevertheless, it employs the method within the case of positive growth. If no positive growth of modularity is not generally attained, the node p stays in the same cluster. The operation will be performed repeatedly and successively executed for all nodes until no enhancement in modularity can be attained. A node is often considered and allocated several times. Hence the first phase terminates when a local maximum has been reached that is if no single node movement can increase the modularity.

Based on the clusters derived within the first phase, a replacement network is made within the 2nd phase, whose nodes are now the clusters derived from the earlier phase. To derive the weights for the links among the clusters, the sum of the weights of the links among the nodes of two respective clusters is employed. If such a replacement network was derived with meta-cluster then the process of the first phase is provided to the successive network and therefore modularity score can be further improved. The combination of both phases is named as pass. Such passes are repeatedly administered until there is no more change within the cluster and maximal modularity is attained.

3.6 GraphX

GraphX is HADOOP’s Spark-based Parallel graph processing API that is utilized for graph-relevant techniques such as PageRank, Shortest path, community detection, recommendation system, and link finding [23]. It integrates the benefits of graph-parallel and data-parallel systems by representing the graph-relevant operations inside Spark Framework. It improves the Spark RDD by launching a special Graph at the high level of abstraction; that graph is called a directed multigraph in which properties are attached with both vertices and edges [24, 25].

The other speedy graph processing method such as Graph Lab and Giraph maintains Spark’s flexibility, fault tolerance. Graphs are used to represent or store different information such as geospatial data, social network data, email communication networks, co-author networks, paper citation networks, and web page link structures. In GraphX property, the Graph concept is introduced in the edge table and vertex table. The vertex table will be associated with vertices of a graph where it contains vertex id and properties such as community label, degree, and other Meta information. The edge table is associated with the entire graph, and it contains source node id, destination node id, and properties of edges such as relationship, similarity score.

4 Proposed methodology

In the proposed model, the given social network graph is initially partitioned into communities using the proposed parallel Louvain community detection algorithm. From the derived communities, the CC of each community is calculated using the degree, closeness, and betweenness centralities of basic graph measures. By using the calculated CC, the modified CC-based similarity indices are derived. In the CC-form of local indices, more importance is specified to the intra-community neighbors than inter-community neighbors. The derived CC-form of the local index is employed in the proposed parallel Spark-based link prediction to predict the future link among the nodes pair for the given input graph.

4.1 Proposed parallel louvain community detection algorithm

This section introduces the parallel Louvain method to find out the communities using GraphX API. The core part of our similar Louvain method is depicted in Algorithm 1. Note that whenever the modularity value is largest, a good community separation is achieved. In the Louvain method, every vertex needs to investigate its neighbours communities and select a new community depends on function to extend the evaluated switch in modularity value. The parallel method considers every node as the choice concurrently in lieu of a sequential manner and updating the graph status after every variation. Since the obtained result is from a concurrent way where a few results will be inaccurate and do not increase modularity. After successive iterations, the community selections are more stable and hence, the outcome is achieved which is nearly close to the results of the sequential algorithm.

In Algorithm 1, lines 1-2 reads the input graph from edge list files into the Spark environment in RDD format. Like the original serial Louvain algorithm, the proposed parallel version is also a greedy method, so it continuously performs the graph partition process until getting a good modularity score. So that the initial value for the modularity score is set as low as possible Q_new = -1 in line 3. Lines 4-17 represent the entire process of the Louvain algorithm with a parallel approach. In lines 5-6 the entire graph is randomly partitioned as K subgraphs and the current modularity scores of all subgraphs are calculated separately and aggregated as Q_curr before the Louvain phases are started.

Algorithm 1: Parallel Louvain Algorithm
Input: list of edges of Network Graph (G) and Threshold
ρ for modularity gain
Output: Graph with community labels
1. edge _ RDD ⇒ sc . read _ text _ File (EdgeList);
2. Graph ⇐ Graph . read _ from _ Edges (edge _ RDD);
3. initially set: Qnew ⇐ 1;
4. while (1) do
5. K subgraph ⇐ Graph. Parallelize
$(P rocesor_count = K)$ ;
6. Q_curr ⇐ Modularity _ calculate (Ksubgraphs);
7. foreach processor ∈ Kdo
8. Louvain.Initial_Com(subgraph);
9. Louvain.Modularity_Optimization (subgraph);
10. end for
11. Qnew ⇐ Modularity _ calculate (Ksubgraph);
12. ifQnew - Qcurr < ρthen
13. break;
14. end if
15. Q_new ⇐ Q_curr;
16. Graph ⇐ Louvain _ aggregation _ process
(K subgraph);
17. end while
18. returnGraph

The two core phases of the Louvain method are performed on each subgraph in a parallel manner is described in lines 7-10. In line 11, a new modularity score is calculated combined by merging all sub-graphs. In line 12, the improvement in the partition will be checked. If the improvement in new partitions is not more than the threshold value (ρ = 0.01) the algorithm is stopped and returns the final partitions as communities. If the improvement is more than ρ (ρ = 0.01), then in line 15, the new modularity score is updated, and in line 16, the new complete graph with newly identified clusters is constructed from the new subgraph partitions generated after the complete iteration of the Louvain algorithm in order to take the next iteration of the complete Louvain phases. All sub-graphs are aggregated to generate a new clustered graph.

The parallel Louvain algorithm is also generating the same number of communities as a serial algorithm with a similar structure. Since the serial Louvain algorithm operates on each node of the graph individually, so we have parallelized the Louvain method in order to generate the communities as quickly as possible. And also, this community information is the input of our link prediction process. The execution time of serial Louvain and the proposed parallel Louvain algorithms on five larger data sets are demonstrated in Fig. 2. Since the proposed method uses the same idea of serial Louvain, the number of communities derived by parallel Louvain is similar to the serial version.

Fig. 2

Comparison between Serial and Parallel Louvain Algorithm.

From Fig. 2, it is observed that the execution time of the serial Louvain algorithm is increased rapidly from few minutes to few hours when the network size is increased, and the possibility to reaches the time limit and memory limit exceeds while processing the huge real-time data sets having millions of nodes. To mitigate this problem, the proposed Spark-based parallel Louvain method has been employed to derive the communities and the execution time of our parallel Louvain algorithm on a 4-node spark cluster on five large data sets are depicted in Fig. 2. The execution time of this cluster is rapidly reduced and nearly 10 times better than the serial algorithm since the spark is based on in-memory computation.

4.2 Derivation of proposed CC-based similarity indices

Network Graph G is divided into k number of communities by the proposed parallel Louvain method, and the labels C1, C2, … Ck (k > 1) are utilized to definite the derived communities, and x^Ci represents that node x associated to a distinct community with label Ci. β_x,y specifies the set of familiar neighbors of node pair (x, y), described by β_x,y = {w|w ∈ Γ (x) ∩ Γ (y)}. Then, the set of common neighbors belong to community Ci of (x, y) is described by $λ_{x, y}^{Ci} {= {w | w}^{Ci}}$ and $λ_{x, y}^{Ci}$ specifies the set of all common neighbors of a pair (x, y) belongs to community Cj. Here, $λ_{x, y} = λ_{x, y}^{C 1} \cup λ_{x, y}^{C 2} \dots$ . $\cup λ_{x, y}^{Cn}$ .

For example, consider a simple network with 2 communities C1, C2 in Fig. 3. A node pair (3, 5) having three common neighbors, i.e., λ_x,y = {2, 4, 6}, $λ_{x, y}^{C 1} = {2, 4}$ and $λ_{x, y}^{C 2} = {6}$ . In this work, it is assumed that every common neighbor will contribute to making a future link among the vertex pair, and its contribution is based on their community importance. Generally, the common neighbor belongs to the community, which has high importance in an entire network having a high impact than neighbor belongs to other community. So, the possibility of interaction between pairs of vertices is always based on the overall community importance of neighbor nodes. The overall importance of the community can be calculated based on their centrality measures.

Fig. 3

A simple network with 2 community structures.

After deriving the communities using a parallel Louvain algorithm, the significance of each community is calculated using three centralities (degree, closeness, betweenness) as demonstrated in Algorithm 2. Here, communities derived from parallel Louvain algorithm are taken as input and the community centralities of each community are generated. The degree, closeness, and betweenness centralities of each node of every community are calculated in lines 5-8. In this work, the average of betweenness and closeness is taken as global centrality since it is based on entire graph structures and it is estimated at line 9. Since the betweenness and closeness centrality are the global importance of a particular node in the entire graph so that we have named their average value as global centrality. Subsequently, we have considering the both local and global importance of each node in the graph, we have combined both by taking the average of them and we named as structural centrality of a node. The structural centrality can be evaluated at line 10. The largest structural centrality of a node that belongs to a particular community Ci is taken as community centrality of that community Ci; this entire process is described in lines 11-14. Finally, lines 16-18 represent the community centrality value of each community is normalized between 0 and 1.

Then consider the community centrality of each community will be CC₁, CC₂, …, CC_n. The CC-based similarity measure is illustrated in Equation (4). Afterward, the entire communities are divided into two categories intra-community C_intra and inter-community C_inter. $S_{x, y}^{CN - CC} = {cc}_{intra} * ∣ λ_{xy}^{c_{intra}} ∣ + \sum_{inter = 0}^{n} {cc}_{inter} * ∣ λ_{xy}^{c_{inter}} ∣ .$ (4) where, $\sum_{i = 1}^{n} {CC}_{i} = 1$ . The intra-community neighbors are important because they have more impact on making the relationship among the two nodes. So, the above equation can be modified as, $\begin{matrix} S_{x, y}^{CN - CC} = α {* cc}_{intra} * ∣ λ_{xy}^{c_{intra}} ∣ + (1 - α) \\ \sum_{inter = 0}^{n} {cc}_{inter} * ∣ λ_{xy}^{c_{inter}} ∣ . \end{matrix}$ (5) where 0 < = α < =1. A sime network with 2 community structures.

Algorithm 2: CC Identification
Input: Community set C = {C1, C2, C3, … Cn} Ci ∈ G (V, E),
Adjacency Matrix A
Output: Structural centrality of each community
1. C_score = {φ};
2. CC = {φ};
3. for each Ci ∈ C
4. Sc = 0;
5. for each vi ∈ V
6. $DCvi = \frac{\deg (v)}{N - 1}$ ; //LC: Local Centrality
7. CCvi= $\frac{N - 1}{\sum_{u} d (v, u)}$ ; //Closeness centrality
8. BC_{vi=S≠vi≠tV} = ρ_st (vi)/ρ_st; //Betwenness centrality
9. GCi = avg(CCvi+BC_vi); //GC: Global Centrality
10. SCi = avg(DCi+GCi); //Structural Cenatrality
11. if SCi > Sc then
a. Sc = SCi;
12. end if
13. C_score = C_score ∪ Sc;
14. end for
15. Sum = ΣC_score;
16. for C_score(i) ∈ C_score
17. CC = CC ∪ (C_score(i)/Sum);
18. end for
19. end for

Even in Equation (4), different communities participated during the link prediction process but it provides equal importance to all the communities. But in a real-world scenario, the neighboring nodes within the same community influences more than other neighboring nodes during the link prediction process. So that we have given more importance to intra-community neighbors rather than inter-community neighbors. So that we have restructured Equation (4) as Equation (5). The term cc_intra. represents the community centrality of the Intra community to which the predicting node pair belongs.

4.3 Standard similarity indices and proposed CC-based similarity indices

In order to predict the links between the nodes, 9 local similarity indices depend on familiar neighbors are frequently utilized in link prediction problems and they are listed in Table 1. The proposed work identified the new link prediction indices CC formulated by connecting the similarity measure suggested in Equation (5) with the local similarity indices described in Table 1. Unlike the community-based link prediction techniques [26 –29], the CC-based similarity algorithm can be applied on some specific local indices but applied for all 9 local indices and evolve the family of CC-based local similarity indices. The local indices (9) and CC forms are demonstrated in Table 2.

Table 1
Nine standard similarity indices [47 –50]

Sl. No Standard measures Expression

1 Common Neighbors (CN) $S_{x, y}^{CN} = ∣ Λ_{x, y} ∣$ .

2 Salton (Sal) $S_{x, y}^{sal} = \frac{∣ Λ_{x, y} ∣}{\sqrt{k (x) * k (y)}}$ .

3 Jaccard (Jac) $S_{x, y}^{jac} = \frac{∣ Λ_{x, y} ∣}{| Γ (x) \cup Γ (y) |}$ .

4 Serensen (Sor) $S_{x, y}^{sar} = \frac{2 ∣ Λ_{x, y} ∣}{k (x) + k (y)}$

5 Hub Promoted Index (HPI) $S_{x, y}^{HPI} = \frac{∣ Λ_{x, y} ∣}{\min {k (x), k (y)}}$ .

6 Hub Depressed Index (HDI) $S_{x, y}^{HDI} = \frac{∣ Λ_{x, y} ∣}{\max {k (x), k (y)}}$ .

7 Leicht-Holme-Newman Index (LHN) $S_{x, y}^{LHN} = \frac{∣ Λ_{x, y} ∣}{k (x) * k (y)}$

8 Adamic – Adar (AA) $S_{x, y}^{AA} = \sum_{z ɛ Λ_{x, y}} \frac{1}{log k (z)}$ .

9 Resource Allocation (RA) $S_{x, y}^{RA} = \sum_{z ɛ Λ_{x, y}} \frac{1}{k (z)}$

Sl. No	Standard measures	Expression
1	Common Neighbors (CN)	$S_{x, y}^{CN} = ∣ Λ_{x, y} ∣$ .
2	Salton (Sal)	$S_{x, y}^{sal} = \frac{∣ Λ_{x, y} ∣}{\sqrt{k (x) * k (y)}}$ .
3	Jaccard (Jac)	$S_{x, y}^{jac} = \frac{∣ Λ_{x, y} ∣}{\| Γ (x) \cup Γ (y) \|}$ .
4	Serensen (Sor)	$S_{x, y}^{sar} = \frac{2 ∣ Λ_{x, y} ∣}{k (x) + k (y)}$
5	Hub Promoted Index (HPI)	$S_{x, y}^{HPI} = \frac{∣ Λ_{x, y} ∣}{\min {k (x), k (y)}}$ .
6	Hub Depressed Index (HDI)	$S_{x, y}^{HDI} = \frac{∣ Λ_{x, y} ∣}{\max {k (x), k (y)}}$ .
7	Leicht-Holme-Newman Index (LHN)	$S_{x, y}^{LHN} = \frac{∣ Λ_{x, y} ∣}{k (x) * k (y)}$
8	Adamic – Adar (AA)	$S_{x, y}^{AA} = \sum_{z ɛ Λ_{x, y}} \frac{1}{log k (z)}$ .
9	Resource Allocation (RA)	$S_{x, y}^{RA} = \sum_{z ɛ Λ_{x, y}} \frac{1}{k (z)}$

Table 2

Proposed CC-based 9 local indices

CN-CC	$S_{x, y}^{CN - CC} = α ({cc}_{intra} * ∣ λ_{xy}^{C_{intra}} ∣) + (1 - α) \sum_{inter = 0}^{n} {cc}_{inter} * ∣ λ_{xy}^{c_{inter}} ∣$
Sal-CC	$S_{x, y}^{CN - CC} = \frac{α ({cc}_{intra} * ∣ λ_{xy}^{C_{intra}} ∣) + (1 - α) \sum_{inter = 0}^{n} {cc}_{inter} * ∣ λ_{xy}^{c_{inter}} ∣}{\sqrt{k (x) + k (y)}}$ .
Jac-CC	$S_{x, y}^{CN - CC} = \frac{α ({cc}_{intra} * ∣ λ_{xy}^{C_{intra}} ∣) + (1 - α) \sum_{inter = 0}^{n} {cc}_{inter} * ∣ λ_{xy}^{c_{inter}} ∣}{∣ Γ (x) \cup Γ (y) ∣}$ .
Sor-CC	$S_{x, y}^{CN - CC} = \frac{2 (α * {cc}_{intra} * ∣ λ_{xy}^{c_{intra}} ∣ + (1 - α) \sum_{inter = 0}^{n} {cc}_{inter} * ∣ λ_{xy}^{c_{inter}} ∣)}{k (x) + k (y)}$ .
HPI-CC	$S_{x, y}^{CN - CC} = \frac{α ({cc}_{intra} * ∣ λ_{xy}^{C_{intra}} ∣) + (1 - α) \sum_{inter = 0}^{n} {cc}_{inter} * ∣ λ_{xy}^{c_{inter}} ∣}{\min (k (x), k (y))}$ .
HDI-CC	$S_{x, y}^{CN - CC} = \frac{α ({cc}_{intra} * ∣ λ_{xy}^{C_{intra}} ∣) + (1 - α) \sum_{inter = 0}^{n} {cc}_{inter} * ∣ λ_{xy}^{c_{inter}} ∣}{\max (k (x), k (y))}$
LHN-CC	$S_{x, y}^{CN - CC} = \frac{α ({cc}_{intra} * ∣ λ_{xy}^{C_{intra}} ∣) + (1 - α) \sum_{inter = 0}^{n} {cc}_{inter} * ∣ λ_{xy}^{c_{inter}} ∣}{(k (x) * k (y))}$
AA-CC	$S_{x, y}^{CN - CC} = α * {cc}_{intra} \sum_{z \in λ_{xy}^{C_{int ra}}} \frac{1}{log k (z)} + (1 - α) \sum_{inter = 0}^{n} {cc}_{inter} \sum_{z \in λ_{xy}^{C_{int ra}}} \frac{1}{log k (z)}$
RA-CC	$S_{x, y}^{CN - CC} = α * {cc}_{intra} \sum_{z \in λ_{xy}^{C_{int ra}}} \frac{1}{k (z)} + (1 - α) \sum_{inter = 0}^{n} {cc}_{inter} \sum_{z \in λ_{xy}^{C_{int ra}}} \frac{1}{k (z)}$

4.4 Proposed parallel CC-based link prediction method

The conventional link prediction techniques can be carried out serially and contain a wide variety of matrix calculations. For massive graphs, the matrix calculations yield more time and are even hard to compute, and the memory limit will be exceeded. Therefore, the link prediction method has been parallelized based on GraphX [24]. The principle process of parallel CC-based link prediction is depicted in Algorithm 3. Every node transmits and receives the node information as well as community details to and from their neighborhoods during every super step. After that, the similarity score of every predicted link can be calculated during every core step.

Algorithm 3: Parallel CC-based Link Prediction Algorithm
Input: Edge List, Vertex list with Community label and CC
Output: AUC
1. edge _ RDD ⇐ sc . read _ text _ file (EdgeList);
2. vertex _ RDD ⇐ sc . read _ text _ File (VertexId, CCvalue);
3. G ⇐ Graph . read _ from _ Edges (edge _ RDD);
4. G ⇐ ParallelLouvain (G);
5. [ED^T, ED^P] ⇐ Edge _ Divide (edge _ RDD);
6. Ksubgraph ⇐ Graph . parallize (processor _ count = K);
7. for each processor p_ido
8. for each v ∈ V do
9. Γ (v) ⇐ neighbours _ nd (v);
10. k (v) ⇐ degree _ find (v);
11. for each w ∈ V (v ≠ w) do
12. (v, w) ⇐ form an link;
13. if (v, w) ∉ ED^T then
14. ED^New ⇐ (v, w);
15. end if
16. end for
17. end for
18. for each (v, w) ∈ ED^Newdo
19. for each vi ∈ Λ_x,y
20. if commity _ label (vi) = = C_i
21. $Λ_{x, y}^{Ci} \Leftarrow v_{i}$ ;
22. end for
23. Sx, y ⇐ CalculateSim (y);
24. end for
25. end for
26. AUC _ calculation (ED^New);
27. returnAUC

Once communities are derived using the Parallel Louvain algorithm, the edge RDD is split into two sets as training RDD edges (EDT) and testing RDD edges (EDP). Next, the input graph is split into K Processors where each processor gets one partition and performs similarity calculations for links that include both non-existent and testing edges. There are 4 predominant super steps in this parallel technique, as shown in Fig. 4. From Fig. 4, it can be noticed that during super step 1, every node sends its precise ID and community detail to all its neighbourhood nodes.

Fig. 4

Graphx CC-based link prediction process.

During super step 2, every node composes a message based on the details collected from its neighbour nodes, including neighbours list and their ID, community label, and node degree, and then pass this composed message to all its neighbour’s node. Meantime, a new edge RDD (ED^New) is constructed to sre these testing edges along with non-existing edges and the link has similarity attributes. During super step 3, every node gets both node and community details about all the feasible triplets. The neighbor details collected over various paths mean that there are many familiar neighbours among the current node and neighbors.During super step 4, at every node x, the number of familiar neighbours belong to every possible community Ci is counted as $Λ_{x, y}^{Ci}$ . Subsequently, for every link (x,y) in the set ED^New, the similarity score is calculated corresponding to our proposed version in Table 2. For some of the links in ED^New, their similarity score is zero since there are no common neighbours among the two vertices of all links. Finally, the Area Under the receiver operating characteristic Curve (AUC) [14] score is computed on the root processor and it consumes lesser time to complete.

5 Performance evaluation

The empirical evaluation of the proposed CC-based link prediction on 10 real word networks from different fields is demonstrated in the following section. The running time evaluations of the proposed parallel approach on 4 large networks are discussed.

5.1 Simulation setup

The experiment can be conducted using a 10-fold CV to validate the prediction efficiency of the anticipated technique. Consequently, the noticed links set E is randomly partitioned as 2 sets in every round where one part will be Training set E^T that contains 90 percent of the links and another part is testing set E^P that includes the remaining 10 percent of links.

The training set has been employed to produce the communities for every network by using a parallel Louvain algorithm. Afterward, the similarity scores are computed for all probe links (E^p), non-existent links using every local index, W forms, and CC forms. Here the value for the parameter L is set based on the number of links having a similarity value larger than the average similarity score among all the links from E^p and E^N^on. Finally, the AUC measurement is exploited to measure the prediction efficiency of all indices. The matching pairs are randomly selected from non-existent links and probe links n = 8000 times for the AUC computation process.

5.2 Dataset

The 13 real-world networks have been employed to evaluate the proposed CC-based local indices are enumerated in Table 3. The basic graph network properties are depicted in Table 4. |V| and |E| represents the number of nodes and edges, D_avg is the average network graph degree, the clustering coefficient of the network is signified by C_coef and PLavg implies the average path of the social network.

Table 3
Description of 13 real world data sets

Data Set Description

C.elegans [30] CSV file represents Neural network of C. elegans

Dolphins [31] CSV file represents frequent interactions between 62 dolphins.

Football [32] CSV file represents a network graph of football games among the division IA colleges in America.

Karate [30] CSV file represents friendship network graph of karate club in Zachary

Metabolic [33] CSV file represents the metabolic network of Caenorhabditis elegans

Net Science [34] CSV file represents the social network graph that describes co authorship between scientists.

Political Blogs [35] CSV file represents a network graph for hyperlinks among the web logs about US politics.

Power [30] CSV file represents a geographical power grid network of western states from USA

USA Air [43] CSV file represents a geographical network structure of US air transportation system

Yeast [36] CSV file represents biology network graph which describes the interaction between proteins.

Ca-AstroPh [44] CSV file represents the scientific collaborations among authors and papers submitted to Astro Physics category.

Soc-Epinions1 [45] CSV file represents who-trust-whom online social network shows consumer review site Epinions.com.

Amazon0601 [46] CSV file represents product co-purchasing network based on Customers Who Bought This Item.

Data Set	Description
C.elegans [30]	CSV file represents Neural network of C. elegans
Dolphins [31]	CSV file represents frequent interactions between 62 dolphins.
Football [32]	CSV file represents a network graph of football games among the division IA colleges in America.
Karate [30]	CSV file represents friendship network graph of karate club in Zachary
Metabolic [33]	CSV file represents the metabolic network of Caenorhabditis elegans
Net Science [34]	CSV file represents the social network graph that describes co authorship between scientists.
Political Blogs [35]	CSV file represents a network graph for hyperlinks among the web logs about US politics.
Power [30]	CSV file represents a geographical power grid network of western states from USA
USA Air [43]	CSV file represents a geographical network structure of US air transportation system
Yeast [36]	CSV file represents biology network graph which describes the interaction between proteins.
Ca-AstroPh [44]	CSV file represents the scientific collaborations among authors and papers submitted to Astro Physics category.
Soc-Epinions1 [45]	CSV file represents who-trust-whom online social network shows consumer review site Epinions.com.
Amazon0601 [46]	CSV file represents product co-purchasing network based on Customers Who Bought This Item.

Table 4

Graph Properties of 13 real world data sets

Networks	\|V\|	\|E\|	D_avg	C-coef	PL_avg	Communities count
C.elegans	297	2345	15.791	0.169	3.992	20
Football	115	613	10.661	0.403	2.508	15
Dolphin	62	159	5.129	0.303	3.357	10
Karathe	34	78	4.588	0.285	1.274	2
NS	1589	2742	3.451	0.878	5.823	334
PB	1490	025	25.537	0.172	3.39	27
Metabolic	453	2040	9.007	0.327	2.522	41
Power	4941	6594	2.669	0.107	18.989	167
US Air	332	2126	12.807	0.313	2.41	28
Yeast	2375	11693	9.847	0.153	4.14	27
Ca-AstroPh	18772	198110	14	0.6306	40.25	384
Soc-Epinions1	75877	508836	14	0.1378	110.25	410
Amazon0601	403394	3387388	21	0.4177	350.52	812

5.3 Evaluation metrics

To measure the accuracy of the proposed link prediction model, the popular metric AUC is utilized and observed for the given score of non-observed edges. The probability that randomly selected testing edges from set E^P yields a larger score than a randomly chosen non-existent edge from E^N^on. $AUC = \frac{x_{1} + 0.5 x_{2}}{n} .$ (6) where x₁ represents among n independent experiments the number of times the testing edges having better value rather unavailable edges. x₂ denotes the number of edges having an identical value from both sets. The precision and recall measures are derived from calculating the accuracy of the proposed model as follows [48]: $Precision = \frac{l}{L} .$ (7) $Recall = \frac{l}{| E^{p} |}$ (8) where l. indicates the number of top similarity links belongs to the testing set E^P, L implies the top L links with top similarity score from both training and testing sets. (i.e., E^P and E^N^on), and |E^P| signifies the number of links taken from the testing set.

6 Results and discussions

The proposed CC-based indices model is initially compared with 9 primary local indices. Additionally, the proposed model has been compared against the W-form link prediction technique in which only within-cluster familiar neighbours are utilized [37]. The investigation can be performed on the CC form of each local indices with αarameter from α = 0 to α = 1 to examine how well the intra-community common neighbours contribute to the link prediction process. The CC form produces results nearly the same as local indices at α = 0.5. Typically, when the α value increases from 0 to 1, it may be observed that the AUC value initially increases drastically a then gradually slows down and finally drops. For example, the CN-CC and RA-CC are taken for consideration and this drift will be noticeable among the majority of 10 data sets designated in Figs. 5 and 6.

Fig. 5

a. AUC results of RA-CC on first 5 data sets.

Fig. 5

b. AUC results of RA-CC on second 5 data sets.

From Figs. 5 and 6, it is manifest that the AUC value of CN-CC increases faster than RA-CC values. When the α value exceeds 0.1, the AUC value of CN-CC increases immediately and reaches the highest value at α = 0.8. It gradually decreases when the α value goes beyond the value of 0.8 and reaches the least value when α = 1. The AUC value of the first 5 real-time datasets achieved the value of 0.8702 whereas the next 5 different datasets obtained the value of 0.8675.

Fig. 6

a. AUC results of CN-CC on first 5 data sets.

Fig. 6

b. AUC results of CN-CC on second 5 data sets.

Similarly, the AUC score of RA-CC reaches the highest value when the α value reaches 0.6 and gradually decreases when α > 0.6 and reaches to least value at α = 1. Moreover, both CN-CC and RA-CC have good prediction efficiency on each of the 13 network data sets when α ∈ (0.6, 0.8). Specifically, in RA-CC, there is a remarkable enhancement on AUC score when α > 0.5 rather than when α < 0.5. Nonetheless, the prediction efficiency of both CN-CC and RA-CC reaches the much least value when α = 1, which is less than the prediction accuracy of primary indices.

Since all other inter-community common neighbours are not considered during the link prediction task at α = 1, some salient details are missing for the prediction process and finally result in the worst prediction accuracy. The AUC results of CC forms of other indices are nearly identical to those of CN-CC and RN-CC, indicating that intra-community neighbours have more effect on link prediction than neighbours from other communities even they also participated in the link prediction process. It is valuable to involve every neighbour from different communities with their community importance individually and prioritize familiar intra-community neighbours from other community neighbours to quantify the performance of the overall link prediction process.

Table 5 illustrates all CC forms’ prediction accuracy using AUC on 10 real-world networks. An enormous value of AUC on each data set is represented in bold font. Every CC-based local index’s specified results are achieved based on the optimal parameter α∈ (0, 1) subject to the maximum AUC on each network. Initially, all CC-based indices have better accuracy on link prediction than their standard indices on the 13 networks data sets.

Table 5

AUC values of each similarity indices on ten larger real-world data sets

AUC	C.elegans	Dolphins	Football	Karate	Metabolic	NS	PB	Power	USAir	Yeast
CN	0.8472	0.7752	0.8445	0.7173	0.9202	0.9358	0.9176	0.5878	0.9355	0.8925
CN-W	0.7417	0.7506	0.8386	0.7326	0.7377	0.9317	0.8917	0.5869	0.9508	0.8584
CN-CC	0.8575	0.7897	0.8587	0.7523	0.9340	0.9406	0.9209	0.5891	0.9438	0.8932
Sal	0.7989	0.7703	0.8554	0.6612	0.8133	0.9355	0.8744	0.5883	0.9105	0.8916
Sal-W	0.7269	0.7431	0.8397	0.6928	0.7284	0.9319	0.8566	0.5866	0.7374	0.8577
Sal-CC	0.8186	0.7890	0.8665	0.7106	0.8602	0.9408	0.8791	0.5896	0.9099	0.8927
Jac	0.7921	0.7759	0.8556	0.6460	0.7759	0.9356	0.8717	0.5879	0.9001	0.8922
Jac-W	0.7271	0.7478	0.8400	0.6859	0.7272	0.9318	0.8565	0.5868	0.7379	0.8577
Jac-CC	0.8144	0.7940	0.8667	0.7014	0.8428	0.9403	0.8780	0.5894	0.8997	0.8925
Sor	0.7921	0.7759	0.8556	0.6464	0.7774	0.9353	0.8724	0.5876	0.8997	0.8917
Sor-W	0.7267	0.7475	0.8397	0.6848	0.7265	0.9316	0.8565	0.5864	0.7376	0.8574
Sor-CC	0.8150	0.7940	0.8664	0.7020	0.8433	0.9403	0.8782	0.5895	0.8997	0.8927
HPI	0.8061	0.7587	0.8535	0.7285	0.9107	0.9356	0.8528	0.5879	0.8716	0.8908
HPI-W	0.7286	0.7346	0.8398	0.7305	0.7362	0.9316	0.8393	0.5866	0.7328	0.8567
HPI-CC	0.8253	0.7805	0.8653	0.7532	0.9165	0.9405	0.8601	0.5897	0.8823	0.8920
HDI	0.7806	0.7776	0.8547	0.6309	0.7638	0.9357	0.8690	0.5879	0.8932	0.8920
HDI-W	0.7260	0.7499	0.8396	0.6804	0.7263	0.9316	0.8536	0.5862	0.7377	0.8574
HDI-CC	0.8087	0.7971	0.8663	0.6962	0.8354	0.9403	0.8755	0.5897	0.8949	0.8925
LHN	0.7246	0.7581	0.8573	0.6354	0.7393	0.9352	0.7607	0.5879	0.7702	0.8880
LHN-W	0.7130	0.7352	0.8408	0.6803	0.7256	0.9314	0.7682	0.5868	0.7197	0.8550
LHN-CC	0.7803	0.7531	0.8689	0.6965	0.8207	0.9401	0.7869	0.5892	0.8230	0.8897
AA	0.8633	0.7794	0.8443	0.7455	0.9517	0.9358	0.9213	0.5882	0.9468	0.8932
AA-W	0.7448	0.7519	0.8386	0.7505	0.7432	0.9324	0.8937	0.5869	0.7528	0.8586
AA-CC	0.8675	0.7989	0.8582	0.7721	0.9540	0.9407	0.9233	0.5895	0.9506	0.8940
RA	0.8675	0.7779	0.8443	0.7533	0.9565	0.9358	0.9223	0.5878	0.9530	0.8933
RA-R	0.7454	0.7514	0.8384	0.7555	0.7436	0.9322	0.8947	0.5865	0.7531	0.8587
RA-CC	0.8702	0.7982	0.8579	0.7795	0.9578	0.9411	0.9247	0.5896	0.9541	0.8941

The enhancement is apparent among Metabolic and karate, which can be associated with their topological structures. Next, the CC forms of local indices have the best accuracy on link prediction rather than corresponding W forms on the 13 social networks data sets. Because the W forms of indices only considering the intra familiar neighbours, which are merely equivalent to CC forms during α = 1. Additionally, all W forms have poor accuracy on link prediction than their primary indices on 9 of the 13 networks excluding the Karate, Ca-AstroPh, Soc-Epinions 1, and Amazon 0601 when α = 1. Thus, the proposed CC-based local indices are experimentally verified to be an efficient technique for link prediction problems.

Tables 6 and 7 describes the prediction accuracy of our proposed modified Similarity indices based on the precision and recall results along with basic default indices and their W form. The proposed CC form has superior precision and recall value on 9 data sets among the ten small-scale networks, particularly the CN-CC form has attained the best outcomes on 5 datasets. Moreover, nearly all CCs form having superior prediction outcomes than their primary standard indices and W form on 10 datasets. Finally, the proposed CC-based local indices are demonstrated experimentally to be an efficient technique for link prediction.

Table 6

Precision values of each similarity on ten larger real-world data sets

Precision	C.elegans	Dolphins	Football	Karate	Metabolic	NS	PB	Power	USAir	Yeast
CN	0.6804	0.7486	0.8271	0.5771	0.6651	0.8917	0.6352	0.6108	0.7834	0.6166
CN-W	0.6779	0.7399	0.8225	0.6559	0.6677	0.8872	0.6316	0.6101	0.6525	0.6223
CN-CC	0.7	0.754	0.8241	0.6844	0.6674	0.8953	0.6353	0.6167	0.7868	0.6295
Sal	0.579	0.642	0.8334	0.37	0.5059	0.8336	0.5561	0.5318	0.4577	0.6095
Sal-W	0.5744	0.6346	0.8304	0.3701	0.5019	0.8327	0.5554	0.538	0.4218	0.6118
Sal-CC	0.5795	0.6394	0.8485	0.373	0.505	0.8383	0.5575	0.5471	0.4998	0.6133
Jac	0.5831	0.6706	0.8397	0.3701	0.5006	0.8229	0.5591	0.5259	0.4849	0.6107
Jac-W	0.5832	0.6686	0.8376	0.3701	0.5029	0.823	0.561	0.5334	0.4322	0.6122
Jac-CC	0.5855	0.6773	0.8517	0.3744	0.5037	0.8279	0.5622	0.5395	0.5032	0.6134
Sor	0.5831	0.6706	0.8398	0.3701	0.5002	0.8229	0.5591	0.5289	0.4849	0.6107
Sor-W	0.5833	0.6673	0.8379	0.3701	0.4993	0.823	0.5609	0.5274	0.4278	0.6122
Sor-CC	0.5839	0.6761	0.8545	0.3744	0.5002	0.8279	0.5622	0.5334	0.5028	0.6134
HPI	0.5702	0.574	0.8518	0.733	0.6316	0.8604	0.4886	0.5531	0.5499	0.6079
HPI-W	0.5654	0.5728	0.8548	0.6886	0.5812	0.8594	0.4925	0.5577	0.4696	0.6108
HPI-CC	0.5697	0.5768	0.8614	0.7473	0.6408	0.865	0.4922	0.5622	0.5517	0.6114
HDI	0.5827	0.6801	0.842	0.3716	0.5031	0.8118	0.5575	0.5311	0.5069	0.6104
HDI-W	0.5847	0.6814	0.8334	0.3716	0.4985	0.8124	0.5586	0.5258	0.4513	0.6122
HDI-CC	0.5896	0.6834	0.8511	0.383	0.4989	0.8166	0.5595	0.5365	0.5081	0.6134
LHN	0.5581	0.5606	0.9035	0.3773	0.4923	0.7718	0.4567	0.5137	0.4109	0.5716
LHN-W	0.5587	0.5614	0.8987	0.3773	0.4873	0.7745	0.4571	0.5168	0.4112	0.6047
LHN-CC	0.5589	0.5694	0.9169	0.3815	0.4904	0.778	0.4573	0.5244	0.4108	0.6053
AA	0.6637	0.6639	0.7638	0.5444	0.7058	0.8642	0.6314	0.5615	0.7925	0.6199
AA-W	0.6677	0.6821	0.7689	0.5516	0.7219	0.8619	0.6303	0.5577	0.6739	0.6173
AA-CC	0.6683	0.6981	0.7771	0.5887	0.7455	0.8692	0.632	0.5654	0.8042	0.6218
RA	0.6611	0.644	0.762	0.5273	0.7846	0.8647	0.6326	0.5661	0.8614	0.6228
RA-W	0.6652	0.6668	0.7673	0.5473	0.7333	0.8624	0.6332	0.5638	0.7305	0.6178
RA-CC	0.6653	0.6954	0.7771	0.5601	0.801	0.8705	0.6345	0.5683	0.8612	0.6237

Table 7

Recall values of each similarity on ten larger real-world data sets

Recall	C.elegans	Dolphins	Football	Karate	Metabolic	NS	PB	Power	USAir	Yeast
CN	0.4674	0.5476	0.5931	0.4225	0.4506	0.7239	0.3923	0.4107	0.6374	0.4826
CN-W	0.4649	0.5389	0.5885	0.5013	0.4532	0.7194	0.3886	0.41	0.5065	0.4883
CN-CC	0.487	0.553	0.5901	0.5298	0.4529	0.7275	0.3923	0.4166	0.6408	0.4955
Sal	0.366	0.441	0.5994	0.2154	0.2914	0.6658	0.3131	0.3317	0.3117	0.4755
Sal-W	0.3614	0.4336	0.5964	0.2155	0.2874	0.6649	0.3124	0.3379	0.2758	0.4778
Sal-CC	0.3665	0.4384	0.6145	0.2184	0.2905	0.6705	0.3145	0.347	0.3538	0.4793
Jac	0.3701	0.4696	0.6057	0.2155	0.2861	0.6551	0.3161	0.3258	0.3389	0.4767
Jac-W	0.3702	0.4676	0.6036	0.2155	0.2884	0.6552	0.318	0.3333	0.2862	0.4782
Jac-CC	0.3725	0.4763	0.6177	0.2198	0.2892	0.6601	0.3192	0.3394	0.3572	0.4794
Sor	0.3701	0.4696	0.6058	0.2155	0.2857	0.6551	0.3161	0.3288	0.3389	0.4767
Sor-W	0.3703	0.4663	0.6039	0.2155	0.2848	0.6552	0.3179	0.3273	0.2818	0.4782
Sor-CC	0.3709	0.4751	0.6205	0.2198	0.2857	0.6601	0.3192	0.3333	0.3568	0.4794
HPI	0.3572	0.373	0.6178	0.5784	0.4171	0.6926	0.2456	0.353	0.4039	0.4739
HPI-W	0.3524	0.3718	0.6208	0.534	0.3667	0.6916	0.2495	0.3576	0.3236	0.4768
HPI-CC	0.3567	0.3758	0.6274	0.5927	0.4263	0.6972	0.2492	0.3621	0.4057	0.4774
HDI	0.3697	0.4791	0.608	0.217	0.2886	0.644	0.3145	0.331	0.3609	0.4764
HDI-W	0.3717	0.4804	0.5994	0.217	0.284	0.6446	0.3156	0.3257	0.3053	0.4782
HDI-CC	0.3766	0.4824	0.6171	0.2284	0.2844	0.6488	0.3165	0.3364	0.3621	0.4794
LHN	0.3451	0.3596	0.6695	0.2227	0.2778	0.604	0.2137	0.3136	0.2649	0.4376
LHN-W	0.3457	0.3604	0.6647	0.2227	0.2728	0.6067	0.2141	0.3167	0.2652	0.4707
LHN-CC	0.3459	0.3684	0.6829	0.2269	0.2759	0.6102	0.2143	0.3243	0.2648	0.4713
AA	0.4507	0.4629	0.5298	0.3898	0.4913	0.6964	0.3884	0.3614	0.6465	0.4859
AA-W	0.4547	0.4811	0.5349	0.397	0.5074	0.6941	0.3873	0.3576	0.5279	0.4833
AA-CC	0.4553	0.4971	0.5431	0.4341	0.531	0.7014	0.389	0.3653	0.6582	0.4878
RA	0.4481	0.443	0.528	0.3727	0.5701	0.6969	0.3896	0.366	0.7154	0.4888
RA-W	0.4522	0.4658	0.5333	0.3927	0.5188	0.6946	0.3902	0.3637	0.5845	0.4838
RA-CC	0.4523	0.4944	0.5431	0.4055	0.5865	0.7027	0.3915	0.3682	0.7152	0.4897

The experiments have been implemented on Spark environment with 1,2,4,8 and 16 nodes cluster. Each system has similar hardware: Intel i5 3.1 GHz processor, 16 GB RAM, and 1TB HD. The Spark version utilized is spark 1.6. The proposed parallel CC-Based Link Prediction method is simulated with an overall of 13 datasets. The execution time of the proposed approach over 3 larger data sets, Ca-AstroPh, Soc-Epinions 1, Amazon0601 is depicted in Fig. 7 and the AUC value of these data sets for RA, CA, RA-W, and CA-W along with the proposed RA-CC and CA-CC are exhibited in Table 8. Here, the execution time ranges from a few hundred seconds to a few thousand seconds and it rises relatively linearly with the increases in the size of the network.

Fig. 7

Execution time of proposed method on 3 large networks.

Table 8

AUC value of the proposed method over existing methods

Methods	Dolphins	Karate	Metabolic	NS	PB	USAir	Yeast	Ca-AstroPh	Soc-Epinions1	Amazon0601
GNN	0.7121	0.7218	0.9415	0.9318	0.8918	0.9415	0.8212	0.9710	0.8901	0.9065
DICN	0.7300	0.7654	0.9214	0.9747	0.8995	0.9367	0.8278	0.8914	0.8238	0.8912
NCC	0.7943	0.7044	0.9114	0.9194	0.9014	0.9416	0.6866	0.8654	0.8324	0.8247
RA-CC	0.7982	0.7795	0.9578	0.9411	0.9247	0.9541	0.8941	0.9738	0.8601	0.9005

The running time reduces with the growth of cluster size, which is clearer on the larger datasets. The running time of all the datasets is decreased at a cluster with 4 nodes less than 50% of the execution time at a single node cluster. Moreover, the speed of running time is reduced slowly when the cluster size exceeds 8. These results inferred that the proposed CC-form has a massive advantage compared to the serial algorithm. The improvement increases more as the parallelism grows where the number of nodes to be chosen is based on the size of the datasets. When the number of nodes within the cluster goes beyond a particular number then the performance enhancement is not apparent.

The execution efficiency of the proposed parallel CC-based link prediction method has been evaluated using the speedup metric. The speed of every spark cluster with different sizes can be calculated using the following equation. $speedup (C_{size}) = \frac{T_{size}}{T_{1}}$ (9) where C_size represents the cluster with different sizes, T_size indicates the execution time of the proposed link prediction method in the cluster with different sizes, T₁ denotes the execution time of the proposed link prediction method in a single node cluster.

The speedup of the proposed parallel algorithm for different size clusters is demonstrated in Fig. 8. According to Fig. 8, it is evident that the speedup of spark clusters is started to double at cluster size = 2 and the doubling is continued till to reach the cluster size = 8. Afterward, the speedup is increased only gradually for the cluster size with 10 and 16. From this, it is clear that if the number of processors in the spark clusters is increased, the speedup is reached the maximum value. The speedup is not improved even the processors further increase in the spark clusters.

Fig. 8

Speedup of different clusters on 3 larger datasets.

Another vital contribution of the current research is to compare the proposed method over the other existing methods like Graph Neural Network (GNN) [48], Direct-Indirect Common Neighbours (DICN) [49], and Node-Coupling Clustering (NCC) [50]. We have compared one of our proposed Community based metric RA-CC with the above-mentioned existing method in terms of the AUC value that is illustrated in Table 9. From Table 9, it is clear that the proposed RA-CC having a superior AUC value on 7 data sets than the other 3 methods. Since GNN only uses the direct neighboring nodes to find the link likelihood between the node pairs, so community information has not participated during the link prediction process. Even though DICN utilizes the second-order common neighboring nodes along with direct common neighboring nodes during the link prediction process, the performance is not better than the proposed CC-based method.

Table 9

AUC values of 3 large-scale data sets

AUC	Ca-AstroPh	Soc-Epinions1	Amazon0601
CN	0.9506	0.8372	0.8723
CN-W	0.9516	0.8478	0.8910
CN-CC	0.9681	0.8527	0.8927
RA	0.9675	0.8481	0.8835
RA-W	0.9710	0.8511	0.8890
RA-CC	0.9738	0.8601	0.9005

The results also expose that the GNN method having a better AUC value in two larger data sets Soc-Epinions1 and Amazon0601 compare to other methods. Since nodes are sparsely distributed in the large-scale networks, the score-based methods including the proposed method are struggling to reach a high score than the GNN method. Since GNN is an unsupervised learning method, the feature vector for GNN is formed using 9 standard similarity indices. Finally, it is manifest that the proposed RA-CC provides better prediction accuracy in all small-scale and medium-scale networks, it also yields good accuracy in large-scale networks than the other 2 score-based methods.

7 Conclusion

In this work, the proposed model was derived from a group of link prediction indices based on CC. The neighbour from different communities are participated along with their community importance and specified the preference for intra-community neighbours than other community neighbours. The proposed model yields better predictions about the future link by restructuring the 9 classical indices. The experiments have been evaluated on 13 real-world datasets. It demonstrates that the prediction performance is enhanced with the influence of all common community neighbours and it turns into poor while considering the intra-community common neighbours. It was compared with the w-form of local similarity indices then the proposed CC-based link prediction has achieved better prediction accuracy. Furthermore, the proposed model has superior precision and recall value on 9 datasets among the ten small-scale networks. These experiment results manifest that the proposed model has been considered an efficient technique for link prediction.

References

Singh

A.K.

and Kailasam

, Link prediction-based influence maximization in online social networks, Neurocomputing 453 (2021), 151–163.

Wei

, Li

, Zongmin

and Weinan

, TPH: A Three-Phase-based Heuristic algorithm for influence maximization in social networks, Journal of Intelligent & Fuzzy Systems 39 (2020), 4393–4403.

Longjie

, Lu

, Hongsheng

and Xiaoyun

, Towards effective link prediction: A hybrid similarity model, Journal of Intelligent & Fuzzy Systems 40(3) (2021), 4013–4026.

Beleva

V.G.

, et al., Network analysis of protein adaptation: Modeling the functional impact of multiple mutations, Molecular Biology and Evolution 35(6) (2018), 1507–1519.

Kagan

, Elovichi

and Fire

, Generic anomalous vertices detection utilizing a link prediction algorithm, Social Network Analysis and Mining 8(1) (2018), 1–12.

and Szymanski

, Predicting Viral News Events in Online Media, IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPSW) (2017), 1447–1456.

Zitnik

, Agrawal

and Leskovec

, Modeling polypharmacy side effects with graph convolutional networks, Bioinformatics 34 (2018), 457–466.

Zhang

Q.M.

, Lu

L.Y.

, Wang

W.Q.

, Zhu

Y.X.

and Zhou

, Potential theory for directed networks, PLoS ONE 8(55437) (2013), 1–13.

Yang

and Zhang

X.D.

, Predicting missing links in complex networks based on common neighbors and distance, Sci Rep 6(38208) (2016), 1–12.

10.

Feng

, Zhao

J.C.

and Xu

, Link prediction in complex networks: A clustering perspective, Eur Phys J B 85(1) (2012), 1–11.

11.

Deylami

H.A.

and Asadpour

, Link prediction in social networks using hierarchical community detection, Proc 7th Conf Inf Knowl Technol 6 (2015), 1–5.

12.

, He

, Huang

, Zhang

, Shi

and Zhou

, Node-coupling clustering approaches for link prediction, Knowl-Based Syst 89 (2015), 669–680.

13.

Soundarajan

and Hopcroft

, Using community information to improve the precision of link prediction methods, Proc Int Conf World Wide Web (2012), 607–608.

14.

Valverde-Rebaza

J.C.

and de Andrade Lopes

, Link prediction in complex networks based on cluster information, in Advances in Artificial Intelligence 4 (2012), 92–101.

15.

F.H.

, He

, Huang

G.Y.

, Zhang

Y.C.

and Shi

, A clustering-based link prediction method in social networks, Proc Int Conf Comput Sci 29 (2014), 432–442.

16.

Wang

, Ma

, Liu

, Yuan

, Shen

and Li

, A vertex similarity index using community information to improve link prediction accuracy, IEEE Int Conf Syst Man Cybern (2017), 1–12.

17.

Jeon

and Kim

, Community-adaptive link prediction, Proc Int Conf Data Mining (2017), 1–30.

18.

Rusinowska

, Berghammer

, De Swart

and Grabisch

, Social networks: Prestige, centrality, and influence, Relational and Algebraic Methods in Computer Science Lecture Notes in Computer Science 6663 (2011), 22–39.

19.

Dangalchev

, Residual Closeness of Generalized Thorn Graphs, FundamentaI Informaticae 162(1) (2018), 1–15.

20.

Freeman

L.C.

, Borgatti

S.P.

and White

D.R.

, Centrality in valued graphs: A measure of betweenness based on network flow, Soc Netw 13 (1991), 141–154.

21.

Blondel

and Guillaume

, Fast unfolding of communities in large networks, Journal of Statistical Mechanics: Theory and Experiment 2008 (2008), 1–8.

22.

Anthonisse

J.M.

, The rush in a directed graph, Technical report, Stichting Mathematisch Centrum, Amsterdam, 1971.

23.

Freeman.

L.C.

, A set of measures of centrality based on betweenness, Sociometry 40 (1977), 35–41.

24.

Xin

R.S.

, Gonzalez

J.E.

, Franklin

M.J.

and Stoica

, Graphx:Aresilient distributed graph system on a spark, Proc Int Workshop Graph Data Manage Exper Syst 12 (2013), 1–6.

25.

Malak

M.S.

, Spark GraphX in Action, (2016).

26.

Valverde-Rebaza

and Lopes

A.D.

, Structural link prediction using community information on Twitter, Proc 4th Int Conf Comput Aspects Social Netw (Cason) 11 (2012), 132–137.

27.

Soundarajan

and Hopcroft

, Using community information to improve the precision of link prediction methods, Proc Int Conf World Wide Web 12 (2012), 607–608.

28.

Valverde-Rebaza

J.C.

and de Andrade Lopes

, Link prediction in complex networks based on cluster information, Advances in Artificial Intelligence 4 (2012), 92–101.

29.

Yang

, Hu

R.J.

and Zhang

R.S.

, An improved link prediction algorithm based on common neighbors index with community membership information, Proc IEEE 7th Int Conf Softw Eng Service Sci (ICSESS) 45 (2016), 90–93.

30.

Watts

D.J.

and Strogatz

S.H.

, Collective dynamics of ‘small-world networks, Nature 393 (1998), 440–442.

31.

Lusseau

, Schneider

, Boisseau

O.J.

, Haase

, Slooten

and Dawson

S.M.

, The bottlenose dolphin community of Doubtful Sound features a large proportion of long-lasting associations, Behav Ecol Sociobiol 54 (2003), 396–405.

32.

Girvan

and Newman

M.E.J.

, Community structure in social and biological networks, Proc Nat Acad Sci USA 99(12) (2002), 7821–7826.

33.

Duch

and Arenas

, Community detection in complex networks using extremal optimization, Phys Rev E, Stat Phys Plasmas Fluids Relat Interdiscip 72(027104) (2005), 1–12.

34.

Newman

M.E.J.

, Finding community structure in networks using the eigenvectors of matrices, Phys Rev E, Stat Phys Plasmas Fluids Relat Interdiscip 74(036104) (2006), 1–11.

35.

Adamic

L.A.

and Glance

, The political blogosphere and the 2004 US election: Divided they blog, in Proc WWW-Workshop Weblogging Ecosyst (2005), 36–43.

36.

von Mering

, et al., Comparative assessment of large-scale data sets of protein-protein interactions, Nature 417 (2002), 99–403.

37.

Valverde-Rebaza

J.C.

and de Andrade Lopes

, Link prediction in complex networks based on cluster information, in Advances in Artificial Intelligence 4 (2012), 92–101.

38.

Valverde-Rebaza

and Lopes

A.D.

, Structural link prediction using community information on Twitter, in Proc 4th Int Conf Comput Aspects Social Netw (Cason) (2012), 132–137.

39.

Wang

, Ma

, Liu

, Yuan

, Shen

and Li

, A vertex similarity index using community information to improve link prediction accuracy, IEEE Int Conf Syst, Man, Cybern (2017), 1–12.

40.

Barabasi

A.L.

and Albert

, Emergence of scaling in random networks, Science 286 (1999), 509–512.

41.

Yang

, Yang

and Zhang

P.Y.

, A new link prediction algorithm based on local links, Proc Int Conf Web-Age Inf Manage (2015), 16–28.

42.

Sun

, Hu

, Zhao

, Yao

and Fan

, An improved link prediction algorithm based on degrees and similarities of nodes, IEEE/ACIS Int Conf Comput Inf Sci (2017), 13–18.

43.

http://konect.uni-koblenz.de/

44.

Leskovec

, Kleinberg

and Faloutsos

, Graph evolution: Densification and shrinking diameters, ACM Trans Knowl Discovery Data 1(1) (2007), 1–17.

45.

Richardson

, Agrawal

and Domingos

, Trust management for the semantic Web, Proc. Semantic Web ISWC 2870 (2003), 351–368.

46.

Leskovec

, Adamic

L.A.

and Huberman

B.A.

, The dynamics of viral marketing, ACM Trans 1 (2007), 1–11.

47.

Lü

and Zhou

, Link prediction in complex networks: A survey, Phys A, Statist Mech Appl 390(6) (2011), 1150–1170.

48.

Zhang

and Chen

, Link Prediction Based on Graph Neural Networks, in Proceedings of 32nd Conference on Neural Information Processing Systems, Canada (2018).

49.

Zareie

and Sakellariou

, Similarity-based link prediction in social networks using latent relationships between the users, Nature Article No. 20137 (2020), 1–16.

50.

, Node-coupling clustering approaches for link prediction, Knowl Based Syst {89 (2015), 669–680.