Maximum Independent Set Algorithm for Hypergraph Data

被引：0

作者：

Xu L.-T. ^{[1
]}

Li R.-H. ^{[1
]}

Dai Y.-H. ^{[2
]}

Wang G.-R. ^{[1
]}

机构：

[1] School of Computer Science and Technology, Beijing Institute of Technology, Beijing

[2] Diankeyun Technologies Co. Ltd., Beijing

来源：

Ruan Jian Xue Bao/Journal of Software | 2024年 / 35卷 / 06期

关键词：

heuristic algorithm; hypergraph; maximum independent set;

D O I：

10.13328/j.cnki.jos.006926

中图分类号：

学科分类号：

摘要：

Hypergraphs are generalized representations of ordinary graphs, which are common in many application areas, including the Internet, bioinformatics, and social networks. The independent set problem is a fundamental research problem in the field of graph analysis. Most of the traditional independent set algorithms are targeted for ordinary graph data, and how to achieve efficient maximum independent set mining on hypergraph data is an urgent problem to be solved. To address this problem, this study proposes a definition of hypergraph independent sets. Firstly, two properties of hypergraph independent set search are analyzed, and then a basic algorithm based on the greedy strategy is proposed. Then a pruning framework for hypergraph approximate maximum independent set search is proposed, i.e., a combination of exact pruning and approximate pruning, which reduces the size of the graph by the exact pruning strategy and speeds up the search by the approximate pruning strategy. In addition, four efficient pruning strategies are proposed in this study, and a theoretical proof of each pruning strategy is presented. Finally, experiments are conducted on 10 real hypergraph data sets, and the results show that the pruning algorithm can efficiently search for hypergraph maximum independent sets that are closer to the real results. © 2024 Chinese Academy of Sciences. All rights reserved.

引用

页码：2999 / 3012

页数：13

共 38 条

[1]

Berman P, Furer M., Approximating maximum independent set in bounded degree graphs, Proc. of the 5th Annual ACM-SIAM Symp. on Discrete Algorithms, pp. 365-371, (1994)

[2]

Fu AWC, Wu HH, Cheng J, Wong RCW., IS-Label: An independent-set based labeling scheme for point-to-point distance querying, Proc. of the VLDB Endowment, 6, 6, pp. 457-468, (2013)

[3]

Halldorsson MM, Radhakrishnan J., Greed is good: Approximating independent sets in sparse and bounded-degree graphs, Algorithmica, 18, 1, pp. 145-163, (1997)

[4]

Robson JM., Algorithms for maximum independent sets, Journal of Algorithms, 7, 3, pp. 425-440, (1986)

[5]

Puthal D, Nepal S, Paris C, Ranjan R, Chen JJ., Efficient algorithms for social network coverage and reach, Proc. of the 2015 IEEE Int’l Congress on Big Data, pp. 467-474, (2015)

[6]

Basagni S., Finding a maximal weighted independent set in wireless networks, Telecommunication Systems, 18, 1–3, pp. 155-168, (2001)

[7]

Lee G, Ko J, Shin K., Hypergraph motifs: Concepts, algorithms, and discoveries, Proc. of the VLDB Endowment, 13, 12, pp. 2256-2269, (2020)

[8]

Yoon SE, Song H, Shin K, Yi Y., How much and when do we need higher-order information in hypergraphs? A case study on hyperedge prediction, Proc. of the 2020 Web Conf, pp. 2627-2633, (2020)

[9]

Kook Y, Ko J, Shin K., Evolution of real-world hypergraphs: Patterns and models without oracles, Proc. of the 2020 IEEE Int’l Conf. on Data Mining (ICDM), pp. 272-281, (2020)

[10]

Benson AR, Abebe R, Schaub MT, Jadbabaie A, Kleinberg J., Simplicial closure and higher-order link prediction, Proc.of the National Academy of Sciences of the United States of America, 115, 48, pp. E11221-E11230, (2018)

← 1 2 3 4 →