从不确定图中发现K紧密子图

摘要：

由蛋白质交互网络、社会网络及无线通信网络构成的图中存在许多不确定性.如何高效获取不确定图中有价值的信息,如蛋白质网络中关键的功能集团、社会网络中适于投放广告的团体及通信网络中应重点维护的区域等,具有重要的现实意义.从理论上证明了在不确定图中发现最紧密子图问题具有NP-Hard复杂性；基于树搜索策略提出了通过枚举解空间及剪枝获得最优解的算法TreeClose;针对树搜索算法TreeClose在处理大图时空间复杂度过高的问题,提出了基于贪心思想的2-近似算法GreedyClose.实验结果表明,通过上述算法可以高效快速地在不确定图中发现紧密子图,从而解决在实际应用中遇到的各种问题.

关键词：不确定图、数据挖掘、近似算法、紧密子图

所属期刊栏目：5

分类号：TP311(计算技术、计算机技术)

资助基金：The National Natural Science Foundation of China under Grant No.60831160525,60933001;the Key Program of the National Natural Science Foundation of China under Grant No.61033015;the General Program of the National Natural Science Foundation of China under Grant No.61173023;the Fundamental Research Funds for the Central Universities of China under Grant No.HIT.NSRIF.201180;the Program of Graduate Innovation and Creativity Funds of Heilongjiang Province under Grant No.YJSCX2011-239HLJ;the Scientific and Technological Innovation Project of Heilongjiang University under Grant No.2011386,2011387

在线出版日期：2012-01-14（万方平台首次上网日期，不代表论文的发表时间）

页数：共13页

页码：791-803