{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,3]],"date-time":"2026-10-03T00:46:36Z","timestamp":1790988396333,"version":"4.1.0"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2013,4,30]],"date-time":"2013-04-30T00:00:00Z","timestamp":1367280000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGKDD Explor. Newsl."],"published-print":{"date-parts":[[2013,4,30]]},"abstract":"<jats:p>How do we find patterns and anomalies in very large graphs with billions of nodes and edges? How to mine such big graphs efficiently? Big graphs are everywhere, ranging from social networks and mobile call networks to biological networks and the World Wide Web. Mining big graphs leads to many interesting applications including cyber security, fraud detection, Web search, recommendation, and many more.<\/jats:p>\n          <jats:p>In this paper we describe Pegasus, a big graph mining system built on top of MapReduce, a modern distributed data processing platform. We introduce GIM-V, an important primitive that Pegasus uses for its algorithms to analyze structures of large graphs. We also introduce HEigen, a large scale eigensolver which is also a part of Pegasus. Both GIM-V and HEigen are highly optimized, achieving linear scale up on the number of machines and edges, and providing 9.2x and 76x faster performance than their naive counterparts, respectively.<\/jats:p>\n          <jats:p>Using Pegasus, we analyze very large, real world graphs with billions of nodes and edges. Our findings include anomalous spikes in the connected component size distribution, the 7 degrees of separation in a Web graph, and anomalous adult advertisers in the who-follows-whom Twitter social network.<\/jats:p>","DOI":"10.1145\/2481244.2481249","type":"journal-article","created":{"date-parts":[[2013,5,3]],"date-time":"2013-05-03T12:30:25Z","timestamp":1367584225000},"page":"29-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["Big graph mining"],"prefix":"10.1145","volume":"14","author":[{"given":"U.","family":"Kang","sequence":"first","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,4,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Hadoop information. http:\/\/hadoop.apache.org\/.  Hadoop information. http:\/\/hadoop.apache.org\/."},{"key":"e_1_2_1_2_1","unstructured":"Hbase information. http:\/\/hbase.apache.org\/.  Hbase information. http:\/\/hbase.apache.org\/."},{"key":"e_1_2_1_3_1","unstructured":"Mahout information. http:\/\/lucene.apache.org\/mahout\/.  Mahout information. http:\/\/lucene.apache.org\/mahout\/."},{"key":"e_1_2_1_4_1","unstructured":"The open cloud consortium. http:\/\/opencloudconsortium.org\/.  The open cloud consortium. http:\/\/opencloudconsortium.org\/."},{"key":"e_1_2_1_5_1","volume-title":"Diameter of the world wide web. Nature, (401):130--131","author":"Albert R.","year":"1999","unstructured":"R. Albert , H. Jeong , and A.-L. Barabasi . Diameter of the world wide web. Nature, (401):130--131 , 1999 . R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the world wide web. Nature, (401):130--131, 1999."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2008.04.002"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_8_1","first-page":"321","volume-title":"ICML","author":"Bradley J. K.","year":"2011","unstructured":"J. K. Bradley , A. Kyrola , D. Bickson , and C. Guestrin . Parallel coordinate descent for l1-regularized loss minimization . In ICML , pages 321 -- 328 , 2011 . J. K. Bradley, A. Kyrola, D. Bickson, and C. Guestrin. Parallel coordinate descent for l1-regularized loss minimization. In ICML, pages 321--328, 2011."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00083-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557049"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327492"},{"key":"e_1_2_1_12_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611971446","volume-title":"Applied numerical linear algebra","author":"Demmel J. W.","year":"1997","unstructured":"J. W. Demmel . Applied numerical linear algebra . SIAM , 1997 . J. W. Demmel. Applied numerical linear algebra. SIAM, 1997."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1805895"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1083-6101.2007.00367.x"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316229"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020426"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767930"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/276675.276685"},{"key":"e_1_2_1_19_1","volume-title":"Matrix computations","author":"Golub G. H.","year":"1996","unstructured":"G. H. Golub and C. F. Van Loan . Matrix computations . Johns Hopkins University Press , 1996 . G. H. Golub and C. F. Van Loan. Matrix computations. Johns Hopkins University Press, 1996."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2011.26"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2010.121"},{"key":"e_1_2_1_22_1","first-page":"13","volume-title":"PAKDD (2)","author":"Kang U.","year":"2011","unstructured":"U. Kang , B. Meeder , and C. Faloutsos . Spectral analysis for billion-scale graphs: Discoveries and implementation . In PAKDD (2) , pages 13 -- 25 , 2011 . U. Kang, B. Meeder, and C. Faloutsos. Spectral analysis for billion-scale graphs: Discoveries and implementation. In PAKDD (2), pages 13--25, 2011."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972818.11"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339583"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0283-9"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.14"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1921632.1921634"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/309847.309954"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.89"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.6028\/jres.045.026"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367591"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557081"},{"key":"e_1_2_1_34_1","first-page":"340","volume-title":"UAI","author":"Low Y.","year":"2010","unstructured":"Y. Low , J. Gonzalez , A. Kyrola , D. Bickson , C. Guestrin , and J. M. Hellerstein . Graphlab: A new framework for parallel machine learning . In UAI , pages 340 -- 349 , 2010 . Y. Low, J. Gonzalez, A. Kyrola, D. Bickson, C. Guestrin, and J. M. Hellerstein. Graphlab: A new framework for parallel machine learning. In UAI, pages 340--349, 2010."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.14778\/2212351.2212354"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_2_1_37_1","volume-title":"Power laws, pareto distributions and zipf's law. Contemporary Physics, (46):323--351","author":"Newman M. E. J.","year":"2005","unstructured":"M. E. J. Newman . Power laws, pareto distributions and zipf's law. Contemporary Physics, (46):323--351 , 2005 . M. E. J. Newman. Power laws, pareto distributions and zipf's law. Contemporary Physics, (46):323--351, 2005."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376726"},{"key":"e_1_2_1_39_1","volume-title":"The PageRank citation ranking: Bringing order to the web. Technical report","author":"Page L.","year":"1998","unstructured":"L. Page , S. Brin , R. Motwani , and T. Winograd . The PageRank citation ranking: Bringing order to the web. Technical report , Stanford Digital Library Technologies Project , 1998 . L. Page, S. Brin, R. Motwani, and T. Winograd. The PageRank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014135"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.142"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_42"},{"key":"e_1_2_1_43_1","volume-title":"Microsoft Research","author":"Shao B.","year":"2012","unstructured":"B. Shao , H. Wang , and Y. Li . The trinity graph engine . In Microsoft Research , 2012 . B. Shao, H. Wang, and Y. Li. The trinity graph engine. In Microsoft Research, 2012."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807278"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.70"},{"key":"e_1_2_1_46_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719574","volume-title":"Numerical linear algebra","author":"Trefethen L. N.","year":"1997","unstructured":"L. N. Trefethen and D. Bau III. Numerical linear algebra . SIAM , 1997 . L. N. Trefethen and D. Bau III. Numerical linear algebra. SIAM, 1997."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2008.72"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020581"}],"container-title":["ACM SIGKDD Explorations Newsletter"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2481244.2481249","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2481244.2481249","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:39:14Z","timestamp":1750235954000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2481244.2481249"}},"subtitle":["algorithms and discoveries"],"short-title":[],"issued":{"date-parts":[[2013,4,30]]},"references-count":48,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2013,4,30]]}},"alternative-id":["10.1145\/2481244.2481249"],"URL":"https:\/\/doi.org\/10.1145\/2481244.2481249","relation":{},"ISSN":["1931-0145","1931-0153"],"issn-type":[{"value":"1931-0145","type":"print"},{"value":"1931-0153","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,4,30]]},"assertion":[{"value":"2013-04-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}