Selective Edge Shedding in Large Graphs Under Resource Constraints
Selective Edge Shedding in Large Graphs Under Resource Constraints
复制标题
DOI：
10.1109/icde51399.2021.00200
复制
发表时间：
2021-04
期刊：
影响因子：
--
通讯作者：
Yiling Zeng;Chunyao Song;Tingjian Ge
中科院分区：
文献类型：
--
作者：
Yiling Zeng;Chunyao Song;Tingjian Ge
随着信息时代的飞速发展，许多复杂系统都可以用图来建模。然而，前所未有的数据增长使得日常用户处理和挖掘非常大的图形变得非常困难，因为他们的计算资源有限，例如个人电脑和笔记本电脑。为了应对这一挑战，我们提出了选择性边缘脱落。本文提出了两种保持顶点度的边脱落方法，其核心是保持期望的顶点度，从而捕捉网络的基本特征。这两种方法都允许用户根据计算资源约束来控制缩减图的大小。实验结果表明，本文提出的方法在图分析任务上的准确率比竞争性方法提高了65%，而运行时间仅为竞争性方法的26%-57%，充分体现了本文提出的方法的优势.
With the rapid development of the information age, many complex systems can be modeled as graphs. However, the unprecedented growth of data makes it extremely difficult for everyday users to process and mine very large graphs, given their limited computing resources such as personal computers and laptops. To address this challenge, we propose selective edge shedding. By estimating the original graph information from the reduced graph, it can accelerate graph algorithms and queries.In this paper, we propose two vertex-degree preserving edge shedding methods, the core of which are to maintain the expected vertex degree, so as to capture the basic characteristics of the network. Both methods allow users to control the size of the reduced graph based on the computing resource constraint. The experimental results show that the methods proposed in this paper can achieve up to 65% higher accuracy on graph analysis tasks compared to the competitive method, while consuming only 26%-57% running time, which fully demonstrates the advantages of the methods proposed in this work.