그래프와 네트워크의 이해
그래프(graph)는 집합, 시퀀스, 격자(lattice), 트리(tree)보다 더 일반적인 범주의 데이터 구조를 표현할 수 있는 강력한 메커니즘입니다. 하나의 그래프만으로도 복잡한 관계와 위계 구조를 자연스럽게 담아낼 수 있기 때문입니다.
실제로 그래프는 인터넷과 소셜 네트워크, 데이터 네트워크, 생물학적 웹, 바이오인포매틱스(생물정보학), 화학 정보학, 컴퓨터 비전, 멀티미디어 및 콘텐츠 검색 등 방대한 영역에서 폭넓게 활용되고 있습니다.
그래프·네트워크 마이닝의 주요 응용 분야
1. 그래프 패턴 마이닝(Graph Pattern Mining)
그래프 패턴 마이닝은 하나 또는 여러 개의 그래프 집합에서 반복적으로 등장하는 빈발 서브그래프(frequent subgraph)를 발견하는 기법입니다. 대표적인 접근 방식으로는 Apriori 기반 방식과 패턴 성장(pattern-growth) 기반 방식 두 가지로 나눌 수 있습니다.
또한 폐쇄 그래프(closed graph)를 추출할 수도 있습니다. 어떤 그래프 g보다 큰 초월그래프(supergraph) 중 g와 동일한 지지도(support count)를 갖는 것이 존재하지 않을 때, 해당 그래프를 '폐쇄 그래프'라고 부릅니다. 이 외에도 근사 빈발 그래프(approximate frequent graph), 결속 그래프(coherent graph), 밀집 그래프(dense graph)와 같은 변형된 그래프 패턴들이 존재합니다. 사용자가 정의한 제약조건을 마이닝 단계 깊숙이 통합하면 마이닝 효율을 한층 높일 수 있습니다.
2. 네트워크의 통계적 모델링(Statistical Modeling of Networks)
네트워크는 각각 객체(object)에 해당하고 속성(property) 집합을 가지는 노드(node)들과, 객체 간의 관계를 나타내는 엣지(edge, 링크)들의 집합으로 구성됩니다.
노드와 링크의 유형이 모두 동일한 경우를 동종(homogeneous) 네트워크라 하며, 친구 네트워크, 공저자 네트워크, 웹 페이지 네트워크가 대표적인 예입니다. 반면 노드와 링크가 서로 다른 유형으로 구성된 경우를 이종(heterogeneous) 네트워크라 하는데, 저자·학회·논문·문서를 연결하는 출판 네트워크나 의사·간호사·환자·질병·치료를 연결하는 의료 네트워크가 그 예입니다.
3. 정보 네트워크 분석을 통한 데이터 정제·통합·검증
거대한 네트워크 안에서 상호 연결된 데이터 요소들 사이에는 정보 중복(information redundancy)이 존재할 수 있습니다. 네트워크 분석을 통해 이러한 중복 정보를 파악하면, 고품질의 데이터 클리닝(data cleaning), 데이터 통합(data integration), 데이터 검증(data validation), 그리고 신뢰성 탐색(trustability search)을 효과적으로 수행할 수 있습니다.
4. 그래프 및 동종 네트워크의 군집화와 분류
대규모 네트워크에 군집 분석(clustering) 기법을 적용하면 네트워크의 구조적 특성과 속성 정보를 바탕으로 숨겨진 커뮤니티, 허브(hub), 이상치(outlier)를 발견할 수 있습니다. 이렇게 개발된 네트워크 군집화 방법들은 분할(partitioning) 기반, 계층(hierarchical) 기반, 밀도(density) 기반 알고리즘으로 분류할 수 있습니다.
5. 이종 네트워크의 군집화, 랭킹, 분류
이종 네트워크는 여러 유형의 노드와 링크가 상호 연결된 구조를 가집니다. 이러한 상호 연결 구조는 매우 풍부한 정보를 담고 있어, 노드와 링크를 상호 보완적으로 개선하고 한 유형에서 얻은 지식을 다른 유형으로 전파(propagation)하는 데 활용할 수 있습니다.
특히 이종 네트워크에서의 군집화와 랭킹(ranking)은 밀접하게 연관되어 함께 수행됩니다. 군집 내에서 높은 순위를 차지한 노드는 낮은 순위의 노드보다 군집 응집도(cohesiveness) 계산에 더 크게 기여하기 때문입니다.