Higher-Order Peak Decomposition
Authors: 
Xingyu Tan, Jingya Qian, Chen Chen, Sima Qing, Yanping Wu, Xiaoyang Wang, Wenjie ZhangAuthors Info & Claims
Pages 4310 - 4314
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,h)-peak, which incorporates higher-order (h-hops) neighborhood information of vertices. Employing the (k,h)-peak model, we explore the higher-order peak decomposition problem that calculates the vertex peakness for all conceivable k values given a particular h. 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.
Supplementary Material
Presentation video.
- Download
- 113.42 MB
References
[1]
Roberto FS Andrade, José GV Miranda, Suani TR Pinho, and Thierry Petit Lobao. 2008. Characterization of complex networks by higher order neighborhood properties. The European Physical Journal B, Vol. 61 (2008), 247--256.
[2]
Roberto F. S. Andrade, José G. V. Miranda, and Thierry Petit Lob ao. 2006. Neighborhood properties of complex networks. Phys. Rev. E, Vol. 73 (Apr 2006), 046101. Issue 4.
[3]
Francesco Bonchi, Arijit Khan, and Lorenzo Severini. 2019. Distance-generalized core decomposition. In Proceedings of the 2019 International Conference on Management of Data. 1006--1023.
[4]
Chen Chen, Mengqi Zhang, Renjie Sun, Xiaoyang Wang, Weijie Zhu, and Xun Wang. 2022. Locating pivotal connections: the K-Truss minimization and maximization problems. World Wide Web, Vol. 25, 2 (2022), 899--926.
[5]
Chen Chen, Qiuyu Zhu, Renjie Sun, Xiaoyang Wang, and Yanping Wu. 2021b. Edge manipulation approaches for k-core minimization: metrics and analytics. IEEE Transactions on Knowledge and Data Engineering, Vol. 35, 1 (2021), 390--403.
[6]
Zi Chen, Long Yuan, Li Han, and Zhengping Qian. 2021a. Higher-order truss decomposition in graphs. IEEE Transactions on Knowledge and Data Engineering (2021).
[7]
Priya Govindan, Chenghong Wang, Chumeng Xu, Hongyu Duan, and Sucheta Soundarajan. 2017. The k-peak decomposition: Mapping the global structure of graphs. In Proceedings of the 26th International Conference on World Wide Web. 1441--1450.
[8]
Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2019. Efficient (α, β)-core computation: An index-based approach. In The World Wide Web Conference. 1130--1141.
[9]
Qing Liu, Xuliang Zhu, Xin Huang, and Jianliang Xu. 2021. Local algorithms for distance-generalized core decomposition over large dynamic graphs. Proceedings of the VLDB Endowment, Vol. 14, 9 (2021), 1531--1543.
[10]
Linyuan Lü, Tao Zhou, Qian-Ming Zhang, and H Eugene Stanley. 2016. The H-index of a network node and its relation to degree and coreness. Nature communications, Vol. 7, 1 (2016), 10168.
[11]
Fragkiskos D Malliaros, Christos Giatsidis, Apostolos N Papadopoulos, and Michalis Vazirgiannis. 2020. The core decomposition of networks: Theory, algorithms and applications. The VLDB Journal, Vol. 29 (2020), 61--92.
[12]
Enys Mones, Lilla Vicsek, and Tamás Vicsek. 2012. Hierarchy measure for complex networks. PloS one, Vol. 7, 3 (2012), e33799.
[13]
Esmaeel Moradi and Balabhaskar Balasundaram. 2018. Finding a maximum k-club using the k-clique formulation and canonical hypercube cuts. Optimization Letters, Vol. 12 (2018), 1947--1957.
[14]
Mark EJ Newman. 2006. Modularity and community structure in networks. Proceedings of the national academy of sciences, Vol. 103, 23 (2006), 8577--8582.
[15]
Renjie Sun, Chen Chen, Xiaoyang Wang, Ying Zhang, and Xun Wang. 2020. Stable community detection in signed social networks. IEEE Transactions on Knowledge and Data Engineering, Vol. 34, 10 (2020), 5051--5055.
[16]
Renjie Sun, Yanping Wu, Chen Chen, Xiaoyang Wang, Wenjie Zhang, and Xuemin Lin. 2022. Maximal balanced signed biclique enumeration in signed bipartite graphs. In 2022 IEEE 38th International Conference on Data Engineering (ICDE). IEEE, 1887--1899.
[17]
Xudong Wu, Long Yuan, Xuemin Lin, Shiyu Yang, and Wenjie Zhang. 2019. Towards efficient k-tripeak decomposition on large graphs. In DASFAA. 604--621.
[18]
Yanping Wu, Renjie Sun, Chen Chen, Xiaoyang Wang, and Qiuyu Zhu. 2020. Maximum signed (k, r)-truss identification in signed networks. In CIKM. 3337--3340.
Index Terms
- Higher-Order Peak Decomposition
Recommendations
A large-scale graph partition algorithm with redundant multi-order neighbor vertex storage
AbstractRecently, graph data become increasingly important and larger in many fields, and many distributed graph computing systems have been proposed to deal with large-scale graphs. The graph partition algorithm is the basis of these systems. In many ...
Highlights- Formulating the graph partitioning problem with redundant storage of multi-order neighbor vertices.
- Presenting a graph partitioning algorithm PARN to solve this problem.
- Performing extensive experiments to show the out-performance ...
Higher-order abstract syntax in classical higher-order logic
LFMTP '09: Proceedings of the Fourth International Workshop on Logical Frameworks and Meta-Languages: Theory and PracticeHigher-Order Abstract Syntax, or HOAS, is a technique for using a higher-order logic as a metalanguage for an object language with binding operators. It avoids formalizing syntactic details related to variable binding. This paper gives an extension to ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2023
5508 pages
ISBN:9798400701245
DOI:10.1145/3583780
- General Chairs:
- Ingo Frommholz,
- Frank Hopfgartner,
- Mark Lee,
- Michael Oakes,
- Program Chairs:
- Mounia Lalmas,
- Min Zhang,
- Rodrygo Santos
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 October 2023
Check for updates
Author Tags
Qualifiers
- Short-paper
Funding Sources
- AEGiS
Conference
CIKM '23: The 32nd ACM International Conference on Information and Knowledge Management
October 21 - 25, 2023
Birmingham, United Kingdom
Acceptance Rates
Overall Acceptance Rate 1,861 of 8,427 submissions, 22%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 102Total Downloads
- Downloads (Last 12 months)102
- Downloads (Last 6 weeks)4
Reflects downloads up to 24 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in