Association Rules with Graph Patterns

Wenfei Fan, Xin Wang, Yinghui Wu, Jingbo Xu

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

We propose graph-pattern association rules (GPARs) for social media marketing. Extending association rules for itemsets, GPARs help us discover regularities between entities in social graphs, and identify potential customers by exploring social influence. We study the problem of discovering top-k diversified GPARs. While this problem is NP-hard, we develop a parallel algorithm with accuracy bound. We also study the problem of identifying potential customers with GPARs. While it is also NP-hard, we provide a parallel scalable algorithm that guarantees a polynomial speedup over sequential algorithms with the increase of processors. Using real-life and synthetic graphs, we experimentally verify the scalability and effectiveness of the algorithms.
Original languageEnglish
Pages (from-to)1502-1513
Number of pages12
JournalProceedings of the VLDB Endowment (PVLDB)
Issue number12
Publication statusPublished - 1 Aug 2015


Dive into the research topics of 'Association Rules with Graph Patterns'. Together they form a unique fingerprint.

Cite this