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.

Key words: uncertain graph, data mining, approximation algorithm, close subgraph

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

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