디지털 라이브러리[ 검색결과 ]
큰 그래프 상에서의 개인화된 페이지 랭크에 대한 빠른 계산 기법
http://doi.org/10.5626/JOK.2022.49.10.859
그래프 내에서 개인화된 페이지랭크(Personalized PageRank, PPR)를 계산하는 것은 검색, 추천, 지식발견 등 여러 분야에서 광범위하게 활용되는 중요한 작업이다. 개인화된 페이지랭크를 계산하는 것은 고비용의 과정이 필요하므로, 개인화된 페이지랭크를 계산하는 효율적이고 혁신적인 방법들이 다수 개발되어왔다. 그러나 수백만 이상의 노드를 가진 대용량 그래프에 대한 PPR 계산은 여전히 시간이 크게 소요되는 작업이다. 그에 더하여, 기존에 제시된 알고리즘들은 그래프 갱신을 효율적으로 처리하지 못하여, 동적으로 변화하는 그래프 처리에 한계가 있다. 이에 대응하여, 본 연구에서는 높은 정밀도를 보장하면서도 빠르게 수렴하는 PPR 계산 알고리즘을 제시한다. 전통적인 거듭제곱법(Power Iteration)에, 축차가속완화법(Successive Over Relaxation)과 초기 추측값 보정법(Initial Guess Revision)을 활용한 벡터 재사용 전략을 적용하여 수렴 속도를 개선하였다. 제시된 방법은 기존 거듭제곱법의 장점인 단순성과 엄밀성을 유지하면서도 수렴율과 계산속도를 크게 개선한다. 또한 개인화된 페이지랭크 벡터의 갱신을 위하여 이전에 계산되어 저장된 벡터를 재사용하여, 갱신에 드는 시간이 크게 단축된다. 본 방법은 주어진 오차 한계에 도달하는 즉시 결과값을 산출하므로 정확도와 계산시간을 유연하게 조절할 수 있으며, 이는 표본 기반 추정방법이나 역행렬 기반 방법이 가지지 못한 특성이다. 실험 결과, 본 방법은 거듭제곱법에 비하여 20배 이상 빠르게 수렴한다는 것이 확인되었으며, 기 제시된 최속 알고리즘과 비교하여도 결과 품질을 일정 수준 이상으로 유지하면서도 수행시간 면에서 우수한 성능을 보이는 것 또한 확인되었다.
메신저 사용자 검증을 위한 그래프 기반 채팅 메시지 분석 모델 제안
http://doi.org/10.5626/JOK.2022.49.9.696
메신저를 통한 범죄와 사고가 증가하고 있어 메신저 사용자 검증의 필요성이 대두되고 있다. 본 연구에서는 전통적인 저자 검증 문제를 채팅 텍스트에 적용해 두 개의 그래프 기반 메신저 사용자 검증 모델을 제안했다. 그래프 랜덤워크 모델은 이전 채팅 메시지로 n-gram 전이 그래프를 구축하고, 작성자를 알 수 없는 메시지로 전이 그래프를 순회한 특성을 학습해서 사용자를 검증한다. 실험결과 10,000개의 채팅 대화에서 정확도 86%의 성능을 보였다. 그래프 볼륨 모델은 시간의 흐름에 따라 전이 그래프의 규모가 증가하는 특성을 이용해 사용자를 검증했고, 1,000개의 채팅 대화에서 정확도 87%의 성능을 낼 수 있었다. 전송 시각을 기준으로 채팅 메시지의 밀도를 계산했을 때, 두 그래프 모델 모두 채팅 밀도가 15 이상일 때 80% 이상의 정확도를 보장할 수 있었다.
부분 그래프 매칭 문제를 위한 새로운 동적 매칭 순서와 성능 비교
http://doi.org/10.5626/JOK.2022.49.1.1
최근 다양한 분야에서 그래프 분석이 사용되고 있다. 그래프 분석에서 가장 핵심적인 문제 중 하나는 부분 그래프 매칭(subgraph matching) 문제이다. 부분 그래프 매칭 문제는 데이터 그래프와 쿼리그래프가 주어졌을 때 데이터 그래프에서 쿼리 그래프의 모든 임베딩(embedding)을 찾는 문제이다. 그동안 이 문제를 해결하는 백트래킹 기반의 많은 알고리즘이 연구되어왔다. 본 논문에서는 이 문제를 해결하는 최신 알고리즘인 DAF에서 제안한 동적 매칭 순서의 문제점을 분석하고 이를 개선한 동적 매칭 순서를 소개한다. 또한, 제안한 매칭 순서를 실제 데이터 그래프를 가지고 실험을 진행하여 가지치기 기법을 사용하지 않았거나 가지치기 기법을 사용하더라도 수행 시간이 매우 짧지 않으면 이전 매칭 순서들보다 효과적임을 입증하였다.
