摘要
研究不确定图数据的挖掘,主要解决不确定图数据上紧密子图挖掘问题.基于加权不确定图数据模型,使用子图期望密度和顶点期望度数来度量子图的紧密程度.给出贪心迭代中期望峰值的特性,利用期望峰值的特性来改进算法执行过程,其结果满足2近似比的同时使得算法具有较高的执行效率.并且严格证明了算法的正确性.带顶点限制的紧密子图挖掘问题是NP难的,改进后的带顶点限制的紧密子图挖掘算法较其它方法更高效快速.
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.
出处
《小型微型计算机系统》
CSCD
北大核心
2015年第11期2479-2483,共5页
Journal of Chinese Computer Systems
基金
河北省自然科学基金项目(F2012203143)资助
关键词
不确定图
数据挖掘
期望密度
紧密子图
uncertain graph
data mining
expected density
dense subgraph
