Research On Continuous Community Search With Attribute Constraints In Temporal Graphs

Continuous community in temporal network is a dense connected subgraph continuously existing in time,which is used to describe the stable close relationship between entities and widely exists in sociology,biology,communication and other fields.At present,most of the problems related to continuous communities are studied from the structural tightness and time continuity of communities,but the potential influence of vertex attribute characteristics on query results is ignored.Aiming at the above problems,this paper studies the problem of continuous community search based on attribute constraints in temporal networks,which is used to search continuous communities that satisfy both attribute constraints and structural constraints.The detailed research content is as follows.Firstly,we define the attribute constrained continuous community search problem: given a threshold of cohesion degree,time continuity degree and a set of restricted attributes,we search for a continuous dense subgraph that conforms to the time and structure constraints and has the largest intersection with the restricted attribute set.This paper proposes a depth-first search based pruning enumeration algorithm PRUNE＿ENUM.The basic idea is to enumerate all candidate sets and judge their satisfiability.In this process,the properties of k-core vertex lower limit,vertex attribute intersection upper limit and subgraph continuity upper limit are used to prune,reduce the enumeration number of candidate sets,and speed up the judgment of community search.Secondly,an optimization algorithm FILTER＿ENUM is proposed to filter the vertices according to the given attribute set.The basic idea is to filter the input graph according to the limited attribute set,and the smaller graph obtained by filtering is used as the starting input of the enumeration algorithm to enumerate the vertex subsets.In the enumeration process,the maximization of attribute and maximization of subgraph of the target community are used to prune,which further reduces the total enumeration number of candidate sets and shortens the running time of the search algorithm.Finally,the query response time of the community,the enumeration number of candidate sets,and the set size in a single enumeration are used as evaluation indicators.Experiments are carried out based on four real-world temporal networks under different threshold requirements and different degrees of attribute restrictions.The experimental results verify the efficiency of the proposed algorithm.