海量不确定图挖掘算法研究

随着现代化数据采集技术的飞速发展，社会各领域中积累了大量用图表示的数据，简称图数据。在图数据的规模不断激增的同时，由于数据采集技术自身固有的随机错误与误差、不及时的数据更新以及数据隐私保护等原因，大量图数据存在不确定性。很多应用领域（如生物信息学、无线传感网、智能交通系统等）迫切需要开展海量不确定图挖掘，即从海量不确定图中自动发现有用的知识。这方面的研究才刚刚起步，研究结果还很少，机遇与挑战并存。本项目研究不确定图的语义模型、海量不确定图的基本操作、海量不确定图挖掘等方面的关键科学技术问题，以语义模型能够有效支持不确定图计算（包括挖掘）、算法的时间复杂性最小化为目标，提出计算有效的新型不确定图语义模型、海量不确定图上基本操作的高效实现算法以及具有代表性的海量不确定图挖掘算法。本项目还将研制一个通用的海量不确定图挖掘原型系统，验证基础研究结果的正确性、有效性和可行性。

近年来，社会各领域积累了大量图数据(graph data)。由于数据采集技术的错误和误差、数据集成、不及时的数据更新、数据隐私保护等原因，大量图数据(如生物网络、知识图谱等)存在不确定性，形成了不确定图数据(uncertain graph data)。从不确定图数据中挖掘有用知识的过程称作不确定图挖掘(uncertain graph mining)，在生物信息学、语义网等领域具有广泛应用。..本项目以海量不确定图数据为研究对象，深入研究了不确定图数据的语义模型、基本操作算法和具有代表性的数据挖掘算法，并研制了不确定图挖掘原型系统。本项目完成了研究计划，取得了一系列理论研究结果。..1. 在不确定图数据的语义模型方面，本项目提出了不确定图的期望语义模型和概率语义模型，以及不依赖于边独立性假设的不确定图可能世界语义模型，并在这些语义模型的基础上开展了研究。..2. 在不确定图数据的基本操作及其实现算法研究方面，本项目提出了不确定图的期望最短路径距离计算操作、k-可达查询操作、概率可达查询操作、不确定图顶点相似性计算操作、不确定图概要操作、不确定图代表可能世界选择操作等一系列基本操作，并设计了这些基本操作的实现算法。..3. 在不确定图数据的挖掘算法研究方面，本项目提出了不确定图随机游走的理论和算法、不确定图上top-k可靠搜索算法、不确定图的频繁子图模式挖掘算法、不确定图的稠密子图挖掘算法、不确定图上近邻模式搜索算法等一些列具有代表性的不确定图挖掘算法。其中代表性研究成果如下：..a. 提出了不确定图随机游走的理论和算法，严格定义了不确定图上随机游走、转移概率等概念，并提出了不确定图随机游走转移概率的高效计算算法。..b. 在国际上首先提出了不确定图“同时计算”新技术，通过同时执行不同可能世界上可共享的计算步骤来减少冗余计算。..本项目出版了国际上首部系统阐述不确定图数据挖掘理论与算法的专著《不确定图数据挖掘》。本项目发表学术论文19篇，其中CCF A类国际期刊1篇，CCF A类国际会议1篇，CCF B类国际期刊1篇，CCF B类国际会议4篇。本项目应邀在国内外学术会议上做特邀报告3次。本项目负责人获得2012年中国计算机学会优秀博士学位论文奖、2013年全国优秀博士学位论文提名奖。