[SNS analysis] 그래프 관련 기본 개념

소셜 미디어 데이터의 5가지 특징

1. participation: 사용자의 높은 참여도

2. openness

3. conversation

4. community

5. connectedness

 

 

소셜미디어 mining challenges

1. big data paradox: 데이터는 많지만, 양질의 데이터라고는 할 수 없음

2. obtaining sufficient samples: sample 규모를 적절히 정하기 어려움

3. noise removal fallacy: 전처리를 얼마나 할 것인가에 대한 문제점

4. evaluation dilemma: ground truth의 부재로, 분석 결과의 정확도를 확인하기 어려움

 

 

graph 종류

1. directed graph = arc

2. undirected graph

 

dmml.asu.edu./smm

 

graph 관련 표기법

undirected graph에서 N(v7)은

N(v7) = v1, v4, v6

 

 

graph 관련 이론

Theorem1. degree의 총합은 모든 edge의 2배와 같다.

Lemma1. 홀수개의 degree를 가지고 있는 node의 수는 짝수이다.

Lemma2. in-degree의 총합의 out-degree의 수와 같다.

 

 

degree의 분포

degree의 분포의 총합은 1이다.

dmml.asu.edu./smm

 

 

graph로 표현할 때 기억해야 할 3가지.

1. Does not lose information

2. Can be manipulated easily by computers

3. Can have mathematical methods applied easily

 

 

graph 저장 방식

1. adjacency matrix

> 장점: 표현이 간단하다.

> 단점: sparse한 표한 기법 

 

2. adjacency list

> 장점: 적은용량으로 저장이 가능

> 단점: 탐색하기에 까다로운 구조임

dmml.asu.edu./smm

3. Edge list (잘 사용하지 않음)