面向超图的极大团搜索算法

doi:10.11772/j.issn.1001-9081.2022091334

《计算机应用》唯一官方网站 ›› 2023, Vol. 43 ›› Issue (8): 2319-2324.DOI: 10.11772/j.issn.1001-9081.2022091334

• 第十九届CCF中国信息系统及应用大会 •

面向超图的极大团搜索算法

徐兰天¹, 李荣华¹, 戴永恒², 王国仁¹

^1.北京理工大学计算机学院，北京 100081
^2.电科云（北京）科技有限公司，北京 100041

收稿日期:2022-09-06 修回日期:2022-09-23 接受日期:2022-10-08 发布日期:2022-11-02 出版日期:2023-08-10
通讯作者: 李荣华
作者简介:徐兰天（1997—），男，河北唐山人，硕士研究生，主要研究方向：图数据挖掘
戴永恒（1983—），男，北京人，工程师，博士，主要研究方向：领域建模、专家知识结构化、融合的机器学习
王国仁（1966—），男，北京人，教授，博士，CCF会员，主要研究方向：数据挖掘。
基金资助:
国家自然科学基金资助项目(62072034);国家重点研发计划课题(2021YFB3301301)

Maximal clique searching algorithm for hypergraphs

Lantian XU¹, Ronghua LI¹, Yongheng DAI², Guoren WANG¹

^1.School of Computer Science and Technology，Beijing Institute of Technology，Beijing 100081，China
^2.Diankeyun （Beijing） Technology Company Limited，Beijing 100041，China

Received:2022-09-06 Revised:2022-09-23 Accepted:2022-10-08 Online:2022-11-02 Published:2023-08-10
Contact: Ronghua LI
About author:XU Lantian， born in 1997， M. S. candidate. His research interests include graph data mining.
DAI Yongheng， born in 1983， Ph. D.， engineer. His research interests include domain modeling， expert knowledge structuring， integrated machine learning.
WANG Guoren， born in 1966， Ph. D.， professor. His research interests include data mining.
Supported by:
National Natural Science Foundation of China(62072034);National Key Research and Development Program of China(2021YFB3301301)

摘要/Abstract

摘要：

现实世界中的实体关系大多不能用简单的二元关系来表示，而超图能很好地表示实体间的多元关系。因此，提出超图团和极大团的定义，并给出了搜索超图极大团的精确算法和近似算法。首先，分析了现有的普通图上的极大团搜索算法无法直接应用到超图上的原因。然后，基于超图的特性和极大团的定义，提出了一种新颖的保存超点间邻接关系的数据结构，并提出了一种超图上的精确极大团搜索算法。由于精确算法的速度较慢，因此结合支撑点（pivot）的剪枝思想，削减递归层数，提出了一种超图上的近似极大团搜索算法。在多个真实超图数据集上的实验结果显示，所提近似算法在找到大多数极大团的前提下，提高了搜索速度，当在3-uniform超图上，测试超图团的点数为22时，加速比达到了1 000以上。

关键词: 超图, 极大团, 集合枚举, 近似算法, 支撑点

Abstract:

Most of entity relationships in the real world cannot be represented by simple binary relations， and hypergraph can represent the n-ary relations among entities well. Therefore， definitions of hypergraph clique and maximal clique were proposed， and the exact algorithm and approximation algorithm for searching hypergraph maximal clique were given. First， the reason why the existing maximal clique searching algorithms on ordinary graphs cannot be applied to hypergraphs directly was analyzed. Then， based on the characteristics of hypergraph and the definition of maximal clique， a novel data structure for preserving the adjacency relations among hyperpoints was proposed， and an accurate maximal clique searching algorithm on hypergraph was proposed. As the running of the exact algorithm is slow， the pruning idea of pivots was combined with， the number of recursive layers was reduced， and an approximation maximal clique searching algorithm on hypergraph was proposed. Experimental results on multiple real hypergraph datasets show that under the premise finding most maximal cliques， the proposed approximation algorithm improves the search speed. When the number of test hypergraph cliques on 3-uniform hypergraph is 22， the acceleration ratio reaches over 1 000.

Key words: hypergraph, maximal clique, set enumeration, approximation algorithm, pivot

中图分类号:

TP311.1

徐兰天, 李荣华, 戴永恒, 王国仁. 面向超图的极大团搜索算法[J]. 计算机应用, 2023, 43(8): 2319-2324.

Lantian XU, Ronghua LI, Yongheng DAI, Guoren WANG. Maximal clique searching algorithm for hypergraphs[J]. Journal of Computer Applications, 2023, 43(8): 2319-2324.

图/表 8

图1 4-超团

Fig. 1 Four-hclique

图2 超点组的邻接关系

Fig. 2 Adjacency relationships in hgroup

图3 BKH算法的R，P，X集合

Fig. 3 R，P，X sets of BKH algorithm

图4 d大小超边r化

Fig. 4 d-edge to r-edges

表1 超图极大团搜索算法的运行时间比较

Tab. 1 Comparison of running time of hypergraph maximal clique searching algorithms

K	r	edge	搜索K，r超图团的时间/s		加速比
K	r	edge	BKH	BKHpivot	加速比
12	3	220	0.07	0.01	7.00
12	4	495	0.14	0.07	2.00
14	3	364	0.26	0.03	8.67
14	4	1 001	0.49	0.21	2.33
16	3	560	1.03	0.05	20.60
16	4	1 820	2.88	0.31	9.29
18	3	816	5.11	0.04	127.75
18	4	3 060	14.49	1.07	13.54
20	3	1 140	25.73	0.04	643.25
20	4	4 845	87.75	1.75	50.14
22	3	1 540	123.08	0.09	1 367.56
22	4	7 315	438.73	6.79	64.61

表2 数据集基本信息

Tab. 2 Basic information about dataset

数据集	$\| E \| = m$	$\| V \| = n$
contact-primary-school	106 879	242
contact-high-school	172 035	327
email-Eu	234 760	1 005

表2 数据集基本信息

Tab. 2 Basic information about dataset

数据集	$\| E \| = m$	$\| V \| = n$
contact-primary-school	106 879	242
contact-high-school	172 035	327
email-Eu	234 760	1 005

表3 超图极大团的搜索结果比较

Tab. 3 Comparison of search results of hypergraph maximal clique

r	数据集	edge	BKH			BKHpivot
r	数据集	edge	num	time/s	memory/KB	num	time/s	memory/KB
3	contact-primary-school	5 139	3 469	0.040	4 804	3 085	0.030	4 808
	contact-high-school	2 370	1 633	0.025	4 500	1 483	0.020	4 352
	email-Eu	160 605	6 330	42 905.000	13 248	3 806	1.488	13 304
4	contact-primary-school	381	345	0.008	4 072	340	0.008	4 028
	contact-high-school	238	210	0.006	3 788	205	0.007	4 072
	email-Eu	714 535	2 750	226 458.000	61 576	2 392	16.899	61 484

图5 两种算法的超图极大团数

Fig. 5 Number of hypergraph maximal cliques for two algorithms

参考文献 16

1	HAO F， LI S， MIN G Y， et al. An efficient approach to generating location-sensitive recommendations in ad-hoc social network environments［J］. IEEE Transactions on Services Computing， 2015， 8（3）： 520-533. 10.1109/tsc.2015.2401833
2	SHANG H L， TAO Y D， GAO Y， et al. An improved invariant for matching molecular graphs based on VF2 algorithm［J］. IEEE Transactions on Systems， Man， and Cybernetics： Systems， 2015， 45（1）： 122-128. 10.1109/tsmc.2014.2327058
3	LIU J Z， LEE Y T. Graph-based method for face identification from a single 2D line drawing［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence， 2001， 23（10）： 1106-1119. 10.1109/34.954601
4	LI R H， GAO S， QIN L， et al. Ordering heuristics for k-clique listing［J］. Proceedings of the VLDB Endowment， 2020， 13（12）： 2536-2548. 10.14778/3407790.3407843
5	BRON C， KERBOSCH J. Algorithm 457： finding all cliques of an undirected graph［J］. Communications of the ACM， 1973， 16（9）： 575-577. 10.1145/362342.362367
6	TOMITA E， TANAKA A， TAKAHASHI H. The worst-case time complexity for generating all maximal cliques and computational experiments［J］. Theoretical Computer Science， 2006， 363（1）： 28-42. 10.1016/j.tcs.2006.06.015
7	MITZENMACHER M， PACHOCKI J， PENG R， et al. Scalable large near-clique detection in large-scale networks via sampling［C］// Proceedings of the 21st ACM Special Interest Group on Knowledge Discovery and Data Mining. New York： ACM， 2015： 815-824. 10.1145/2783258.2783385
8	WU Q H， HAO J K， GLOVER F. Multi-neighborhood tabu search for the maximum weight clique problem［J］. Annals of Operations Research， 2012， 196（1）： 611-634. 10.1007/s10479-012-1124-3
9	CHIBA N， NISHIZEKI T. Arboricity and subgraph listing algorithms［J］. SIAM Journal on Computing， 1985， 14（1）： 210-223. 10.1137/0214017
10	MAKINO K， UNO T. New algorithms for enumerating all maximal cliques［C］// Proceedings of the 2004 Scandinavian Workshop on Algorithm Theory， LNCS 3111. Berlin： Springer， 2004： 260-272.
11	ÖSTERGÅRD P R J. A fast algorithm for the maximum clique problem［J］. Discrete Applied Mathematics， 2002， 120（1/2/3）： 197-207. 10.1016/s0166-218x(01)00290-6
12	DANISCH M， BALALAU O， SOZIO M. Listing k-cliques in sparse real-world graphs［C］// Proceedings of the 2018 World Wide Web Conference. Republic and Canton of Geneva： International World Wide Web Conferences Steering Committee， 2018： 589-598. 10.1145/3178876.3186125
13	JAIN S， SESHADHRI C. A fast and provable method for estimating clique counts using Turán’s theorem［C］// Proceedings of the 26th International Conference on World Wide Web. Republic and Canton of Geneva： International World Wide Web Conferences Steering Committee， 2017： 441-449. 10.1145/3038912.3052636
14	EDEN T， RON D， SESHADHRI C. On approximating the number of k-cliques in sublinear time［J］. SIAM Journal on Computing， 2020， 49（4）： 747-771. 10.1137/18m1176701
15	LIU E L L， WANG J. The maximum number of cliques in hypergraphs without large matchings［J］. The Electronic Journal of Combinatorics， 2020， 27（4）： No.P4.14. 10.37236/9604
16	BENSON A R， ABEBE R， SCHAUB M T， et al. Simplicial closure and higher-order link prediction［J］. Proceedings of the National Academy of Sciences of the United States of America， 2018， 115（48）： E11221-E11230. 10.1073/pnas.1800683115

[1]	李晓杰, 崔超然, 宋广乐, 苏雅茜, 吴天泽, 张春云. 基于时序超图卷积神经网络的股票趋势预测方法[J]. 《计算机应用》唯一官方网站, 2022, 42(3): 797-803.
[2]	田玲, 张谨川, 张晋豪, 周望涛, 周雪. 知识图谱综述——表示、构建、推理与知识超图理论[J]. 《计算机应用》唯一官方网站, 2021, 41(8): 2161-2186.
[3]	张永凯, 武志昊, 林友芳, 赵苡积. 面向交通流量预测的时空超关系图卷积网络[J]. 《计算机应用》唯一官方网站, 2021, 41(12): 3578-3584.
[4]	周阳, 吴启武, 姜灵芝. 基于分布式路径计算单元的多域光网络组密钥管理方案[J]. 计算机应用, 2019, 39(4): 1095-1099.
[5]	余江兰, 李向利, 赵朋飞. 基于核技巧和超图正则的稀疏非负矩阵分解[J]. 计算机应用, 2019, 39(3): 742-749.
[6]	刘胜久, 李天瑞, 杨宗霖, 珠杰. 带权超网络的度量方法及其性质[J]. 计算机应用, 2019, 39(11): 3107-3113.
[7]	尹远, 张昌, 文凯, 郑云俊. 基于DiffNodeset结构的最大频繁项集挖掘算法[J]. 计算机应用, 2018, 38(12): 3438-3443.
[8]	唐海波, 林煜明, 李优, 蔡国永. 基于模拟退火与贪心策略的平衡聚类算法[J]. 计算机应用, 2018, 38(11): 3132-3138.
[9]	徐乾, 陈鸿昶, 吴铮, 黄瑞阳. 基于带权超图的跨网络用户身份识别方法[J]. 计算机应用, 2017, 37(12): 3435-3441.
[10]	李春英, 汤庸, 汤志康, 黄泳航, 袁成哲, 赵剑冬. 面向大规模学术社交网络的社区发现模型[J]. 计算机应用, 2015, 35(9): 2565-2568.
[11]	高文宇, 李华. 团图点删除问题的近似算法[J]. 计算机应用, 2015, 35(8): 2137-2139.
[12]	刘彩苹蔡玉武毛建旭蔡玉文. 无线传感器网络不重复记录求和近似算法[J]. 计算机应用, 2014, 34(2): 313-317.
[13]	任梅詹永照潘道远孙佳瑶. 基于概率超图的视频事件语义检测[J]. 计算机应用, 2012, 32(11): 3014-3017.
[14]	杨慧孟凡星. 改进的SAX符号化算法在QAR数据中的应用[J]. 计算机应用, 2012, 32(05): 1484-1487.
[15]	高文宇张力. 贝叶斯网最优消元顺序的近似构造算法[J]. 计算机应用, 2011, 31(08): 2072-2074.

面向超图的极大团搜索算法

Maximal clique searching algorithm for hypergraphs

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

图/表 8

参考文献 16

相关文章 15

编辑推荐

Metrics