|
|||||
|
|
| 从不确定图中发现K紧密子图 | |
| 引用本文： | 韩蒙,李建中,邹兆年.从不确定图中发现K紧密子图[J].计算机科学与探索,2011,5(9):791-803. |
| 作者姓名： | 韩蒙 李建中 邹兆年 |
| 作者单位： | 1. 黑龙江大学计算机科学技术学院,哈尔滨,150080 2. 黑龙江大学计算机科学技术学院,哈尔滨150080;哈尔滨工业大学计算机科学与技术学院,哈尔滨150001 3. 哈尔滨工业大学计算机科学与技术学院,哈尔滨,150001 |
| 基金项目： | 国家自然科学基金No.60831160525,60933001,国家自然科学基金重点项目No.61033015,国家自然科学基金面上项目No.61173023; 中央高校基本科研业务费专项资金No.HIT.NSRIF.201180; 黑龙江省研究生创新科研基金项目No.YJSCX2011-239HLJ; 黑龙江大学学生学术科技创新项目No.2011386,2011387~~ |
| 摘 要： | 由蛋白质交互网络、社会网络及无线通信网络构成的图中存在许多不确定性。如何高效获取不确定图中有价值的信息,如蛋白质网络中关键的功能集团、社会网络中适于投放广告的团体及通信网络中应重点维护的区域等,具有重要的现实意义。从理论上证明了在不确定图中发现最紧密子图问题具有NP-Hard复杂性;基于树搜索策略提出了通过枚举解空间及剪枝获得最优解的算法TreeClose;针对树搜索算法TreeClose在处理大图时空间复杂度过高的问题,提出了基于贪心思想的2-近似算法GreedyClose。实验结果表明,通过上述算法可以高效快速地在不确定图中发现紧密子图,从而解决在实际应用中遇到的各种问题。 |
| 关 键 词： | 不确定图 数据挖掘 近似算法 紧密子图 |
| 修稿时间： | |
Finding K Close Subgraphs in an Uncertain Graph |
|
| HAN Meng,LI Jianzhong,ZOU Zhaonian.Finding K Close Subgraphs in an Uncertain Graph[J].Journal of Frontier of Computer Science and Technology,2011,5(9):791-803. | |
| Authors: | HAN Meng LI Jianzhong ZOU Zhaonian |
| Affiliation: | 1. School of Computer Science and Technology, Heilongjiang University, Harbin 150080, China 2. School of Computer Science and Technology, Harbin Institute of Technology, Harbin 150001, China |
| Abstract: | Uncertainty is inherent in many of graphs which are abstracted from protein-protein interaction (PPI) networks, social networks or wireless communication networks. How to get the valuable information, such as the crucial function group in PPI networks, the group which makes advertisers more properly, and the nodes which guarantee to communicate with their neighboring nodes well, plays an important role in practical settings. This paper shows that the problem to find the closest subgraph is NP-Hard, and proposes an efficient search-tree based algorithm with pruning techniques TreeClose. Because search-tree based algorithm TreeClose needs too large space when processing larger graphs, the paper also proposes an efficient greedy approximate algorithm GreedyClose. Moreover, the experimental results verify that the proposed algorithms are efficient in practice. |
| Keywords: | uncertain graph data mining approximation algorithm close subgraph |
| 本文献已被 CNKI 万方数据 等数据库收录！ | |
| 点击此处可从《计算机科学与探索》浏览原始摘要信息 | |
| 点击此处可从《计算机科学与探索》下载全文 | |
