中文摘要：

针对复杂网络中节点和边及其属性值均可能存在不确定性的实际,以及采用传统的紧密子图挖掘算法挖掘出的紧密子图实际上并不一定紧密的问题,在已提出的概率属性图基础上,提出紧密概率属性子图的概念,将其分为紧密概率I型属性子图和紧密概率II型属性子图,并用期望紧密度对其进行度量,同时给出了相应的紧密子图判定定理;进一步提出K-紧密概率属性子图高效挖掘算法,以快速发现复杂网络中联系紧密且顶点和边的存在概率最高的K个子图;最后通过蛋白质网络和虚拟网络中的数据对算法进行了模拟实验,验证了算法在不同大小的复杂网络中具有较好的适应性及较高的挖掘效率.

英文摘要：

In complicated networks,the uncertainty of edge, vertex and its attributesexist, and the dense sub-graph mining by the traditional algorithm may be not dense. So the dense probability attribute sub-graph was put forward based on probability attribute graph. Firstly, the dense probability I attribute sub-graph and the dense pro-bability II attribute sub-graph are defined, simultaneously, the expectation tightness function and the corresponding theorems of dense sub-graph were given respectively. Then the efficient mining algorithm of K-densely sub-graph was designed, in order to find K-dense sub-graphs with the highest probability of vertex and edge in complicated networks. Finally, simulation experiment of protein network and virtual network shows that the algorithm has higher mining efficiency and better adaptability in different sizes of complicated networks.