# A Novel Algorithm for Local Network Alignment Based on Network Embedding
## 4 Embedding Scenarios
### Case Study 1: Evaluation of the Similarity of Embeddings  
In this case study, we show that the embeddings do not modify the similarity among nodes. Using publicly available network generators in the NetworkX package [39], we build synthetic networks with scale free topology. We build two initial networks, \(Rand_{1}\) and \(Rand_{2}\), having 6000 edges, respectively. Then, we obtain a noisy counterpart for each network by rewiring 5%, 10%, 20%, 25% and 50% of the edges, respectively. Next, we build five rewired network instances at each noise level obtaining a total of ten networks. We consider the first network and its randomized versions 256 (R1-0, R1-5, R1-10, R1-15, R1-20, R1-25, R1-50) and the second network and its randomized 257 versions (R2-0, R2-5, R2-10, R2-15, R2-20, R2-25, R2-50). For each network, we determine 258 embeddings using the DeepWalk, node2 Vec and LINE algorithms. Let GDV [14] be the signature of each node of a network, calculated on the basis of the orbits of the graphlet. We measure the similarity across all of the node pairs \(v_{1i},w_{2j}\) of the two networks (e.g., network 1 and network 2) by using the cosine distance among the Graphlet Degree Vectors (GDVs):  
\[\langle GDV(v_{1i}),GDV(w_{2j})\rangle\quad v_{1i}\in V_{1},w_{2j}\in V_{2} \tag{1}\]  
where the dot product between \(GDV(v_{1i})\) and \(GDV(w_{2j})\) is proportional to the \(cos(\theta)\), with \(\theta\) being the angle between the two vectors. Then, we use the cosine similarity among all the embeddings \(cos(f(v_{1i}),f(v_{2j})\) as a similarity measure, in line with previous works (e.g., see [23]). We obtain two vectors representing the ranked similarities among node pairs measured in the different spaces. In order to compare these rankings, the Rank-Biased Overlap (RBO) [40] is used. The RBO measure, developed in the information retrieval to calculate a score for comparing indefinite rankings, is used to handle tied ranks and rankings of different lengths. It provides a monotonic score in the interval \([0,1]\). We calculate the RBO score for each pair of randomized networks by using Algorithm 1 reported below. Given two networks, \(G_{1}\) and \(G_{2}\), and two embeddings, \(F(G_{1})\) and \(F(G_{2})\), the RBO Score calculates the overall agreements among the similarity of pairs of nodes and the corresponding pairs of embeddings. RBO takes values in the range (0, 1), where 0 means disjoint and 1 means identical ranked lists. Thus, in our case, a higher value means that there is agreement between rankings; hence, the embedding preserves inter-network similarities. ```
0:\(G_{1}=(V_{1},E_{1})\), and \(G_{2}=(V_{2},E_{2})\)
0:\(F(V_{1})\), \(F(V_{2})\). 0:\(GDV\) [Any other similarity measure providing a monotonic score of similarity]
0:\(Score_{RBO}\) [Score of the Ranked Biased Overlap] for all\(v,w\in V_{1},V_{2}\)do \(Sim(v,w)=GDV(v,w)\) endfor for all\(f(v),f(w)\in F(V_{1}),F(V_{2})\)do \(SimEmb(f(v),f(w))=cosine(f(v),f(w))\) endfor \(Rank1=(Sim)\) \(Rank2=(SimEmb)\) [Let sort both the results on the basis of similarity score and make a ranking] \(Score_{RBO}=RBO(Rank1,Rank2)\) [Calculate the RBO between rankings]
```  
**Algorithm 1** Comparing Node Similarities as Rankings  
Tables 1-3 summarize the results. We consider the first network and its randomized versions (R1-0, R1-5, R1-10, R1-15, R1-20, R1-25, R1-50) and the second network and its randomized versions (R2-0, R2-5, R2-10, R2-15, R2-20, R2-25, R2-50). For each network, we determine the embeddings using the algorithms (DeepWalk, node2 Vec and LINE). We then measure the similarity among all node pairs and all embedding pairs. Finally, we measure the agreement of rankings using RBO values.