Skip to main content
Article
Mining Top-K Large Structural Patterns in a Massive Network
Proceedings of VLDB Endowment: 37th VLDB 2011, Seattle
  • Feida ZHU, Singapore Management University
  • Qiang QU, Peking University
  • David LO, Singapore Management University
  • Xifeng YAN, University of California, Santa Barbara
  • Jiawei HAN, University of Illinois, Urbana Champaign
  • Philip S. YU, University of Illinois, Chicago
Publication Type
Conference Proceeding Article
Publication Date
9-2011
Abstract

With ever-growing popularity of social networks, web and bio-networks, mining large frequent patterns from a single huge network has become increasingly important. Yet the existing pattern mining methods cannot offer the efficiency desirable for large pattern discovery. We propose Spider- Mine, a novel algorithm to efficiently mine top-K largest frequent patterns from a single massive network with any user-specified probability of 1 − ϵ. Deviating from the existing edge-by-edge (i.e., incremental) pattern-growth framework, SpiderMine achieves its efficiency by unleashing the power of small patterns of a bounded diameter, which we call “spiders”. With the spider structure, our approach adopts a probabilistic mining framework to find the top-k largest patterns by (i) identifying an affordable set of promising growth paths toward large patterns, (ii) generating large patterns with much lower combinatorial complexity, and finally (iii) greatly reducing the cost of graph isomorphism tests with a new graph pattern representation by a multi-set of spiders. Extensive experimental studies on both synthetic and real data sets show that our algorithm outperforms existing methods.

Publisher
VLDB Endowment
City or Country
Saratoga, CA
Additional URL
http://www.vldb.org/pvldb/vol4/p807-zhu.pdf
Citation Information
Feida ZHU, Qiang QU, David LO, Xifeng YAN, et al.. "Mining Top-K Large Structural Patterns in a Massive Network" Proceedings of VLDB Endowment: 37th VLDB 2011, Seattle (2011) p. 807 - 818
Available at: http://works.bepress.com/david_lo/64/