[1]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]
Copy

Maximum clique enumeration and verification algorithm on α uncertain graphs

CAAI Transactions on Intelligent Systems[ISSN 1673-4785/CN 23-1538/TP] Volume: 19 Number of periods: 2024 6 Page number: 1539-1551 Column: 学术论文—人工智能基础 Public date: 2024-12-05
Title:
Maximum clique enumeration and verification algorithm on α uncertain graphs
Author(s):
ZHAO Danfeng1;  LYU Yanyan1;  ZHANG Wenbo1;  HUANG Dongmei2;  GAO Feng3
1. College of Information, Shanghai Ocean University, Shanghai 201306, China;
2. College of Electronics and Information Engineering, Shanghai University of Electric Power, Shanghai 200090, China;
3. Guangdong Midea Refrigeration Co. LTD., Foshan 528
Keywords:
uncertain graph; maximal clique; data mining; enumeration algorithm; verification algorithm; subgraph division; inversion list; mapping table
CLC:
TP311
DOI:
10.11992/tis.202304058
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.
Similar References:

Memo

-

Last Update: 2024-11-05

Copyright © CAAI Transactions on Intelligent Systems