应用子图划分策略的不确定图极大团枚举算法
An Enumeration Algorithm of the Maximal Cluster from the Uncertain Graph Using Subgraph Partition Strategy
摘要: 为了更加高效地枚举出不确定图极大团，通过对现有确定图和不确定图极大团枚举算法进行研究，结合在相同图结构下确定图极大团与不确定图极大团之间的关系，提出了一种基于相同图结构确定图极大团子图划分的高效不确定图极大团枚举算法D-MULE-D。通过在不同的真实数据集上进行实验测试，对比D-MULE-D算法和MULE算法的运行时间，验证D-MULE-D算法的可行性和高效性。
Abstract: In order to more efficiently enumerate maximal clique from the uncertain graph, by studying the existing algorithms of the maximal clique enumeration from the deterministic and uncertain graph, and according to the relationship of the maximal clique from the deterministic graph and the α-maximal clique from the uncertain graph under the same graph structure, an efficient enumeration algorithm of the α-maximal clique from the uncertain graph based on the subgraph partition of the maximal clique from the deterministic graph with the same graph structure, called D-MULE-D, is proposed in this paper. Experimental tests were carried out on different real data sets to verify the feasibility and efficiency of the D-MULE-D algorithm, by comparing the running time of the D-MULE-D algorithm with the MULE algorithm.
文章引用：赵孟. 应用子图划分策略的不确定图极大团枚举算法[J]. 计算机科学与应用, 2020, 10(6): 1150-1157. https://doi.org/10.12677/CSA.2020.106119

参考文献

[1] Mcauley, J. and Leskovec, J. (2014) Discovering Social Circles in Ego Networks. ACM Transactions on Knowledge Discovery from Data, 8, 4-28. [Google Scholar] [CrossRef] 
[2] Satuluri, V., Parthasarathy, S. and Ruan, Y. (2012) Local Graph Sparsification for Scalable Clustering. Proceedings of the 2011 ACM SIGMOD International Con-ference on Management of Data, Athens, June 2012, 721-732. [Google Scholar] [CrossRef] 
[3] Eppstein, D., Loffler, M. and Strash, D. (2013) Listing All Maximal Cliques in Large Sparse Real-World Graphs. ACM Journal of Experimental Algorithmics, 8, 224-227. [Google Scholar] [CrossRef] 
[4] Svendsen, M., Mukherjee, A.P. and Tirthapura, S. (2015) Mining Maximal Cliques from a Large Graph Using Mapreduce: Tackling Highly Uneven Subproblem Sizes. Journal of Parallel and Distributed Computing, 79, 104-114. [Google Scholar] [CrossRef] 
[5] Jin, R., Liu, L. and Aggarwal, C.C. (2011) Discovering Highly Re-liable Subgraphs in Uncertain Graphs. Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, 21-24 August 2011, 992-1000. [Google Scholar] [CrossRef] 
[6] Khan, A., Bonchi, F., Gionis, A. and Gullo, F. (2014) Fast Reliabil-ity Search in Uncertain Graphs. Proceedings of the 16th International Conference on Extending Database Technology, New Orleans, 24-28 March 2014, 535-546.
[7] Koch, I. (2011) Enumerating All Connected Maximal Common Sub-graphs in Two Graphs. Theory Compute Science, 250, 1-30. [Google Scholar] [CrossRef] 
[8] Mukherjee, A.P., Xu, P. and Tirthapura, S. (2015) Mining Maximal Cliques from an Uncertain Graph. 2015 IEEE 31st International Conference on Data Engineering, Seoul, 13-17 April 2015, 243-254. [Google Scholar] [CrossRef] 
[9] Mukherjee, A.P., Xu, P. and Tirthapura, S. (2017) Enumeration of Maximal Cliques from an Uncertain Graph. IEEE Transactions on Knowledge and Data Engineering, 29, 543-555. [Google Scholar] [CrossRef]