{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,29]],"date-time":"2025-05-29T04:05:07Z","timestamp":1748491507992,"version":"3.41.0"},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319193144"},{"type":"electronic","value":"9783319193151"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19315-1_10","type":"book-chapter","created":{"date-parts":[[2015,6,6]],"date-time":"2015-06-06T10:42:08Z","timestamp":1433587328000},"page":"110-121","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Computing Heat Kernel Pagerank and a Local Clustering Algorithm"],"prefix":"10.1007","author":[{"given":"Fan","family":"Chung","sequence":"first","affiliation":[]},{"given":"Olivia","family":"Simpson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,7]]},"reference":[{"key":"10_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-72504-6_1","volume-title":"Theory and Applications of Models of Computation","author":"R Andersen","year":"2007","unstructured":"Andersen, R., Chung, F.: Detecting sharp drops in pagerank and a simplified local partitioning algorithm. In: Cai, J.-Y., Cooper, S.B., Zhu, H. (eds.) TAMC 2007. LNCS, vol. 4484, pp. 1\u201312. Springer, Heidelberg (2007)"},{"doi-asserted-by":"crossref","unstructured":"Andersen, R., Chung, F., Lang, K.: Local graph partitioning using pagerank vectors. In: IEEE 47th Annual Symposium on Foundations of Computer Science, pp. 475\u2013486. IEEE (2006)","key":"10_CR2","DOI":"10.1109\/FOCS.2006.44"},{"doi-asserted-by":"crossref","unstructured":"Andersen, R., Peres, Y.: Finding sparse cuts locally using evolving sets. In: Proceedings of the 41st Annual Symposium on Theory of Computing, pp. 235\u2013244. ACM (2009)","key":"10_CR3","DOI":"10.1145\/1536414.1536449"},{"key":"10_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-30541-2_4","volume-title":"Algorithms and Models for the Web Graph","author":"C Borgs","year":"2012","unstructured":"Borgs, C., Brautbar, M., Chayes, J., Teng, S.-H.: A sublinear time algorithm for pagerank computations. In: Bonato, A., Janssen, J. (eds.) WAW 2012. LNCS, vol. 7323, pp. 41\u201353. Springer, Heidelberg (2012)"},{"issue":"1","key":"10_CR5","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0169-7552(98)00110-X","volume":"30","author":"S Brin","year":"1998","unstructured":"Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. ISDN Syst. 30(1), 107\u2013117 (1998)","journal-title":"Comput. Netw. ISDN Syst."},{"issue":"50","key":"10_CR6","doi-asserted-by":"publisher","first-page":"19735","DOI":"10.1073\/pnas.0708838104","volume":"104","author":"F Chung","year":"2007","unstructured":"Chung, F.: The heat kernel as the pagerank of a graph. Proc. Natl. Acad. Sci. 104(50), 19735\u201319740 (2007)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"3","key":"10_CR7","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1080\/15427951.2009.10390643","volume":"6","author":"F Chung","year":"2009","unstructured":"Chung, F.: A local graph partitioning algorithm using heat kernel pagerank. Internet Math. 6(3), 315\u2013330 (2009)","journal-title":"Internet Math."},{"key":"10_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/978-3-319-03536-9_16","volume-title":"Algorithms and Models for the Web Graph","author":"F Chung","year":"2013","unstructured":"Chung, F., Simpson, O.: Solving linear systems with boundary conditions using heat kernel pagerank. In: Bonato, A., Mitzenmacher, M., Pra\u0142at, P. (eds.) WAW 2013. LNCS, vol. 8305, pp. 203\u2013219. Springer, Heidelberg (2013)"},{"doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Trevisan, L.: Approximating the expansion profile and almost optimal local graph clustering. In: IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 187\u2013196. IEEE (2012)","key":"10_CR9","DOI":"10.1109\/FOCS.2012.85"},{"issue":"3","key":"10_CR10","doi-asserted-by":"publisher","first-page":"497","DOI":"10.1145\/990308.990313","volume":"51","author":"R Kannan","year":"2004","unstructured":"Kannan, R., Vempala, S., Vetta, A.: On clusterings: good, bad and spectral. J. ACM (JACM) 51(3), 497\u2013515 (2004)","journal-title":"J. ACM (JACM)"},{"key":"10_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1007\/978-3-319-03536-9_6","volume-title":"Algorithms and Models for the Web Graph","author":"K Kloster","year":"2013","unstructured":"Kloster, K., Gleich, D.F.: A nearly-sublinear method for approximating a column of the matrix exponential for matrices from large, sparse networks. In: Bonato, A., Mitzenmacher, M., Pra\u0142at, P. (eds.) WAW 2013. LNCS, vol. 8305, pp. 68\u201379. Springer, Heidelberg (2013)"},{"doi-asserted-by":"crossref","unstructured":"Leskovec, J., Lang, K.J., Dasgupta, A., Mahoney, M.W.: Statistical properties of community structure in large social and information networks. In: Proceedings of the 17th International Conference on World Wide Web, pp. 695\u2013704. ACM (2008)","key":"10_CR12","DOI":"10.1145\/1367497.1367591"},{"unstructured":"Lin, F., Cohen, W.W.: Power iteration clustering. In: Proceedings of the 27th International Conference on Machine Learning (ICML 2010), pp. 655\u2013662 (2010)","key":"10_CR13"},{"unstructured":"Lin, F., Cohen, W.W.: A very fast method for clustering big text datasets. In: Proceedings of the 19th European Conference on Artificial Intelligence, pp. 303\u2013308 (2010)","key":"10_CR14"},{"doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Simonovits, M.: The mixing rate of markov chains, an isoperimetric inequality, and computing the volume. In: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, pp. 346\u2013354. IEEE (1990)","key":"10_CR15","DOI":"10.1109\/FSCS.1990.89553"},{"issue":"4","key":"10_CR16","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1002\/rsa.3240040402","volume":"4","author":"L Lov\u00e1sz","year":"1993","unstructured":"Lov\u00e1sz, L., Simonovits, M.: Random walks in a convex body and an improved volume algorithm. Random Struct. Algorithms 4(4), 359\u2013412 (1993)","journal-title":"Random Struct. Algorithms"},{"key":"10_CR17","first-page":"849","volume":"2","author":"AY Ng","year":"2002","unstructured":"Ng, A.Y., Jordan, M.I., Weiss, Y., et al.: On spectral clustering: analysis and an algorithm. Adv. Neural Inf. Proc. Syst. 2, 849\u2013856 (2002)","journal-title":"Adv. Neural Inf. Proc. Syst."},{"doi-asserted-by":"crossref","unstructured":"Orecchia, L., Sachdeva, S., Vishnoi, N.K.: Approximating the exponential, the lanczos method and an $$\\tilde{O}$$(m)-time spectral algorithm for balanced separator. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 1141\u20131160. ACM (2012)","key":"10_CR18","DOI":"10.1145\/2213977.2214080"},{"unstructured":"Sachdeva, S., Vishnoi, N.K.: Matrix inversion is as easy as exponentiation (2013). arXiv preprint arXiv:1305.0526","key":"10_CR19"},{"doi-asserted-by":"crossref","unstructured":"Spielman, D.A., Teng, S.H.: Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In: Proceedings of the thirty-sixth annual ACM symposium on Theory of Computing, pp. 81\u201390. ACM (2004)","key":"10_CR20","DOI":"10.1145\/1007352.1007372"},{"unstructured":"Spielman, D.A., Teng, S.H.: A local clustering algorithm for massive graphs and its application to nearly-linear time graph partitioning. CoRR abs\/0809.3232 (2008)","key":"10_CR21"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19315-1_10","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T11:46:26Z","timestamp":1748432786000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19315-1_10"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319193144","9783319193151"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19315-1_10","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"7 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}