프로그래머가 알아야 할 알고리즘 40 Chapter 5 그래프 알고리즘

5장. 그래프 알고리즘

 

요약

그래프의 종류들과 그래프를 사용한 알고리즘 방법론들을 알 수 있었다.

 

 

 

내용 정리

 

그래프 알고리즘(graph algorithm)

• 복잡하고 상호연결성이 높은 자료 구조에서 원하는 정보를 가장 빠르게 찾을 수 있는 방법
• 전통적으로 검색 분야에서 크게 쓰이고 있음
• 최근 빅데이터, 소셜미디어, 분산형 데이터 분석에도 사용되고 있음

 

 

 

5.1 그래프 표현 이해하기

 

그래프(Graph)

• 버텍스(vertex)와 엣지(edge)로 구성된 자료 구조
• 버텍스(vertex): 네트워크를 구성하는 개체로 하나의 노드로 볼 수 있다.
  • 모든 버텍스는 버텍스 집합에 속한다 (v ∈ V).
• 엣지(edge): 두 버텍스가 관계가 있을 때, 이를 이어서 엣지로 표현함
  • 모든 엣지는 엣지 집합에 속한다 (e ∈ E).
• 네트워크의 개수는 |V|, 엣지 개수는 |E|로 표현한다.

 

 

 

파이썬에서 코드 구현

파이썬에서는 netwrokx 라이브러리를 이용해 네트워크를 생성 및 분석할 수 있다.

 

import networkx as nx

G = nx.Graph() # 빈 그래프 생성

G.add_node("Mike") # 버텍스 하나 추가
G.add_nodes_from(["Amine", "Wasim", "Nick"]) # 버텍스 여러 개 추가

G.add_edge("Mike", "Amine") # 엣지 한 개 추가

G.add_edge("Amine", "Imran") # 네트워크 내에 아직 존재하지 않는 버텍스도 엣지에 미리 포함될 수 있다.

list(G.nodes) # 생성한 버텍스 출력
>> ["Mike", "Amine", "Wasim", "Nick"]

list(G.edges) # 생성한 엣지 출력
>> [("Mike", "Amine"), ("Amine", "Imran")]

 

 

그래프 유형

1. 무방향 그래프
2. 방향 그래프
3. 무방향 멀티 그래프
4. 방향 멀티 그래프

 

 

 

1. 무방향 그래프(undirected graph)

 

무방향 그래프

 

• 서로 연결된 노드 사이에는 어떤 상하 관계나 순서가 존재하지 않는다.
• 무방향 엣지(undirected edge): 방향이 존재하지 않는 엣지로 무방향 그래프를 나타낸다.

 

 

 

2. 방향 그래프(directed graph)

 

방향 그래프

 

• 노드 사이 관계에서 방향성이 존재하는 경우

 

 

 

3. 무방향 멀티 그래프(undirected multigraph)

 

무방향 멀티 그래프

 

• 두 노드를 사이에 여러 관계가 존재할 때를 표현할 수 있는 그래프
• 서로 다른 유형의 관계를 표현할 수 있다.
• 멀티 그래프(multigraph): 두 노드 사이의 엣지가 2개 이상으로 표현될 수 있는 그래프.

 

 

 

4. 방향 멀티 그래프 (directed multigraph)

 

방향 멀티 그래프

 

• 멀티그래프에 있는 노드 사이에 방향 관계가 존재할 때

 

 

 

특수한 유형의 엣지

엣지는 그래프에 있는 여러 버텍스간의 관계를 표현한다. 여기서 특수한 유형의 엣지들이 존재한다.

• 셀프 엣지(self-edge): 버텍스가 자기 자신과의 관계가 있을 때 표현하는 엣지

 

• 하이퍼 엣지(hyperedge): 엣지 하나가 셋 이상의 버텍스에 연결된 형태
  • 하이퍼 그래프(hypergraph): 하나 이상의 하이퍼 엣지가 있는 그래프를 지칭

 

 

 

에고 중심 네트워크

버텍스 m이 존재할 때, 해당 버텍스의 정보는 연결된 이웃들을 통해 간접적으로 추정할 수 있다.

• 에고(ego): 관심있는 버텍스를 지칭 (위에서는 버텍스 m)
• 에고 중심 네트워크: 에고 (버텍스 m)와 에고에 직접적으로 연결된 이웃들로 구성된 네트워크
  • 알터(alter): 버텍스 m과 직접적으로 연결된 버텍스들
  • 알터만을 이웃으로 지칭할 시, 버텍스 m의 이웃 도수(degree)는 1이다.
  • 에고 중심 네트워크는 도수가 n인 이웃으로 확장도 가능하다.

 

소셜 네트워크 분석

소셜 네트워크 분석(Social Network Analysis, SNA)은 그래프 이론의 주요 활용 분야로 다음 조건을 만족한다.

• 그래프 속 버텍스는 사람을 의미한다.
• 그래프 속 엣지는 사회적 관계 (친구, 친족, 연인 등)를 표현한다.
• 그래프 분석을 통해 사회적 관계, 의미, 효과 등 결과를 도출한다.

 

즉, SNA는 사람들간 형성하는 다양한 관계를 그래프로 표현해 인간관계와 상호작용에 대한 통찰을 분석한다.

 

 

 

 

5.2 네트워크 분석 이론 살펴보기

 

네트워크 분석 이론(network analysis theory)

• 그래프를 추상화하는 방법으로 네트워크를 설정하고, 네트워크 분석을 위해 고안된 알고리즘을 적용하는 방법론

 

최단 경로

경로(path)

• 시작 버텍스와 끝 버텍스 사이에 있는 일련의 연속적인 버텍스들을 의미
• 경로 상 버텍스 집합을 p라고 할 때 아래 조건을 만족해야 한다.
  • 경로 내에 특정 버텍스는 단 한번만 등장해야 한다.
  • 즉, p는 중복된 버텍스를 허용하지 않는다.

• 경로의 길이: 경로를 구성하는 엣지의 개수
• 최단 경로(shortest path): 방문해야 하는 버텍스들을 포함하는 모든 가능한 경로 중에서 가장 거리가 짧은 경로

 

다익스트라 알고리즘(Dijikstra's algorithm)

• 최단 경로 탐색 알고리즘으로 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘에서 변형된 버전이다.
• BFS와 달리 엣지간 이동 비용이 다를 때 사용되며, 이동 비용은 1 이상이다.
• 단일 출발지(single source)로 부터 최단 경로를 계산하는 알고리즘이다.
• GPS(Global Positioning System, 범지구위치결정시스템)이나 네트워크 라우팅 알고리즘 등 다양한 분야에서 사용되는 알고리즘

 

플로이드-워셜 알고리즘(Floyd-Warshall algorithm)

• 모든 출발지-도착지 쌍의 최단 경로를 구할 때 사용하는 알고리즘

 

 

삼각형

삼각형 그래프(triangle graph)

• 세 개의 버텍스가 세 개의 엣지로 연결된 형태
• 모든 버텍스들의 쌍이 서로 관계가 존재한다.
• 소셜 네트워크 분석에서 버텍스의 성향을 파악하는데 자주 활용된다.

 

 

밀도

밀도(density)

• 그래프에서 최대로 허용 가능한 엣지 개수와 관측된 엣지 개수의 비율을 나타낸다.
• 밀도는 0에서 1사이의 값을 가진다.
  • 0은 모든 버텍스간 서로 관계가 없을 때이다.
  • 1은 모든 버텍스의 쌍이 서로 관계를 가질 때이다.

 

• 삼각형 네트워크는 모든 버텍스 간 사옿 연결돼 있으므로 밀도가 1이다.
• 밀도는 다음과 같이 표현된다.

네트워크의 밀도

 

 

완전 연결 네트워크(fully connected network)

• 모든 버텍스의 쌍들이 서로 관계가 있는 네트워크
• 즉, 모든 버텍스들이 서로 연결된 네트워크다.
• 버텍스 개수가 N인 완전 연결 네트워크의 엣지 수는 다음과 같다.

완전 연결 네트워크의 엣지 수

 

 

중심성 지표 이해하기

 

중심성 지표는 네가지가 존재한다.

1. 도수
2. 매개
3. 근접
4. 고유벡터

 

 

1. 도수 중심성

도수 중심성(degree centrality)

• 도수(degree): 특정 버텍스에 연결된 엣지 수
  • 도수가 높을수록 해당 버텍스가 다른 버텍스와 잘 연결돼 네트워크 내에서 메시지를 빠르게 전파할 수 있다.
  • 도수가 높을수록 네트워크 내에서 해당 버텍스의 영향도가 커지며, 도수 중심성이 높아진다고 표현한다.
• 도수 중심성은 버텍스의 도수를 (|V| - 1)로 나눈 값이다.

버텍스 a의 도수 중심성

 

도수 중심성 예시

도수 중심성 예시

 

위 그림에서 버텍스 C의 도수 중심성은 다음과 같다.

버텍스 C의 도수 중심성

 

 

2. 매개 중심성

매개 중심성(betweenness centrality)

• 그래프 내에서 버텍스가 다른 버텍스들 사이에서 위치하는 정도를 나타냄
• 컴퓨터 네트워크 분야에서 통신 장애 등 부정적 효과를 나타내는데 주로 매개 중심성을 이용함

 

 

매개 중심성 계산 방법

 

그래프 aGraph에 속한 버텍스 a의 매개 중심성을 계산한다고 하자.

1) aGraph에 있는 버텍스들로 페어를 구성하고 페어 간 최단 경로를 계산한다. 페어 간 최단경로를 아래와 같이 표기한다.

페어 간      최단경로

 

2) 페어간 최단 경로를 이용해 버텍스 a를 지나는 최단 경로 개수를 구한다. 버텍스 a를 지나는 최단 경로 개수는 아래와 같이 표기한다.

a를 지나는      최단 경로 개수

 

3) 매개 중심성 계산 공식은 아래와 같다.

버텍스 a의 매개 중심성

 

 

3. 공정성과 근접 중심성

공정성(fairness)

• 버텍스 a의 공정성은 자기 자신과 그래프 내 다른 버텍스와의 거리를 모두 더한 것
• 공정성은 대상 버텍스에 직접 연결되지 않은 버텍스와의 거리도 모두 반영한다.

 

근접 중심성(closeness centrality)

• 공정성에 역수를 취한 것

 

근접 중심성 계산 과정

1) 버텍스 a와 다른 버텍스들 간 최단 경로를 구한다.

2) 최단 경로의 거리를 모두 더한다.

3) 그 값의 역수를 취한다.

버텍스 a의 근접 중심성

 

 

4. 고유벡터 중심성

고유벡터 중심성(eigenvector centrality)

• 다른 버텍스의 중심성을 가중치로 반영함
• 다른 버텍스에 영향을 많이 끼치는 a 버텍스와 연결된 b 버텍스는 고유벡터 중심성이 높다.
• 페이지랭크 알고리즘이 고유벡터 중심성 지표에서 파생된 방법론이다.

 

 

5. 파이썬으로 각 중심성 지표 계산하기

 

간단한 네트워크 생성하기

import networkx as nx
import matplotlib.pyplot as plt

vertices = range(1, 10)
edges = [(7, 2), (2, 3), (7, 4), (4, 5), (7, 3), (7, 5), (1, 6), (1, 7), (2, 8), (2, 9)]

G = nx.Graph()
G.add_nodes_from(vertices)
G.add_edges_from(edges)

nx.draw(G,with_labels = True, node_color = 'y', node_size = 800)

 

생성된 네트워크

 

 

각 버텍스의 중심성 지표 계산하기

# 도수 중심성
nx.degree_centrality(G)
>> {1: 0.25,
 2: 0.5,
 3: 0.25,
 4: 0.25,
 5: 0.25,
 6: 0.125,
 7: 0.625,
 8: 0.125,
 9: 0.125}

# 매개 중심성
nx.betweenness_centrality(G)
>> {1: 0.25,
 2: 0.46428571428571425,
 3: 0.0,
 4: 0.0,
 5: 0.0,
 6: 0.0,
 7: 0.7142857142857142,
 8: 0.0,
 9: 0.0}

# 근접 중심성
nx.closeness_centrality(G)
>> {1: 0.5,
 2: 0.6153846153846154,
 3: 0.5333333333333333,
 4: 0.47058823529411764,
 5: 0.47058823529411764,
 6: 0.34782608695652173,
 7: 0.7272727272727273,
 8: 0.4,
 9: 0.4}

# 고유벡터 중심성
centrality = nx.eigenvector_centrality(G)
sorted((v, '{:0.2f}'.format(c)) for v, c in centrality.items())
>> [(1, '0.24'),
 (2, '0.45'),
 (3, '0.36'),
 (4, '0.32'),
 (5, '0.32'),
 (6, '0.08'),
 (7, '0.59'),
 (8, '0.16'),
 (9, '0.16')]

• 버텍스 7이 모든 중심성 지표에서 높은 값을 가진다.
  • 그림 상에서도 버텍스 7이 그래프 중심에 있다고 볼 수 있다.
  • 버텍스 7이 그래프 내에서 가장 중요하다고 할 수 있다.

 

 

 

 

5.3 그래프 순회 이해하기

 

0. 그래프 순회

그래프 순회(graph traversal)

• 특정 방식에 따라 그래프에 있는 모든 버텍스와 엣지를 확인하는 과정
• 그래프 순회는 모든 버텍스와 엣지를 단 한번만 방문한다.
• 순회 방식에 따라 너비 우선 검색(BFS)와 깊이 우선 검색(DFS)로 나뉜다.

 

 

1. 너비 우선 탐색

너비 우선 탐색(BFS, Breadth-First Search)

• 폭을 넓게 탐색하는 방식
• 그래프 내에 레이어 또는 레벨로 구성된 이웃 그룹들을 단계별로 탐색할 때 적용할 수 있는 알고리즘

 

너비 우선 탐색 방법

 

1) 루트 버텍스(특정 버텍스)에서 부터 알고리즘을 시작한다.

2) 버텍스의 이웃 버텍스들을 탐색한다.

3) 이웃의 확인이 끝나면 다음 레이어로 이동해 검색을 반복한다.

 

 

 

파이썬 코드 구현

 

인접 리스트로 버텍스간 관계 설정하기

인접 리스트(adjacency list): 버텍스별 최근접 이웃들(버텍스간 엣지 연결)의 정보를 가지고 있는 리스트

 

graph = {
    'Amin' : {'Wasim', 'Nick', "Mike"},
    'Wasim' : {'Imran', 'Amin'},
    'Imran' : {'Wasim', 'Faras'},
    'Faras' : {'Imran'},
    'Mike' : {'Amin'},
    'Nick': {'Amin'}
}

 

BFS 구현하기

 

초기 설정

 

그래프 순회는 버텍스들을 한번만 방문해야 하기 때문에 방문 기록을 관리하면서 앞으로 어떤 버텍스를 방문해야 하는지 체크한다.

• visited: 방문한 버텍스를 저장한다. 초기에는 비어있다.
• queue: 다음 번 검색에서 방문할 버텍스를 저장한다. 리스트나 큐를 사용한다.

 

메인 루프

• 큐에 있는 버텍스를 하나씩 꺼내어 기록을 확인한다.
  • 방문 기록이 없으면 해당 버텍스에 연결된 이웃 버텍스를 큐에 추가한다.
  • 방문 기록이 있으면 큐에 있는 다음 버텍스로 이동한다.

 

파이썬 구현

def bfs(graph, start):
    visited = []
    queue = [start]
    
    while queue:
        node = queue.pop(0)
        
        if node not in visited:
            visited.append(node)
            neighbors = graph[node]
            
            for neighbor in neighbors:
                queue.append(neighbor)
                
    return visited
    
bfs(graph, 'Amin')
>> ['Amin', 'Wasim', 'Nick', 'Mike', 'Imran', 'Faras']

 

 

2. 깊이 우선 탐색

깊이 우선 탐색(DFS, Depth-First Search)

• 개별 경로를 하나씩 끝까지 탐색하는 방법
• 선택한 경로의 끝에 도달하면 DFS는 경로에서 방문한 모든 버텍스들을 방문처리한다.
• 그리고 경로를 시작한 가장 앞단의 버텍스로 이동해, 해당 버텍스에서 방문하지 않은 또다른 경로가 있다면 다시 탐색을 시작한다.
• 새로운 경로가 더이상 존재하지 않으면 알고리즘을 종료한다.

 

불(bool) 플래그

• 불 플래그를 이용해 버텍스 방문기록을 관리하면 순환 경로에 빠지는 것을 방지할 수 있다.

 

DFS 파이썬 구현

• DFS는 스택을 이용해서 구현한다.

def dfs(graph, start, visited = None):
    
    if visited is None:
        visited = set()
    
    visited.add(start)
    print(start)
    
    for next in graph[start] - visited:
        dfs(graph, next, visited)
    
    return visited


dfs(graph, "Amin")
>> Amin
Wasim
Imran
Faras
Nick
Mike
{'Amin', 'Faras', 'Imran', 'Mike', 'Nick', 'Wasim'}

 

 

 

5.4 활용 사례 - 사기 범죄 분석하기

 

호모필릭 네트워크

호모필리(homophily)

• 인간은 보통 자신과 비슷한 사람들과 어울리는데, 이런 인간의 사회적 경향성을 뜻함

 

호모필릭 네트워크(homophilic network)

• 어떤 공통적 특징을 바탕으로 연결된 집단을 의미함
• 사기 범죄자 수사에서도 호모필릭 네트워크를 활용할 수 있다.
  • 장점: 범죄자로 확인된 많은 사람들과 관계를 맺고 있는 사람은 범죄를 저지를 가능성이 있다고 추정할 수 있다.
  • 단점: 연좌죄(guily by association) 논란이 생길 수 있다.

 

 

간단한 네트워크 및 범죄자(F)와 비범죄자(NF) 생성 코드

import networkx as nx
import matplotlib.pyplot as plt

vertices = range(1, 10)
edges = [(7, 2), (2, 3), (7, 4), (4, 5), (7, 3), (7, 5), (1, 6), (1, 7), (2, 8), (2, 9)]

G = nx.Graph()
G.add_nodes_from(vertices)
G.add_edges_from(edges)
pos = nx.spring_layout(G)

# 비범죄자(NF) 버텍스
nx.draw_networkx_nodes(G, pos, nodelist = [1, 4, 3, 8, 9], 
                       node_color = 'g', node_size = 1300)

# 범죄자(F) 버텍스
nx.draw_networkx_nodes(G, pos, nodelist = [2, 5, 6, 7], 
                       node_color = 'r', node_size = 1300)

# 엣지와 버텍스 레이블 표시
nx.draw_networkx_edges(G, pos, edges, width = 3, alpha = .5, edge_color = 'b')

labels = {}
labels[1] = r'1 NF'
labels[2] = r'2 F'
labels[3] = r'3 NF'
labels[4] = r'4 NF'
labels[5] = r'5 F'
labels[6] = r'6 F'
labels[7] = r'7 F'
labels[8] = r'8 NF'
labels[9] = r'9 NF'

nx.draw_networkx_labels(G, pos, labels, font_size = 16)

 

 

 

새로운 인물 q 추가 및 q의 범죄 연루 가능성 분석

 

새로운 인물 q가 인물 1, 5와 관계를 맺고 있을 때, q가 범죄를 저지를 확률은 어떻게 계산할 수 있을까?

간단한 사기분석 방법과 고급 기법으로 나눠서 분석한다.

 

 

1) 간단한 사기 분석 방법

• 네트워크에 있는 사람의 행동은 그 사람과 연결된 사람들에 의해서만 영향을 받는다고 가정함
• 즉, 버텍스가 직접 연결된 경우에만 비슷한 행동을 한다고 가정
• 이에 따라 버텍스 q가 F일 확률 P(F|q)는 다음과 같다.

버텍스 q가 사기꾼(F)일 확률

 

• Neighbourhood_{n}: 버텍스 n의 이웃 집합
• w(n, n_{j}): 버텍스 n과 n_{j}를 잇는 엣지의 가중치
  • 범죄자와 연결 시 1
  • 비범죄자와 연결 시 0
• degree_{q}: 버텍스 q의 도수
• DOS_{normalized_{j}}: j에 대한 의심 수준을 수치화 한 것으로 아래에서 상세히 설명한다.

 

 

수식을 통해 계산 시 범죄자일 확률 P(F|q)은 아래와 같다.

 

 

• 범죄자로 분류할 임계값(threshold)를 설정해야 한다.
  • 해당 임계값을 넘을 시 범죄자(F)로 분류하고, 미만일 시 비범죄자(NF)로 분류한다.
  • 중간값을 두어 범죄 유의 클래스를 형성할 수 있다.
• 그래프에 새로운 버텍스가 추가되면 버텍스 도수와 엣지 정보가 바뀌기 때문에 다시 계산해야 한다.

 

 

간단한 분석 방법의 한계

• 각 버텍스의 중요도를 활용하지 않는다. 즉, 직접 연결된 이웃들의 상태로만 영향을 받는다.
• 범죄 여부만 가중치에서 활용할 뿐 범죄의 중요도는 반영하기 어렵다.

 

 

 

2) 감시탑 사기 분석 방법

 

감시탑 사기 분석 방법은 부정적 효과 점수와 의심 수준을 통해 구하게 된다.

 

우선 네트워크의 9개 버텍스의 중심성 값과 지표 평균, 부정적 지수가 아래처럼 주어지고, 이를 통해 DOS 점수와 DOS 표준 점수를 구할 수 있다.

버텍스별 중심 지표와 DOS 점수

 

부정적 효과 점수와 의심 수준은 다음과 같다.

• 부정적 효과 점수: 사기 범죄를 저지른 사람의 범죄 강도를 나타낼 수 있다.
  • 범죄 유형에 따라 다른 범죄 점수를 매기는 것으로, 범죄의 경도 또는 피해 규모를 바탕으로 수치를 정한다.
  • 수치는 죄목에 따라서, 혹은 분석가에 따라 주관적으로 설정된다.
• 의심 수준(DOS, Degree Of Suspicion): 어떤 사람이 사기 범죄자일지에 대한 의심을 수치화 한 것
  • 범위: 0 ~ 9 사이로 해당 인물의 의심 수준이 0에 가까울수록 위험도가 낮으며, 9에 가까울수록 위험도가 높게 됨
  • 부정적 효과 점수와 중심성 지표의 평균값을 곱해 DOS를 산출함
  • 산출된 DOS 값 중 최댓값을 각 DOS 값에 나누어서 표준화된 값을 구하게 됨 (0이 최소, 1이 최대)

 

이를 통해 새로 추가된 버텍스 k의 DOS 점수는 다음과 같이 구할 수 있다.

 

버텍스 k의 DOS 점수

 

 

버텍스 k의 DOS 표준 점수는 다음과 같다.

버텍스 k의 DOS 표준 점수

 

 

각 버텍스의 DOS 표준 점수는 아래와 같다.

 

 

DOS 표준 점수는 0과 1사이 값이고, DOS 표준점수를 구간별로 나누어 특정 인물의 사기 위험성을 분류할 수 있다.

 

 

• 분석에 따르면 버텍스 k는 중간 높은 위험에 속하기 때문에 범죄 연루 여부에 대해 심각히 고려할 필요가 있다.

 

 

네트워크 분석의 발전 및 장단점

• 최근에 개발되는 네트워크 분석 기법들은 시간의 흐름에 따라 변화하는 그래프의 특징을 분석에 반영하기도 한다.
  • 연구자는 시간에 따라 네트워크의 버텍스 간 관계가 어떻게 변화하는지 파악할 수 있다.
  • 단점: 시계열 정보가 추가되면서 분석의 복잡도를 크게 증가시킬 수 있다.
  • 장점: 기존 방법으로 얻을 수 없는 통찰력을 얻을 수 있다.