Research On Mining Dense Subgraphs In Uncertain Graphs

With the rapid development of the Internet and information technology,the data generated by various industries has also increased.These data can often generate huge value.How to tap the core data hidden behind become the core issue of the information technology.As a classic data structure,graph are widely used in social networks,text retrieval,bioinformatics,and other fields due to their significant advantages in describing data and structural characteristics.Data information described using graphs is called graph data,while mining valuable,hidden information not known in graph data is called graph mining.In practical applications,due to differences in data sources and limitations of technical means,inaccurate or even missing graph data may be caused.Uncertain graphs are proposed to represent such graph data containing inaccurate information and are analyzed in terms of type data.Processing must consider the uncertainty,so the problem for mining uncertain graphs is called a new problem in the field of graph mining.The dense subgraph serves as a sub-region which internal edges are relatively dense are generally regarded as the core part of the graph.How to mine dense subgraphs in uncertain graphs has important application value and theoretical significance.The main work contents and research results of this paper are as follows:1.Firstly,this paper introduces the mining of dense subgraphs in traditional certain graph,including the definition of dense subgraphs and the research background of dense subgraph mining algorithms.Then this paper introduces the research background and mathematical expressions of uncertain graphs.Finally,the definition of dense subgraphs based on uncertain graphs and the research status of mining algorithms are introduced.2.The subgraphs found by the current dense mining algorithms in uncertain graphs have the disadvantages like low reliability,high space complexity,and low density.For the above drawbacks,this paper proposes a novel concept of β-subgraph and the optimal β-subgraph.A greedy optimalβ-subgraph mining algorithm is purposed.Experiments show that the optimal β-subgraph perform better than the dense subgraph produced by previous algorithms both in reliability and density.3.The algorithm of keyword extraction based on graph theory has been widely used nowadays,but the traditional unsupervised keyword extraction algorithms have the disadvantages that they can’t reflect the lexical semantic information and have low accuracy in the face of short text.This paper proposes a local similarity formula between words combine word2 vec and a candidate keyword extraction algorithm based on uncertain graphs through the concept of vertex density and candidate keyword evaluation indicators DEN was purposed,and finally a keyword evaluation optimization criteria DEN-IDF was purposed.Experiments show that the accuracy of DEN-IDF is significantly improved compared with the traditional keyword extraction algorithm.