Day_10. Community Analysis

Community Analysis

**Chp6 부분으로 Chp5는 skip**



Community의 정의
= 공통 사항에 대해 뭉친 사람들의 그룹



Community 의 분석을 해야 하는 이유
= 개개인의 분석은 의미파악하기 힘드나 거시적으로 크게보면 공통분모가 존재하는 경우가 있다,
= Ex)정치성향 ,공화,민주당 지지자들의 그룹등



Explicit - 명시적/ Implicit - 묵시적 Community
=개인의 의식에 상관없이 Community 로 구분되는 상황



Implicit Community 파악하기
Ex)일반인이 해외에 국제전화를 건다면 개인은 아무 의식 없이 하는 전화지만 통신사 에서는 국제전화를 자주 이용하는 고객 그룹에 넣을수 있고 이를통한 마케팅 같은 부분에 사용할수 있음
Ex)단백질,신체 장기의 상호작용, 각각은 개인의 일을 할뿐이지만 크게보면 그룹으로 나눌수 있다

=detection,
---Discovering implicit communities – 묵시적 community 식별하기

=Evolution
---Studying temporal evolution of communities – 시간이 지나며 변하는 것 연구

=Evaluation
---Evaluation Detected communities – 탐지한 community에 대한 평가 시행

Community detection = 커뮤니티 내부의 노드의 연결은 strong, 커뮤니티간의 연결은 weak

파란색에 해당하는 커뮤니티 내부의 연결은 강하게 많이 연결되어 있으나
빨간색에 해당하는 커뮤니티 “간” 연결은 한줄로 되어 있다
“실제로는 이런 상황은 드물고 “최대한 이런 상황을 만드는 것” 이 중요하다”



Why analysis the community?
=복잡한 개인의 상황을 고려하지 않아도 된다
=개인정보 공개의 위험이 적게 분석할 수 있다



Clustering 과 community의 차이는?
=비슷해 보이는데 차이가 있다! 무었일까?



=clustering
--data 가 link 되어있지 않다
--거리를 기준으로 묶는다 – k-mean
---- k-mean 사용시 ego-centric network 에서 주로 사용한다

-자기 중심 네트워크

-------un-supervised learning 에서 사용한다
Community
=data 가 서로 link 되어 있다
=discrete(분해) 되는 성질이 있어서 나눌 수 있다



Community 를 나누는 방법
1.그룹의 속성을 이용해서 나눈다
2.그룹의 맴버를 기준으로 나눈다

Member 기반 community 를 detection(식별) 하기
=노드의 특성을 생각해보자!!

1.Degree
--노드의 degree를 보고 판단하자

2.Reachability
--노드간 가까운 것 끼리 판단해보자

3.Similarity
--노드간의 유사성을 보고 판단하자


Degree 기반 탐색
Clique-구획-
=가장 일반적인 노드간의 서브 그래프로 “완전 서브그래프” complete subgraph 를 의미한다
==complete graph
-----있는 노드들이 모두 연결되어 있다

Maximum Clique pruning(가지치기) 이란?

Pruning 이 할수 있는 것
=사이즈 K보다 더 큰 Clique을 검색할 때
=clique를 찾으면 각 노드의 degree는 k와 같거나 k-1 의 크기여야 한다
=k가 클 때 소셜미디어에서 power law degree distribution 법칙에 의해 많은 노드가 가지치기(pruning) 된다

Pruning 절차
=모든 노드에서 k-1 degree의 노드는 제거한다
=반복적으로 시행한다


Ex)다음 그래프에서 k가 4일 때 pruning 하면 제거되는 순서는?

K=4 –pruning 에서는 k-1 =3이며 degree가 (4-1)=3 이하인 노드 먼저 제거 된다
--Step - 1 – 9 , 2가 먼저 제거된다, 노드의 엣지가 1,2이기 때문
--Step - 2 – 1 , 3 이 제거된다 (노드 2가 사라져서 1,3에 해당하는 degree가 줄었음)
--Step – 3 – 4 가 제거된다 (노드 1,3 이 제거되며 4의 degree가 2가 되었음)


K-plex 방법론

**이때 V는 서브 그래프의 node의 개수**

==는 서브 그래프상 노드 v의 degree
==서브 그래프상의 node의 개수

==Clique 의 k는 1-plex로 나타낼수 있다
==최대 k-plex 탐색은 시간 복잡도 상으로 좋지않다

Ex)

1,2,3 plex를 찾자 --V=6 (그래프의 노드갯수)

1-plex --->= 6-1 ---
2-plex --->= 6-2 ---

k-core 방법론
=최소 k만큼 연결이 보장된 노드들을 추리는 것, k값의 상승은 그래프가 dense해짐을 의미한다


k-shell 방법론
=k-core에 속하나 (k+1)-core 즉 주위에 있는 노드를 의미한다

Ex)
=0-core = 전체 그래프를 의미한다
=k-core 에 해당하는 complete graph는 존재할수 없다
=k-1-core 는 complete graph를 의미한다


Clique percolation Method (CPM) 방법론
=Clique를 대형 커뮤니티 탐색을 위한 기초 seed로 사용하는 방법론

입력
=파라미터 k와 네트워크

과정
=주어진 네트워크에서 k-clique 에 해당하는 그래프를 모두 탐색한다
=연결된 clique는 그래프의 구성요소로 커뮤니티가 형성된다

Clique 크기가 3인 영역을 나누면(v는 생략)
{1,2,3},{3,4,5},{4,5,6},{4,5,7},{4,6,7},{5,6,7},{6,7,8},{8,9,10}


크기로 잘라내면 3부분으로 나뉜다
{1,2,3,},{3,4,5,6,7,8},{8,9,10}