빅 데이터와 그래프 이론의 새로운 지평: 하이퍼그래프에서 심플리셜 복합체까지 빅 데이터의 시대는 우리가 정보를 이해하고 분석하는 방식을 근본적으로 변화시켰습니다. 이 글에서는 빅 데이터가 그래프 이론을 어떻게 새로운 차원으로 이끌었는지를 탐구합니다. 그래프 이론은 정점(vertex)과 간선(edge)을 사용하여 데이터 간의 연결성을 모델링하는 수학의 한 분야입니다. 이는 정보의 복잡한 구조를 단순화하여 이해할 수 있게 해줍니다. 전통적 그래프 이론의 한계 … Read more
어김없이 돌아온 그래프이론글이다. 이번에는 Cartesian product, grid, greedy coloring, interval representation등에 대해 알아보겠다. Cartesian product, grid, greedy coloring, interval representation는 쉬운개념들이니까 이해하기 쉬울것이다. Cartesian Product 그래프 그래프 $G$와 $H$가 있따고 합시다. $G$와 $H$의 cartesian product는 기호로는 $G\square H$라고 씁니다. $G\square H$는 vertex set이 $V(G) \times V(H)$입니다. $E(G) $는 어떻게 정의될까요? $(u,v)$와 $(u^\prime, v^\prime)$이 있다고 합시다. … Read more
이번 글에서는 그래프이론의 clique number에 대해 알아보자. 그리고 지난 글에서 chromatic number에 대해 얘기하였었는데 chromatic number와 clique number의 관계에 대해서도 알아보자. 참 재밌는 결과들이 있으니까 clique number와 chromatic number의 관계를 꼭 알아보도록 하자. 그러면 이제 시작해보자. clique number 그래프 $G$가 있다고 하자. clique number의 기호는 $\omega(G)$라고 하겠다. 그래프 $G$에 pairwise하게 adjacent vertices 들로 구성된 … Read more
여기서부터 입력그래프 (Graph)가 있다고 하고 이것을 색칠할려고 한다. 그래프 얘기를 시작하기전에 지도를 생각해보자. 지도에 여러 도시가 있을 때 이 도시들을 색칠하고 싶은데 서로 이웃하는 도시는 서로 다른 색으로 칠할려고 한다. 생각해보면 쉬우면서도 어려운데 이것을 수학적으로 추상화시키면 그래프가 있고 각각의 도시를 vertex로 설정하고 이웃한다는것을 edge로 표현한담에 adjacent 한 vertex들은 다른 색으로 칠하면 되는 문제이다. 이번 글에서는 … Read more
그래프이론에서 vertex 끼리 adjacet한지 아닌지 중요하다. adjacent 한지 아닌지를 기록하여 adjacency matrix에 나타낸다. 그리고 이 matrix의 eigen value와 eigen value multiplicity 도 구해서 그래프 구조를 구하는데 활용한다. 이번 글에서는 그래프의 adjacency matrix와 이것의 eigen value와 eigen value 의 multiplicity 기록한 spectrum matrix에 대해 알아보겠다. Adjacency matrix 그래프 $G$가 있다고 하자. $G$의 vertex를 … Read more
Graph의 Spectral Filtering에 대해 알아보자. loop가 없는 simple graph $G=(V,E)$가 있다고 하자. $G$의 normalized Laplacian matrix를 $L^{norm}$ 이것의 대각화 표현을 $L^{norm}=U \Lambda U^T$이라고 하자 (참고글: Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 0과 2사이인 이유). 지난 글 (Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의)에서 봤듯이 $L^{norm}$의 eigen value는 인접한 vertex들의 차이가 얼마나 … Read more
이번 글에서는 Graph Convolution (그래프 컨볼루션)에 대해 알아보자. Graph convolution에 대해 알아보기전에 아래의 글들을 이해하고 오길 바란다. Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의 Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 0과 2사이인 이유 그러면 이제 Graph Convolution에 대해 알아보자. Graph convolution의 정의 loop가 없는 simple graph $G=(V,E)$가 있다고 하자. $L^{norm}$은 $G$의 … Read more
이번 글에서는 Graph Fourier Transform (그래프 푸리에 변환)의 필요성과 정의에 대해 알아보도록 하자. 오늘의 글을 본격적으로 진행하기 전에 몇가지를 정의하고 시작하자. loop가 없는 simple graph $G=(V,E)$가 있다고 하자. $D$를 $G$의 degree matrix라고 정의하고 $A$를 $G$의 adjacency matrix라고 정의하자. 그리고 $L^{norm}$을 $G$의 normalized laplacian matrix라고 정의하자. (참고글: Graph의 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 eigen value가 … Read more
이번 글에서는 Normalized Laplacian matrix (정규화된 라플라시안 행렬)과 이것의 eigen value가 0과 2사이라는 사실을 설명해보겠다. Normalized Laplacian matrix에 대해 알아보기 전에 Normalized adjacency matrix를 정의하고 그것으로 부터 Normalized Laplacian matrix를 정의한 이 후 글을 이어가겠다. Normalized Laplacian matrix 알아보기 그래프 $G=(V,E)$가 있다고 하자. $V=\{1,2,…,n\}$이라고 편하게 표시하자. Nomralized Adjacency matrix 정의 Normalized Laplacian matrix에 대해 알아보기전에 … Read more
이번 글에서는 그래프 (graph)의 Laplacian matrix (라플라시안 행렬)과 Laplacian matrix의 성질들을 알아보겠다. Laplacian matrix는 positive definite matrix이고 이에 따라 eigen value가 0보다 크거나 같으며 Laplacian matrix의 eigen value에는 무조건 0이 있다는 것까지 알아보자. Laplacian matrix의 정의 방향이 없는 undirected simple graph $G=(V,E)$가 있다고 하자. 편하게 $V=\{1,2,3,…,n\}$이라 표현하겠다. $\mathbf{D}$를 이 graph $G$의 degree matrix라 하고 $\mathbf{A}$를 … Read more