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