智能系统学报2024，Vol.19Issue(6)：1539-1551,13.DOI:10.11992/tis.202304058
不确定图上的极大团枚举及高效验证算法
Maximum clique enumeration and verification algorithm on α uncertain graphs
摘要
Abstract
The existing maximal clique enumeration method for uncertain graphs,which uses"subgraph division-enu-meration-verification,"is not efficient for large-scale graphs.As the number of pseudo-maximal cliques increases,the verification speed notably decreases.Therefore,the multi-inversion list enumerates uncertain maximal cliques(MILEUMC)algorithm is proposed to address the aforementioned problem.This algorithm improves efficiency by de-fining and constructing the α uncertain graph before subgraph division and enumeration,which reduces the size of the graph and enhances enumeration efficiency.In the"verification"phase,the algorithm introduces a novel method based on multiple inverted lists.The method involves two stages:the removal of inclusion relations(deduplication)and the re-moval of pseudo-maximum cliques.During each stage,multiple posting lists with different indexes are built,and verific-ation is completed in accordance with the attributes of maximal cliques.Simultaneously,the corresponding inversion lists and mapping tables are dynamically updated,thereby reducing the workload and saving time.Compared to mul-tiple real data sets,experimental results verify the efficiency of the MILEUMC algorithm.Furthermore,the algorithm is more suitable for identifying maximal cliques in sparser graphs,where connections between nodes are closer.关键词
不确定图/极大团/数据挖掘/枚举算法/验证算法/子图划分/倒排表/映射表Key words
uncertain graph/maximal clique/data mining/enumeration algorithm/verification algorithm/subgraph divi-sion/inversion list/mapping table分类
计算机与自动化引用本文复制引用
赵丹枫,吕闫妍,张文博,黄冬梅,高峰..不确定图上的极大团枚举及高效验证算法[J].智能系统学报,2024,19(6):1539-1551,13.基金项目
国家自然科学基金青年项目(42106190,62102243). （42106190,62102243）
