[SOCIAL MEDIA MINING3] - Graph/NetworkTraversal Algorithms

Graph/Tree Traversal

• There are two main techniques:

– Depth-First Search (DFS)

– Breadth-First Search (BFS)

 

Depth-First Search (DFS)

Breadth-First Search (BFS)

너비 우선 탐색(BFS)은 노드에서 시작하여, 먼저 해당 노드의 모든 직접 이웃 노드들을 방문하고, 그 다음 레벨로 넘어가기 위해 이웃 노드들의 이웃을 탐색

 

Finding Shortest Paths

Dijkstra’s Algorithm

1. 초기화:출발 노드에는 0을 할당하고, 다른 모든 노드에는 무한대를 할당합니다.

• 모든 노드를 미방문 상태로 표시합니다.
• 출발 노드를 현재 노드로 설정합니다.

2. 현재 노드를 기준으로 미방문 이웃 노드들을 고려하고, 그들의 잠정적인 거리를 계산합니다.

만약 잠정적인 거리가 이웃 노드의 거리보다 작다면, 이웃 노드의 거리를 잠정적인 거리로 갱신합니다.

 

3. 현재 노드의 모든 이웃들을 고려한 후, 현재 노드를 방문한 상태로 표시하고 미방문 노드 집합에서 제거합니다.

4. 목적지 노드가 방문한 상태로 표시되었거나, 미방문 노드들 중 가장 작은 잠정적인 거리가 무한대인 경우에는 알고리즘을 종료합니다.

5. 미방문 노드 중 잠정적인 거리가 가장 작은 노드를 다음 "현재 노드"로 설정하고, 단계 2로 돌아갑니다.

 

Finding Minimum Spanning Tree

회색 시작점에서 edge 중 최소 weight를 갖는 값을 선택

 

Network Flow

각 파이프는 에지(edge)로 표현되며, 에지에는 용량(capacity)이 할당됩니다. 무한한 공급원은 그래프의 출발점(source)에 해당하고, 무한한 흡수원은 그래프의 도착점(sink)에 해당합니다. 네트워크에서는 역방향의 유량이 불가능하므로, 에지는 한쪽 방향으로만 흐를 수 있습니다. 네트워크 플로우 문제에서는 출발점에서 도착점으로 최대한 많은 유량을 흘려보내는 최적의 플로우를 찾는 것이 목표

들어온 정보량 = 나간 정보량

 

 

Ford-Fulkerson Algorithm(최대유량)

(2번 슬라이드 이후내용 정리 필요)

 

Maximum Bipartite Matching

주어진 문제는 사용자들이 특정 제품에만 관심을 가지는 경우가 있고, 각 제품은 하나의 사본만 가지고 있다는 조건이 있는데, 이를 이분 그래프로 표현할 수 있다고 합니다.

사용자와 제품을 노드로 나타낸 이분 그래프에서, 사용자와 그들이 관심을 가진 제품들을 연결하는 엣지(간선)가 있다고 가정합니다.

사용자들이 최대한 많은 수의 제품을 구매하려면, 사용자와 제품 간의 연결을 최대한 많이 형성해야 합니다. 단, 같은 노드(사용자)를 공유하는 두 개의 엣지(사용자가 같은 제품에 관심을 가진 경우)가 없도록 해야 합니다.

이 문제는 그래프 이론에서 최대 이분 매칭(maximum bipartite matching) 개념을 활용하여 해결할 수 있습니다.

구인 구직 예시 굳

https://dhpark1212.tistory.com/entry/%EC%9D%B4%EB%B6%84-%EA%B7%B8%EB%9E%98%ED%94%84-vs-%EC%9D%B4%EB%B6%84-%EB%A7%A4%EC%B9%AD

 

이분 그래프 & 최대 이분 매칭 (Bipartite Graph & Maximum Bipartite Matching)

 

Bridge and a Local Bridge

Bridge: Bridges are edges whose removal will increase the number of connected components

두 그룹을 연결하고 있는 연결선