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

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