Font Size: a A A

Research On Dense Subgraph Query For Large And Dynamic Graphs

Posted on:2018-08-13Degree:MasterType:Thesis
Country:ChinaCandidate:Y XieFull Text:PDF
GTID:2348330512987345Subject:Computer application technology
Abstract/Summary:PDF Full Text Request
As a kind of data structure which can effectively describe the complex relationship among the various entities in the real world,graph is widely used in practical fields such as social relations networks,co-author networks,communication networks,biological information networks and so on.With the rapid development of these emerging large networks,the various types of applications constantly emerge and are enriched.And the graph data is also rapidly increasing and frequently updating,so the demand for large and dynamic graph processing becomes more and more urgent.Dense subgraph query is a hot topic in graph data processing,and plays an important role in complex network analysis.It aims to find a densely connected subgraph containing the query node in a graph for a given node or a set of nodes.However,most existing dense subgraph query methods do not consider the spreading influence of nodes.In many application domains,they need stricter requirements which consider the potential spreading influence of nodes and ask for the spreading influence of nodes within subgraph is not lower than query node.For example,in military intelligence analysis domain,consider an ordinary soldier gets confidential information in an army interaction network.He will try his best to pass information to the soldiers with higher influence who usually take on important positions as soon as possible in the detachment containing him.Find a core subgraph made up of these people helps to analyze military intelligence,key person and their relationships.In addition,the existing dense subgraph query methods are mainly focus on small and medium or large static graphs,and the research results for large and dynamic graphs are less.That makes them have limitations in practical applications.In view of the above problems,this thesis studies the dense subgraph query method for large and dynamic graphs,proposes a center-core dense subgraph query method based on k-core decomposition and the dynamic maintenance method of the center-core graph index,and the main contributions are summarized as follows:(1)Putting forward a novel dense subgraph model called center-core.Effectively evaluating the spreading influence of nodes by coreness which is computed based on k-core decomposition algorithm.Constraining subgraph connectivity,minimum degree and spreading influence of nodes according to the corresponding application semantics,the network topology and the hierarchical division for spreading influence of nodes.The model can capture the spreading influence of nodes and ensure the density of the subgraph.At the same time,motivating the problem of center-core dense subgraph query for given query nodes.(2)Proposing a space-efficient index structure called center-core-graph index which can well preserved the key information about center-core including the hierarchical division for spreading influence of nodes and connected relation among nodes.Effectively impressing the storage space of index and the graph scale of processing by filtering redundant information.(3)Putting forward a center-core dense subgraph query method based on center-core-graph index to realize rapidly query in large graphs.This method speed up the query by directly retrieving the index which greatly reduces the query time.(4)Proposing an incremental index update strategy and corresponding algorithms for dynamic graphs.During the dense subgraph query processing,the change of graph structure only affects partial nodes and edges when the graph is updated frequently.Only the partial adjustment of graph data and index should be carried out to realize dynamic maintenance.(5)Extensive experiments over real data sets demonstrate the efficiency and effectiveness of the proposed center-core dense subgraph query method based on k-core decomposition and the dynamic maintenance method of the index.They all have great query efficiency and low index storage space,and has good applicability in large and dynamic graphs in practical application.
Keywords/Search Tags:dense subgraph query, large graph, dynamic graph, spreading influence, minimum degree
PDF Full Text Request
Related items