강의 복습 내용

[Day 21] 그래프 이론 기초 & 그래프 패턴

[Graph 1강] 그래프란 무엇이고 왜 중요할까?

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

1.1 그래프란 무엇일까?

• 그래프(Graph)는 정점 집합과 간선 집합으로 이루어진 수학적 구조입니다
• 하나의 간선은 두 개의 정점을 연결합니다
• 모든 정점 쌍이 반드시 간선으로 직접 연결되는 것은 아닙니다
• 그래프는 네트워크(Network)로도 불립니다
• 정점(Vertex)은 노드(Node)로 간선은 엣지(Edge) 혹은 링크(Link)로도 불립니다

1.2 그래프가 왜 중요할까?

• 우리 주변에는 많은 복잡계(Complex System)가 있습니다
• 사회는 70억 인구로 구성된 복잡계입니다
• 통신 시스템은 전자 장치로 구성된 복잡계입니다
• 그 밖에도, 정보와 지식, 뇌, 신체 역시 복잡계로 생각할 수 있습니다
• Q. 이런 복잡계가 가진 공통적인 특성은 무엇일까요?
  • A. 구성 요소 간의 복잡한 상호작용입니다
• Q. 이런 복잡계를 어떻게 표현할까요?
  • 정답은 그래프(Graph) 입니다!
  • 그래프는 복잡계를 표현하고 분석하기 위한 언어입니다- 복잡계는 구성 요소들 간의 상호작용으로 이루어집니다
  • 상호작용을 표현하기 위한 수단으로 그래프가 널리 사용됩니다
  • 복잡계를 이해하고, 복잡계에 대한 정확한 예측을 하기 위해서는 복잡계 이면에 있는 그래프에 대한 이해가 반드시 필요합니다
• 그래프를 공부함으로써 복잡계가 등장하는 수많은 분야에 활용할 수 있습니다 전산학, 물리학, 생물학, 화학, 사회과학 등이 그 예시입니다

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

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

• 정점 분류(Node Classification) 문제
  • 트위터에서의 공유(Retweet) 관계를 분석하여, 각 사용자의 정치적 성향을 알 수 있을까?
  • 단백질의 상호작용을 분석하여 단백질의 역할을 알아낼 수 있을까?
• 연결 예측(Link Prediction) 문제
  • 페이스북 소셜네트워크는 어떻게 진화할까?
• 추천(Recommendation) 문제
  • 각자에게 필요한 물건은 무엇일까? 어떤 물건을 구매해야 만족도가 높을까?
• 군집 분석(Community Detection) 문제
  • 연결 관계로부터 사회적 무리(Social Circle)을 찾아낼 수 있을까?
• 랭킹(Ranking) 및 정보 검색(Information Retrieval) 문제
  • 웹(Web)이라는 거대한 그래프로부터 어떻게 중요한 웹페이지를 찾아낼 수 있을까?
• 정보 전파(Information Cascading) 및 바이럴 마케팅(Viral Marketing) 문제
  • 정보는 네트워크를 통해 어떻게 전달될까? 어떻게 정보 전달을 최대화 할 수 있을까?

2.2 우리 수업의 목적 및 범위

• 앞선 질문과 관련된 인공지능 기술을 배웁니다
• 정점 분류, 연결 예측, 추천, 군집 분석, 랭킹, 정보 검색, 정보 전파, 바이럴 마케팅 등
• 최첨단 기술보다는 기초와 직관적인 방법론에 집중합니다
• 하지만 그래프 신경망(Graph Neural Networks) 등 최첨단 기술도 일부 소개합니다

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

3.1 그래프의 유형 및 분류

• 방향이 없는 그래프(Undirected Graph) vs 방향이 있는 그래프(Directed Graph)
  • 간선에 방향이 없는 그래프 : 협업 관계 그래프, 페이스북 친구 그래프
  • 간선에 방향이 있는 그래프 : 인용 그래프, 트위터 팔로우 그래프
• 가중치가 없는 그래프(Unweighted Graph) vs 가중치가 있는 그래프(Weighted Graph)
  • 간선에 가중치가 없는 그래프 : 웹 그래프, 페이스북 친구 그래프
  • 간선에 가중치가 있는 그래프 : 전화 그래프, 유사도 그래프
• 동종 그래프(Unpartite Graph) vs 이종 그래프(Bipartite Graph)
  • 동종 그래프는 단일 종류의 정점을 가집니다 : 웹 그래프, 페이스북 친구 그래프
  • 이종 그래프는 두 종류의 정점을 가집니다 : 다른 종류의 정점사이에만 간선이 연결됩니다, 전자 상거래 구매내역 (사용자, 상품), 영화 출연 그래프 (배우, 영화)
• Q. 다음 전자 상거래 구매 내역은 어떤 유형의 그래프일까요?
  • A. 방향성이 없고, 가중치가 있는 이종 그래프입니다

3.2 그래프 관련 필수 기초 개념

• 그래프(Graph)는 정점 집합과 간선 집합으로 이루어진 수학적 구조입니다
• 보통 정점들의 집합을 𝑽, 간선들의 집합을 𝑬, 그래프를 𝑮 = (𝑽, 𝑬)로 적습니다
• 정점의 이웃(Neighbor)은 그 정점과 연결된 다른 정점을 의미합니다
• 정점 𝑣의 이웃들의 집합을 보통 𝑵(𝒗) 혹은 𝑵𝒗로 적습니다

3.3 그래프 관련 필수 기초 개념

• 방향성이 있는 그래프에서는 나가는 이웃과 들어오는 이웃을 구분합니다
• 정점 𝑣에서 간선이 나가는 이웃(Out-Neighbor)의 집합을 보통 𝑵out(𝒗)로 적습니다
• 정점 𝑣로 간선이 들어오는 이웃(In-Neighbor)의 집합을 보통 𝑵in(𝒗)로 적습니다

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

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

• 본 수업에서는 그래프를 다루기 위해 파이썬 라이브러리인 NetworkX를 사용합니다.
• NetworkX를 이용하여, 그래프를 생성, 변경, 시각화할 수 있습니다
• 그래프의 구조와 변화 역시 살펴볼 수 있습니다
• 본 수업에서는 사용하지 않지만, Snap.py 라는 라이브러리도 많이 사용됩니다
• 실습
  • 실습에 필요한 라이브러리를 불러옵니다
  • 그래프를 초기화합니다
  • 정점을 추가하고, 정점의 수를 세고, 목록을 반환합니다
  • 더 많은 정점을 추가합니다
  • 간선을 추가하고, 목록을 반환합니다
  • 더 많은 간선을 추가합니다
  • 만들어진 그래프를 시각화합니다

4.2 그래프의 표현 및 저장

• 간선 리스트(Edge List): 그래프를 간선들의 리스트로 저장

  • 각 간선은 해당 간선이 연결하는 두 정점들의 순서쌍(Pair)으로 저장됩니다
  • 방향성이 있는 경우에는 (출발점, 도착점) 순서로 저장됩니다

• 인접 리스트(Adjacent list) – 방향성이 없는 경우:

  • 각 정점의 이웃들을 리스트로 저장
  • 각 정점의 나가는 이웃들과 들어오는 이웃들을 각각 리스트로 저장

• 인접 행렬(Adjacency Matrix) – 방향성이 없는 경우

  • 정점 수 × 정점 수 크기의 행렬
  • 정점 𝑖와 𝑗 사이에 간선이 있는 경우, 행렬의 𝑖행 𝑗열 (그리고 𝑗행 𝑖열) 원소가 1
  • 정점 𝑖와 𝑗 사이에 간선이 없는 경우, 행렬의 𝑖행 𝑗열 (그리고 𝑗행 𝑖열) 원소가 0

• 인접 행렬(Adjacency Matrix) – 방향성이 있는 경우

  • 정점 수 × 정점 수 크기의 행렬
  • 정점 𝑖에서 𝑗로의 간선이 있는 경우, 행렬의 𝑖행 𝑗열 원소가 1
  • 정점 𝑖에서 𝑗로의 간선이 없는 경우, 행렬의 𝑖행 𝑗열 원소가 0

• 실습

  • NetworkX를 이용하여 그래프를 표현하고 저장하기
    • 일반 행렬은 전체 원소를 저장하므로 정점 수의 제곱에 비례하는 저장 공간을 사용
    • 희소 행렬은 0이 아닌 원소만을 저장하므로 간선의 수에 비례하는 저장 공간을 사용

• 1강 정리

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

• 그래프는 정점 집합과 간선 집합으로 이루어진 수학적 구조입니다
• 그래프는 복잡계를 표현하고 분석하기 위한 언어입니다

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

• 정점분류, 연결예측, 추천, 군집분석, 랭킹, 정보검색, 정보전파, 바이럴마케팅 등

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

• 방향성이 있는/없는 그래프, 가중치가 있는/없는 그래프, 동종/이종 그래프
• 나가는/들어가는 이웃

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

• 파이썬 라이브러리 NetworkX
• 간선 리스트, 인접 리스트, 인접 행렬

[Graph 2강] 실제 그래프는 어떻게 생겼을까?

1. 실제 그래프 vs 랜덤 그래프

1.1 주요 개념 복습

• 그래프(Graph)는 정점 집합과 간선 집합으로 이루어진 수학적 구조입니다
• 보통 정점들의 집합을 𝑽, 간선들의 집합을 𝑬, 그래프를 𝑮 = (𝑽, 𝑬)로 적습니다
• 정점의 이웃(Neighbor)은 그 정점과 연결된 다른 정점을 의미합니다
• 정점 𝑣의 이웃들의 집합을 보통 𝑵(𝒗) 혹은 𝑵𝒗로 적습니다

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

• 실제 그래프(Real Graph)란 다양한 복잡계로 부터 얻어진 그래프를 의미합니다
• 소셜 네트워크, 전자상거래 구매 내역, 인터넷, 웹, 뇌, 단백질 상호작용, 지식 그래프 등
• 본 수업에서는 MSN 메신저 그래프를 실제 그래프의 예시로 사용합니다
  • MSN 메신저 그래프 : 1억 8천만 정점 (사용자), 13억 간선 (메시지를 주고받은 관계)
• 랜덤 그래프(Random Graph)는 확률적 과정을 통해 생성한 그래프를 의미합니다
• 본 수업에서는 에르되스(Erdős)와 레니(Rényi)가 제안한 랜덤 그래프 모델을 사용합니다
• 에르되스-레니 랜덤 그래프(Erdős-Rényi Random Graph)
  • 임의의 두 정점 사이에 간선이 존재하는지 여부는 동일한 확률 분포에 의해 결정됩니다
  • 에르되스-레니 랜덤그래프 𝐺(𝑛,𝑝)는
    • 𝑛개의 정점을 가집니다
    • 임의의 두 개의 정점 사이에 간선이 존재할 확률은 𝑝입니다
    • 정점 간의 연결은 서로 독립적(Independent)입니다
  • Q. 𝑮(3,0.3)에 의해 생성될 수 있는 그래프와 각각의 확률은?
    

2. 작은 세상 효과

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

• 정점 𝑢와 𝑣의 사이의 경로(Path)는 아래 조건을 만족하는 정점들의 순열(Sequence)입니다
  (1) 𝑢에서 시작해서 𝑣에서 끝나야 합니다
  (2) 순열에서 연속된 정점은 간선으로 연결되어 있어야 합니다
• 경로의 길이는 해당 경로 상에 놓이는 간선의 수로 정의됩니다
• 정점 𝑢와 𝑣의 사이의 거리(Distance)는 𝑢와 𝑣 사이의 최단 경로의 길이입니다
• 그래프의 지름(Diameter)은 정점 간 거리의 최댓값입니다

2.2 작은 세상 효과

• 임의의 두 사람을 골랐을 때, 몇 단계의 지인을 거쳐 연결되어 있을까?
• 여섯 단계 분리(Six Degrees of Separataion) 실험
  • 사회학자 스탠리 밀그램(Stanley Milgram)에 의해 1960년대에 수행된 실험입니다
  • 오마하 (네브라스카 주)와 위치타 (켄사스 주)에서 500명의 사람을 뽑았습니다
  • 그들에게 보스턴에 있는 한 사람에게 편지를 전달하게끔 하였습니다
  • 단, 지인를 통해서만 전달하게끔 하였습니다
• Q. 목적지에 도착하기까지 몇 단계의 지인을 거쳤을까요?
  • A. 25%의 편지만 도착했지만, 평균적으로 6 단계만을 거쳤습니다
• Q. MSN 메신저 그래프에서는 어떨까요?
  • A. 정점 간의 평균 거리는 7 정도 밖에 되지 않습니다
• 이러한 현상을 작은 세상 효과(Small-world Effect)라고 부릅니다
• 한국에서는 “사돈의 팔촌”이 먼 관계를 나타내는 표현으로 사용됩니다
• 즉, 아무리 먼 관계도 결국은 사돈의 팔촌(10촌 관계)입니다
• 작은 세상 효과는 높은 확률로 랜덤 그래프에도 존재합니다
• 모든 사람이 100명의 지인이 있다고 가정해봅시다
• 다섯 단계를 거치면 최대 100억(= 100^5)명의 사람과 연결될 수 있습니다
• 단, 실제로는 지인의 중복 때문에 100억 명보다는 적은 사람일 겁니다
• 하지만 여전히 많은 사람과 연결될 가능성이 높습니다
• 하지만 모든 그래프에서 작은 세상 효과가 존재하는 것은 아닙니다
• 체인(Chain), 사이클(Cycle), 격자(Grid) 그래프에서는 작은 세상 효과가 존재하지 않습니다

3. 연결성의 두터운-꼬리 분포

3.1 필수 개념: 연결성

• 정점의 연결성(Degree)은 그 정점과 연결된 간선의 수를 의미합니다
• 정점 𝑣의 연결성은 해당 정점의 이웃들의 수와 같습니다
  • 보통 정점 𝑣의 연결성은 𝒅(𝒗), 𝒅𝒗 혹은 |𝑵(𝒗)|로 적습니다
• 정점의 나가는 연결성(Out Degree)은 그 정점에서 나가는 간선의 수를 의미합니다
  • 보통 정점 𝑣의 연결성은 𝒅out(𝒗) 혹은 |𝑵out(𝒗)|으로 표시합니다
• 정점의 들어오는 연결성(In Degree)은 그 정점에서 들어오는 간선의 수를 의미합니다
  • 보통 정점 𝑣의 연결성은 𝒅in(𝒗) 혹은 |𝑵in(𝒗)|으로 표시합니다

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

• 실제 그래프의 연결성 분포는 두터운 꼬리(Heavy Tail)를 갖습니다
• 즉, 연결성이 매우 높은 허브(Hub) 정점이 존재함을 의미합니다
• 랜덤 그래프의 연결성 분포는 높은 확률로 정규 분포와 유사합니다
• 이 경우, 연결성이 매우 높은 허브(Hub) 정점이 존재할 가능성은 0에 가깝습니다
• 정규 분포와 유사한 예시로는 키의 분포가 있습니다
• 키가 10 미터를 넘는 극단적인 예외는 존재하지 않습니다

4. 거대 연결 요소

4.1 필수 개념: 연결 요소

• 연결 요소(Connected Component)는 다음 조건들을 만족하는 정점들의 집합을 의미합니다
  (1) 연결 요소에 속하는 정점들은 경로로 연결될 수 있습니다
  (2) (1)의 조건을 만족하면서 정점을 추가할 수 없습니다

4.2 거대 연결 요소

• 실제 그래프에는 거대 연결 요소(Giant Connected Component)가 존재합니다
  • 거대 연결 요소는 대다수의 정점을 포함합니다
  • MSN 메신저 그래프에는 99.9%의 정점이 하나의 거대 연결 요소에 포함됩니다
• 랜덤 그래프에도 높은 확률로 거대 연결 요소(Giant Connected Component)가 존재합니다
  • 단, 정점들의 평균 연결성이 1보다 충분히 커야 합니다
  • 자세한 이유는 Random Graph Theory를 참고하시기 바랍니다

5. 군집 구조

5.1 필수 개념: 군집

• 군집(Community)이란 다음 조건들을 만족하는 정점들의 집합입니다
  (1) 집합에 속하는 정점 사이에는 많은 간선이 존재합니다
  (2) 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재합니다
  수학적으로 엄밀한 정의는 아닙니다

5.1 필수 개념: 지역적 군집 계수

• 지역적 군집 계수(Local Clustering Coefficient)는 한 정점에서 군집의 형성 정도를 측정합니다
  • 정점 𝑖의 지역적 군집 계수는 정점 𝑖의 이웃 쌍 중 간선으로 직접 연결된 것의 비율을 의미합니다
  • 정점 𝑖의 지역적 군집 계수를 𝑪𝒊로 표현합시다
  • 참고로 연결성이 0인 정점에서는 지역적 군집 계수가 정의되지 않습니다
• 잠깐, 지역적 군집 계수가 군집이랑 어떻게 연결되는 것이죠?
• 정점 𝑖의 지역적 군집 계수가 매우 높다고 합시다
• 즉, 정점 𝑖의 이웃들도 높은 확률로 서로 간선으로 연결되어 있습니다
• 정점 𝑖와 그 이웃들은 높은 확률로 군집을 형성합니다

5.1 필수 개념: 전역 군집 계수

• 전역 군집 계수(Global Clustering Coefficient)는 전체 그래프에서 군집의 형성 정도를 측정합니다
• 그래프 𝐺의 전역 군집 계수는 각 정점에서의 지역적 군집 계수의 평균입니다
• 단, 지역적 군집 계수가 정의되지 않는 정점은 제외합니다

5.2 높은 군집 계수

• 실제 그래프에서는 군집 계수가 높습니다. 즉 많은 군집이 존재합니다
• 여러가지 이유가 있을 수 있습니다
• 동질성(Homophily): 서로 유사한 정점끼리 간선으로 연결될 가능성이 높습니다 같은 동네에 사는 같은 나이의 아이들이 친구가 되는 경우가 그 예시입니다
• 전이성(Transitivity): 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줄 수 있습니다 친구를 서로에게 소개해주는 경우가 그 예시입니다
• 반면 랜덤 그래프에서는 지역적 혹은 전역 군집 계수가 높지 않습니다
• 구체적으로 랜덤 그래프 𝐺(𝑛, 𝑝)에서의 군집 계수는 𝑝입니다
• 랜덤 그래프에서의 간선 연결이 독립적인 것을 고려하면 당연한 결과입니다
• 즉 공통 이웃의 존재 여부가 간선 연결 확률에 영향을 미치지 않습니다

6. 실습: 군집 계수 및 지름 분석

6.1 그래프 불러오기

• 이번 실습에서는 다음 세 종류의 그래프의 구조를 분석합니다
  • 균일 그래프(Regular Graph), 작은 세상 그래프(Small-world Graph), 랜덤 그래프(Random Graph)
• 작은 세상 그래프는 균일 그래프의 일부 간선을 임의로 선택한 간선으로 대체한 그래프입니다
• 파일에 저장된 균일 그래프를 읽어옵니다
• 파일에 저장된 작은 세상 그래프와 랜덤 그래프도 읽어서 불러옵니다

6.2 군집 계수 계산

• 주어진 그래프의 전역 군집 계수를 계산하는 함수를 정의합니다

6.3 지름 계산

• 주어진 그래프의 지름을 계산하는 함수를 정의합니다

6.4 비교 분석

• 정의한 함수를 이용하여, 세 가지의 그래프를 비교합니다
  

2강 정리
1. 실제 그래프 vs 랜덤 그래프: 실제 그래프는 복잡계로부터 얻어지는 반면, 랜덤 그래프는 확률적 과정을 통해 생성합니다
2. 작은 세상 효과: 실제 그래프의 정점들은 가깝게 연결되어 있습니다
3. 연결성의 두터운 꼬리 분포: 실제 그래프에는 연결성이 매우 높은 허브 정점이 존재합니다
4. 거대 연결 요소: 실제 그래프에는 대부분의 정점을 포함하는 거대 연결 요소가 존재합니다
5. 군집 구조: 실제 그래프에는 군집이 존재하며, 실제 그래프는 군집 계수가 높습니다
6. (실습) 파이썬을 이용한 지름 및 군집 계수 분석

피어 세션 정리

강의 리뷰 및 Q&A

• [Graph 1강] 그래프란 무엇이고 왜 중요할까?
• [Graph 2강] 실제 그래프는 어떻게 생겼을까?

과제 진행 상황 정리 & 과제 결과물에 대한 정리

[과제 1] 그래프를 컴퓨터 언어로 표현하기 & 페이지랭크 알고리즘 구현하기

class Graph_dict(DiGraph):

• 그래프에 정점(v)를 추가합니다.

• 그래프에서 정점(v)과 그 정점이 속한 간선들을 모두 제거합니다. 만약 그래프에 정점이 존재 하지 않는 경우, 함수를 종료합니다.

• 그래프의 정점(v)의 나가는 이웃(out − neighbors)을 반환합니다.

• 그래프의 정점(v)에서 나가는 간선의 수를 반환합니다.

class Graph_numpy_array(DiGraph):

• 그래프에 간선(v1,v2)이 존재하는 지 검사합니다. 만약 간선이 존재하면 True를 반환하고, 간 선이 존재하지 않으면 False를 반환합니다.

총평

오늘은 그래프 이론의 기초를 배웠습니다.
기초 지식이 없는 분야라서 그런지 조금 어색했지만, 생각보다 재미있었습니다.
특히, 활용도가 높은 분야라고 생각되어 배워두면 제게 도움이 되리라고 생각합니다.
그리고 난이도는 쉬웠지만, 과제다운 과제를 수행할 수 있어서 좋았습니다.

이번 주는 비교적 여유가 있다고 생각합니다.
지난주가 힘들었던 만큼, 이번 주는 되도록 일과 삶의 균형을 맞추면서 공부할 생각입니다.

오늘보다 더 성장한 내일의 저를 기대하며, 내일 뵙도록 하겠습니다.

읽어주셔서 감사합니다!