이웃의 구성 범위 규정하기
1.두 node간 (거리는 생각하지 않고) 경로만 있으면 이웃이다
---대부분 해당되는 경우라 효과가 미비하다
---Graph 는 어쨌든 연결 되어있기 때문에
2.두 node간 이웃일 때(직접 1:1연결)만 이웃으로 하자
---clique를 찾는것과 같다, 일종의 complete graph 를 찾는 것
===>두개 모두 문제가 있다
1,2의 중간에서 타협점을 찾아야 한다
**clique– 완전 그래프, 각 노드의 degree는 노드개수 k-1**
K-clique = 이전 clique와는 다르다, k-clique는 최대 subgraph – largest shortest path = 직경이 k와 같거나 작다
k-club = k-clique와 비슷하나 subgraph에서 최단거리 노드쌍은 subgraph 내에 존재해야 한다
k-clan – 최단 거리에 해당하는 k에 맞는 모든 node의 쌍, 모든 k-clan은 c-clique에 해당하나 역은 성립하지 않는다
Node similarity – 노드간 유사도의 측정
1.structured equivalances = 이웃되는 노드끼리 파악해서 공통 사항을 추출
=k-means 정리 역시 structured equivalances 의 종류이다
2.regular equivalances – 서로의 이웃끼리 유사한가 판단하는 것
Graph – based community detection – 그룹의 속성을 가지고 유사도 파악
=연결이 weak 한 부분을 기준으로 나눠서 판단한다
=그룹 내부의 연결성은 dense, 각 그룹”간” 연결은 sparse 하다
===3가지 속성 위주로 살펴본다
1.balance – spectral cluster
2.robust – k-connected
3.modular – modularity maximizing
Graph clustering – 큰 그래프를 서브그래프로 쪼개는 것
=cut – 그래프를 쪼개기 위해 삭제한 edge의 list
=cut size – cut에 속한 edge의 개수
예시 그래프를 이용해 그래프 쪼개기
a로
Cut = [8,9] Cut_size=1
b로
Cut=[4,6][5,7][4,7],[5,6] cut_size=4
c로
cut=[3,4],[3,5] cut_size=2
***max flow 이론에서 min flow 탐색시 cut을 잘할수 있음
***min cut 사용시 한쪽이 single 나머지는 graph 전체로 나뉠수 있다
***B의 경우 clique를 쪼개야 되서 cut의 사이즈가 커진다
***C의 경우가 적절하다
###적절한 Cut C 구하는 방법###
1.Ratio cut
자른 엣지의 개수
잘라낸 클러스터 pi에 있는 노드의 개수 2.Normalized cut
잘라낸 파티션 PI에 있는 노드 전체의 차수 (Degree) Ex)
Cut A
1.Ratio Cut(P)
[1,2,3,4,5,6,7,8] [9] =
P2노드개수 = 1 , 자른엣지 = 1
2.Normalized Cut(P)
[1,2,3,4,5,6,7,8] [9,] =
Cut B
1.Ratio Cut(P)
[1,2,3,4] [5,6,7,8,9]
2.Normalized Cut(p)
[1,2,3,4] [5,6,7,8,9]
==p2엣지개수 * 2 +2 = 16 (노드 5,6에 하나씩)
###계산 결과 분석###
##cut의 size가 작은게 좋은 cut이다##
Matrix의 형태와 cut Matrix의 형태로 나타내면
이며 row는 node를 column 은 파티션,community 를 의미한다
이면 해당 노드가 속한 community 는 1번 community(partition)이다
는 diagonal matrix로 adjust matrix 에서 하단에 sum 을 한 것Ex)
에서 D를 구하면 다음과 같다
[220]이 산출된다
댓글 없음:
댓글 쓰기