Neo4j Documentation - 그래프 알고리즘(3) : Community detection algorithms
Neo4j Documentation - 그래프 알고리즘
Community detection algorithms
연결성은 그래프 이론의 핵심 개념으로 커뮤니티 찾기 등 정교한 네트워크 분석을 가능하게 한다. 연결성은 커뮤니티를 찾고 그룹핑의 질을 정량화할 때 사용된다. 그래프 내의 다른 유형의 커뮤니티들을 살펴보면 그래프 내의 허브나 계층구조, 그룹의 경향성 등을 찾아낼 수 있다.
1. Triangle Count and Clustering Coefficient
정의 및 적용
-
소셜 네트워크 분석에서 많이 활용되는 방법
-
커뮤니티를 탐지하고 해당 커뮤니티들의 응집력, 그래프의 안정성 등을 측정
-
얼마나 많은 노드들이 triangle을 형성하는지 측정(Triangle Count)
-
이웃의 노드들이 서로 클러스터를 형성할 가능성을 측정(Clustering Coefficient)
-
Clustering Coefficient 알고리즘은 클러스터링할 수 있는 그룹(가능성)에 비해 클러스터링되는 정도를 측정, Triangle Count를 계산에 사용함
-
Clustering Coefficient 알고리즘은 Local clustering(이웃 노드들과 결집될 가능성)과 global clustering(전체 커뮤니티 대상)으로 나뉨
사용 가능 그래프
- undirected / unweighted 그래프에 사용
사용 예시
-
웹사이트의 스팸 여부를 결정할 때
-
페이스북의 social graph
-
상호 연결에 기반하여 공통 주제가 있는 페이지 커뮤니티 검색
2. Strongly Connected Components(SCC)
정의 및 적용
-
그래프가 어떤 구조로 이루어졌는지, 또 타이트한 클러스터들을 각각 식별하기 위해 사용함
-
관계 방향에 따라 동일한 그룹의 다른 모든 노드에서 각 노드에 연결할 수 있는 그룹 찾기
-
방향 그래프 상에서 두 정점 u와 v에 대해 양 방향으로 가는 경로가 모두 있을 때
-
클러스터들을 개별 노드들로 분리해 클러스터간 분석을 할 때 사용함
-
데드락을 유발할 수 있는 프로세스를 찾아내기도 함
사용 가능 그래프
-
directed/undirected (direction:INCOMING/OUTCOMING)
-
weighted/unweighted (weightProperty : 'weight'/null)모두 지원
사용 예시
-
모든 구성원이 직접 또는 간접적으로 모든 구성원의 지분을 소유하는 회사 집합 찾기
-
멀티홉 무선 네트워크에서 라우팅 성능을 측정할 때 서로 다른 네트워크 구성의 연결 계산
-
비슷한 특징들을 가진 그룹을 찾아내고 그런 사람들에게 좋아할만한 페이지를 추천하거나 구매할 만한 상품을 추천하는 데에 사용
3. Connected Components (Union Find or Weakly Connected Components)
정의 및 적용
- 그래프의 구조를 이해하는 데 사용됨
-그룹 간의 공통 노드들을 빠르게 보여주어 사기(fraud) 탐지에 유용함
-
관계 방향에 관계없이 동일한 그룹의 다른 모든 노드에서 각 노드에 연결할 수 있는 그룹 찾기
-
방향에 관계없이 모든 두 꼭짓점 사이에 경로가 존재
사용 가능 그래프
-
directed/undirected (direction:INCOMING/OUTCOMING)
-
weighted/unweighted (weightProperty : 'weight'/null)모두 지원
사용 예시
-
데이터베이스 레코드들 내 중복제거
-
인용 네트워크 분석
4. Label Propagation(LPA)
정의 및 적용
-
인접한 노드들에 따라 label을 분산하여 클러스터를 추정
-
그래프 내 커뮤니티를 찾아내는 빠른 알고리즘
-
그룹핑이 명확하지 않거나 가중치로 노드가 어떤 커뮤니티에 속하는 지 결정할 수 있는 네트워크에 사용할 때 잘 맞음
-
조합된 관계와 노드 가중치가 가장 높은 인접 영역에 label을 할당하여 클러스터 중첩을 해결
-
pull / push 방법 두 개가 있음
- 다른 알고리즘들과 다르게 LPA는 같은 그래프에서 여러 번 run할 때 다른 결과(커뮤니티 구조)들을 도출함 -> semi-supervised learning에 사용(spark, neo4j는 learning의 max 횟수 지정되어있음)
사용 가능 그래프
-
directed/undirected (direction:INCOMING/OUTCOMING)
-
weighted/unweighted (weightProperty : 'weight'/null)모두 지원
사용 예시
-
의미 분석의 한 부분인 트위터를 이용한 극성 분류
-
잠재적으로 위험할 수 있는 처방 약물의 조합 찾기
-
기계 학습 모델에 대한 대화 특징 및 사용자 의도 찾기
5. Louvain Modularity
정의 및 적용
-
관계 가중치와 밀도를 정의된 추정치 또는 평균과 비교하여 그룹화의 정확도를 극대화하는 알고리즘
-
커뮤니티들의 계층을 보여주기 때문에 네트워크의 구조들을 이해하는 데 유용함
-
그래프를 작은 모듈(클러스터)들로 나누고 각 그룹핑들의 strength를 측정하는 모듈화기법을 사용함
-
모듈성이란 네트워크의 모듈화정도를 말하며 클러스터 내부의 관계와 클러스터 외부의 관계의 밀도를 비교함. 즉, 클러스터 내부의 연결에만 집중하는 것이 아니라 클러스터 간의 관계도 비교
-
두 단계의 방법을 반복하는 방식의 알고리즘
-
광대하고 복잡한 네트워크 속에서 커뮤니티를 찾아낼 때 사용 (모듈성을 계산하는 일반적인 방법이 너무 오랜 시간이 걸릴 때, 즉 큰 그래프의 모듈성을 계산할 때 등 사용)
-
다른 층위의 개별 단위들에 집중할 수 있고 subcommunity 내에서 또 subcommunity를 찾아야 하는 등의 경우에 사용
사용 가능 그래프
-
undirected
-
weighted/unweighted (weightProperty : 'weight'/null)지원
사용 예시
-
cyberattack을 탐지할 때
-
트위터나 유튜브같은 소셜 플랫폼에서 토픽들을 추출할 때
-
brain's functional network 내에서 계층적 커뮤니티 구조를 찾아낼 때
