应用子图划分策略的不确定图极大团枚举算法

摘要

为了更加高效地枚举出不确定图极大团，通过对现有确定图和不确定图极大团枚举算法进行研究，结合在相同图结构下确定图极大团与不确定图极大团之间的关系，提出了一种基于相同图结构确定图极大团子图划分的高效不确定图极大团枚举算法D-MULE-D。通过在不同的真实数据集上进行实验测试，对比D-MULE-D算法和MULE算法的运行时间，验证D-MULE-D算法的可行性和高效性。 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.