{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,19]],"date-time":"2026-05-19T07:13:19Z","timestamp":1779174799781,"version":"3.51.4"},"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":[[2014,8]]},"abstract":"<jats:p>We propose a new scalable algorithm that can compute Personalized PageRank (PPR) very quickly. The Power method is a state-of-the-art algorithm for computing exact PPR; however, it requires many iterations. Thus reducing the number of iterations is the main challenge.<\/jats:p>\n          <jats:p>We achieve this by exploiting graph structures of web graphs and social networks. The convergence of our algorithm is very fast. In fact, it requires up to 7.5 times fewer iterations than the Power method and is up to five times faster in actual computation time.<\/jats:p>\n          <jats:p>To the best of our knowledge, this is the first time to use graph structures explicitly to solve PPR quickly. Our contributions can be summarized as follows.<\/jats:p>\n          <jats:p>1. We provide an algorithm for computing a tree decomposition, which is more efficient and scalable than any previous algorithm.<\/jats:p>\n          <jats:p>\n            2. Using the above algorithm, we can obtain a\n            <jats:italic>core-tree decomposition<\/jats:italic>\n            of any web graph and social network. This allows us to decompose a web graph and a social network into (1) the\n            <jats:italic>core<\/jats:italic>\n            , which behaves like an expander graph, and (2) a small tree-width graph, which behaves like a\n            <jats:italic>tree<\/jats:italic>\n            in an algorithmic sense.\n          <\/jats:p>\n          <jats:p>3. We apply a direct method to the small tree-width graph to construct an LU decomposition.<\/jats:p>\n          <jats:p>\n            4. Building on the LU decomposition and using it as\n            <jats:italic>pre-conditoner<\/jats:italic>\n            , we apply GMRES method (a state-of-the-art advanced iterative method) to compute PPR for whole web graphs and social networks.\n          <\/jats:p>","DOI":"10.14778\/2732977.2732978","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"1023-1034","source":"Crossref","is-referenced-by-count":54,"title":["Computing personalized PageRank quickly by exploiting graph structures"],"prefix":"10.14778","volume":"7","author":[{"given":"Takanori","family":"Maehara","sequence":"first","affiliation":[{"name":"National Institute of Informatics and JST, ERATO"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Takuya","family":"Akiba","sequence":"additional","affiliation":[{"name":"The University of Tokyo and JST, ERATO"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yoichi","family":"Iwata","sequence":"additional","affiliation":[{"name":"The University of Tokyo and JST, ERATO"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ken-ichi","family":"Kawarabayashi","sequence":"additional","affiliation":[{"name":"National Institute of Informatics and JST, ERATO"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623753"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2247596.2247614"},{"key":"e_1_2_1_3_1","volume-title":"Nature","author":"Albert R.","year":"1999","unstructured":"R. Albert , H. Jeong , and A.-L. Barabasi . Diameter of the World-Wide Web . Nature , 1999 . R. Albert, H. Jeong, and A.-L. Barabasi. Diameter of the World-Wide Web. Nature, 1999."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90189-6"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895479894278952"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(89)90031-0"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/2022148.2022153"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008992.1009048"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39890-5_6"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1963405.1963488"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988752"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807297"},{"key":"e_1_2_1_14_1","volume-title":"Spectral Graph Theory. Cbms Regional Conference Series in Mathematics","author":"Chung F.","year":"1997","unstructured":"F. Chung . Spectral Graph Theory. Cbms Regional Conference Series in Mathematics , 1997 . F. Chung. Spectral Graph Theory. Cbms Regional Conference Series in Mathematics, 1997."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00026-005-0237-z"},{"key":"e_1_2_1_16_1","volume-title":"SIAM","author":"Davis T. A.","year":"2006","unstructured":"T. A. Davis . Direct methods for sparse linear systems . SIAM , 2006 . T. A. Davis. Direct methods for sparse linear systems. SIAM, 2006."},{"key":"e_1_2_1_17_1","first-page":"10","volume-title":"OSDI","author":"Dean J.","year":"2004","unstructured":"J. Dean and S. Ghemawat . MapReduce: simplified data processing on large clusters . In OSDI , pages 10 -- 10 , 2004 . J. Dean and S. Ghemawat. MapReduce: simplified data processing on large clusters. In OSDI, pages 10--10, 2004."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cam.2006.10.080"},{"key":"e_1_2_1_19_1","volume-title":"How descriptive are GMRES convergence bounds? Technical report","author":"Embree M.","year":"1999","unstructured":"M. Embree . How descriptive are GMRES convergence bounds? Technical report , Oxford University Computing Laboratory , 1999 . M. Embree. How descriptive are GMRES convergence bounds? Technical report, Oxford University Computing Laboratory, 1999."},{"key":"e_1_2_1_20_1","volume-title":"http:\/\/facebook.com\/press\/info.php?statistics","year":"2012","unstructured":"Facebook. http:\/\/facebook.com\/press\/info.php?statistics , 2012 . Facebook. http:\/\/facebook.com\/press\/info.php?statistics, 2012."},{"key":"e_1_2_1_21_1","first-page":"2","article-title":"Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments","author":"Fogaras D.","year":"2005","unstructured":"D. Fogaras , B. R\u00e1cz , K. Csalog\u00e1ny , and T. Sarl\u00f3s . Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments . Internet Math. , 2 , 2005 . D. Fogaras, B. R\u00e1cz, K. Csalog\u00e1ny, and T. Sarl\u00f3s. Towards scaling fully personalized PageRank: Algorithms, lower bounds, and experiments. Internet Math., 2, 2005.","journal-title":"Internet Math."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/2140436.2140441"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2339530.2339538"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.10.013"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0710032"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0273-0979-06-01126-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90009-9"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400830329"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"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","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_38_1","volume-title":"Stanford InfoLab","author":"Page L.","year":"1999","unstructured":"L. Page , S. Brin , R. Motwani , and T. Winograd . The pagerank citation ranking: Bringing order to the web. Technical report , Stanford InfoLab , 1999 . L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(84)90013-3"},{"key":"e_1_2_1_40_1","volume-title":"Numerical methods for large eigenvalue problems","author":"Saad Y.","year":"1992","unstructured":"Y. Saad . Numerical methods for large eigenvalue problems , volume 158 . SIAM , 1992 . Y. Saad. Numerical methods for large eigenvalue problems, volume 158. SIAM, 1992."},{"key":"e_1_2_1_41_1","volume-title":"SIAM","author":"Saad Y.","year":"2003","unstructured":"Y. Saad . Iterative methods for sparse linear systems . SIAM , 2003 . Y. Saad. Iterative methods for sparse linear systems. SIAM, 2003."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/0907058"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807181"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1777432.1777434"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSB.2005.9"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/800113.803648"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2732977.2732978","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:19:54Z","timestamp":1672226394000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2732977.2732978"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,8]]},"references-count":45,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2014,8]]}},"alternative-id":["10.14778\/2732977.2732978"],"URL":"https:\/\/doi.org\/10.14778\/2732977.2732978","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,8]]}}}