logo

수학에서 그래프의 레이아웃 📂그래프이론

수학에서 그래프의 레이아웃

개요

수학에서 그래프 혹은 네트워크레이아웃layout이라 함은 어쨌거나 2D 혹은 3D로 시각화할 때 구체적으로 버텍스와 에지를 어떻게 배치할지에 대한 알고리즘이라 요약할 수 있다.

코드

편의상 모든 코드가 깃허브에 공개된 줄리아를 기준으로 작성한다1. 예시로 사용한 그래프는 바라바시-알버트 모델로 생성했다.

julia> G = barabasi_albert(50, 2)
{50, 96} undirected simple Int64 graph

julia> coordinates = random_layout(G)
([0.5010198458212828, 0.3452510059580436, 0.23056277180207596, 0.9451881326291259, 0.449381314574683, 0.4542317082538514, 0.599934409205972, 0.30717602583409154, 0.49093984675628266, 0.2715011111637651  …  0.681936012233088, 0.5814119530837815, 0.4207410774873547, 0.9727858272079993, 0.8552495989245602, 0.01141962455772294, 0.2899567788836197, 0.3666521897515005, 0.3711803454000888, 0.9162070908084106], [0.6301320613076998, 0.08213345094706803, 0.8807313434091223, 0.3037072145751386, 0.2696238790669454, 0.6634585165568677, 0.5096441313648647, 0.9252054034990449, 0.7087281373799236, 0.2122981806086709  …  0.5749195632507926, 0.7426568432084615, 0.42337991561728805, 0.7403457672559728, 0.09122908201258395, 0.06875442916534202, 0.5150784327498186, 0.0052746330721339385, 0.49087546999990384, 0.9942182342312704])

_layout 계열의 함수들은 해당 알고리즘에서 계산되는 좌표를 리턴한다. 시각화에 있어서 이러한 좌표를 직접 구할 수 있다는 것은 매우 큰 장점이다.

spring layout

spring.svg

random layout

random.svg

circular layout

circular.svg

shell_layout이라는 함수도 있는데 분명히 구현이 circular_layout과 다르지만 시각적으로는 차이가 없어서 생략했다.

stressmajorize layout

stressmajorize.svg

spectral layout

spectral.svg

전체 코드

using Graphs, GraphPlot, Plots, Random, GraphRecipes
G = barabasi_albert(50, 2)
coordinates = random_layout(G)

gplot(G, layout = spring_layout)
gplot(G, layout = random_layout)
gplot(G, layout = circular_layout)
gplot(G, layout = shell_layout)
gplot(G, layout = stressmajorize_layout)
gplot(G, layout = spectral_layout)

환경

  • OS: Windows
  • julia: v1.10.0