The Research Of Reachability Problems In Large-scale Attribute Networks

In the real world,various connections between entities can be modeled and represented by corresponding complex networks,for example,the interaction between users can be modeled as social networks,the interaction between proteins can be modeled as protein networks,and the regulatory relationships between genes can be modeled as biological networks.With the advancement of technology and the development of society,the connections between entities have become stronger and the corresponding networks have expanded in size.In order to study these networks,we usually abstract the networks as graph structures in data structures.Where the entities in the network correspond to the nodes in the graph,and the connections between entities correspond to the edges between the nodes in the graph.As a fundamental problem in graph analysis,reachability query has been widely utilized in several computer science fields.In real situations,the connections between entities are often multiple,i.e.,the connections between entities(i.e.,edges in the graph structure)can contain multiple attributes,and such networks are also known as multi-attribute networks.The existing work for reachability queries only considers the case when the edges in the graph have only one attribute or no attribute.Therefore,the current reachability model is not applicable to reachability queries on attribute graphs with multi-attribute edges.Moreover,most of the research on reachability queries in attribute networks is based on determining the reachability between nodes given constraints.However,the goal of many practical applications is to find the smallest set of attributes that make two nodes reachable,rather than to determine the reachability under specified constraints.Therefore,this thesis firstly proposes two reachability models for multi-attribute graphs,i.e.,the necessary attribute constraint reachability model and the existence attribute constraint reachability model,and proposes the corresponding reachability query problem for the two reachability models.Then,in order to speed up the reachability query,this thesis proposes the corresponding index algorithms based on the idea of 2-hop cover for the two reachability models and proposes the optimization strategies based on the node degree and the number of attributes according to the properties of the index to speed up the construction of the index.After that,this thesis presents the minimum reachable attribute set problem in attribute networks and designs a hot point-based algorithm and a bottom-up algorithm to solve the problem.For the reachability problem in multi-attribute networks and the minimum reachable attribute set problem in attribute networks,we conducted experiments on several real datasets to verify the efficiency of the proposed algorithm based on the response time of different types of queries and the response time of queries with different node degree distribution,and the scalability of the proposed algorithm based on the response time of queries with different number of attributes and the response time of queries with different number of nodes.