{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,13]],"date-time":"2026-03-13T08:58:22Z","timestamp":1773392302683,"version":"3.50.1"},"reference-count":45,"publisher":"Association for Computing Machinery (ACM)","issue":"12","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,8]]},"abstract":"<jats:p>\n            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-\n            <jats:italic>k<\/jats:italic>\n            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.\n          <\/jats:p>","DOI":"10.14778\/2824032.2824048","type":"journal-article","created":{"date-parts":[[2015,9,16]],"date-time":"2015-09-16T12:18:17Z","timestamp":1442405897000},"page":"1502-1513","source":"Crossref","is-referenced-by-count":83,"title":["Association rules with graph patterns"],"prefix":"10.14778","volume":"8","author":[{"given":"Wenfei","family":"Fan","sequence":"first","affiliation":[{"name":"Univ. of Edinburgh and Beihang Univ."}]},{"given":"Xin","family":"Wang","sequence":"additional","affiliation":[{"name":"Southwest Jiaotong Univ."}]},{"given":"Yinghui","family":"Wu","sequence":"additional","affiliation":[{"name":"Washington State Univ."}]},{"given":"Jingbo","family":"Xu","sequence":"additional","affiliation":[{"name":"Univ. of Edinburgh and Beihang Univ."}]}],"member":"320","published-online":{"date-parts":[[2015,8]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"GraMi. https:\/\/github.com\/ehab-abdelhamid\/GraMi.  GraMi. https:\/\/github.com\/ehab-abdelhamid\/GraMi."},{"key":"e_1_2_1_2_1","unstructured":"Nielsen global online consumer survey. http:\/\/www.nielsen.com\/content\/dam\/corporate\/us\/en\/newswire\/uploads\/2009\/07\/pr_global-study_07709.pdf.  Nielsen global online consumer survey. http:\/\/www.nielsen.com\/content\/dam\/corporate\/us\/en\/newswire\/uploads\/2009\/07\/pr_global-study_07709.pdf."},{"key":"e_1_2_1_3_1","unstructured":"Pokec social network. http:\/\/snap.stanford.edu\/data\/soc-pokec.html.  Pokec social network. http:\/\/snap.stanford.edu\/data\/soc-pokec.html."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/170036.170072"},{"key":"e_1_2_1_5_1","volume-title":"Battling predictability and overconcentration in recommender systems","author":"Amer-Yahia S.","year":"2009","unstructured":"S. Amer-Yahia , L. V. Lakshmanan , S. Vassilvitskii , and C. Yu . Battling predictability and overconcentration in recommender systems . IEEE Data Eng. Bull ., 32(4), 2009 . S. Amer-Yahia, L. V. Lakshmanan, S. Vassilvitskii, and C. Yu. Battling predictability and overconcentration in recommender systems. IEEE Data Eng. Bull., 32(4), 2009."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1007\/978-3-642-04180-8_25","volume-title":"Machine learning and knowledge discovery in databases","author":"Berlingerio M.","year":"2009","unstructured":"M. Berlingerio , F. Bonchi , B. Bringmann , and A. Gionis . Mining graph evolution rules . In Machine learning and knowledge discovery in databases , pages 115 -- 130 . 2009 . 10.1007\/978-3-642-04180-8_25 M. Berlingerio, F. Bonchi, B. Bringmann, and A. Gionis. Mining graph evolution rules. In Machine learning and knowledge discovery in databases, pages 115--130. 2009. 10.1007\/978-3-642-04180-8_25"},{"key":"e_1_2_1_7_1","volume-title":"PAKDD","author":"Bringmann B.","year":"2008","unstructured":"B. Bringmann and S. Nijssen . What is frequent in a single graph ? In PAKDD , 2008 . B. Bringmann and S. Nijssen. What is frequent in a single graph? In PAKDD, 2008."},{"key":"e_1_2_1_9_1","first-page":"197","volume-title":"NSDI","author":"Cao Q.","year":"2012","unstructured":"Q. Cao , M. Sirivianos , X. Yang , and T. Pregueiro . Aiding the detection of fake accounts in large scale social online services . In NSDI , pages 197 -- 210 , 2012 . Q. Cao, M. Sirivianos, X. Yang, and T. Pregueiro. Aiding the detection of fake accounts in large scale social online services. In NSDI, pages 197--210, 2012."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2004.75"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623623"},{"key":"e_1_2_1_12_1","first-page":"79","volume-title":"CAV","author":"Dovier A.","year":"2001","unstructured":"A. Dovier , C. Piazza , and A. Policriti . A fast bisimulation algorithm . In CAV , pages 79 -- 90 , 2001 . A. Dovier, C. Piazza, and A. Policriti. A fast bisimulation algorithm. In CAV, pages 79--90, 2001."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732286.2732289"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1366102.1366103"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732983"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34624-8_4"},{"key":"e_1_2_1_17_1","volume-title":"WWW","author":"Gal\u00e1rraga L. A.","year":"2013","unstructured":"L. A. Gal\u00e1rraga , C. Teflioudi , K. Hose , and F. Suchanek . AMIE: association rule mining under incomplete evidence in ontological knowledge bases . In WWW , 2013 . L. A. Gal\u00e1rraga, C. Teflioudi, K. Hose, and F. Suchanek. AMIE: association rule mining under incomplete evidence in ontological knowledge bases. In WWW, 2013."},{"key":"e_1_2_1_18_1","volume-title":"USEWOD workshop","author":"Gallego M. A.","year":"2011","unstructured":"M. A. Gallego , J. D. Fern\u00e1ndez , M. A. Mart\u00ednez-Prieto , and P. de la Fuente. An empirical study of real-world SPARQL queries . In USEWOD workshop , 2011 . M. A. Gallego, J. D. Fern\u00e1ndez, M. A. Mart\u00ednez-Prieto, and P. de la Fuente. An empirical study of real-world SPARQL queries. In USEWOD workshop, 2011."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526761"},{"key":"e_1_2_1_20_1","volume-title":"IMC","author":"Gong N. Z.","year":"2012","unstructured":"N. Z. Gong Evolution of social-attribute networks: measurements, modeling, and implications using google+ . In IMC , 2012 . 10.1145\/2398776.2398792 N. Z. Gong et al. Evolution of social-attribute networks: measurements, modeling, and implications using google+. In IMC, 2012. 10.1145\/2398776.2398792"},{"key":"e_1_2_1_21_1","volume-title":"ICT Innovations","author":"Grujic I.","year":"2014","unstructured":"I. Grujic , S. Bogdanovic-Dinic , and L. Stoimenov . Collecting and analyzing data from e-government facebook pages . In ICT Innovations , 2014 . I. Grujic, S. Bogdanovic-Dinic, and L. Stoimenov. Collecting and analyzing data from e-government facebook pages. In ICT Innovations, 2014."},{"key":"e_1_2_1_22_1","volume-title":"KDD workshop","author":"Holder L. B.","year":"1994","unstructured":"L. B. Holder , D. J. Cook , S. Djoko , Substucture discovery in the subdue system . In KDD workshop , 1994 . L. B. Holder, D. J. Cook, S. Djoko, et al. Substucture discovery in the subdue system. In KDD workshop, 1994."},{"key":"e_1_2_1_23_1","volume-title":"ICDE","author":"Huang J.","year":"2014","unstructured":"J. Huang , K. Venkatraman , and D. J. Abadi . Query optimization of distributed pattern matching . In ICDE , 2014 . J. Huang, K. Venkatraman, and D. J. Abadi. Query optimization of distributed pattern matching. In ICDE, 2014."},{"key":"e_1_2_1_24_1","volume-title":"Principles of Data Mining and Knowledge Discovery.","author":"Inokuchi A.","year":"2000","unstructured":"A. Inokuchi , T. Washio , and H. Motoda . An apriori-based algorithm for mining frequent substructures from graph data . In Principles of Data Mining and Knowledge Discovery. 2000 . A. Inokuchi, T. Washio, and H. Motoda. An apriori-based algorithm for mining frequent substructures from graph data. In Principles of Data Mining and Knowledge Discovery. 2000."},{"issue":"01","key":"e_1_2_1_25_1","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1017\/S0269888912000331","article-title":"A survey of frequent subgraph mining algorithms","volume":"28","author":"Jiang C.","year":"2013","unstructured":"C. Jiang , F. Coenen , and M. Zito . A survey of frequent subgraph mining algorithms . Knowledge Eng. Review , 28 ( 01 ): 75 -- 105 , 2013 . C. Jiang, F. Coenen, and M. Zito. A survey of frequent subgraph mining algorithms. Knowledge Eng. Review, 28(01):75--105, 2013.","journal-title":"Knowledge Eng. Review"},{"key":"e_1_2_1_26_1","first-page":"263","volume-title":"KDD","author":"Kamber M.","year":"1996","unstructured":"M. Kamber and R. Shinghal . Evaluating the interestingness of characteristic rules . In KDD , pages 263 -- 266 , 1996 . M. Kamber and R. Shinghal. Evaluating the interestingness of characteristic rules. In KDD, pages 263--266, 1996."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.54"},{"key":"e_1_2_1_28_1","volume-title":"DBKDA","author":"Kim S.-H.","year":"2013","unstructured":"S.-H. Kim , K.-H. Lee , H. Choi , and Y.-J. Lee . Parallel processing of multiple graph queries using MapReduce . In DBKDA , 2013 . S.-H. Kim, K.-H. Lee, H. Choi, and Y.-J. Lee. Parallel processing of multiple graph queries using MapReduce. In DBKDA, 2013."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989284.1989310"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(90)90192-K"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1007\/978-3-540-44918-8_11","volume-title":"Quality measures in data mining","author":"Lallich S.","year":"2007","unstructured":"S. Lallich , O. Teytaud , and E. Prudhomme . Association rule interestingness: Measure and statistical validation . In Quality measures in data mining , pages 251 -- 275 . 2007 . S. Lallich, O. Teytaud, and E. Prudhomme. Association rule interestingness: Measure and statistical validation. In Quality measures in data mining, pages 251--275. 2007."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2012.37"},{"issue":"6","key":"e_1_2_1_33_1","doi-asserted-by":"crossref","first-page":"1150","DOI":"10.1016\/j.physa.2010.11.027","article-title":"Link prediction in complex networks: A survey","volume":"390","author":"L\u00fc L.","year":"2011","unstructured":"L. L\u00fc and T. Zhou . Link prediction in complex networks: A survey . Physica A: Statistical Mechanics and its Applications , 390 ( 6 ): 1150 -- 1170 , 2011 . L. L\u00fc and T. Zhou. Link prediction in complex networks: A survey. Physica A: Statistical Mechanics and its Applications, 390(6):1150--1170, 2011.","journal-title":"Physica A: Statistical Mechanics and its Applications"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339540"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/568574.568580"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SASO.2013.13"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2621934.2621939"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735493"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11257-004-7961-2"},{"key":"e_1_2_1_40_1","volume-title":"FSTTCS","author":"Saha D.","year":"2007","unstructured":"D. Saha . An incremental bisimulation algorithm . In FSTTCS , 2007 . D. Saha. An incremental bisimulation algorithm. In FSTTCS, 2007."},{"key":"e_1_2_1_41_1","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/3-540-34416-0_28","volume-title":"Data Science and Classification","author":"Schmitz C.","year":"2006","unstructured":"C. Schmitz , A. Hotho , R. J\u00e4schke , and G. Stumme . Mining association rules in folksonomies . In Data Science and Classification , pages 261 -- 270 . 2006 . C. Schmitz, A. Hotho, R. J\u00e4schke, and G. Stumme. Mining association rules in folksonomies. In Data Science and Classification, pages 261--270. 2006."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2013.03.005"},{"key":"e_1_2_1_43_1","volume-title":"Business Insider Intelligence","author":"Smith C.","year":"2013","unstructured":"C. Smith . Twitter users say they use the site to influence their shopping decisions . Business Insider Intelligence , 2013 . C. Smith. Twitter users say they use the site to influence their shopping decisions. Business Insider Intelligence, 2013."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150452"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/HICSS.2006.272"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-46027-6","volume-title":"Association rule mining: models and algorithms","author":"Zhang C.","year":"2002","unstructured":"C. Zhang and S. Zhang . Association rule mining: models and algorithms . 2002 . C. Zhang and S. Zhang. Association rule mining: models and algorithms. 2002."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2824032.2824048","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:16:18Z","timestamp":1672222578000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2824032.2824048"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8]]},"references-count":45,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["10.14778\/2824032.2824048"],"URL":"https:\/\/doi.org\/10.14778\/2824032.2824048","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,8]]}}}