Networks
Network: graph representation with data
- 네트워크는 서로 상호작용하는 entity 간 복잡한 시스템을 설명할 수 있는 범용 언어임
- 표현하고자 하는 object를 선으로 연결함으로써 network를 만듦
- 데이터 가용성을 고려하였을 때 다양한 도메인에서 사용될 수 있음
- web/mobile, bio, health, medical, etc.
- Impact!
- social network, drug design, AI reasoning
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F1bea6b0b-8783-42bb-9568-7c51aac04bbe%2Fimage.png)
Many types of networks
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F2c726a7a-a535-48b2-b22c-d0eaa8b57144%2Fimage.png)
- 모든 network는 저마다 object가 의미하는 바가 다르며, 그들간의 관계 또한 다름
- 주어진 network를 이해하지 못하면 모델링을 할 수 없음! (투빅스1강이 EDA인 이유)
Ways to Analyze Networks
- Node classification
- Link prediction
- Community detection
- Netwrok similarity
Structure of Graphs
Components of a Network
- Objects N: nodes, vertices
- Interactiosn E: links, edges
- System G(N, E): network, graph
Networks or Graphs?
- Network: real system
- web, social network
- Language: network, node, drug network
- Graph: netwowrk의 수학적 표현
- web graph, social graph
- Language: graph, vertex, edge
- 서로 경계가 모호하기때문에 일반적으로 혼용하는 편!
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F215a4901-aff4-4af2-a2d7-46628f4f21a5%2Fimage.png)
Choice of Network Representation
Direction of edges
- Undiredcted graph: 링크가 양방향인 그래프
- EX) collaborations, friendship
- Directed graph: 링크에 특정 방향이 주어지는 그래프
- citation/quotation, 인스타 DM, 팔로잉, 좋아요
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F59997f1a-ac4a-466f-a004-1be2172d3d83%2Fimage.png)
Node Degrees
- Degree(차수): 노드에 부속되어 있는 link의 수
- Undirected graoph의 평균 차수
k=N1i=1∑Nki=N2E (E=edge 개수, N=node 개수, ki=i째 node의 차수)
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F28b39857-8fe6-4f2b-9622-0a726220bd11%2Fimage.png)
- 위의 예시에서는 kA=4
- Directed의 경우는 in-degree와 out-degree가 구분됨
- 전체 차수는 두 가지 degree 총합임
k=N2E
Complete Graph
- undirected graph의 최대 edge 개수 Emax=2N(N−1)
- Complete graph: 최대 edge개수를 가진 undirected grpah
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F50b4d287-d43b-4403-a32d-62e51ab0ae09%2Fimage.png)
Bipartite Graph
- Bipartite graph: 서로 다른 종류의 독립된 노드들로 구성된 그래프
- 두 가지 노드 타입 U, V로 나눌 수 있음
- U에 속하는 노드는 V에 속한 노드에게만 연결되고 U끼리는 독립임
- V에 속하는 노드는 U에 속한 노드에게만 연결되고 V끼리는 독립임
- Bipartite graph는 실제 도메인에서 많이 나타나는 구조이며, 특히 추천시스템에서 많이 사용되는 개념임
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F66e08d82-3992-4adf-8a6e-dfdc13565807%2Fimage.png)
Representing Graphs
Adjacency Matrix
- Adjacency Matrix(인접행렬): 그래프를 연결 유무를 1과 0으로 나눠 행렬로 표현한 것
- Undirected의 경우 대칭으로 나타나며 Undirected는 단방향일 수 있기 때문에 대칭이 아닐 수도 있음
- 노드가 많아질 수록 즉, 행렬의 차원이 커질 수록 Sparse해진다는 단점이 있음
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Ff42a61b8-b6f4-474e-82a7-3a3b168af13b%2Fimage.png)
Edge list
- Edge를 연결된 노드 쌍으로 표현한 것
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fc100132b-f51e-4f97-977b-a59de4265809%2Fimage.png)
Adjacency list
- 출발방향의 노드를 Key값으로, 도착 노드를 Value값으로 가지는 Dictioanry형태
- 단방향이거나 거대한 그래프에서 효율이 좋음
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Febe1e324-9b57-41c1-bbbd-8ef0e9f32605%2Fimage.png)
Edge Attrbutes
- Weight: edge에 weight를 줄 수 있음 (와인 추천 시 와인에 대한 평점을 edge에 weight 주기)
- Ranking: 짱절친, 절친, 아는 사이
- Type: 친구, 친척, 직장동료
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fd6347382-39f8-4340-a608-465f8cefbde3%2Fimage.png)
More types of Graph
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Ff5865a00-418f-49c1-8f1a-32ef5d235942%2Fimage.png)
Connectivity of Undirected Graphs
- Connected graph(undirected): 어떤 노드에서 출발하든지 다른 모든 노드로 도착할 수 있음
- Disconnected graph: 최소 2개 이상의 connected graph로 구성됨
- Bridge edge: 삭제되면 connected에서 disconnected로 바꿀 수 있는 edge
- Articulation node: 삭제되면 connected에서 disconnected로 바꿀 수 있는 node
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Ffc8a202c-cfa1-4ba7-9c6f-1213bcf71d8d%2Fimage.png)
- Disconnected의 경우 인접행렬은 block-diagonal 형태가 된다
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F89c7601e-4ed7-4300-9e4f-50fad9449723%2Fimage.png)
Connectivity of Directed Graphs
-
Strongly connected directed graph: 어떤 노드에서 출발하든지 edge방향을 지키면서 다른 모든 노드로 도착할 수 있음
-
Wealky connected directed graph: 어떤 노드에서 출발하든지 edge방향을 무시한다면 다른 모든 노드로 도착할 수 있음
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2Fa3a4715a-866d-42bd-a4d4-46e23d051f35%2Fimage.png)
-
Strongly connected components(SCCs): 그래프에서 부분적으로 나타나는 connected subgraph
- SCCs 포함유무에 따라 In-component, Out-component로 분류
![](https://velog.velcdn.com/images%2Ftobigs-gnn1213%2Fpost%2F899a9d9f-f73e-4e7b-95d2-e3026669d0a9%2Fimage.png)
투빅스 13기 정민준
그래프의 구조와 속성에 대해 전반적으로 알 수 있었습니다.
좋은강의 감사합니다 :)