[cs224w] 1.3 Choice of Graph Representation

https://www.youtube.com/watch?v=P-m1Qv6-8cI&list=PLoROMvodv4rPLKxIpqhjhPgdQy7imNkDn&index=3 

 

graph representation 의 선택에 대해서 소개한다

 

 

 그래프 또는 네트워크의 구성요소는 무엇일까? 네트워크는 객체들의 두 종류로 구성된다 이 객체들을 노드(node) 또는 정점(vertice)라고 부른다. 이들 사이에 상호작용 또는 엣지를 갖는다. 

 

 

 그래프에 대해 무엇이 중요할까? 그래프는 common language이다. 

 

 

 적절한 graph representation을 선택하는 것은 중요하다. node와 edge를 무엇으로 선택하는지는 중요하다.

 

 

 데이터셋이 주어졌을 때, node와 edge를 어떻게 선택할까? 

 

 

 유향 그래프와 무향 그래프의 차이점을 설명한다.

 

 

 

 이분 그래프도 존재한다.

 

 

 이분 그래프는 다음과 같이 project 할 수 있다.

 

 

 graph를 어떻게 표현할까?

 

 

 node degree는 다음과 같이 계산한다.

 

 

 real world의 graph는 sparse 하다.

 

 

 

 edge list로도 표현할 수 있다.

 

 

 adjacency list의 특징. 

 

 

 다양한 종류의 option이 존재

 

 

 edge를 weight로 줌.

 

 

 self-loop를 갖는 graph도 존재한다. 또한 multigraph도 존재.

 

 

 무향 그래프에서 connectivity도 설명함

 

 

 conectivity를 adjacent로 표현하면 block 형태 

 

 

 

 유향 그래프에서 connectivity