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

• 作者: 李建中 邹兆年 韩蒙
• 来源期刊: 计算机科学与探索
• 学科: 工学
• 关键词: 不确定图 数据挖掘 近似算法 紧密子图
• 年，卷（期）: 2011,（9）
• 所属期刊栏目: 学术研究
• 页码范围: 791-803
• 分类号: TP311
• 字数: 8662字
• 语种: 中文
• DOI: 10.3778/j.issn.1673-9418.2011.09.003

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李建中	黑龙江大学计算机科学技术学院	237	6003	33.0	72.0
5	韩蒙	黑龙江大学计算机科学技术学院	2	32	2.0	2.0
6	邹兆年	哈尔滨工业大学计算机科学与技术学院	17	244	9.0	15.0