【摘要】 现实生活中的网络,如生物蛋白网络、无线传感器网络等都存在着很多不确定性,如何准确、快速地发现其中有效的信息具有特别重要的意义.由于发现前K个最紧密子图具有较高的复杂性并且实现条件较高,本文根据实际背景研究了从不确定图中发现存在概率较高的前K个紧密子图问题,分析不确定图的连通性和紧密子图存在概率,提出了不确定相对K紧密子图发现算法.在算法中,首先计算不确定图的连通指数,确定不确定阈值,根据不确定阈值计算子图存在概率,最终得到K个相对紧密子图.最后,通过若干组实验,验证了此算法可以高效、准确地发现不确定图中的紧密子图,能够解决生活中出现的各种问题.更多还原

【Abstract】 Uncertainty is universal in real life application,such as biological protein networks,wireless sensor networks,etc.How to find information efficiently and accurately has special significance.It is difficult to find maximal cliques and the complexity is high,this paper tries to find top- A:close subgraphs with higher probability from uncertain graphs.We analyze connectivity and existence probability of close subgraphs,and put forward K relatively close subgraph discovery algorithm in uncertain graph.In the algorithm,we first calculate the connectivity index of uncertain graph,determine uncertain threshold,calculate probability of subgraphs according to uncertain threshold.Then we can get K relatively close subgraphs.Finally,by experiments we verify the algorithm that can discover uncertain close subgraphs efficiently and accurately.Meanwhile,it can solve various problems encountered in real life such as protein interaction networks.更多还原