Contents

  1. 1. 그래프란 무엇이고 왜 중요할까?
    1. 1.1. 그래프란 무엇일까?
    2. 1.2. 그래프가 왜 중요할까?
  2. 2. 그래프 관련 인공지능 문제
    1. 2.1. 그래프 관련 인공지능 문제
  3. 3. 그래프 관련 필수 기초 개념
    1. 3.1. 그래프의 분류
    2. 3.2. 그래프의 기초 개념
  4. 4. 그래프의 표현 및 저장
    1. 4.1 파이썬 라이브러리 NetworkX 소개
    2. 4.2. 그래프의 표현 및 저장
  5. 5. Random Graphs
    1. 5.1. real graph
    2. 5.2. random graph
  6. 6. small-world network
    1. 6.1. Preliminaries
    2. 6.2. Small-world Effect
  7. 7. Heavy-Tailed Degree Distributions
    1. 7.1. Degree
    2. 7.2.Heavy-Tailed Degree Distributions
  8. 8. Giant Connected Component
    1. 8.1. Connected Component란?
    2. 8.2. Giant Connected component
  9. 9. Cluster
    1. 9.1. Local Clustering Coefficient
    2. 9.2. Global Clustering Coefficient

그래프 강의의 첫 시간으로 그래프 이론 및 본 강의에서 다룰 내용에 대해서 짧게 소개하고, 그래프 관련 필수 개념들을 소개하는 시간을 갖습니다.

그래프는 다양한 복잡계(Complex Network)를 분석할 수 있는 언어입니다. 그래프를 통해서 다양한 문제들에 접근하기 전에 정점, 간선, 방향성, 가중치 등 그래프 이론에서 사용하는 개념들에 대해서 배워봅니다. 각 정의들을 명확하게 이해하는 데 집중하면서 강의를 들어주시면 감사하겠습니다.

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

1.1. 그래프란 무엇일까?

그래프는 정점집합과 간선 집합으로 이루어진 수학적 구조이다.

하나의 간선은 두 개의 정점을 연결한다.
모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아니다.

Graph Structure는 네트워크로도 불리며, 정점은 vertex 혹은 노드(node) 그리고 간선은 엣지(edge) 혹은 링크(link)라고도 불린다.


1.2. 그래프가 왜 중요할까?

우리 주변에는 많은 복잡계(Complex system)가 있다.

70억 인구로 구성된 사회, 전자 장치로 구성된 통신 시스템, 그 밖에도 정보와 지식, 뇌, 신체 등은 복잡계로 이루어져 있다.

Q. 이런 복잡계가 가진 공통적인 특성은 무엇일까요?
A. 구성 요소 간의 복잡한 상호작용 때문이다.

Q2. 그렇다면 복잡계를 어떻게 표현해야할까?
A2. 그래프 구조를 이용해 표현할 수 있다.

그래프는 복잡계를 효과적으로 표현하고 분석하기 위한 언어이다.

image

온라인 소셜 네트워크를 그래프로 표현한 모습

이외에도 다양한 종류의 Complex System을 Graph를 활용하여 표현할 수 있다.

imageimageimage

imageimageimage

(좌측 상단부터 시계방향으로)뇌(뉴런), 지식그래프, 화학 분자구조, 이미지 분해, 세포간 유사도 그래프, 단백질의 상호작용을 나타낸 모습니다.

그래프는 complex system을 효과적으로 표현하기 위한 구조라고 할 수 있다. 복잡계는 구성 요소들간의 상호작용으로 이루어진다. 상호작용을 표현하기 위한 수단으로 그래프가 널리 사용된다. 복잡계를 이해하고, 복잡계에 대한 정확한 예측을 하기 위해서는 복잡계 이면에 있는 그래프에 대한 이해가 반드시 필요하다. 그래프를 공부함으로써 복잡계가 등장하는 수 많은 분야에 활용 할 수 있다. ex) 전산학, 물리학, 생물학, 화학, 사회과학 등.


2. 그래프 관련 인공지능 문제

2.1. 그래프 관련 인공지능 문제

Node classification

  • 트위터의 공유(retweet) 관계를 분석하여, 각 사용자의 정치적 성향을 알 수 있다.
  • 단백질의 상호작용을 분석하여 단백질의 각 역할을 알아낼 수 있을까?

Link Prediction(거시적 관점)

  • 페이스북 소셜 네트워크는 어떻게 진화할 것인지

Recommendation(미시적 관점)

  • 각자에게 필요한 물건은 무엇일까? 어떤 물건을 구매해야 만족도가 높을 까?

Community detection

  • 연결관계로부터 사회적 무리를 찾아낼 수 있을까?
  • ex) 그래프 내에서 빽빽하게 모여있는 군집을 찾고, 의미있는 Social circle을 찾을 수 있다.

Ranking 및 Information Retrieval

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

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

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


3. 그래프 관련 필수 기초 개념

3.1. 그래프의 분류

Undirected graph

  • edge에 방향이 없는 그래프
  • vertex to vertex의 edge에 방향이 없는 그래프를 의미한다.
  • ex) 페이스북 친구

Directed graph

  • edge에 방향이 있는 그래프
  • ex) 인스타, 트위터의 팔로우 팔로워 관계

Unweighted graph

  • edge에 가중치가 없는 그래프
  • 웹 그래프, 페이스북 친구 그래프 등의 경우에서처럼 연결별로 특정한 의미부여가 없는 그래프를 말한다.

Weighted graph

  • edge에 가중치가 있는 그래프
  • 전화그래프
  • 유사도 그래프 등의 경우처럼 edge별로 ‘중요도’가 각기 다른 그래프를 의미한다.
  • edge에 가중치가 부여되어 edge들 간에도 차별성을 준다.

Unpartite Graph

  • 단일 종류의 정점(vertex)를 가진다.
  • 모두 한 종류의 vertex로 되어있으며, vertex간의 차이가 없는 그래프다

Bipartite Graph

  • 다른 종류의 정점사이에만 간선이 연결되는 그래프
  • ex) 전자상거래 구매내역(사용자, 상품)
  • 영화출연 그래프(배우, 영화)


3.2. 그래프의 기초 개념

이 부분은 블로그 내 포스팅에서 확인하길 바란다.


4. 그래프의 표현 및 저장

4.1 파이썬 라이브러리 NetworkX 소개

그래프를 생성, 변경, 시각화할 수 있는 파이썬 라이브러리 NetworkX에 대한 자세한 정보는 여기에서 확인할 수 있다.

또한, 비슷한 용도로 사용되는 Snap.py라는 라이브러리는 여기에서 확인할 수 있다.

두 라이브러리의 경우 NetworkX는 속도가 느린 대신 사용성이 좋고, 반대로 snap.py의 경우에는 속도가 빠르지만 사용에 어려움이 있다고 하니 참고바란다.

라이브러리 loading

image

그래프 초기화

image

Vertex 추가, 카운트 그리고 목록 반환

image

더 많은 vertex 추가

image

Edge 추가하고 목록 반환

image

더 많은 edge 추가

image

그래프 시각화

imageimage


4.2. 그래프의 표현 및 저장

간선에 방향성이 없는 경우 및 방향성이 있는 경우, 순서쌍의 순서에 유의해서 출력한다.

NetworkX를 이용하여 그래프를 표현하고 저장하기

image

일반 행렬은 전체 원소를 저장하므로 정점 수의 제곱에 비례하는 저장공간을 사용 희소행렬은 0이 아닌 원소만을 저장하므로 간선의 수에 비례하는 저장공간을사용 예시) 정점의 수가 10만, 간선의 수가 100만이라면 정점의 수의 제곱(100억) » 간선의수(100만)


5. Random Graphs

5.1. real graph

생활 속의 실제 그래프는 더 큰 범주에서 벌어나는 일에 대한 그래프이므로 이상적인 구조의 graph structure 및 theory를 따르지 않는다.


5.2. random graph

Erdős-Rényi Random Graph

임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정됩니다 에르되스-레니 랜덤그래프$G(n,p)$는

  • $n$개의 정점을 가진다.
  • 임의의 두 개의 정점 사이에 간선이 존재할 확률은 $p$이다.
  • 점정 간의 연결은 서로 독립적(Independent)이다.

Q. $G(3, 0.3)$에 의해 생성될 수 있는 그래프와 각 확률은?

image


6. small-world network

인간 관계에서 몇 단계만 거치면 서로 연결되어 있다는 것을 보인 이론이다.

https://en.wikipedia.org/wiki/Small-world_network


6.1. Preliminaries

Graph structure에서의 Path, Distance, Diameter 등의 기본 개념은 본 포스팅에서 생략하도록 한다. 더 자세한 내용은 해당 정의 링크(Path 정의, Distance 정의 Diameter 정의)에서 추가적으로 확인하길 바란다.


6.2. Small-world Effect

Stanley Milgram의 Six Degrees of Separation test

  • 사회학자 스탠리 밀그램에 의해 1960년에 수행한 실험이다.
  • 오마하와 위치타에서 500명의 사람을 뽑는다.
  • 그들에게 보스턴에 있는 한 사람에게 편지를 전달하게끔 하였다.
  • 단, 지인을 통해서만 전달하게끔 하였다.

image

결과적으로 25%의 편지만 도착했고, 평균적으로 6단계만을 거쳤다.

image

비슷한 실험으로, MSN 메신저에서 정점간 평균 거리는 7정도 밖에 되지 않았다. (단, 거대 연결 구조만을 고려했다. 이는 뒤에서 설명하도록 한다.)

image


7. Heavy-Tailed Degree Distributions

7.1. Degree

Graph에서의 Degree는 해당 vertex에 연결된 edge의 수를 의미한다. 특히, 방향성이 존재하는 directed graph에서는 out degree와 In degree로 나뉘게 된다. 자세한 내용은 여기에서 확인하길 바란다. 특히, $d(v)$와 $\vert N(v)\vert$에 대한 내용을 잘 살펴보길 바란다.


7.2.Heavy-Tailed Degree Distributions

실생활에서의 그래프의 degree distribution는 Heavy Tail을 갖는다. (꼬리가 길게 뽑혀나오는 형태의 분포). 그 말인즉슨 degree가 매우 높은 허브(hub) vertex가 존재함을 의미한다.

반면에 랜덤그래프의 degree distribution은 높은 확률로 정규분포와 유사하다. 이 경우, degree가 매우 높은 허브 정점이 존재할 가능성은 0에 가깝다.

image


8. Giant Connected Component

8.1. Connected Component란?

Connected 하지 않은 graph의 각 component를 의미한다. 수학적으로 표현된 더 자세한 내용은 해당 링크에서 확인할 수 있다.

3개의 Component로 구성된 graph

image


8.2. Giant Connected component

실제 생활 속 그래프에는 대부분 Giant connected component가 존재하며, 이는 대다수의 vertices를 포함하는 구조로 되어있다.

example)

MSN 메신저 그래프에는 99.9%의 vertices가 하나의 거대한 component의 요소에 포함된다. (쉽게 말하자면, 독립적인 vertex가 전체 그래프 내에서 거의 없음을 의미한다. )

image

Random graph의 GCC

랜덤 그래프에도 높은 확률로 GCC가 존재한다. 단, vertices의 평균 degree가 1보다 충분히 커야한다. 자세한 내용은 random graph theory를 참고하길 바란다.

cf) 랜덤그래프의 거대 연결 요소

Random Graphs and Giant Components에 대한 내용은 포스팅에서 확인할 수 있다. 궁금한 분들은 참고하길 바란다.


9. Cluster

Community란 다음 조건들을 만족하는 vertices의 집합을 의미한다.

  • 집합에 속하는 정점 사이에는 많은 간선들이 존재한다.
  • 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재한다.

image


9.1. Local Clustering Coefficient

Local Clustering Coefficient는 한 정점에서 군집의 형성 정도를 측정한다.

  • 정점 $i$의 지역적 군집 계수는 정점 $i$의 이웃 쌍 중 간선으로 직접 연결된 것의 비율을 의미한다. 이 때, Local clustering coefficient를 $C_i$로 표시한다.
  • 예)
    • image
    • 정점 1의 이웃은 4개이며, 총 6개의 이웃 쌍$((2,3),(2,4),(2,5),(3,4),(3,5),(4,5))$이 존재한다. 그 중 3개의 쌍$((2,4),(2,3),(3,5))$이 간선으로 직접 연결되어있다. 따라서 $C_1=\frac{3}{6}=0.5$이다.
    • image
  • 참고로 degree가 0인 vertex에서는 지역적 군집 계수가 정의되지 않는다.

그렇다면 GCC가 Cluster와 어떻게 연결되는 것인가?

  • 정점 $i$의 GCC가 매우 높다고 가정하자. 이는 vertex $i$의 이웃들이 서로 높은 확률로 연결되어있다는 의미이고, 그렇기에 vertex $i$와 $i$의 Neighborhood $N(i)$는 높은 확률로 Cluster를 형성한다는 의미이다.


9.2. Global Clustering Coefficient

실제 그래프에서는 군집 계수가 높다. 즉, 많은 군집이 존재한다. 여기에는 몇 가지 이유가 있을 수 있다.

  1. 동질성(homophily) : 서로 유사한 정점끼리 간선으로 연결될 가능성이 높다.

    image

  2. 전이성(Transitivity) : 공통 Neighbor가 있는 경우, 해당 Neighbor가 매개 역할을 해줄 수 있다.

    image

반면 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않다.

구체적으로 랜덤그래프 $G(n,p)$에서의 군집계수는 $p$이다. 랜덤 그래프에서의 간선 연결이 독립적인 것을 고려하면 당연한 결과다. 즉 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않는다.