Higher-Order Peak Decomposition
Publication Name
International Conference on Information and Knowledge Management, Proceedings
Abstract
k-peak is a well-regarded cohesive subgraph model in graph analysis. However, the k-peak model only considers the direct neighbors of a vertex, consequently limiting its capacity to uncover higher-order structural information of the graph. To address this limitation, we propose a new model in this paper, named (k, ℎ)-peak, which incorporates higher-order (ℎ-hops) neighborhood information of vertices. Employing the (k, ℎ)-peak model, we explore the higher-order peak decomposition problem that calculates the vertex peakness for all conceivable k values given a particular ℎ. To tackle this problem efficiently, we propose an advanced local computation based algorithm, which is parallelizable, and additionally, devise novel pruning strategies to mitigate unnecessary computation. Experiments as well as case studies are conducted on real-world datasets to evaluate the efficiency and effectiveness of our proposed solutions.
Open Access Status
This publication is not available as open access
First Page
4310
Last Page
4314