Abstract
Cohesive subgraph mining has been applied in many areas, including social networks, cooperation networks, and biological networks. The k-truss of a graph is the maximal subgraph in which each edge is contained in at least k triangles. Existing k-truss models are defined solely in pairwise graphs and are hence unsuitable for hypergraphs. In this paper, we propose a novel problem, named \((k,\alpha ,\beta )\)-truss computation in hypergraphs. We then propose two hypergraph conversions. The first converts a hypergraph into a pairwise graph, while the second converts it into a projected graph. We further propose two algorithms for computing \((k,\alpha ,\beta )\)-truss in hypergraphs based on these two types of conversions. Experiments show that our \((k,\alpha ,\beta )\)-truss model is effective and our algorithms are efficient in large hypergraphs.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
All datasets are obtained from https://www.cs.cornell.edu/~arb/data/.
- 2.
References
Batagelj, V., Zaversnik, M.: An o(m) algorithm for cores decomposition of networks. Comput. Sci. 1(6), 34–37 (2003)
Chang, L., Yu, J.X., Qin, L., Lin, X., Liu, C., Liang, W.: Efficiently computing k-edge connected components via graph decomposition. In: SIGMOD, pp. 205–216. ACM (2013)
Cohen, J.: Trusses: cohesive subgraphs for social network analysis. national security agency technical report (2008)
Fang, Y., Yang, Y., Zhang, W., Lin, X., Cao, X.: Effective and efficient community search over large heterogeneous information networks. Proc. VLDB Endow. 13(6), 854–867 (2020)
Hu, A.L., Chan, K.C.: Utilizing both topological and attribute information for protein complex identification in PPI networks. IEEE/ACM Trans. Comput. Biol. Bioinf. 10(3), 780–792 (2013)
Hu, S., Wu, X., Chan, T.H.: Maintaining densest subsets efficiently in evolving hypergraphs. In: CIKM, pp. 929–938. ACM (2017)
Huang, X., Cheng, H., Qin, L., Tian, W., Yu, J.X.: Querying k-truss community in large and dynamic graphs. In: SIGMOD, pp. 1311–1322. ACM (2014)
Lee, G., Choe, M., Shin, K.: How do hyperedges overlap in real-world hypergraphs? - patterns, measures, and generators. In: WWW, pp. 3396–3407 (2021)
Lee, G., Ko, J., Shin, K.: Hypergraph motifs: concepts, algorithms, and discoveries. Proc. VLDB Endow. 13(11), 2256–2269 (2020)
Leng, M., Sun, L.Y., Bian, J.N., Yu-Chun, M.A.: An o(m) algorithm for cores decomposition of undirected hypergraph. J. Chin. Comput. Syst. 34, 2568–2573 (2013)
Liu, H., Latecki, L.J., Yan, S.: Dense subgraph partition of positive hypergraphs. IEEE Trans. Pattern Anal. Mach. Intell. 37(3), 541–554 (2015)
Liu, Q., Zhao, M., Huang, X., Xu, J., Gao, Y.: Truss-based community search over large directed graphs. In: SIGMOD, pp. 2183–2197. ACM (2020)
Luo, Q., Yu, D., Cai, Z., Lin, X., Cheng, X.: Hypercore maintenance in dynamic hypergraphs. In: ICDE, pp. 2051–2056 (2021)
Palla, G., Deranyi, I., Farkas, I., Vicsek, T.: Uncovering the overlapping community structure of complex networks in nature and society. Nature 435(7043), 814 (2005)
Pu, L., Faltings, B.: Hypergraph learning with hyperedge expansion. In: Flach, P.A., De Bie, T., Cristianini, N. (eds.) ECML PKDD 2012. LNCS (LNAI), vol. 7523, pp. 410–425. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33460-3_32
Seidman, S.B.: Network structure and minimum degree. Soc. Netw. 5(3), 269–287 (1983)
Sozio, M., Gionis, A.: The community-search problem and how to plan a successful cocktail party. In: SIGKDD, pp. 939–948 (2010)
Sun, B., Chan, T.H., Sozio, M.: Fully dynamic approximate k-core decomposition in hypergraphs. ACM Trans. Knowl. Discov. Data 14(4), 39:1–39:21 (2020)
Wang, J., Cheng, J.: Truss decomposition in massive networks. Proc. VLDB Endow. 5(9), 812–823 (2012)
Wang, K., Zhang, W., Lin, X., Zhang, Y., Qin, L., Zhang, Y.: Efficient and effective community search on large-scale bipartite graphs. In: ICDE, pp. 85–96 (2021)
Yang, Y., Fang, Y., Lin, X., Zhang, W.: Effective and efficient truss computation over large heterogeneous information networks. In: ICDE, pp. 901–912. IEEE (2020)
Yoon, S., Song, H., Shin, K., Yi, Y.: How much and when do we need higher-order informationin hypergraphs? A case study on hyperedge prediction. In: WWW, pp. 2627–2633 (2020)
Zou, Z.: Bitruss decomposition of bipartite graphs. In: Navathe, S.B., Wu, W., Shekhar, S., Du, X., Wang, X.S., Xiong, H. (eds.) DASFAA 2016. LNCS, vol. 9643, pp. 218–233. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-32049-6_14
Acknowledgements
The work was supported by National Key Research and Development Program of China (Grant No. 2020YFB1707900, No. 2021YFB2700700), National Natural Science Foundation of China Grant No. 62072035, Open Research Projects of Zhejiang Lab (Grant No. 2020KE0AB04), CCF-Huawei Database System Innovation Research Plan Grant No. CCF-HuaweiDBIR2021007B.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Wang, X., Chen, Y., Zhang, Z., Qiao, P., Wang, G. (2022). Efficient Truss Computation for Large Hypergraphs. In: Chbeir, R., Huang, H., Silvestri, F., Manolopoulos, Y., Zhang, Y. (eds) Web Information Systems Engineering – WISE 2022. WISE 2022. Lecture Notes in Computer Science, vol 13724. Springer, Cham. https://doi.org/10.1007/978-3-031-20891-1_21
Download citation
DOI: https://doi.org/10.1007/978-3-031-20891-1_21
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-20890-4
Online ISBN: 978-3-031-20891-1
eBook Packages: Computer ScienceComputer Science (R0)