디지털 라이브러리[ 검색결과 ]
네트워크의 중첩 클러스터링 구조를 고려한 정보 확산 모델
http://doi.org/10.5626/JOK.2020.47.4.422
정보 전파(information diffusion) 연구란 네트워크에서 특정 노드(initial adopters)가 새로운 정보를 습득할 것으로 가정하고, 그로부터 다른 노드로 퍼지는 정보의 전파 양상(cascading behavior)에 대한 메커니즘을 모델링하는 것이다. 대부분의 기존 정보 전파 연구들은 노드가 하나의 클러스터(cluster)에만 속한다고 가정하며, 이 가정에 의해 클러스터가 정보 전파를 방해함을 보여 왔다. 하지만, 실제 네트워크에는 노드가 여러 클러스터에 속할 수 있다. 즉, 클러스터는 중첩될 수 있다. 본 연구는 네트워크에 중첩 클러스터(overlapping cluster)가 존재할 때의 정보 전파 양상에 대해 소개한다. 새로운 정보를 습득한 노드가 네트워크의 중첩 클러스터에 속하거나 네트워크의 각 노드에 대해 정보 공존성(compatibility)을 허용하였을 때 클러스터는 정보 전파의 방해요소가 아님을 보인다. 네 개의 실제 네트워크 데이터 셋(dataset)에서 본 연구에서 제시한 모델과 이론을 검증한다.
정교한 이웃 노드 선택법을 활용한 그래프 합성곱 네트워크
http://doi.org/10.5626/JOK.2019.46.11.1193
그래프 합성곱 네트워크(GCNs)는 합성곱 구조를 활용하여 주변 노드들의 정보를 종합하는 방식으로 대상 노드의 표현력을 높인다. 높은 성능을 보이기 위해서는 우선적으로 대상 노드에게 필요한 정보를 전달할 수 있는 주변 노드를 선별하고, 이후 학습시 적절한 필터(filter) 값을 습득하는 과정이 수반되어야한다. 최근 GCNs 알고리즘들은 1-hop 거리의 노드들을 선택하는 등의 비교적 간단한 이웃 노드정의를 활용하고 있다. 이러한 경우 불필요한 정보가 대상 노드에 전파되어 성능을 저하하는 문제가 발생한다. 본 논문에서는 대상 노드와 주변 노드간의 유사도 계산을 통해 유효한 이웃 노드를 선별하여 활용하는 GCN 알고리즘을 제안한다.
대용량 그래프 압축과 마이닝을 위한 그래프 정점 재배치 분산 알고리즘
수십억 개 간선들로 구성된 대용량 그래프를 어떻게 효과적으로 압축할 수 있을까? 정점 재배치를 통해 인접 행렬의 0이 아닌 값들을 집중시키면 그래프를 효율적으로 압축할 수 있을 뿐 아니라 페이지랭크 등 여러 그래프 마이닝 알고리즘의 수행 속도를 개선할 수 있다. 최신 정점 재배치 기법인 SlashBurn 은 실세계 네트워크의 멱법칙 특성을 활용하는 실세계 그래프에 효과적인 방법이다. 하지만 단일 머신 기반으로 설계되어 대용량 그래프에 대해 처리 속도가 현저히 느려지거나 적용이 불가능한 한계가 있다. 본 논문에서는 이러한 한계를 극복하기 위한 분산 SlashBurn을 제안한다. 분산 SlashBurn은 대규모의 정점재배치 프로세스를 분산 처리하여 대용량 그래프를 기존 방법보다 훨씬 빠르고 확장성 있게 처리한다. 대용량 실세계 그래프들에 대한 실험 결과, 분산 SlashBurn은 단일 머신 SlashBurn보다 45배 이상 빠르게 동작하였고, 16배 이상 큰 그래프를 처리할 수 있었다.
