[CS224W] 1-3. Choice of Graph Representation

이 포스트는 CS224W : Machine Learning with Graphs 강의를 기반으로 작성되었습니다.

Graph 기본 구조

• nodes, vertices : 정점
• links, edges : 간선 (node들을 연결해 주는 link)
• network, graph : node와 edge로 이루어진 system

Graph 종류

• Directed Graph : link가 방향이 있는 그래프
• Undirected Graph : link에 방향이 없는 symmetric한 그래프

• Bipartite Graph : node들이 두 set으로 나눠지고, 각 set에서의 node는 서로 연결되어 있지 않은 그래프
  • ex) authors-to-papers, actors-to-movies
  • 각 set에 대해서 projection 시킬 수 있음

• Weighted Graph : node나 edge에 가중치 부여
  → 인접 행렬에서 0 / 1 대신 가중치로 표현
• Unweighted Graph : node나 edge에 가중치 부여 X

• self-edges (self-loops) : 자신의 node로 향하는 edge가 있는 그래프 
• multigraph : 같은 node끼리 edge가 여러개 있는 그래프
  → 인접 행렬에서 0 / 1 대신 edge 개수로 표현

Graph 표현 방식

• 인접 행렬 (Adjacency Matrix)
  • matrix 내 (i, j) 원소값이 1이면, node i와 node j 사이 link가 있는 것
  • matrix 내 (i, j) 원소값이 0이면, node i와 node j 사이 link가 없는 것
  • undirected graph는 인접 행렬이 symmetric함
  • 실제 대부분 네트워크는 sparse하므로, 인접 행렬도 대부분 0으로 채워져 있음

• 인접 리스트 (Adjacency list)
  • node별로 연결된 node 목록 나열
  • 그래프가 크거나 sparse할 때 유용
  • 빠르게 주어진 node에 대한 이웃을 찾을 수 있음

• node / edge attributes
  • weight : 가중치
    ex) 커뮤니케이션 빈도 수, ...
  • ranking : 중요도 랭킹
    ex) best friend, second best friend, ...
  • type : 형식
    ex) friend, relative, co-worker, ...
  • sign : 표시
    ex) 친구인지 적인지, 신뢰하는지 불신하는지, ...
  • 그래프 구조에 기반한 특성
    ex) 공통 친구 수, ...