그래프란 무엇이고 왜 중요할까?

그래프란 무엇일까?

• 그래프는 정점(노드) 집합과 간선(엣지, 링크) 집합으로 이루어진 수학적 구조

• 하나의 간선은 두 개의 정점을 연결

• 모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아님

• 우리 주변에는 많은 복잡계(Complex System) 이 있음

  • 사회, 통신 시스템, 뇌, 신체 등

  • 복잡계는 구성 요소 간의 상호작용으로 이루어짐, 복잡계의 상호작용을 그래프로 표현

    → 그래프는 복잡계를 효과적으로 표현하기 위한 언어

그래프 관련 인공지능 문제

정점 분류 (Node Classification) 문제

• 트위터에서 공유(Retweet) 관계를 분석하여, 각 사용자의 정치적 성향을 알 수 있을까?

- 비슷한 정치적 성향을 가진 사람끼리 공유를 더 많이함
- 새로운 정점이 등장했을 때 어떤 글을 공유했냐에 따라 정치적 성향 예측 가능

연결 예측 (Link Prediction) 문제

• 거시적 관점
  • 주어진 그래프가 어떻게 성장할지 예측하는 문제
  • 페이스북 소셜네트워크는 어떻게 진화할까?
• 미시적 관점
  • 추천 (Recommendation) 문제
  • 각 정점이 앞으로 어떤 정점과 연결될지 예측하는 문제

군집 분석 (Community Detection) 문제

• 서로 밀접하게 연결된 정점들의 집합, 군집을 찾아내는 문제
• 많은 그래프에서 군집은 의미있는 구조를 띔
• 연결 관계로부터 사회적 무리 (Social Circle) 을 찾아낼 수 있을까?

랭킹 (Ranking) 및 정보 검색 (Information Retrieval) 문제

• 웹이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼 수 있을까?

정보 전파 (Information Cascading) 및 바이럴 마케팅 (Viral Marketing) 문제

• 정보는 네트워크를 통해 어떻게 전달될까? 어떻게 정보 전달을 최대화 할 수 있을까?

그래프 관련 필수 기초 개념

그래프의 유형 및 분류

• 방향
  • 방향이 없는 그래프 (Undirected Graph)
    • 페이스북 친구 그래프
    • 협업 관계 그래프
  • 방향이 있는 그래프 (Directed Graph)
    • 트위터 팔로우 그래프
    • 인용 그래프
• 가중치
  • 가중치가 없는 그래프 (Unweighted Graph)
    • 페이스북 친구 그래프
  • 가중치가 있는 그래프 (Weighted Graph)
    • 전화 그래프 (전화 횟수)
    • 유사도 그래프
• 정점의 종류
  • 동종 그래프 (Unpartite Graph)
    • 단일 종류의 정점을 가짐
    • 페이스북 친구 그래프
  • 이종 그래프 (Bipartite Graph)
    • 두 종류의 정점을 가짐
    • 다른 종류의 정점사이에만 간선이 연결됨
    • 배우 - 영화

기초 개념

• 정점들의 집합 V, 간선들의 집합 E, 그래프 G = (V, E)
• 정점의 이웃은 그 정점과 연결된 다른 정점
  • N(1) = {2, 5}
• 방향성이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분함
  • 나가는 이웃 (Out-Neighbor) 의 집합을 $N\mathit{out}(v)$ 으로 적음
  • 들어오는 이웃 (In-Neighbor) 의 집합을 $N\mathit{in}(v)$ 으로 적음

(실습) 그래프의 표현 및 저장

• 파이썬 라이브러리 NetworkX 사용 (Snap.py 라는 라이브러리도 많이 사용함, 사용 불편하지만 빠름)
  • 그래프 생성, 변경, 시각화 가능
  • 그래프의 구조와 변화 분석 가능

https://colab.research.google.com/drive/1-cbGAX97xMUyn1CkXApn0BWcpKRBRWlB?usp=sharing

https://colab.research.google.com/drive/1pNeTsA_8yeM6rAJPgoBQBiZFwQ9is6eh

간선을 표현하는 방법

• 간선 리스트 (Edge List) : 그래프를 간선들의 리스트로 저장
  • 방향성이 있는 경우에는 (출발점, 도착점) 순서로 저장
• 인접 리스트 (Adjacency List) : 각 정점의 이웃들을 리스트로 저장
  • 방향성이 없는 경우
    • 1 : {2, 5}
    • 2 : {1, 3, 5}
    • ...
  • 방향성이 있는 경우, in 과 out 을 따로 만듦
    • out
      • 1 : {2}
      • 2 : {5}
      • ...
    • in
      • 1 : {5}
      • 2 : {1, 3, 5}
      • ...
• 인접 행렬 (Adjacency Matrix)
  • 정점 수 x 정점 수 크기의 행렬 (일반 행렬, nx.to_numpy_array)
    • 방향성이 없는 경우, 정점 i 와 정점 j 에 간선이 있으면 A[i][j] = 1, A[j][i] = 1
    • 방향성이 있는 경우, 정점 i 에서 정점 j 로 가는 간선이 있으면 A[i][j] = 1
  • 0이 아닌 원소만을 저장하여 간선의 수에 비례하는 저장 공간 사용 (희소 행렬, nx.to_scipy_sparse_matrix)
    • 0 이 많을 때 효율적

---

실제 그래프는 어떻게 생겼을까?

실제 그래프 vs 랜덤 그래프

• 실제 그래프는 다양한 복잡계로부터 얻어진 그래프
  • 소셜 네트워크, 인터넷, 웹, 전자상거래 구매 내역 등
  • MSN 메신저 그래프를 예로 보자
    • 1억 8천만 정점 (사용자)
    • 13억 간선 (메시지를 주고받은 관계)
• 랜덤 그래프는 확률적 과정을 통해 생성한 그래프
  • 에르되스-레니 랜덤 그래프
    • 임의의 두 정점 사이에 간선이 존재하는지 여부를 동일한 확률 분포로 결정
    • 에르되스-레니 랜덤그래프 G(n, p) 는
      • n 개의 정점을 가짐
      • 임의의 두 개의 정점 사이에 간선이 존재할 확률은 p
      • 정점 간의 연결은 서로 독립적
      • G(3, 0.3) 에 의해 생성될 수 있는 그래프와 각각의 확률은?

            - 8 개의 결과가 나올 수 있으며 각 확률은 p 나 not p 를 n 번이 되도록 곱함

그래프의 구조적 특성

• 실제 그래프의 구조적 특성
  • 작은 세상 효과
  • 연결성의 두터운 꼬리 분포
  • 거대 연결 요소
  • 군집 구조
• 랜덤 그래프의 구조적 특성 (항상 만족하진 않음)
  • 작은 세상 효과
  • 거대 연결 요소

필수 개념 : 경로, 거리 및 지름

• 정점 u 와 v 사이의 경로(path) 는 아래 조건을 만족하는 정점들의 순열(sequence)
  • u 에서 시작해서 v 에서 끝나야 함
  • 순열에서 연속된 정점은 간선으로 연결돼야 함

• 경로의 길이는 해당 경로 상에 놓인 간선의 수, 경로의 정점 개수 - 1
  • 경로 1, 4, 6, 8 의 길이는 3
• 정점 u 와 v 사이의 거리(Distance) 는 u 와 v 사이의 최단 경로의 길이
  • 위 예시에서 여러 경로 중 가장 길이가 작은 3
• 그래프의 지름(Diameter) 은 정점 간 거리의 최댓값
  • 위 예시에서 2 와 8 or 2 와 7 의 거리인 4 가 지름

작은 세상 효과

• 임의의 두 사람을 골랐을 때, 몇 단계의 지인을 거쳐 연결되어 있을까?

• 여섯 단계 분리 (Six Degrees of Separation) 실험

  • 1960년대 수행된 실험에서 한 지역에서 다른 지역으로 편지를 보낼 때 지인을 통해 전달할 경우 6 단계가 걸린다는 실험

  • MSN 메신저에서도 정점 간의 평균 거리는 7 정도 (거대 연결 구조에 속하는 정점만 고려)

    → 이러한 현상을 작은 세상 효과라고 함

• 작은 세상 효과는 높은 확률로 랜덤 그래프에도 존재

  • 모든 사람이 100명의 지인이 있다 하면 5명만 거쳐도 100억명을 알 수 있음
  • 하지만 모든 그래프에서 효과가 나타나지 않음 (체인, 사이클, 격자 그래프에서는 효과가 존재하지 않음)

연결성 (Degree)

• 정점의 연결성은 그 정점과 연결된 간선의 수
• 해당 정점의 이웃들의 수와 같음
• d(v), $d_v$ 혹은 |N(v)| 로 적음
• 방향 그래프에서는 in, out 존재

연결성의 두터운 꼬리 분포

• 실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail) 를 가짐
  • 즉, 연결성이 매우 높은 허브(Hub) 정점이 존재
  • 트위터 팔로워 일반인과 비교하여 BTS (Hub) 는 매우 높은 연결성 지님
• 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사
  • 실제 분포 중 안되는 경우는 키의 분포, 10 미터 넘을 수 없음

거대 연결 요소

• 연결 요소 (Connected Component) 의 조건
  • 연결 요소에 속하는 정점들은 경로로 연결될 수 있음
  • 위 조건을 만족하면서 정점을 추가할 수 없음
• 실제 그래프에는 거대 연결 요소 (Giant Connected Component) 가 존재함
  • 거대 연결 요소는 대다수의 정점을 포함
  • MSN 메신저 그래프에는 99.9% 의 정점이 하나의 거대 연결 요소에 포함됨

• 랜덤 그래프에도 높은 확률로 거대 연결 요소 존재
  • 단, 정점들의 평균 연결성이 1보다 충분히 커야함
  • 자세한 이유는 Random Graph Theory 참고

군집 구조

• 군집 (Community) 이란 다음 조건들을 만족하는 정점들의 집합 (수학적으로 엄밀한 정의는 아님)
  • 집합에 속하는 정점 사이에는 많은 간선이 존재
  • 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재
• 지역적 군집 계수 (Local Clustering Coefficient) 는 한 정점에서 군집의 형성 정도를 측정
  • 정점 i 의 지역적 군집 계수는 정점 i 의 이웃 쌍 중 간선으로 직접 연결된 것의 비율
  • 정점 i 의 LCC 는 $C_i$ 로 표현
  • 이웃끼리 연결된 개수 / 이웃개수C2
• 지역적 군집 계수와 군집과 관계
  • 정점 i 의 지역적 군집 계수가 매우 높으면, 정점 i 의 이웃끼리 많이 연결돼있기 때문에 정점 i 와 그 이웃들은 높은 확률로 군집 형성
• 전역 군집 계수 (Global Clustering Coefficient) 는 전체 그래프에서 군집의 형성 정도를 측정
  • 그래프 G 의 전역 군집 계수는 각 정점에서의 지억적 군집 계수의 평균 (단, 연결성이 0이라 지역적 군집 계수가 정의되지 않는 정점 제외)
• 실제 그래프는 군집 계수가 높음. 즉 많은 군집이 존재
  • 다양한 이유
    • 동질성 (Homophily) : 서로 유사한 정점끼리 간선으로 연결될 가능성이 높음
      • 같은 동네에 사는 같은 나이의 아이들이 친구가 됨
    • 전이성 (Transitivity) : 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줌
      • 친구를 서로에게 소개해주는 경우
• 반면, 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않음
  • 랜덤 그래프 G(n, p) 에서 군집 계수는 p 인데, 이는 독립적이므로 간선 연결에 있어 전이성과 동질성이 없음. 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않음

---

참조

• BoostCamp AI Tech