Top-k Query Of Edges With Maximum Impact On Uncertain Graphs

With the rapid development of the Internet and big data,massive data have been produced in information interaction,information processing and storing of information.As one of the most general data structures,graphs have significant advantages when they are used to model property and structure features of knowledge.The data described by graphs are called the graph data.For example,the protein interconnect network of biology and social network can modeled as graphs.With the improvement of data processing technology,the requirement of the accuracy of data is getting higher,and noises and errors in data's acquisition and processing are included into studies.With the subject extending to uncertain data from certain data,the model expends to uncertain graph model,adding probability dimension to the certain graph.The impact edges of uncertain graph can affect the graph structure and function,once destroyed,the entire system will have a great influence,and even cause the system to crash.We cannot simply utilize the study on certain graphs to solve the problems on uncertain graphs due to the dimension of probability on each edge.Even a simple query problem becomes a # p-complete problem on uncertain graphs and the calculation cost is very high and difficult.With regard to the problems above,we mostly study the problem of query of edges with maximum impact on uncertain graphs and propose two models of computing edges impact.The content is as follows.(1)The maximum impact edges query algorithm based on average distance difference model.Firstly in this algorithm we use sampling techniques to simplify the size of the instance graph space,and then we calculate the different average distance of graph which is used as the criterion of the impact of the edge to graph after deleting the edge on each instance graph.Therefore,the experiment verifies the accuracy and time efficiency of the algorithm.(2)The maximum impact edges query algorithm based on the extended model of edge betweenness centrality.The edge betweenness centrality can be used to indicate the size of the impact of edges,but has a certain one-sided nature.The extended model of edge betweenness centrality adds the node betweenness centrality and the degree distribution of endpoints to support the impact of the edge,which is more accurately to measure the influence of the edge impact.The experiment also verifies the algorithm has better accuracy and efficiency.