정리에 사용하는 자료는 neo4j 공식 documentation(그래프 알고리즘 사용자 가이드)과 graph algorithm neo4j라는 neo4j에서 제공하는 도서이다.
알고리즘 분류
neo4j graph algorithm 라이브러리가 제공하는 알고리즘은 크게 다섯 가지의 카테고리와 세부 항목들로 나뉜다.
1. Centrality algorithms (정리 완료)
: 중심성이란, 모든 네트워크에서 어떤 노드가 더 중요한 지를 이해하는 것이다. 중심성 알고리즘은 정보를 신속하게 퍼뜨리는 능력을 가진 것을 중요하게 여기는 유형과 별개의 그룹을 결합하는 것을 중요하게 여기는 유형 등으로 나뉜다.
- PageRank
- ArticleRank
- Betweenness Centrality
- Closeness Centrality
- Harmonic Centrality
- Eigenvector Centrality
- Degree Centrality
2. Community detection algorithms (정리 완료)
: 연결성은 그래프 이론의 핵심 개념으로 커뮤니티 찾기 등 정교한 네트워크 분석을 가능하게 한다. 연결성은 커뮤니티를 찾고 그룹핑의 질을 정량화할 때 사용된다. 그래프 내의 다른 유형의 커뮤니티들을 살펴보면 그래프 내의 허브나 계층구조, 그룹의 경향성 등을 찾아낼 수 있다.
- Louvain
- Label Propagation
- Connected Components
- Strongly Connected Components
- Triangle Counting / Clustering Coefficient
- Balanced Triads
3. Path Finding algorithms
: Path는 그래프 분석과 그래프 알고리즘의 필수적 요소이다. 최단 거리를 찾는 것은 그래프 알고리즘으로 수행되는 작업 중 가장 빈번하게 이루어지는 편이며 그 작업은 다른 분석의 기반이 된다. 최단 거리란 가장 적은 이동이나 최소의 weight으로 해당 경로를 순회하는 것이다. 최단 경로 외에도 평균 최단 경로, 최단 경로 중 가장 긴 경로(=지름, diameter) 찾기 등에도 Path Finding algorithm을 사용한다.
- Minimum Weight Spanning Tree
- Shortest Path
- Single Source Shortest Path
- All Pairs Shortest Path
- A*
- Yen's K-Shortest paths
- Random Walk
4. Similarity algorithms
- Jaccard Similarity
- Cosine Similarity
- Pearson SImilarity
- Euclidean Similarity
- Overlap Similarity
5. Link Prediction algorithms
: 링크 예측이란 현재 네트워크에서 관측되지 않은 링크(미래에 등장, 빠져있거나 등..)를 예측하는 것이다. 공통 이웃의 수와 같은 구조적 유사성 지표를 통해서 관측되지 않은 링크의 존재를 예측하는 방법이 일반적이다. 더 높은 유사성을 가진 노드 쌍은 연결될 가능성이 더 높다고 간주한다.[1]
- Adamic Adar
- Common Neighbors
- Preferential Attachment
- Resource Allocation
- Same Community
- Total Neighbors
이제 각 알고리즘들의 의미와 사용법, 예제 등에 대해 기술할 것이다.
참고문헌
[1] Kai Zhou, et al. "Attacking Similarity-Based Link Prediction in Social Networks,", 2018.
옛날에 티스토리에 썼던 글들을 영차영차 옮겨오는 중인데, 이후에도 다시 공부할지는 조금 의문.
