Reduction of large-scale graphs: Effective edge shedding at a controllable ratio under resource constraints
Reduction of large-scale graphs: Effective edge shedding at a controllable ratio under resource constraints
复制标题
大规模图的缩减：资源约束下可控比例的有效边缘脱落
DOI：
10.1016/j.knosys.2022.108126
复制
发表时间：
2022-01
影响因子：
8.8
通讯作者：
Ying Zhang
中科院分区：
文献类型：
--
作者：
Yiling Zeng;Chunyao Song;Tingjian Ge;Ying Zhang
随着技术的进步，许多复杂的系统可以用网络/图来表示。然而，当使用有限的计算资源，如便携式计算机或个人台式计算机时，由于我们生成的数据量空前增长，用户无法存储和挖掘大规模的图形。为了应对这一挑战，我们提出了有效的边缘剥离。有效的边剥离可以减少需要处理的数据量和相应的存储空间，同时加快图的算法和查询速度，从而支持交互分析，帮助知识发现，并消除噪声。为了提取图的基本特征，在保持期望顶点度的基础上，提出了两种有效的边剥离方法。这两种方法都允许用户控制边剥离过程，从而基于计算资源约束生成预定大小的简化图。使用四个不同领域的真实数据集，我们对我们的方法进行了广泛的实验评估，并在七个图分析任务上与最新的图摘要方法进行了比较。实验结果表明，该方法在图形分析任务中的准确率比目前最先进的方法高58.6%。对于非常大的数据集，我们的方法在生成约简图时只消耗竞争方法的0.3%的运行时间。以上结果充分说明了本文方法的优越性。
As technology advances, many complicated systems can be represented by networks/graphs. However, when using limited computing resources such as portable computers or personal desktop computers, users are not able to store and mine large-scale graphs due to the unparalleled growth of the amount of data we generate. In order to address this challenge, we present effective edge shedding. Effective edge shedding can reduce the amount of data to be processed and the corresponding storage space while speeding up graph algorithms and queries, thereby supporting interactive analysis, helping knowledge discovery, and eliminating noise. In this paper, to extract the underlying features of a graph, we present two effective edge shedding methods on the basis of preserving the expected vertex degree. Both methods allow users to control the edge shedding process, thus generating a reduced graph of the predefined size based on the computing resource constraint. Using four real-world datasets in different domains, we performed an extensive experimental evaluation of our methods and compared them with the state-of-the-art graph summarization method on seven graph analysis tasks. The results indicate that our methods can achieve up to 58.6% higher accuracy on graph analysis tasks compared with the state-of-the-art method. For very large datasets, our methods consumes only 0.3% of the running time of the competitive method when generating the reduced graph. The above results fully illustrate the advantages of our methods.
登录
查看更多内容
影响因子：
1
作者：
Brandes, U
通讯作者：
Brandes, U
DOI：
10.1007/978-3-030-58292-0_190774
发表时间：
2021
期刊：
Encyclopedic Dictionary of Archaeology
影响因子：
--
作者：
通讯作者：
--
DOI：
--
发表时间：
2003
期刊：
--
影响因子：
--
作者：
M. Mihail;Nisheeth K. Vishnoi
通讯作者：
M. Mihail;Nisheeth K. Vishnoi
DOI：
10.1145/2939672.2939754
发表时间：
2016-08
期刊：
KDD : proceedings. International Conference on Knowledge Discovery & Data Mining
影响因子：
--
作者：
Grover A;Leskovec J
通讯作者：
Leskovec J
一种用于复杂网络采样的新型绿色算法
影响因子：
8.7
作者：
Chao Tong;Yu Lian;Jianwei Niu;Zhongyu Xie;Yang Zhang
通讯作者：
Yang Zhang