Cited By
View all- Wei JYang ZLuo QZhang YQin LZhang W(2024)High-Order Local Clustering on HypergraphsICST Transactions on Scalable Information Systems10.4108/eetsis.743111:6Online publication date: 15-Nov-2024
Hierarchical Structure Construction on Hypergraphs
Authors: 
Qi Luo, Wenjie Zhang, 
Zhengyi Yang, Dong Wen, Xiaoyang Wang, Dongxiao Yu, Xuemin LinAuthors Info & Claims
Pages 1597 - 1606
Abstract
Exploring the hierarchical structure of graphs presents notable advantages for graph analysis, revealing insights ranging from individual vertex behavior to community distribution and overall graph stability. This paper studies hierarchical structures within hypergraphs, where a hyperedge can connect multiple vertices. We observed that directly extending hierarchical frameworks from pairwise graphs to hypergraphs overlooks high-order interactions and can result in either high computational complexity or sparse hierarchy structure. To address this challenge, we introduce a dual-layer hypergraph hierarchy consisting of a primary hierarchy and a secondary hierarchy, enabling the construction of a refined hypergraph hierarchy in linear time. The dual-layer hierarchy establishes a global hierarchy based on vertex cohesion, utilizing vertex-induced subhypergraphs, and a local hierarchy based on hyperedge containment, employing edge-induced subhypergraphs. The combination of global and local hierarchy mitigates the homogeneity and sparsity issues inherent in single-layer hierarchies, allowing more effective modeling of high-order interactions. Furthermore, we propose an efficient hierarchical construction algorithm by leveraging a novel hyperedge-based disjoint set to identify connected subhypergraphs. Additionally, to optimize the local hierarchy further and prevent the emergence of excessively redundant levels, we introduce a compact local hierarchy by defining a restricted subgraph metric to eliminate redundancy caused by large-sized hyperedges. Empirical studies on real-world hypergraphs demonstrate the effectiveness of our approach.
References
[1]
Naheed Anjum Arafat, Arijit Khan, Arpit Kumar Rai, and Bishwamittra Ghosh. 2023. Neighborhood-based Hypergraph Core Decomposition. Proc. VLDB Endow., Vol. 16, 9 (2023), 2061--2074.
[2]
Alain Barrat, Marc Barthélemy, and Alessandro Vespignani. 2008. Dynamical Processes on Complex Networks. Cambridge University Press.
[3]
Vladimir Batagelj and Matjaz Zaversnik. 2003. An O(m) Algorithm for Cores Decomposition of Networks. CoRR, Vol. cs.DS0310049 (2003).
[4]
Federico Battiston, Giulia Cencetti, Iacopo Iacopini, Vito Latora, Maxime Lucas, Alice Patania, Jean-Gabriel Young, and Giovanni Petri. 2020. Networks beyond pairwise interactions: structure and dynamics. CoRR, Vol. abs/2006.01764 (2020).
[5]
Eden Chlamt$acutea$$checkc$, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca. 2018. The Densest k-Subhypergraph Problem. SIAM J. Discret. Math., Vol. 32, 2 (2018), 1458--1477.
[6]
Philip S. Chodrow and Andrew Mellor. 2020. Annotated Hypergraphs: Models and Applications. Applied Network Science, Vol. 5 (2020), 9. Issue 1.
[7]
Philip S Chodrow, Nate Veldt, and Austin R Benson. 2021. Generative hypergraph clustering: From blockmodels to modularity. Science Advances, Vol. 7, 28 (2021), eabh1303.
[8]
Deming Chu, Fan Zhang, Wenjie Zhang, Xuemin Lin, and Ying Zhang. 2022. Hierarchical Core Decomposition in Parallel: From Construction to Subgraph Search. In 38th IEEE International Conference on Data Engineering, ICDE. IEEE, 1138--1151.
[9]
Aaron Clauset, Cristopher Moore, and Mark EJ Newman. 2008. Hierarchical structure and the prediction of missing links in networks. Nature, Vol. 453, 7191 (2008), 98--101.
[10]
Jonathan Cohen. 2008. Trusses: Cohesive Subgraphs for Social Network Analysis. In National Security Agency Technical report, Vol. 16. 3--29.
[11]
Martina Contisciani, Federico Battiston, and Caterina De Bacco. 2022. Inference of hyperedges and overlapping communities in hypergraphs. Nature communications, Vol. 13, 1 (2022), 7229.
[12]
Michele Coscia. 2018. Using arborescences to estimate hierarchicalness in directed complex networks. PloS one, Vol. 13, 1 (2018), e0190825.
[13]
Jonathan J Crofts and Desmond J Higham. 2011. Googling the brain: Discovering hierarchical and asymmetric network structures, with applications in neuroscience. Internet Mathematics, Vol. 7, 4 (2011), 233--254.
[14]
Dániel Czégel and Gergely Palla. 2015. Random walk hierarchy measure: What is more hierarchical, a chain, a tree or a star? Scientific reports, Vol. 5, 1 (2015), 17994.
[15]
Daniel Delling, Julian Dibbelt, Thomas Pajor, and Tobias Zündorf. 2017. Faster Transit Routing by Hyper Partitioning. In 17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS (OASICS, Vol. 59). 8:1--8:14.
[16]
John R. Douceur. 2002. The Sybil Attack. In Peer-to-Peer Systems, First International Workshop, IPTPS, Revised Papers (Lecture Notes in Computer Science, Vol. 2429). Springer, 251--260.
[17]
Alexandre P. Francisco and Arlindo L. Oliveira. 2011. Fully Generalized Graph Cores. In Complex Networks. Springer Berlin Heidelberg, Berlin, Heidelberg, 22--34.
[18]
Kasimir Gabert, Ali Pinar, and Ümit V. cCatalyürek. 2021. A Unifying Framework to Identify Dense Subgraphs on Streams: Graph Nuclei to Hypergraph Cores. In The Fourteenth ACM International Conference on Web Search and Data Mining. ACM, 689--697.
[19]
Shuguang Hu, Xiaowei Wu, and T.-H. Hubert Chan. 2017. Maintaining Densest Subsets Efficiently in Evolving Hypergraphs. In Proceedings of Conference on Information and Knowledge Management, CIKM. ACM, 929--938.
[20]
Xin Huang, Hong Cheng, Lu Qin, Wentao Tian, and Jeffrey Xu Yu. 2014. Querying k-truss community in large and dynamic graphs. In International Conference on Management of Data, SIGMOD. ACM, 1311--1322.
[21]
Igor Kabiljo, Brian Karrer, Mayank Pundir, Sergey Pupyrev, Alon Shalita, Yaroslav Akhremtsev, and Alessandro Presta. 2017. Social Hash Partitioner: A Scalable Distributed Hypergraph Partitioner. Proc. VLDB Endow., Vol. 10, 11 (2017), 1418--1429.
[22]
Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H Eugene Stanley, and Hernán A Makse. 2010. Identification of influential spreaders in complex networks. Nature physics, Vol. 6, 11 (2010), 888--893.
[23]
Jingyi Lin and Yifang Ban. 2013. Complex network topology of transportation systems. Transport reviews, Vol. 33, 6 (2013), 658--685.
[24]
Zhe Lin, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Zhihong Tian. 2021. Hierarchical Core Maintenance on Large Dynamic Graphs. Proc. VLDB Endow., Vol. 14, 5 (2021), 757--770.
[25]
Qingyuan Linghu, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2020. Global Reinforcement of Social Networks: The Anchored Coreness Problem. In Proceedings of the 2020 International Conference on Management of Data, SIGMOD. ACM, 2211--2226.
[26]
Qingyuan Linghu, Fan Zhang, Xuemin Lin, Wenjie Zhang, and Ying Zhang. 2022. Anchored coreness: efficient reinforcement of social networks. VLDB J., Vol. 31, 2 (2022), 227--252.
[27]
Boge Liu, Long Yuan, Xuemin Lin, Lu Qin, Wenjie Zhang, and Jingren Zhou. 2020. Efficient ((α), (β))-core computation in bipartite graphs. VLDB J., Vol. 29, 5 (2020), 1075--1099.
[28]
Yu Liu, Qi Luo, Mengbai Xiao, Dongxiao Yu, Huashan Chen, and Xiuzhen Cheng. 2024. Reordering and Compression for Hypergraph Processing. IEEE Trans. Comput. (2024), 1--14. https://doi.org/10.1109/TC.2024.3377915
[29]
Qi Luo, Zhenzhen Xie, Yu Liu, Dongxiao Yu, Xiuzhen Cheng, Xuemin Lin, and Xiaohua Jia. 2024. Sampling hypergraphs via joint unbiased random walk. World Wide Web (WWW), Vol. 27, 2 (2024), 15.
[30]
Qi Luo, Dongxiao Yu, Zhipeng Cai, Xuemin Lin, and Xiuzhen Cheng. 2021. Hypercore Maintenance in Dynamic Hypergraphs. In International Conference on Data Engineering. 2051--2056.
[31]
Qi Luo, Dongxiao Yu, Zhipeng Cai, Xuemin Lin, Guanghui Wang, and Xiuzhen Cheng. 2023. Toward maintenance of hypercores in large-scale dynamic hypergraphs. VLDB J., Vol. 32, 3 (2023), 647--664.
[32]
Qi Luo, Dongxiao Yu, Xiuzhen Cheng, Zhipeng Cai, Jiguo Yu, and Weifeng Lv. 2020. Batch Processing for Truss Maintenance in Large Dynamic Graphs. IEEE Trans. Comput. Soc. Syst., Vol. 7, 6 (2020), 1435--1446.
[33]
Qi Luo, Dongxiao Yu, Yu Liu, Yanwei Zheng, Xiuzhen Cheng, and Xuemin Lin. 2023. Finer-Grained Engagement in Hypergraphs. In 39th IEEE International Conference on Data Engineering, ICDE. IEEE, 423--435.
[34]
David W. Matula and Leland L. Beck. 1983. Smallest-Last Ordering and clustering and Graph Coloring Algorithms. J. ACM, Vol. 30, 3 (1983), 417--427.
[35]
Andrew McCrabb and Valeria Bertacco. 2021. Optimizing Vertex Pressure Dynamic Graph Partitioning in Many-Core Systems. IEEE Trans. Comput., Vol. 70, 6 (2021), 936--949.
[36]
Enys Mones, Lilla Vicsek, and Tamás Vicsek. 2012. Hierarchy measure for complex networks. PloS one, Vol. 7, 3 (2012), e33799.
[37]
Flaviano Morone, Gino Del Ferraro, and Hernán A. Makse. 2019. The k-core as a predictor of structural collapse in mutualistic ecosystems. Nature Physics, Vol. 15, 1 (2019), 95--102.
[38]
Giannis Moutsinas, Weisi Shuaib, Choudhry Guo, and Stephen Jarvis. 2021. Graph hierarchy: a novel framework to analyse hierarchical structures in complex networks. Scientific Reports, Vol. 11, 1 (2021), 13943.
[39]
Canh Hao Nguyen and Hiroshi Mamitsuka. 2021. Learning on Hypergraphs With Sparsity. IEEE Trans. Pattern Anal. Mach. Intell., Vol. 43, 8 (2021), 2710--2722. https://doi.org/10.1109/TPAMI.2020.2974746
[40]
Xavier Ouvrard. 2020. Hypergraphs: an introduction and review. ArXiv, Vol. abs/2002.05014 (2020).
[41]
Alessio Pagani, Guillem Mosquera, Aseel Alturki, Samuel Johnson, Stephen Jarvis, Alan Wilson, Weisi Guo, and Liz Varga. 2019. Resilience or robustness: identifying topological vulnerabilities in rail networks. Royal Society Open Science, Vol. 6, 2 (2019), 181301.
[42]
Marios Papachristou and Jon M. Kleinberg. 2022. Core-periphery Models for Hypergraphs. In The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 1337--1347.
[43]
Ahmet Erdem Sariyüce, C. Seshadhri, Ali Pinar, and Ümit V. cCatalyürek. 2015. Finding the Hierarchy of Dense Subgraphs using Nucleus Decompositions. In Proceedings of the 24th International Conference on World Wide Web. ACM, 927--937.
[44]
Stephen B. Seidman. 1983. Network structure and minimum degree. Social Networks, Vol. 5, 3 (1983), 269--287.
[45]
Bintao Sun, T.-H. Hubert Chan, and Mauro Sozio. 2020. Fully Dynamic Approximate k-Core Decomposition in Hypergraphs. ACM Trans. Knowl. Discov. Data, Vol. 14, 4 (2020), 39:1--39:21.
[46]
Robert E Tarjan and Jan Van Leeuwen. 1984. Worst-case analysis of set union algorithms. J. ACM, Vol. 31, 2 (1984), 245--281.
[47]
Charalampos E. Tsourakakis. 2015. The K-clique Densest Subgraph Problem. In Proceedings of the 24th International Conference on World Wide Web, WWW. ACM, 1122--1132.
[48]
Jia Wang and James Cheng. 2012. Truss Decomposition in Massive Networks. Proc. VLDB Endow., Vol. 5, 9 (2012), 812--823.
[49]
Kai Wang, Xuemin Lin, Lu Qin, Wenjie Zhang, and Ying Zhang. 2022. Towards efficient solutions of bitruss decomposition for large-scale bipartite graphs. VLDB J., Vol. 31, 2 (2022), 203--226.
[50]
Zhengyi Yang, Wenjie Zhang, Xuemin Lin, Ying Zhang, and Shunyang Li. 2023. HGMatch: A Match-by-Hyperedge Approach for Subgraph Matching on Hypergraphs. In 39th IEEE International Conference on Data Engineering, ICDE. IEEE, 2063--2076.
[51]
Wenqian Zhang, Zhengyi Yang, Dong Wen, and Xiaoyang Wang. 2023. Efficient Distributed Core Graph Decomposition. In 2023 IEEE International Conference on Data Mining Workshops (ICDMW). 1023--1031. https://doi.org/10.1109/ICDMW60847.2023.00135
[52]
Ying Zhang, Lu Qin, Fan Zhang, and Wenjie Zhang. 2019. Hierarchical Decomposition of Big Graphs. In 35th IEEE International Conference on Data Engineering. IEEE, 2064--2067.
Index Terms
- Hierarchical Structure Construction on Hypergraphs
Recommendations
Covering Non-uniform Hypergraphs
A subset of the vertices in a hypergraph is a cover if it intersects every edge. Let (H) denote the cardinality of a minimum cover in the hypergraph H, and let us denote by g(n) the maximum of (H) taken over all hypergraphs H with n vertices and with no ...
Odd cycles and Θ-cycles in hypergraphs
A @Q-cycle of a hypergraph is a cycle including an edge that contains at least three base points of the cycle. We show that if a hypergraph H=(V,E) has no @Q-cycle, and |e|>=3, for every edge e@__ __E, then @__ __"e"@__ __"E(|e|-1)=<2|V|-2 with equality ...
Maximally edge-connected hypergraphs
The edge-connectivity of a connected graph or hypergraph is the minimum number of edges whose removal renders the graph or hypergraph, respectively, disconnected. The edge-connectivity of a (hyper) graph cannot exceed its minimum degree. For graphs, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2024
5705 pages
Copyright © 2024 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 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
Conference
CIKM '24
Sponsor:
CIKM '24: The 33rd ACM International Conference on Information and Knowledge Management
October 21 - 25, 2024
ID, Boise, USA
Acceptance Rates
Overall Acceptance Rate 1,861 of 8,427 submissions, 22%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 138Total Downloads
- Downloads (Last 12 months)138
- Downloads (Last 6 weeks)50
Reflects downloads up to 30 Dec 2024
Other Metrics
Citations
Cited By
View all- Wei JYang ZLuo QZhang YQin LZhang W(2024)High-Order Local Clustering on HypergraphsICST Transactions on Scalable Information Systems10.4108/eetsis.743111:6Online publication date: 15-Nov-2024
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in