Day21 학습정리 - 그래프 이론 기초 & 그래프 패턴

강의복습

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

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

• 그래프(Graph): 정점(Vertex) 집합과 간선(Edge) 집합으로 이루어진 수학적 구조
  • 하나의 간선은 두 개의 정점을 연결

• 그래프는 네트워크(Network)로도 불림
  • 정점: Node, 간선: Link

• 복잡계를 표현하고 분석하기 위한 언어

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

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

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

• 방향성이 없는 그래프(Undirected Graph) / 방향성이 있는 그래프(Directed Graph)

• 가중치가 없는 그래프(Unweighted Graph) / 가중치가 있는 그래프(Weighted Graph)

• 동종 그래프(Unpartite Graph) / 이종 그래프(Bipartite Graph - 다른 종류의 정점 사이에만 간선이 연결됨)

• 정점들의 집합: 𝑽, 간선들의 집합: 𝑬, 그래프: 𝑮 = (𝑽,𝑬)
• 정점의 이웃(Neighbor): 그 정점과 연결된 다른 정점
  정점 𝑣의 이웃들의 집합: 보통 𝑵(𝒗) 혹은 𝑵_𝒗로 적음
  
• 나가는 이웃(Out-Neighbor)의 집합: 𝑵_𝒐𝒖𝒕(𝒗)
  들어오는 이웃(In-Neighbor)의 집합: 𝑵_𝒊𝒏(𝒗)

4) 그래프의 표현 및 저장

• 파이썬 라이브러리
  • NetworkX: networkx.org/documentation/stable/index.html
  • Snap.py: snap.stanford.edu/snappy/

• 간선 리스트
  • 방향성 없는 경우: 그래프를 간선들의 리스트로 저장
  • 방향성 있는 경우: (시작점, 출발점) 순서로 저장
• 인접 리스트
  • 방향성 없는 경우: 각 정점의 이웃들을 리스트로 저장
  • 방향성 있는 경우: 각 정점의 나가는 이웃들과 들어오는 이웃들을 각각 리스트로 저장

• 인접 행렬
  • 방향성 없는 경우: 정점 i와 j 사이에 간선이 있으면 i행 j열과 j행 i열 원소 1, 없으면 0
  • 방향성 있는 경우: 정점 i에서 j로의 간선이 있으면 i행 j열 원소 1, 없으면 0

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

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

• 실제 그래프: 복잡계로부터 얻어짐
• 랜덤 그래프: 확률적 과정을 통해 생성
• 에르되스-레니 랜덤 그래프(Erdős-Rényi Random Graph): G(n,p)
  • n개의 정점 가짐
  • 임의의 두 개의 정점 사이에 간선이 존재할 확률: p
  • 정점 간의 연결은 서로 독립적

2) 작은 세상 효과

• 정점 u와 v 사이의 경로(Path): 다음 조건을 만족하는 정점들의 순열(Sequence)
  • u에서 시작해서 v에서 끝나야 함
  • 순열에서 연속된 정점은 간선으로 연결되어 있어야 함
• 정점 u와 v 사이의 거리(Distance): u와 v 사이의 최단 경로의 길이
• 그래프의 지름(Diameter): 정점 간 거리의 최댓값
• 작은 세상 효과(Small-world Effect): 실제 그래프의 정점들은 가깝게 연결되어 있음

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

• 정점의 연결성(Degree): 그 정점과 연결된 간선의 수, 𝒅(𝒗), 𝒅_𝒗 혹은 |𝑵(𝒗)|로 표시
• 나가는 연결성(Out Degree): 그 정점에서 나가는 간선의 수, 𝒅_𝒐𝒖𝒕(𝒗) 혹은 |𝑵_𝒐𝒖𝒕(𝒗)|로 표시
  들어오는 연결성(In Degree): 그 정점으로 들어오는 간선의 수, 𝒅_𝒊𝒏(𝒗) 혹은 |𝑵_𝒊𝒏(𝒗)|로 표시
• 실제 그래프에는 연결성이 매우 높은 허브(Hub) 정점이 존재함 → Heavy Tail

4) 거대 연결 요소

• 연결 요소(Connected Component): 다음 조건들을 만족하는 정점들의 집합
  • 연결 요소에 속하는 정점들은 경로로 연결될 수 있음
  • 첫번째 조건을 만족하면서 정점을 추가할 수 없음
• 실제 그래프에는 대부분의 정점을 포함하는 거대 연결 요소(Giant Connected Component)가 존재함
• 랜덤 그래프에도 높은 확률로 거대 연결 요소가 존재하지만 평균 연결성이 1보다 충분히 커야 함

5) 군집 구조

• 군집(Community): 다음 조건들을 만족하는 정점들의 집합
  
  • 집합에 속하는 정점 사이에는 많은 간선이 존재
  • 집합에 속하는 정점과 그렇지 않은 정점 사이에는 적은 수의 간선이 존재
• 지역적 군집 계수(Local Clustering Coefficient): 한 정점에서 군집의 형성 정도 측정
  (정점 i의 이웃 쌍 중 간선으로 직접 연결된 것의 비율)
  • 𝑪_𝒊 = 𝒏 / (𝒌_𝒊(𝒌_𝒊 - 1) / 2) = 2𝒏 / 𝒌_𝒊(𝒌_𝒊 - 1)
  • 𝑪_𝒊: 정점 𝒗_𝒊의 지역적 군집 계수
    𝒏: 정점 𝒗_𝒊의 이웃 안의 edge 개수
    𝒌_𝒊: 정점 𝒗_𝒊의 degree
  • degree가 2 미만인 정점에 대해 지역적 군집 계수 0으로 정의하는 경우도 있음
• 전역 군집 계수(Global Clustering Coefficient): 전체 그래프에서 군집의 형성 정도 측정
  (각 정점에서의 지역적 군집 계수의 평균)
• 실제 그래프에는 군집이 존재하며, 실제 그래프는 군집 계수가 높음
  • 동질성(Homophily): 서로 유사한 정점끼리 간선으로 연결될 가능성 높음
  • 전이성(Transivity): 공통 이웃이 있는 경우, 공통 이웃이 매개 역할을 해줄 수 있음

𝑪𝒊 

6) 파이썬을 이용한 지름 및 군집 계수 분석 

3. 과제 코드 분석

Metaclass

위키독스

Python의 metaclasses(메타클래스) 이해하기

---

코멘트

이번주에는 그래프에 대해 배운다. 다행히 오늘 강의는 크게 어려운 내용은 없었던 것 같다.