计算机科学技术学报(英文版)
計算機科學技術學報(英文版)
계산궤과학기술학보(영문판)
JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY
2015年
4期
799-809
,共11页
唐宏%牟帅%黄晋%朱佳%陈健%丁蕊
唐宏%牟帥%黃晉%硃佳%陳健%丁蕊
당굉%모수%황진%주가%진건%정예
common contact%k-hop query%reachability%social network
The problem of k-hop reachability between two vertices in a graph has received considerable attention in recent years. A substantial number of algorithms have been proposed with the goal of improving the searching e?ciency of the k-hop reachability between two vertices in a graph. However, searching and traversing are challenging tasks, especially in large-scale graphs. Furthermore, the existing algorithms propounded by different scholars are not satisfactory in terms of feasibility and scalability when applied to different kinds of graphs. In this work, we propose a new algorithm, called Zip, in an attempt to e?ciently determine the common contacts between any two random vertices in a large-scale graph. First, we describe a novel algorithm for constructing the graph index via binary searching which maintains the adjacent list of each vertex in order. Second, we present the ways to achieve a sequential k-hop contact set by using the loser tree, a merge sorting algorithm. Finally, we develop an e?cient algorithm for querying common contacts and an optimized strategy for k-hop contact set serialization. Experimental results on synthetic and real datasets show that the proposed Zip algorithm outperforms existing state-of-the-art algorithms (e.g., breadth-first searching, GRAIL, the graph stratification algorithm).