Association rules with graph patterns

作者：Wenfei, Fan; Xin, Wang; Yinghui, Wu; Jingbo, Xu

来源：Proceedings of the VLDB Endowment, 2015, 8(12): 1502-1513.

DOI：10.14778/2824032.2824048

<jats:p>
We propose graph-pattern association rules (GPARs) for social media marketing. Extending association rules for item-sets, 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-
<jats:italic>k</jats:italic>
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.
</jats:p>

• 出版日期2015-8
• 单位北京航空航天大学; 西南交通大学