Zip： An Algorithm Based on Loser Tree for Common Contacts Searching in Large Graphs  

作　　者：唐宏 牟帅 黄晋 朱佳 陈健 丁蕊 

机构地区：[1]School of Information Science and Technology, Sun Yat-sen University, Guangzhou 510006, China [2]School of Software Engineering, South China University of Technology, Guangzhou 510006, China [3]School of Computer Science, South China Normal University, Guangzhou 510631, China

出　　处：《Journal of Computer Science & Technology》2015年第4期799-809,共11页计算机科学技术学报（英文版）

摘　　要：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）.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）.

关 键 词：common contact k-hop query REACHABILITY social network 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程] TP311.13[自动化与计算机技术—控制科学与工程]