Graph pattern matching is typically defined in terms of subgraph isomorphism,
which makes it an np-complete problem. Moreover, it requires bijective
functions, which are often too restrictive to characterize patterns
in emerging applications. We propose a class of graph patterns, in
which an edge denotes the connectivity in a data graph within a predefined
number of hops. In addition, we define matching based on a notion
of bounded simulation, an extension of graph simulation. We show
that with this revision, graph pattern matching can be performed
in cubic-time, by providing such an algorithm. We also develop algorithms
for incrementally finding matches when data graphs are updated, with
performance guarantees for dag patterns. We experimentally verify
that these algorithms scale well, and that the revised notion of
graph pattern matching allows us to identify communities commonly
found in real-world networks.
%0 Journal Article
%1 fan-2010
%A Fan, Wenfei
%A Li, Jianzhong
%A Ma, Shuai
%A Tang, Nan
%A Wu, Yinghui
%A Wu, Yunpeng
%D 2010
%J Proceedings of the VLDB Endowment
%K 2011 graph matching selected seminar twitter winter
%N 1
%P 264--275
%T Graph Pattern Matching: From Intractable to Polynomial Time
%V 3
%X Graph pattern matching is typically defined in terms of subgraph isomorphism,
which makes it an np-complete problem. Moreover, it requires bijective
functions, which are often too restrictive to characterize patterns
in emerging applications. We propose a class of graph patterns, in
which an edge denotes the connectivity in a data graph within a predefined
number of hops. In addition, we define matching based on a notion
of bounded simulation, an extension of graph simulation. We show
that with this revision, graph pattern matching can be performed
in cubic-time, by providing such an algorithm. We also develop algorithms
for incrementally finding matches when data graphs are updated, with
performance guarantees for dag patterns. We experimentally verify
that these algorithms scale well, and that the revised notion of
graph pattern matching allows us to identify communities commonly
found in real-world networks.
@article{fan-2010,
abstract = {Graph pattern matching is typically defined in terms of subgraph isomorphism,
which makes it an np-complete problem. Moreover, it requires bijective
functions, which are often too restrictive to characterize patterns
in emerging applications. We propose a class of graph patterns, in
which an edge denotes the connectivity in a data graph within a predefined
number of hops. In addition, we define matching based on a notion
of bounded simulation, an extension of graph simulation. We show
that with this revision, graph pattern matching can be performed
in cubic-time, by providing such an algorithm. We also develop algorithms
for incrementally finding matches when data graphs are updated, with
performance guarantees for dag patterns. We experimentally verify
that these algorithms scale well, and that the revised notion of
graph pattern matching allows us to identify communities commonly
found in real-world networks.},
added-at = {2011-10-10T09:53:59.000+0200},
author = {Fan, Wenfei and Li, Jianzhong and Ma, Shuai and Tang, Nan and Wu, Yinghui and Wu, Yunpeng},
biburl = {https://www.bibsonomy.org/bibtex/2ecf1d4cc66062b93c15bd0d05d4a17cf/becker},
interhash = {a81733506d0f1daca3080c78d0da86c2},
intrahash = {ecf1d4cc66062b93c15bd0d05d4a17cf},
journal = {Proceedings of the VLDB Endowment},
keywords = {2011 graph matching selected seminar twitter winter},
month = sep,
number = 1,
pages = {264--275},
timestamp = {2011-10-26T09:09:19.000+0200},
title = {Graph Pattern Matching: From Intractable to Polynomial Time},
volume = 3,
year = 2010
}