# Chapter1. Machine Learning with Graphs

## 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는 아니다.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://tobigs.gitbook.io/tobigs-graph-study/chapter1.-1.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.