An Efficient Algorithm for Mining Dense Subgraph in Uncertain Graphs
Zou Xiao-hon · Journal of Chinese Computer Systems · 2015
This paper studies uncertain graph data mining and especially investigates the problem of mining dense subgraphs from uncertain graph data. Based on the uncertain graph data model with weighted edges,expected density of subgraphs and expected degree of vertexes are employed to measure the dense degree of subgraphs. The characteristics of EDP( expected density peak) is proposed during greedy iterations,which improves the algorithm execution with 2-approximation result and an efficient execution. The algorithm is proved to guarantee the correctness of the final mining result. When the subgraph has a size constraint,the problem of mining dense subgraph becomes NP-hard. Compared with other methods,the improved dense subgraph mining algorithm with size constraint is more efficient.