Chp_2_2 Introduction To Social Media Mining

2.2 그래프의 표현.

그래프의 시각적 표현을 예시로 증명했다.
이 표현에서,인간에게는 쉽게 이해가 가능하나 컴퓨터나 수학적 도구를 사용해서 표현하는건 어려운 일이다.
그래서 다음과 같은 방식으로 노드와 엣지 셋트를 저장할수 있는 방안을 모색하게 된다, 1정보를 놓히지 않는 방안, 2컴퓨터로 조작하기 쉽게,3 수학적 방법론을 이용해 쉽게 적용 가능하다

근접 행렬.
그래프를 표현하는 간단한 방식은 근접 행렬를 사용하는것이다,(흔히 소시오행렬로 알려져있다).

그림 2.4를 보면 행렬에 상응하는 그래프의 예시를 볼수있다.
다음은 노드 vi와 vj에 연결된 대응 행렬를 볼수 있다 0은 두개의 노드에 연결점이 없음을 나타낸다.
일반적으로, 실수로 표현되어 있다면 두개의 노드간의 연결의 강도를 의미한다.
상응하는 매트리스는 그래프에 대한 수학적 표현의 table로 볼수 있다.
소셜 네트워크 상에서, 적은수의 상호작용은, 행렬 cell에서 0으로 채워지게 된다.

이렇게 되면 큰 희소 행렬이 생성되게 된다.
산술 분석에서,희소 행렬 행렬는 많은 부분이 0으로 채워져 있는것을 의미한다.
인접 행렬에서, 대각선 항목은 자체 링크 또는 루프를 나타낸다.
근접 행렬은 일반적으로 다음과 같이 형식화 시킨다

근접 리스트.
근접 리스트에서, 모든 노드는 연결된 모든 노드가 연결된 모든 노드 목록으로 연결된다.
목록은 노드의 순서나 다른 사항에 의해 정렬되는 경우가 많다.
그림 2.4에서 보이는 그래프를 보면, 표 2.1에 상응하는 그래프를 볼수 있다.


엣지 리스트
큰 그래프를 저장하는 단순하고 일반적인 방법은 그래프의 모든 엣지를 저장하는것이다.
이건 보통 엣지 리스트 표현이라고 한다.
그림 2.4에서 보이는 그래프를 엣지 리스트로 표현하면 다음과 같다.

이 표현에서, 각 원소는 (vi; vj) 엣지를 의미한다,구체적으로는 vi에서 vj로 향하는 엣지를 의미한다.
소셜 미디어 네트워크가 희박하기 때문에, 인접한 리스트와 엣지 리스트는 공간 절약에 효과적으로 작용할수 있다.
인접 매트릭스를 사용할때 많은 0을 저장해야 하기 때문이다, 하지만 엣지 리스트를 저장할때는 0이 필요하지 않다.
(그래프를 표현하기 위해서는 관계가 없는 부분을 표시하기 위해 0이 필요하지만 엣지 리스트는 관계만 표현하기 때문에 출발,목적지만 있어도 표현이 가능해서 0이 필요없다)