온라인 사회연결망에서 DPL을 이용한 커뮤니티 기반 샘플링 방안

Abstract

본 논문에서는 온라인 사회연결망으로부터 해당 사회연결망의 특성과 유사한 소규모 사회연결망을 생성하는 방안에 대해서 논의한다. 먼저, 기존 샘플링 방안들을 두 가지 관점으로 분류하고, 이를 통해서 기존 샘플링 방안들의 문제점을 도출한다. 본 논문에서는 기존 샘플링 방안의 문제점을 해결하기 위해서 원본 그래프에서 노드 또는 링크를 균일하게 선택하면서 원본 그래프의 위상 구조를 고려하는 샘플링 방안을 제안한다. 제안하는 방안은 원본 그래프를 커뮤니티들의 집합으로 분할한 후 분할된 각 원본 커뮤니티들에서 노드와 링크를 해당 커뮤니티의 크기에 비례하게 선택하여 샘플 커뮤니티를 생성한다. 그런 후에 샘플 커뮤니티들 간의 연결성을 고려하면서 각 샘플 커뮤니티들을 병합하여 최종 샘플 그래프를 생성한다. 또한, 온라인 사회 연결망에서 노드와 링크 수의 비율을 나타내는 Densification Power Law(DPL)를 이용하여 원본 그래프의 노드와 링크 수의 비율을 반영하는 샘플 그래프를 생성하는 방안을 제안한다. 본 논문에서는 제안하는 방안을 다양한 실제 사회연결망에 대하여 실험하였다. 실험 결과, 위의 두 가지 샘플링 방안을 결합한 방안이 기존 샘플링 방안들에 비해서 성능이 뛰어남을 보였고, 커뮤니티를 이용한 샘플링 방안과 DPL을 이용한 샘플링 방안이 각각 유효하다는 것을 보였다. |In this paper, we discuss methods to create a small network sampled from an original network whose properties are similar to those of the original one. We first categorize existing methods with two different points of view, and point out their problems. Then, we propose a sampling method that uniformly at random select a set of nodes or links from the original network as considering topological structure of the original one. The method partitions the original network into a set of communities and then creates sample communities by sampling nodes or edges from each original community, considering community sizes. Then, it builds the final sample network by merging the sample communities, taking the connectivity among communities in the original network into account. We also propose a method that samples nodes and links from the original network, satisfying the densification power law (DPL) that determines the ratio of the numbers of edges and nodes in a network. We perform a variety of experiments with real-world social network data. The results show that each of our methods is effective in sampling and also that their combination performs best in preserving the properties of original networks.; In this paper, we discuss methods to create a small network sampled from an original network whose properties are similar to those of the original one. We first categorize existing methods with two different points of view, and point out their problems. Then, we propose a sampling method that uniformly at random select a set of nodes or links from the original network as considering topological structure of the original one. The method partitions the original network into a set of communities and then creates sample communities by sampling nodes or edges from each original community, considering community sizes. Then, it builds the final sample network by merging the sample communities, taking the connectivity among communities in the original network into account. We also propose a method that samples nodes and links from the original network, satisfying the densification power law (DPL) that determines the ratio of the numbers of edges and nodes in a network. We perform a variety of experiments with real-world social network data. The results show that each of our methods is effective in sampling and also that their combination performs best in preserving the properties of original networks.