{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,13]],"date-time":"2025-10-13T19:56:18Z","timestamp":1760385378712},"reference-count":27,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:p>Real-life graphs usually have various kinds of events happening on them, e.g., product purchases in online social networks and intrusion alerts in computer networks. The occurrences of events on the same graph could be correlated, exhibiting either attraction or repulsion. Such structural correlations can reveal important relationships between different events. Unfortunately, correlation relationships on graph structures are not well studied and cannot be captured by traditional measures.<\/jats:p>\n          <jats:p>In this work, we design a novel measure for assessing two-event structural correlations on graphs. Given the occurrences of two events, we choose uniformly a sample of \"reference nodes\" from the vicinity of all event nodes and employ the Kendall's \u03c4 rank correlation measure to compute the average concordance of event density changes. Significance can be efficiently assessed by \u03c4's nice property of being asymptotically normal under the null hypothesis. In order to compute the measure in large scale networks, we develop a scalable framework using different sampling strategies. The complexity of these strategies is analyzed. Experiments on real graph datasets with both synthetic and real events demonstrate that the proposed framework is not only efficacious, but also efficient and scalable.<\/jats:p>","DOI":"10.14778\/2350229.2350256","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1400-1411","source":"Crossref","is-referenced-by-count":3,"title":["Measuring two-event structural correlations on graphs"],"prefix":"10.14778","volume":"5","author":[{"given":"Ziyu","family":"Guan","sequence":"first","affiliation":[{"name":"University of California, Santa Barbara, CA"}]},{"given":"Xifeng","family":"Yan","sequence":"additional","affiliation":[{"name":"University of California, Santa Barbara, CA"}]},{"given":"Lance M.","family":"Kaplan","sequence":"additional","affiliation":[{"name":"U.S. Army Research Laboratory, Adelphi, MD"}]}],"member":"320","published-online":{"date-parts":[[2012,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1002\/0470114754"},{"key":"e_1_2_1_2_1","volume-title":"Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47--97","author":"Albert R.","year":"2002","unstructured":"R. Albert and A. Barab\u00e1si . Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47--97 , 2002 . R. Albert and A. Barab\u00e1si. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47--97, 2002."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007608"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772699"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98564"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.5555\/297805.297827"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.2307\/1402729"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972764.22"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.2307\/1989421"},{"key":"e_1_2_1_10_1","volume-title":"Adaptive rejection sampling for gibbs sampling. Journal of the Royal Statistical Society Series C (Applied Statistics), 41(2):337--348","author":"Gilks W.","year":"1992","unstructured":"W. Gilks and P. Wild . Adaptive rejection sampling for gibbs sampling. Journal of the Royal Statistical Society Series C (Applied Statistics), 41(2):337--348 , 1992 . W. Gilks and P. Wild. Adaptive rejection sampling for gibbs sampling. Journal of the Royal Statistical Society Series C (Applied Statistics), 41(2):337--348, 1992."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989421"},{"key":"e_1_2_1_12_1","volume-title":"Morgan Kaufmann","author":"Han J.","year":"2006","unstructured":"J. Han and M. Kamber . Data Mining: Concepts and Techniques . Morgan Kaufmann , 2006 . J. Han and M. Kamber. Data Mining: Concepts and Techniques. Morgan Kaufmann, 2006."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/00401706.1995.10484303"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/245108.245123"},{"key":"e_1_2_1_15_1","volume-title":"Edward Arnold","author":"Kendall M.","year":"1990","unstructured":"M. Kendall and J. Gibbons . Rank correlation methods . Edward Arnold , 1990 . M. Kendall and J. Gibbons. Rank correlation methods. Edward Arnold, 1990."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807261"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.658027"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1982.tb01221.x"},{"issue":"2","key":"e_1_2_1_19_1","first-page":"1","article-title":"Random walks on graphs: A survey","volume":"2","author":"Lov\u00e1sz L.","year":"1993","unstructured":"L. Lov\u00e1sz . Random walks on graphs: A survey . Bolyai Soc. Math. Studies , 2 ( 2 ): 1 -- 46 , 1993 . L. Lov\u00e1sz. Random walks on graphs: A survey. Bolyai Soc. Math. Studies, 2(2):1--46, 1993.","journal-title":"Bolyai Soc. Math. Studies"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972795.51"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2002.1019258"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1830252.1830268"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1538-4632.2004.tb01139.x"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1965575"},{"key":"e_1_2_1_25_1","first-page":"721","volume-title":"ICDM","author":"Yan X.","year":"2002","unstructured":"X. Yan and J. Han . gspan: Graph-based substructure pattern mining . In ICDM , pages 721 -- 724 , 2002 . X. Yan and J. Han. gspan: Graph-based substructure pattern mining. In ICDM, pages 721--724, 2002."},{"key":"e_1_2_1_26_1","first-page":"1","volume-title":"WOSN","author":"Zhao X.","year":"2010","unstructured":"X. Zhao , A. Sala , C. Wilson , H. Zheng , and B. Zhao . Orion: shortest path estimation for large social graphs . In WOSN , pages 1 -- 9 , 2010 . X. Zhao, A. Sala, C. Wilson, H. Zheng, and B. Zhao. Orion: shortest path estimation for large social graphs. In WOSN, pages 1--9, 2010."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687627.1687709"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2350229.2350256","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:24:45Z","timestamp":1672226685000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2350229.2350256"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":27,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.14778\/2350229.2350256"],"URL":"https:\/\/doi.org\/10.14778\/2350229.2350256","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}