Graph Analytics with Python -Node Similarity-
Tags: python, datascience, graph, networkx
Published: 2021-02-09 09:52:39

# Node Similarity

<!--与えられたグラフから今後どのようなエッジが張られるのかを予測するリンク予測手法は数多く存在する．その中でも最もシンプルなアプローチが，類似度の高いノード間にはエッジが張られる可能性が高いと仮定して，ノード間の類似度を計算するものである．ノードの類似度を計算する手法として用いられるのは以下の４つである．-->
There are many link prediction methods to predict what edges will be formed from a given graph. One of the simplest approaches is to calculate the similarity between nodes, assuming that edges are likely to be formed between nodes with high similarity. The following four methods are used to calculate the similarity of nodes.

1. Common Neighbors
2. Jaccard Coefficient
3. Admic/Adar
4. Preferential Attachment

### 1. Common Neighbors
<!--Common Neighborsでは，グラフGと二つの頂点v,wが与えられたときに，vに隣接するノード集合をΓ(v)で表すと，以下の式でvとwの類似度を計算する．-->
In Common Neighbors, given a graph G and two vertices v and w, the set of nodes adjacent to v is denoted by 
Γ(v), and the following formula is used to calculate the similarity between v and w.

{% katex %}
Score(v,w) = |\Gamma (v) \cup \Gamma (w)|
{% endkatex %}

<!--Common Neighborsでは，グラフGと二つの頂点v,wが与えられたときに，vに隣接するノード集合をΓ(v)で表すと，以下の式でvとwの類似度を計算する．-->
In Common Neighbors, given a graph G and two vertices v and w, the set of nodes adjacent to v is denoted by Γ(v), and the following formula is used to calculate the similarity between v and w.

```Python
import networkx as nx
import matplotlib.pyplot as plt
G = nx.karate_club_graph()
plt.figure(figsize=(5,5))
nx.draw_spring(G, node_size=400, node_color="#00C98D", with_labels=True, font_weight="bold")
x = 4
y = 5
print("vertex pair:", x, "and", y)
print("neighbors of", x, ":", list(G.neighbors(x)))
print("neighbors of", y, ":", list(G.neighbors(y)))
print("degree of", x, ":", G.degree(x))
print("degree of", y, ":", G.degree(y))
print("common neighbors:", len(list(nx.common_neighbors(G, x, y))))
```

```
vertex pair: 4 and 5
neighbors of 4 : [0, 6, 10]
neighbors of 5 : [0, 6, 10, 16]
degree of 4 : 3
degree of 5 : 4
common neighbors: 3
```

### 2. Jaccard Coefficient
<!--Common Neighborsはシンプルに共通の隣接ノードの数であった．しかしこれでは，隣接しているノードが全体の中でどの程度を占めているのか分からない．-->
Common Neighbors was simply the number of common neighboring nodes. However, this does not tell us how much of the total is made up of neighboring nodes.

<!--On the other hand, Jaccard Coefficientはvとwの全ての隣接ノードに対する，共通の隣接ノードの割合である．-->
On the other hand, Jaccard Coefficient is the ratio of common neighbors to all neighbors of v and w.

{% katex %}
Score(v,w) = \frac{|\Gamma (v) \cap \Gamma (w)|}{|\Gamma (v) \cup \Gamma (w)|}
{% endkatex %}

```Python
print("Jaccard coefficient:", list(nx.jaccard_coefficient(G, [(x, y)]))[0][2])
```

```
Jaccard coefficient: 0.75
```

### 3. Adamic/Adar
<!--Adamic/AdarはCommon Neighborsを改良したものである．単に共通の隣接ノードを同じものとしてカウントするのではなく，共通の隣接ノードの中で次数の少ないものを重視する類似度である．-->
Adamic/Adar is a modification of Common Neighbors. Adamic/Adar is an improvement on Common Neighbors in that it does not simply count common neighbors as the same, but rather focuses on the nodes with the lowest degree among the common neighbors.

{% katex %}
Score(v,w) = \sum_{x \in \Gamma (v) \cap \Gamma (w)} \frac{1}{\log |\Gamma (x)|}
{% endkatex %}

```Python
print("Adamic/Adar:", list(nx.adamic_adar_index(G, [(x, y)]))[0][2])
```

```
Adamic/Adar: 1.9922605072935597
```

### Preferential Attachment
<!--Preferential Attachmentは隣接ノードの多いノード同士ほど類似度が高いとみなす．-->
In Preferential Attachment, nodes with more neighbors are considered to be more similar to each other.

{% katex %}
Score(v,w) = |\Gamma(v)| ・ |\Gamma(w)|
{% endkatex %}

```Python
print("preferential attachment:", list(nx.preferential_attachment(G, [(x,y)]))[0][2])
```

```
preferential attachment: 12
```

#Conclusion
<!--本記事ではリンク予測で用いられるノードの類似度を計算する手法について説明を行った．次の記事ではリンク予測について説明する．-->
In this article, we have explained the method for calculating the similarity of nodes used in link prediction. In the next article, we will discuss link prediction.