> For the complete documentation index, see [llms.txt](https://tobigs.gitbook.io/tobigs-graph-study/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://tobigs.gitbook.io/tobigs-graph-study/chapter1.-1.md).

# Chapter1. Machine Learning with Graphs

12기 배유나

## Why Networks?

네트워크는 상호작용하는 엔티티의 복잡한 시스템을 설명하기위한 일반적 언어다.

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_3vOj1rC_pbX1XhDa%2Fimage.png?alt=media\&token=c2c1faaa-7973-4c29-ac92-5622b22d2e85)

## Two Types of Networks/Graphs

* Networks(Natural Graphs)  -> interaction?

      사회는 70억 이상의 개개인들의 집합이다.

      전자 장치를 연결하는 통신망

* Information Graphs -> relationship?

     정보, 지식이 구성되고 연결된다 

     유사성 네트워크 : 데이터 수집, 유사 데이터(포인트) 연결

하지만, 둘이 모호할 때가 있다고 합니다. (구분)

## Many Types of Data are Networks

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4ZnDJJb0fHhNa1cxyX%2Fimage.png?alt=media\&token=c55937a5-8213-4a3e-9a8d-909ca9645b4b)

### 이 시스템은 어떻게 구성되는가?

### 이 시스템을 구성하는 요소는 무엇인가?

->  많은 시스템 뒤에는 구성 요소간의 상호 작용을 정의하는 다이어그램, 네트워크가 있다.

->  **네트워크를 이해하지 않으면 이런 시스템을 모델링하고 예측할 수 없다!**

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4ZoCgRFTOlRT8xygQ3%2Fimage.png?alt=media\&token=8402400b-148a-4a8f-b302-86d4e10c874e)

**더 나은 예측을 위해 Relational Structure을 어떻게 이용할까?**

## Graphs : Machine Learning

복잡한 도메인(지식, 텍스트, 이미지 등)은 관계형 그래프로 표현할 수 있는 구조를 가지고 있다.

-> 관계를 **명시적으로 모델링**해 더 나은 성능을 달

## Why should I care about networks ?

* 복잡한 데이터를 설명하기 위한 범용 언어

     과학, 자연, 기술의 네트워크는 생각보다 비슷하다.

* 분야간 단어 공유

     컴퓨터 과학, 사회 과학, 물리학, 경제학, 통계학, 생물학 -> 분야간 공유 가능

* 데이터 가용성, 계산 이슈

     웹/ 모바일, 바이오, 건강, 의료 

* Impact

     소셜 네트워크, 약물 설계, AI 추론 

-> 디지털 회사에 새로운 파장 일으켰다.

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_4GOJwpuPlcOa93Uz%2Fimage.png?alt=media\&token=1b1b9244-08f2-4a73-b73b-c4d7655e831f)

구글 : web이 그래프라고 처음 인지하였다고 함. 그전 web 여러셋의 document로 구성

## Networks and Applications

* Node classification

     주어진 노드의 type, color 예측

* Link classification

     두 노드가 연결되어 있는지 예측

* Community classification

     밀도있게 연결된 노드 클러스터 구분

* Network similarity

     두 노드, 네트워크의 유사도 측정

application 예

### social circle Detection

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4ZssVIq54pjDUmYkf0%2Fimage.png?alt=media\&token=051f0f26-738e-430e-b8c7-4750c0705b2b)

네트워크가 주어졌을때 소셜 서클 발견 가능하다.

## Embedding Nodes

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4ZtiIq3iTY03yXKnC5%2Fimage.png?alt=media\&token=79c23433-e3f5-46cd-bb73-3f0d67addd7b)

노드를 d차원 임베딩에 매핑해서 유사한 네트워크 환경을 가진 노드가 서로 가까이에 되도록 설정

-> 이걸 활용해서 추천이 가능하다.

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_48B0FQFDMQ9s2601%2Fimage.png?alt=media\&token=1e3e8b49-76ea-448a-b3c9-a4ec8005f385)

## Structure of Grphs

### structure of Networks

네트워크는 object 쌍이 링크로 연결된 object 모음

-> 네트워크 구조는 무엇일까?

### Components of a Network

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4Zv2PmeQGyxm2_htia%2Fimage.png?alt=media\&token=2e7b5694-6863-430e-b378-e3bec010f11d)

### Networks or Graphs?

* Network 는 실제 시스템을 의미

web, Social network

(Network, node, link)

* Graph는 network의 수학적 표현

web graph, social graph

(Graph, vertex, edge)

필요할 땐 구별하겠지만, 대부분 두 용어를 번갈아 사용

## Networks : Common Language

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4ZvzIa1tAxP_R6V5UV%2Fimage.png?alt=media\&token=871ae5b4-2029-4a8c-8801-8bc30696b65a)

## Choosing Proper Representations

협력하는 개인을 연결하면 professional network

sexual 관계를 연결하면 sexual network

인용하는 과학 논문을 연결하면 citation network

## How do you define a network

Graph 작성

   노드란? 엣지란?

주어진 도메인, 문제에서 네트워크를 성공적으로 사용하기 위해 적절한 네트워크 representation 선택은 중요한 결정이다.

* 어떤 경우에 독특하고 명확한 표현이 있다.
* 다른 경우에 표현이 unique하지 않음
* 링크를 할당하는 방법에 따라 공부할 내용이 다양

## Choice of Network Representation

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4ZyAbyfx5o1rA3SHbQ%2Fimage.png?alt=media\&token=ba7e1533-3c28-46e1-82ed-7964bea67b60)

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4Zye2j-RZeV0qaZz-B%2Fimage.png?alt=media\&token=3733c631-6fe0-40ca-94b0-03e0cd2098ac)

Node degree K\_i : 노드 i에 인접한 edge 수

undirected Avg.degree는 노드수가 양방이다 보니 2배 -> 2E/N

in-degree : 해당 노드로 향하는

out-degree : 해당 노드가 향하는

### Complete Graph

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4ZzIgtf9kJvNtY0kXb%2Fimage.png?alt=media\&token=ae3e9526-2c62-462e-9d77-8f58ee24f663)

서로 다른 두 개의 꼭짓점이 반드시 하나의 변으로 연결된 그래프

### Bipartite Graph

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4ZzvrpGfYNfs195LK-%2Fimage.png?alt=media\&token=2c765c92-d723-4e9f-a968-369366460fdf)

모든 링크가 U의 노드를 V의 노드에 연결하도록 노드를 U,V로 나눌 수 있는 그래프

U와 V는 독립

**Folded Networks -> 다 : 1**

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_-O7Obch5-DI28gi0%2Fimage.png?alt=media\&token=349090cf-02c3-4a48-81aa-34479cfd5dfa)

### Representing Graphs : 인접행렬 

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_-UpWmO_Vw0GDXdan%2Fimage.png?alt=media\&token=046c97cf-b0c6-4008-ab66-7b18ddda9fd4)

node i와 j로 가는 링크가 있다면 1, 아니면 0

인접행렬 : 그래프에서 어느 꼭짓점들이 변으로 연결되었는지 나타내는 행렬

undirected graph는 대칭행렬이지만, directed graph은 대칭행렬이 아님

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_0EFB1UGl5VNCjAFM%2Fimage.png?alt=media\&token=fb52dc68-0847-406a-b4bc-b221931cb159)

### Representing Graphs : Edge List

엣지 리스트 : 연결된 엣지들의 집합

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_0Vfryj2tOw1mDHq7%2Fimage.png?alt=media\&token=16a83ca8-4eab-4c26-b440-5448489d4ef2)

### Representing Graphs : Adjacency list 인접리스트

그래프의 한 꼭짓점에서 연결되어 있는 꼭짓점들을 하나의 연결 리스트로 표현

인접 행렬에 비해 edge가 희소한 그래프에서 효과적

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_0ye2Fp6keD1eoo7y%2Fimage.png?alt=media\&token=b435a311-c116-42b4-942b-cb59109d9ff4)

### Networks are Sparse Graphs

현실 네트워크는 sparse -> 인접행렬은 0으로 채워짐

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_1C41qHYYLOANKzU4%2Fimage.png?alt=media\&token=e296a9c4-698d-49fd-b727-f63f9004b85b)

### Edge Attributes

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_1M_aLYUnxEJKb--t%2Fimage.png?alt=media\&token=f8ae541b-8ce8-45fa-bfeb-e3f583858e46)

### More Types of Graphs

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_1ZeAgdUCqSCDpdgD%2Fimage.png?alt=media\&token=4acf3f74-4ca5-44ea-82eb-6a1c78751bbe)

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_1dFn2kF9QKuNZEFE%2Fimage.png?alt=media\&token=c759e6e4-cb29-4eca-9778-eb92510d0edf)

### Connectivity of Undirected Graphs

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_2CrOPJyVFYEF8wwh%2Fimage.png?alt=media\&token=44d62442-c0da-499b-8ee3-0def0746ad5a)

두 정점은 경로로 연결 가능

연결이 끊어진 그래프는 둘 이상의 연결된 구성 요소로 구성됨

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_2ILAzycC6BGQpztL%2Fimage.png?alt=media\&token=ba084fba-28a8-463d-88c2-e3ec47ae987f)

여러 components로 된 네트워크 인접행렬은 block-diagonal형태로 작성할 수 있어서 0이 아닌 요소는 사각형으로 제한되고 아니면 모두 0이다.

### Connectivity of Directed Graphs

* strongly connected directed graph

     각 노드에서 다른 모든 노드로 경로가 있고, 반대로도 모든 노드로 경로가 있다.

* weakly connected directed graph

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_37rmuV_32XBzk4e_%2Fimage.png?alt=media\&token=bd159a1f-b99f-41bf-afe9-101ac01b2eec)

### Strongly connected components (SCCs)

![](https://3892657537-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M2xLeAqFxBlU6u7AkUh%2F-M4ZkWMMTIfuYaEtQgsF%2F-M4_3Mjjr8rkkKWBfyZC%2Fimage.png?alt=media\&token=0fb284af-d727-4ff3-82d3-9999f9969e49)

SCC를 식별할 수 있지만 모든 노드가 SCC는 아니다.