Graph algorithms

The traversal technique guarantees that

1. All users are visited; and

2. No user is visited more than once.

 

 

 

graph algorithms의 2가지 main techniques

1. Depth-First Search (stack 기법을 사용함 - FILO)

2. Breadth-First Search (BFS) (queue를 사용함 -FIFO)

 

DFS의 코드 간략화(push)

dmml.asu.edu/smm

단, 밑줄 친 빨간 부분은 

if node에 방문마크가 안되어있는 것만 push해서 S 스택에 넣으라는 

명령어로 바꿔주어야지 속도가 빨라짐

 

BFS와 DFS의 차이점은

BFS는 neighborhood의 노드를 먼저 방문한 다음에,

그 다음에 다른 노드로 옮겨감

 

BFS 이미지(Enqueue) - local탐색

v1-v2-v3-v4-v5-v6-v7

 

DFS 이미지(global 탐색)

v1-v2-v4-v5-v3-v6-v7

 

 

 

 

최단 경로 찾는 알고리즘

Dijkstra's Algorithm: Edge의 weight가 최소가 되는 경우의 path를 찾는 것

Dijkstra알고리즘보다  Floyd-Warshall 알고리즘이 더 효율적임

 

 

Minimum spanning tree:

아래 그림에서 회색의 영역과 흰색의 영역을 연결할 수 있는

최소 비용의 다리를 선택해서 모든 노드를 방문하는 것

한개의 트리에서는 여러개의 minimum spanning tree가 나올 수 있다.

예를 들어, 위에서 1번과 2번으로 표시된 것 중에서도 어떤 edge를 선택하냐에 다른

minimum spanning tree가 생성 된다.

 

 

Network Flow

방향성이 있는 그래프로서 Edge의 값은 network의 용량(capacity)을 의미한다.

source node: 시작점

sink node: 종료 point

특정 노드로 들어온 정보의 양과 나간 정보의 양은 같아야 함. (=flow conservation constraint)

flow value: 시작점에서의 나간 양 또는 종착점에서 들어온 양으로 표현됨.

Network flow의 2가지 constraint: capacity constraint & flow conserviation constraint

 

 

Ford-Fulkerson Algorithm

:Network Flow에서 maximum flow를 구하기위해 사용하는 알고리즘

Augmenting path란?

Any simple path from "s" to "t" in the residual graph is an augmenting path.

아래 그림에서 아무 simple path from "s" to "to"를 augmenting path라고 함

 

MaxFlow Example (중요) - max flow 값 구하기

여러가지 path중 S-A-C-D-T로 이동할 때

가능한 이동량은 가장 최소의 capacity와 같음 그러므로 2임

 

(아래그림) 이렇게 여러번 했을 때, S에서 나간 양 10+9와 T로 들어온 양 10+9

즉, 19가 max flow임

어떤 방법을 해도 max flow는 19의 값으로 나옴

(Ford-Fulkerson Algorithm 생략하심)

 

 

 

Maximum Bipartite Matching

VL은 고객, VR은 상품이라고 가정

한명의 고객은 한개의 상품만 살 수 있음

한개의 상품은 한명의 고객에게만 팔 수 있음

마케팅입장에서는 어떻게 선택하는것이 best옵션일까?

그것을 구하는 것이 maximum matching 문제를 푸는 것임

--> maximum flow로 변형시켜서 문제를 풀수 있음

끝에 S와 T노드를 붙여서 만들 수 있음

모든 edge의 값은 1임

 

 

Bridge and Local Bridge

Local Bridge 정의

When the endpoints have no friend in common

즉, A와 B를 제외하면 왼쪽그룹에서 오른쪽 그룹으로 갈때

최단패스의 길이가 2이상 증가하게 만드는 bridge를 local bridge라 한다.

 

Bridge 정의

아래와 같이 두 그룹을 연결하고 있는 단 하나의 연결선

현실에서는 Bridge를 찾기가 힘들기 때문에

local bridge를 찾는것을 중요하게 생각하면 됨

 

 

Bridge Detection알고리즘

3열 모든 edge에 대해서 "do"이하의 문장을 실행하라

4열 특정 edge를 모든 edge group G에서 제거한 group을 G'이라고하자

라는 뜻임

 

 

 

 

 

 

 

본 내용은 서강대학교 소셜미디어데이터 분석 강의 내용을 정리한 것입니다.