TY - GEN
T1 - Efficient Truss Computation for Large Hypergraphs
AU - Wang, Xinzhou
AU - Chen, Yinjia
AU - Zhang, Zhiwei
AU - Qiao, Peng Peng
AU - Wang, Guoren
N1 - Publisher Copyright:
© 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.
PY - 2022
Y1 - 2022
N2 - 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, α, β) -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, α, β) -truss in hypergraphs based on these two types of conversions. Experiments show that our (k, α, β) -truss model is effective and our algorithms are efficient in large hypergraphs.
AB - 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, α, β) -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, α, β) -truss in hypergraphs based on these two types of conversions. Experiments show that our (k, α, β) -truss model is effective and our algorithms are efficient in large hypergraphs.
KW - Cohesive subgraph
KW - Hypergraph
KW - Truss computation
UR - http://www.scopus.com/inward/record.url?scp=85142682599&partnerID=8YFLogxK
U2 - 10.1007/978-3-031-20891-1_21
DO - 10.1007/978-3-031-20891-1_21
M3 - Conference contribution
AN - SCOPUS:85142682599
SN - 9783031208904
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 290
EP - 305
BT - Web Information Systems Engineering – WISE 2022 - 23rd International Conference, Proceedings
A2 - Chbeir, Richard
A2 - Huang, Helen
A2 - Silvestri, Fabrizio
A2 - Manolopoulos, Yannis
A2 - Zhang, Yanchun
A2 - Zhang, Yanchun
PB - Springer Science and Business Media Deutschland GmbH
T2 - 23rd International Conference on Web Information Systems Engineering, WISE 2021
Y2 - 1 November 2022 through 3 November 2022
ER -