그래프 이론을 적용한 그래프 데이터베이스 활용 사례
그래프 데이터베이스(Graph Database)가 전달하는 가치
표현(Presentation) > 발견(Discovery) > 추론(Inference)
AgensGraph 기반의 5가지 핵심 오퍼링
- AssetManager : 기업에게 시각화 및 모니터링이 가능한 도구
- TextMiner : 비정형 텍스트 데이터에서 가치와 의미가 있는 정보를 찾아내는 기술
- PatternDetector : 위협 예방 및 분석을 위한 패턴 감지
- ChainKeeper :
- DecisionTutor : 데이터 분석을 통한 의사 결정
그래프의 기본구성
- Degree(정도), Strength(힘)
- Degree는 노드가 가진 링크(엣지)의 개수(또는 노드로부터 연결된 노드의 개수)를 의미
- Strength 는 Weighted(가중치) graph에서는 degree 개념을 확장하여 노드가 가진 링크의 강도의 총합
- Weighted graph : 엣지에 가중치가 있는 그래프
- Binary, Weighted(가중치)
- Binary : 엣지의 강도 없음
- Weighted : 엣지의 강도가 있음(엣지가 값을 가지고 있는 것)
- 엣지의 강도 존재 유무에 따 라서 나뉘는 기준
- Undirectional(단방향), Directional(방향)
- 연결선의 방향성의 존재 유무에 따라서 나뉘는 기준
- Undirectional의 경우 한쪽으로 데이터가 향함
- Unipartite(한가지 종류), Multipartite(여러 종류)
- 노드의 구성이 한가지 종류로만 이루어져 있는지, 또는 여러 종류로 이루어져 있는지에 따라서 그래프의 종류를 나눈 것
- 노드의 종류가 2가지로만 이루어져 있는 경우, Bipartite graph, 대부분의 경우에 Bipartite graph로 그려짐
- Hypergraph
- 동시에 다수의 노드를 연결하는 개념
- 노드와 노드 사이의 노드는 특정한 정보를 가지고 있어야 함
- 링크개념을 확장한 기준으로서, 하나의 연결선이 다수의 노드와 연결가능한 그래프를 의미함.
- 일반적으로 Hypergraph data의 경우 hyperedge를 이종의 Node로 표현한 Bipartite graph로 치환하여 정보 손실 없이 데이터를 다룸
- ex. 가족이라는 엣지에 여러 노드들(엄마, 아빠, 형, 누나)이 연결되어 있음
- Motif
- 그래프 네트워크 상에서 특정 국부(Local) 네트워크가 지니는 속성
- 그래프 네트워크 상에서 발견되는 패턴(부분적인 서브그래프, 반복되는 하위 그래프)
- Monoplex, Multiplex, Multilayer graph
- 그래프가 하나의 레이어로만 이루어져 있는지(Monoplex)
- 둘 이상의 레이어로 구성되며 각 레이어를 구성하는 노드는 동일하고 링크의 구성만 바뀌는지(Multiplex)
- 둘 이상의 레이어로 구성되며 각 레이어를 구성하는 노드set 또한 변하는지(Multilayer)
- 여러개의 그래프간의 연관 관계를 찾을 수 있음
그래프 이론 소개 및 활용사례
- Node-Edge Graph
- 노드와 엣지로 표현한 그래프
- 각기 다른 시스템으로 부터 연결 패턴의 유사성이나 다른 점을 찾아 분석
- 몰랐던 사실을 발견할 수 있음
- Ranking(Centrality)
- 중요도를 결정
- 노드에 연결되어 있는 엣지들의 숫자를 이용
- Closeness: 밀집
- Betweenness : 경로
- Pattern detection
- 그래프가 가지고 있는 특정한 규칙을 찾아내는 것
- Jaccard coefficient : 두 집합 사이의 중복되는 것(교집합)을 수치화(0% = 0, 50% = 0.5, 100% = 1)
- Classification (Clustering)
- 정해진 형태로 분류를 하는 것
- Shortest Path
- 노드 간의 최단 경로를 찾는 것
- Min./Max. Spanning Tree
- 엣지의 가중치 최소/최대의 부분집합을 추출
- 아주 복잡한 그래프의 백본을 찾아내는 것
- 도로 설계, 통신망 설계
- 그래프의 핵심을 추려내기 위한 방법
- Text Mining
- 반/비정형 텍스트 데이터를 정형화하고, 특징을 추출하는 기법
- Regression Analysis
- 하나나 그 이상의 독립변수의 종속변수에 대한영향의추정을할수있는통계기법
- Time Series Analysis
- 시간에 따라서 변하는 자료로부터 패턴을 찾고 모델링하는 분석기법
- Bayesian
- 객관의 영역(경험, 기존의 통계 데이터)와 주관의 영역(사실, 실제로 측정 된 증거)을 합쳐서 결과를 추론해 내는 것
참고자료