community analysis 1

community를 분석하는 이유?

글로벌한 관점에서 볼때 특정 행동을 파악할수있음

(개인별로는 안 나타날 수 있음)

 

SNS상에서의 community

formation:

1. 하나의 community가 생성되기위해서는 적어도 2개의 node가 있어야함

2. 그 사이에 interaction이 존재함

2가지의 종류:

1. explicit(emic): 명확한 목적이 있는 community

2. implicit(etic): 암묵적으로 생성된 community (파악해야하는 target임)

eg) 전화가 빈번이 연결되는 그룹을 파악하여 promotion 제공(미국 - 캐나다)

2가지 종류(구조상): 

1. overlapping community

2. disjoint community

 

community 분석 방향

1. community detection

2. community evolution 파악

3. community evaluation

 

1. community detection

node의 cluster를 발견하는 과정

- strong internal connection

- weak connetions between different communities

실제 community를 detection할때

최대한 각 cluster끼리 decoupled할 수 있도록 detection 해야함

 

clustering과 community detection의 차이

cluster는 edge가 없지만 community는 edge가 있음

cluster간의 거리는 discrete하지 않지만 community에선 discrete함.

 

community detection algorithms

1. member 특성 기반 detection (Member-Based Community Detection)

2. 그룹속성 기반 detection - 다음 게시물에서 정리할 것임

 

Member-Based Community Detection

노드 특성 파악하는 것을 기반으로함

1. 노드 degree (cliques)

2. reachability (k-cliques, k-clubs, k-clans)

3. similarity

 

clique: a maximum complete subgraph

모든 노드는 서로 연결되어있음

아래 그림에서 회색노드로 표시된것이 clique임

(빨간색까지 포함하면 그 노드는 다른노드와 연결되어있지 않으므로 clique가 아님)

 

1. 노드 degree (cliques) 파악 방법

• the maximum clique 찾기 (빨간색 - 단 1개 존재)
• all maximum clique 찾기 (파란색, 빨간색 등등) 
  • (단, 더이상의 확장이 불가능해야함 - 빨간색에서 v1, v2, v4는 안됨)

복잡도가 N*P이므로 practical하지 않음

→ 해결책:  

I. Brute Force (잘 사용 안함) - 그래프가 주어질 때, 모든 가능부분집합을 다 찾는 것

  (n개의 노드가 존재하면 2**(n - 1) - 1개의 서로다른 clique이 있음)

→ 개선방향: pruning을 사용함

   size=k(node=k, node-degree=k-1)인 clique을 찾을 때

   degree가 k-1보다 작은 것들을 다 삭제 후, clique를 찾음

all maximum clique 찾기에서 pruning의 예

하지만, pruning을 하더라도 clique으로 community를 찾는 것은 실용적이지 못함

왜냐하면

- clique의 정의에 완전히 만족하는 cliques are rare 

- 아무리 dense한 그룹이더라도 하나의 노드만 제거되면 clique을 만족하지 못함

(아래 그래프에서 6-7의 연결 edge가 사라지면 clique이 아님)

→ 해결책:  clique의 정의를 완화함 : relax cliques

 

II. Relax cliques

k-plex: size=k인 clique는 k-plex이고 이것을 찾는 것임

4일때 1-plex이므로 4-1 즉 모든 노드의 degree가 3이상인 집합

 

k가 작을수록 완전한 clique이고

k가 클 수록 완화된 clique임

 

이 외에도, k-core, k-shell등의 완화된 방법이 있음

k-core: 모든 subgraph에 있는 노드들이 최소 k degree를 갖는 것임

eg)3-core: 모든 subgraph이 있는 노드들은 최소 3-degree를 갖음

** k-core와 k-plex의 차이

k가 증가할 수록 subgraph의 각각의 노드가 k개의 노드를 가지고 있어야 하므로 k-plex보다 더 dense해질 수 있음

k-plex에서는 k가 증가할 수록 느슨한 subgraph임

k-shell: k-core에는 속하지만 (k+1)-core에는 속하지 않는 것임

왼쪽은 2-plex인 동시에 2-core임

 

III. Use cliques as the core for larger communities

Clique Percolation Method (CPM)기법을 활용

총 3개의 community

위와같이 ksize인 clique에서 3-1개의 공통노드를 가지고 있는 것을 연결

단, k값이 너무 크면 계산이 복잡해짐

 

 

2. reachability (k-cliques, k-clubs, k-clans)

- 노드사이에 연결선이 있다면 같은 노드에 속해있다고 하는 방법

  (매우 큰 subgraph가 나옴 - 커뮤니티로 인식하기엔 부적절함)

- 가까이 있는 노드들만 subgraph라고 하는 방법(clique을 찾는 것과 유사)

→ 두개를 합쳐서, 연결성을 고려하며, shortest path를 가진 그룹을 찾는 방법을 고려함

 

3가지 종류의 special subgraphs

1. k-clique: shortest path의 length가 k이거나 k보다 작은 a maximal subgraph

(아래그림에 maximal subgraph는 5이며, 2-clique이므로 shortest path는 2를 초과하지 않음)

v1을 포함하면 v1-v6까지의 shortest path는 3이라서 탈락

단, {v1, v2, v3, v4, v,5}에서 v4,v5를 연결 할때 v6을 거치는 length를 포함함

(nodes on the shortest path should not be necessarily be part of the subgraph)

 

2. k-club: k-clique에서 (nodes on the shortest path should not be necessarily be part of the subgraph)라는 조건이 없는 것

 

3. k-clan: k-club과 k-clique의 교집함

 

 

3. similarity

Node similarity can be defined

– Using the similarity of node neighborhoods (Structural Equivalence) - 여기에 대해서만 정리

  : 같은 노드와 연결되어있음

– Similarity of social circles (Regular Equivalence)

1과 3은 노드 2와, 4를 공통으로 하여 연결되어 있으므로

v1과 v3은 유사하다.

 

 

유사성을 판단하는 2가지 방법

Jaccard Similarity

Cosine similarity

cosine similarity의 유사도의 분모는 root(3*2)임,(두 개 다 0~1사이의 값임)

 

** 유사도를 거리로 환산하기 위해 "1-유사도 = 거리" 를 사용