[1]赵丹枫,吕闫妍,张文博,等.不确定图上的极大团枚举及高效验证算法[J].智能系统学报,2024,19(6):1539-1551.[doi:10.11992/tis.202304058]
ZHAO Danfeng,LYU Yanyan,ZHANG Wenbo,et al.Maximum clique enumeration and verification algorithm on α uncertain graphs[J].CAAI Transactions on Intelligent Systems,2024,19(6):1539-1551.[doi:10.11992/tis.202304058]
点击复制
ZHAO Danfeng,LYU Yanyan,ZHANG Wenbo,et al.Maximum clique enumeration and verification algorithm on α uncertain graphs[J].CAAI Transactions on Intelligent Systems,2024,19(6):1539-1551.[doi:10.11992/tis.202304058]
不确定图上的极大团枚举及高效验证算法
《智能系统学报》[ISSN 1673-4785/CN 23-1538/TP] 卷:
19
期数:
2024年第6期
页码:
1539-1551
栏目:
学术论文—人工智能基础
出版日期:
2024-12-05
- Title:
- Maximum clique enumeration and verification algorithm on α uncertain graphs
- Keywords:
- uncertain graph; maximal clique; data mining; enumeration algorithm; verification algorithm; subgraph division; inversion list; mapping table
- 分类号:
- TP311
- 摘要:
- 现有的不确定图中极大团枚举方法“子图划分—枚举—验证”，在处理大规模图时，整体效率不高；当挖掘出的伪极大团数量较多时，验证速率明显下降。因此，提出高效枚举及验证算法(multiple inversion list enumerate uncertain maximal cliques，MILEUMC)。在子图划分和枚举前，定义并构造概率阈值（α）不确定图，通过缩小图的规模，提高枚举效率；在“验证”时，提出基于多重倒排表的验证方法，分为去重复和去包含关系2个阶段去除伪极大团，以不同索引构建各个阶段的多重倒排表，根据极大团的属性完成验证，同时动态更新相应的倒排表和映射表，以减小工作量，提高时间效率。最后在多个真实的数据集上比较，结果验证了MILEUMC算法的高效性。该算法更适用于在较为稀疏的图上寻找联系更紧密的极大团。
- Abstract:
- The existing maximal clique enumeration method for uncertain graphs, which uses “subgraph division–enumeration–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 defining 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 removal of pseudo-maximum cliques. During each stage, multiple posting lists with different indexes are built, and verification 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 multiple 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.
- 参考文献/References:
-
[1] 徐铭. 不确定图的独立集指标[D]. 北京: 北京交通大学, 2021: 11-12.
XU Ming. Independent set index of uncertain graph[D]. Beijing: Beijing Jiaotong University, 2021: 11-12.
[2] 王恒. 概率图上Top-K极大团枚举问题研究[D]. 上海: 东华大学, 2021: 5-6.
WANG Heng. Research on enumeration problem of Top-K maximal clique on probability graph[D]. Shanghai: Donghua University, 2021: 5-6.
[3] 徐兰天, 李荣华, 戴永恒, 等. 面向超图的极大团搜索算法[J]. 计算机应用, 2023, 43(8): 2319-2324.
XU Lantian, LI Ronghua, DAI Yongheng, et al. Maximal clique searching algorithm for hypergraphs[J]. Journal of computer applications, 2023, 43(8): 2319-2324.
[4] BAI Liang, CHENG Xueqi, LIANG Jiye, et al. Fast graph clustering with a new description model for community detection[J]. Information sciences, 2017, 388/389: 37-47.
[5] KUTER U, GOLBECK J. Using probabilistic confidence models for trust inference in Web-based social networks[J]. ACM transactions on Internet technology, 2010, 10(2): 1-23.
[6] MEHMOOD Y, BONCHI F, GARCíA-SORIANO D. Spheres of influence for more effective viral marketing[C]//Proceedings of the 2016 International Conference on Management of Data. San Francisco: ACM, 2016: 711-726.
[7] ABU-KHZAM F N, BALDWIN N E, LANGSTON M A, et al. On the relative efficiency of maximal clique enumeration algorithms, with applications to high-throughput computational biology[C]//International Conference on Research Trends in Science and Technology. [S. l.]: [s. n.], 2005: 1-10.
[8] KOCH I, LENGAUER T, WANKE E. An algorithm for finding maximal common subtopologies in a set of protein structures[J]. Journal of computational biology: a journal of computational molecular cell biology, 1996, 3(2): 289-306.
[9] SAHA B, HOCH A, KHULLER S, et al. Dense subgraphs with restrictions and applications to gene annotation graphs[C]//BERGER B. Annual International Conference on Research in Computational Molecular Biology. Berlin: Springer, 2010: 456-472.
[10] AGGARWAL C C. Managing and mining uncertain data[M]. [S. l. ]: Springer, 2009.
[11] ADAR E, RE C. Managing uncertainty in social networks[J]. IEEE data engineering bulletin, 2007, 30(2): 15-22.
[12] LIBEN-NOWELL D, KLEINBERG J. The link prediction problem for social networks[C]//Proceedings of the Twelfth International Conference on Information and Knowledge Management. New Orleans: ACM, 2003: 556-559.
[13] BOLDI P, BONCHI F, GIONIS A, et al. Injecting uncertainty in graphs for identity obfuscation[EB/OL]. (2012-08-21) [2021-01-01]. http://arxiv.org/abs/1208.4145.
[14] ZOU Zhaonian, LI Jianzhong, GAO Hong, et al. Mining frequent subgraph patterns from uncertain graph data[J]. IEEE transactions on knowledge and data engineering, 2010, 22(9): 1203-1218.
[15] 桂飞. 面向不确定图的社区发现与搜索算法研究[D]. 合肥: 中国科学技术大学, 2020: 5-6.
GUI Fei. Research on community discovery and search algorithm for uncertain graph[D]. Hefei: University of Science and Technology of China, 2020: 5-6.
[16] 邹兆年, 朱鎔. 大规模不确定图上的Top-K极大团挖掘算法[J]. 计算机学报, 2013, 36(10): 2146-2155.
ZOU Zhaonian, ZHU Rong. Mining Top-K maximal cliques from large uncertain graphs[J]. Chinese journal of computers, 2013, 36(10): 2146-2155.
[17] 朱鎔, 邹兆年, 李建中. 不确定图上的 Top-K 稠密子图挖掘算法[J]. 计算机学报, 2016, 39(8): 1570-1582.
ZHU Rong, ZOU Zhaonian, LI Jianzhong. Mining Top-K dense subgraphs from uncertain graphs[J]. Chinese journal of computers, 2016, 39(8): 1570-1582.
[18] 邹兆年, 李建中, 高宏, 等. 从不确定图中挖掘频繁子图模式[J]. 软件学报, 2009, 20(11): 2965-2976.
ZOU Zhaonian, LI Jianzhong, GAO Hong, et al. Mining frequent subgraph patterns from uncertain graphs[J]. Journal of software, 2009, 20(11): 2965-2976.
[19] MUKHERJEE A P, XU P, TIRTHAPURA S. Mining maximal cliques from an uncertain graph[C]//2015 IEEE 31st International Conference on Data Engineering. Seoul: IEEE, 2015: 243-254.
[20] LI R H, DAI Q, WANG G, et al. Improved algorithms for maximal clique search in uncertain networks[C]//2019 IEEE 35th International Conference on Data Engineering. Macao: IEEE, 2019: 1178-1189.
[21] RASHID A, KAMRAN M, HALIM Z. A top down approach to enumerate α-maximal cliques in uncertain graphs[J]. Journal of intelligent & fuzzy systems, 2019, 36(4): 3129-3141.
[22] 朱成名. 不确定图上极大团枚举算法研究[D]. 秦皇岛: 燕山大学, 2017: 18-42.
ZHU Chengming. Research on maximal clique enumeration algorithm on uncertain graphs[D]. Qinhuangdao: Yanshan University, 2017: 18-42.
[23] 杜明, 钟鹏, 周军锋. 一种面向不确定极大团枚举的高效验证算法[J]. 智能计算机与应用, 2020, 10(3): 14-20.
DU Ming, ZHONG Peng, ZHOU Junfeng. An efficient verification algorithm to the maximal clique enumeration[J]. Intelligent computer and applications, 2020, 10(3): 14-20.
[24] 张艺, 邹晓红. 不确定图中的极大团高效挖掘算法[J]. 燕山大学学报, 2021, 45(6): 529-536.
ZHANG Yi, ZOU Xiaohong. An efficient algorithm for mining maximal cliques in uncertain graphs[J]. Journal of Yanshan University, 2021, 45(6): 529-536.
[25] 张艺. 不确定图中极大团挖掘算法研究[D]. 秦皇岛: 燕山大学, 2022: 5-6.
ZHANG Yi. Research on maximum clique mining algorithm in uncertain graphs[D]. Qinhuangdao: Yanshan University, 2022: 5-6.
备注/Memo
收稿日期:2023-4-28。
基金项目:国家自然科学基金青年项目（42106190，62102243）.
作者简介:赵丹枫，副教授，博士，主要研究方向为图计算与海洋大数据分析，主持国家自然科学基金青年项目，参与国家自然科学基金面上项目、省部级项目等近10项，多次获上海市科学技术奖二等奖、浦东新区科学技术奖一等奖等，发表学术论文20余篇。 E-mail：dfzhao@shou.edu.cn;吕闫妍，硕士研究生，主要研究方向为图数据挖掘。E-mail：504096670@qq.com;高峰，企业导师，博士，主要研究方向为知识图谱、图神经网络、自然语言处理。主导及参与多项行业及团体标准，发表数篇CCF-A类论文，EMNLP2022 审稿专家。E-mail：gaofeng14@midea.com。
通讯作者:高峰. E-mail：gaofeng14@midea.com
更新日期/Last Update:
2024-11-05