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