Edinburgh Research Explorer

Association Rules with Graph Patterns

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

  • Download as Adobe PDF

    Accepted author manuscript, 397 KB, PDF-document

    Licence: Creative Commons: Attribution-NonCommercial-NoDerivatives (CC BY-NC-ND)

https://dl.acm.org/citation.cfm?id=2824048
Original languageEnglish
Pages (from-to)1502-1513
Number of pages12
JournalProceedings of the VLDB Endowment (PVLDB)
Volume8
Issue number12
DOIs
Publication statusPublished - 1 Aug 2015

Abstract

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.

Download statistics

No data available

ID: 77708355