Personalized graph pattern matching via limited simulation

摘要

It is well known that graph simulation and bisimulation can capture the semantics of graphs, described by the type and attribute of the nodes and edges. Graph pattern matching via simulation has been widely used in a variety of applications such as social network. Recently, some works have investigated the personality of graph simulation. Intuitively, the personality allows each node or edge to have different strengths of matching conditions, which are typically restricted by the similarity of nodes or edges in graphs. Motivated by the notion of k-limited bisimilarity, which was proposed by Milner to measure the similarity of nodes in the neighbouring subgraphs, and some examples in practice, we employ the notion of k-limited similarity, a weaker version of k-limited bisimilarity, to revisit graph pattern matching in this paper. After establishing the framework for the graph pattern matching via limited simulation, we give an efficient algorithm to compute the maximum match for limited simulation and analyze its computational complexity. To evaluate the algorithm, a group of experiments are conducted for limited simulation and graph simulation. As an extension of limited simulation, we also consider the notion of limited bisimulation for graph pattern matching, and unfortunately, we find that the graph pattern matching via limited bisimulation is NP-hard.