SMQA: Similarity Nodes Query Algorithm Based On Large Dynamic Evolution Of Graph

Abstract

In the evolution of dynamic graph topology, in order to quantify the change of the change of the relation between the nodes  within a certain time, a concept,  namely ubiquitous  similarity node, was defined, and the level of ubiquitous similarity with the current node was measured by the frequent degree of interaction with the current node and the uniformity  of distribution,  and a similarity node query processing  algorithm for large dynamic graph based on the snapshots was proposed. The concrete content includes the snapshot  expression of the dynamic evolution of graph, namely evolution dynamic graph; the semantic representation and its formal representation of the nodes` ubiquitous similarity  in  the  dynamic  evolution  of  graph,  which  was  characterized  by  the  frequent  degree  of  interaction  and uniformity coefficient of distribution; the matrix representation and processing method of the semantic of the nodes` ubiquitous similarity; the query algorithm for ubiquitous similarity nodes. The experimental results on the synthetic dataset and the real dataset show that the proposed algorithm can deal with the nodes` ubiquitous similarity query on the large dynamic graph can be implemented in the practical applications.