Towards Efficient k-TriPeak Decomposition on Large Graphs

X Wu, L Yuan, X Lin, S Yang, W Zhang - … Mai, Thailand, April 22–25, 2019 …, 2019 - Springer
Database Systems for Advanced Applications: 24th International Conference …, 2019Springer
Analyzing the structure of real-world networks has attracted much attention over years and
cohesive subgraph models are commonly used to characterize the structure of a network.
Recently, a model named k-Peak is proposed to address the issue failing to detect sparser
regions if the network contains distinct regions of different densities in the cohesive
subgraph models. However, k-Peak only considers the edge connection (ie, degree) in the
network and the loose structure restricts the effectiveness of the k-Peak. On the other hand …
Abstract
Analyzing the structure of real-world networks has attracted much attention over years and cohesive subgraph models are commonly used to characterize the structure of a network. Recently, a model named k-Peak is proposed to address the issue failing to detect sparser regions if the network contains distinct regions of different densities in the cohesive subgraph models. However, k-Peak only considers the edge connection (i.e., degree) in the network and the loose structure restricts the effectiveness of the k-Peak. On the other hand, triangles are fundamental building blocks of a network and are widely used in the literature. Motivated by this, in this paper, we propose the k-TriPeak model based on the triangles and study the problem of k-TriPeak decomposition that computes the k-TriPeak for all possible k values to understand the structure of a network. Through investigating the drawbacks of the baseline algorithm following the idea of k-Peak decomposition, we devise a new efficient algorithm to perform the k-TriPeak decomposition. Our new algorithm adopts a top-down decomposition paradigm and integrates two novel upper bounds with which large unnecessary computation can be pruned. We conduct extensive experiments on several large real-world datasets and the experimental results demonstrate the efficiency and effectiveness of our proposed algorithm.
Springer
以上显示的是最相近的搜索结果。 查看全部搜索结果