Boostcamp AI Tech (Day 021)

My assignment: Graph functions

Graph 소개

• 그래프(graph, network)

  • 정점 집합과 간선 집합으로 이루어진 수학적 구조
    • 정점(vertex, node)
    • 간선(edge, link): 두 정점을 연결
  • 복잡계(complex system)
    • 구성 요소 간의 복잡한 상호작용
    • 그래프로 효과적으로 표현하고 분석/예측 가능
    • 전산학, 물리학, 생물학, 화학, 사회과학 등 다양한 분야에 활용 가능

• 그래프 관련 AI tasks

  • 정점 분류(node classification)
    • 트위터에서 retweet 관계를 분석해 각 사용자의 정치적 성향 분류
    • 단백질 상호작용을 분석해 단백질의 역할 분류
  • 연결 예측(link prediction)
    • 페이스북은 앞으로 어떻게 진화할지
  • 추천(recommendation)
    • 누가 어떤 물건을 구매해야 만족도가 높을지
  • 군집 분석(community detection)
    • 연결 관계로부터 사회적 무리(social circle) 찾기
  • 랭킹(ranking), 정보 검색(information retrieval)
    • Web이라는 거대한 그래프로부터 어떻게 중요한 웹페이지 찾을지
  • 정보 전파(information cascading), 바이럴 마케팅(viral marketing)
    • 네트워크를 통해 정보가 어떻게 전달되고, 그것을 어떻게 최대화할 수 있을지

• 이웃(neighbor)

  • $N(v) / N_v:$ 정점 $v$의 이웃들의 집합
  • 방향성이 있을 경우 $N_{in}(v), N_{out}(v)$
    
    

Graph 유형 및 분류

• 간선의 방향 여부

  • 방향 없는 그래프
    • 협업 관계, 페이스북 친구
  • 방향 있는 그래프
    • 주체와 대상이 분리되는 경우
    • 인용, 트위터 팔로우

• 간선의 가중치 유무

  • unweighted
    • 웹, 페이스북 친구
  • weighted
    • 전화, 유사도

• 정점의 종류

  • 동종(unpartite)
    • 단일 종류의 정점
    • 웹, 페이스북
  • 이종(bipartite)
    • 다른 종류의 정점 사이에만 간선이 연결됨
    • 전자상거래 구매내역(사용자, 상품)
    • 영화 출연(배우, 영화)
      
      

Graph 실습

• 파이썬 라이브러리

  • NetworkX
  • $\text{Snap.py}$

• NetworkX 실습

  • Github

• 그래프 저장

  • 간선 리스트(edge list)
    • (노드, 노드)
    • 방향성 있는 경우 (출발점, 도착점)
    • 탐색시 비효율적임
  • 인접 리스트(adjacent list)
    • 1: $[2, 5]$
    • 2: $[1, 3, 5]$
    • 3: $[2, 4]$
    • 4: $[3, 5, 6]$
    • 5: $[1, 2, 4]$
    • 6: $[4]$
    • 방향성 있는 경우 위의 리스트들을 하나 더 만들어서 in, out 구분
  • 인접 행렬(adjacency matrix)
    • 정점수 x 정점수 크기의 행렬
    • i $\rightarrow$ j 간선 있는 경우 1, else 0

• 행렬 저장

  • 일반행렬
    • 전체 원소 저장
    • 정점 수$^2$ 저장 공간 사용
  • 희소(sparse)행렬
    • 0 아닌 원소만 저장
    • 저장 공간 작아짐
    • 원소가 대부분 0이 아닌 경우 속도 느림

필요 개념

• 실제 그래프 vs 랜덤 그래프

  • 실제 그래프(real graph)
    • 다양한 복잡계로부터 얻어진 그래프
    • sns, 전자상거래 구매내역, 웹, 뇌, 단백질 상호작용, 지식 그래프 등
  • 랜덤 그래프
    • 확률적 과정을 통해 생성한 그래프

• 에르되스-레니(Erdös-Rényi) 랜덤 그래프

  • 임의의 두 정점 사이에 간선이 존재하는지 여부를 동일한 확률 분포로 결정
  • $G(n,p)$
    • $n$: 정점 개수
    • $p$: 임의의 두 정점 사이 간선이 존재할 확률
    • 정점간 연결은 서로 독립적(independent)

• 경로, 거리, 지름

  • 정점 $u$와 $v$ 사이의 경로(path)
    • 두 조건을 만족하는 정점들의 순열(sequence)
    • 조건 1. $u$에서 시작해 $v$에서 끝남
    • 조건 2. 순열에서 연속된 정점은 간선으로 연결됨
  • 경로의 길이
    • 해당 경로 상에 놓이는 간선의 수
  • 정점 $u$와 $v$ 사의의 거리(distance)
    • $u$와 $v$ 사이의 최단 경로의 길이
  • 그래프의 지름(diameter)
    • 정점 간 거리의 최댓값

• 작은 세상 효과(small-world effect)

  • 여섯 단계 분리(six degrees of separation) 실험
    • Milgram, 1960
    • 네브라스카 주 오마하, 켄사스 주 위치타에서 500명 선정
    • 보스턴에 있는 한 사람에게, 지인을 통해서만편지를 전달하게 시킴
    • 25% 편지 도착, 평균 6단계 거침
  • MSN 메신저에서도 평균 거리 7
    • 거대 연결 구조만 고려
  • 높은 확률로 랜덤 그래프에 존재
  • chain, cycle, grid 그래프에서는 작은 세상 효과가 존재하지 않음

• 연결성의 두터운 꼬리 분포

  • 정점의 연결성(degree)
    • $d(v), \vert N(v) \vert$
    • 정점 $v$와 연결된 간선의 수
    • 해당 정점의 이웃들의 수와 같음
  • 방향성 있는 그래프의 경우
    • $d_{out}(v), d_{in}(v)$로 구분됨
  • 실제 그래프에서
    • 연결성 분포는 두터운 꼬리(heavy tail)을 가짐
    • 연결성이 매우 높은 허브(hub) 정점이 존재함을 의미
  • 랜덤 그래프에서
    • 연결성 분포는 높은 확률로 정규 분포와 유사
    • 허브 정점이 존재할 가능성이 0에 가까움

• 연결 요소(connected component)

  • 두 조건을 만족하는 정점들의 집합
  • 조건 1. 연결 요소에 속하는 정점들은 경로로 연결될 수 없음
  • 조건 2. 1의 조건을 만족하면서 정점을 추가할 수 없음

• 거대(giant) 연결 요소

  • 대다수의 정점 포함
  • 랜덤 그래프에도 높은 확률로 거대 연결 요소 존재
  • 단, 정점들의 평균 연결성이 1보다 충분히 커야함
  • Random graph theory 참고

• 군집 구조

  • 군집(community)
    • 집합에 속하는 정점 사이에는 많은 간선 존재
    • 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 간선 존재
  • 지역적 군집 계수(local clustering coefficient)
    • 한 정점에서 군집의 형성 정도 측정
    • 정점 i의 이웃 쌍 중 간선으로 직접 연결된 것의 비율
    • $C_i$
    • 연결성이 0인 정점에서는 지역적 군집 계수 정의 안 됨
    • 정점 i의 지역적 군집 계수가 매우 높다면, i의 이웃들이 높은 확률로 서로 직접 연결되어 있기 때문에, i와 이웃들은 높은 확률로 군집을 형성
  • 전역(global) 군집 계수
    • 각 정점에서의 지역적 군집 계수의 평균
    • (지역적 군집 계수가 정의되지 않는 정점 제외)
  • 실제 그래프에서 군집 계수가 높은 이유
    • 동질성(homophily): 유사한 정점끼리 간선으로 연결될 가능성 높음
    • 전이성(transitivity): 공통이웃이 매개 역할을 해주는 경우 있음
  • 랜덤 그래프에서 지역적/전역적 군집 계수 낮은 이유
    • 랜덤 그래프 $G(n,p)$에서 군집 계수는 $p$
    • 간선 연결이 독립적이기 때문
    • 전이성, 동질성 없음
    • 즉, 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않음