{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,19]],"date-time":"2026-02-19T04:23:29Z","timestamp":1771475009650,"version":"3.50.1"},"publisher-location":"Cham","reference-count":44,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319678092","type":"print"},{"value":"9783319678108","type":"electronic"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-67810-8_3","type":"book-chapter","created":{"date-parts":[[2017,9,4]],"date-time":"2017-09-04T21:42:34Z","timestamp":1504561354000},"page":"27-41","source":"Crossref","is-referenced-by-count":14,"title":["Kernels on Graphs as Proximity Measures"],"prefix":"10.1007","author":[{"given":"Konstantin","family":"Avrachenkov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Chebotarev","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dmytro","family":"Rubanov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,9,6]]},"reference":[{"key":"3_CR1","doi-asserted-by":"crossref","unstructured":"Avrachenkov, K., Mishenin, A., Gon\u00e7alves, P., Sokol, M.: Generalized optimization framework for graph-based semi-supervised learning. In: Proceedings of the 2012 SIAM International Conference on Data Mining, pp. 966\u2013974 (2012)","DOI":"10.1137\/1.9781611972825.83"},{"key":"3_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1007\/978-3-319-03536-9_5","volume-title":"Algorithms and Models for the Web Graph","author":"K Avrachenkov","year":"2013","unstructured":"Avrachenkov, K., Gon\u00e7alves, P., Sokol, M.: On the choice of kernel and labelled data in semi-supervised learning methods. In: Bonato, A., Mitzenmacher, M., Pra\u0142at, P. (eds.) WAW 2013. LNCS, vol. 8305, pp. 56\u201367. Springer, Cham (2013). doi: 10.1007\/978-3-319-03536-9_5"},{"issue":"2","key":"3_CR3","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1080\/10556788.2016.1193176","volume":"32","author":"K Avrachenkov","year":"2017","unstructured":"Avrachenkov, K., Chebotarev, P., Mishenin, A.: Semi-supervised learning with regularized Laplacian. Optim. Methods Softw. 32(2), 222\u2013236 (2017)","journal-title":"Optim. Methods Softw."},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Avrachenkov, K., van der Hofstad, R., Sokol, M.: Personalized PageRank with node-dependent restart. In: Proceedings of International Workshop on Algorithms and Models for the Web-Graph, pp. 23\u201333 (2014)","DOI":"10.1007\/978-3-319-13123-8_3"},{"key":"3_CR5","first-page":"635","volume":"2011","author":"L Backstrom","year":"2011","unstructured":"Backstrom, L., Leskovec, J.: Supervised random walks: predicting and recommending links in social networks. Proc. ACM WSDM 2011, 635\u2013644 (2011)","journal-title":"Proc. ACM WSDM"},{"issue":"2","key":"3_CR6","doi-asserted-by":"crossref","first-page":"224","DOI":"10.1016\/j.laa.2011.01.030","volume":"435","author":"D Boley","year":"2011","unstructured":"Boley, D., Ranjan, G., Zhang, Z.L.: Commute times for a directed graph using an asymmetric Laplacian. Linear Algebra Appl. 435(2), 224\u2013242 (2011)","journal-title":"Linear Algebra Appl."},{"key":"3_CR7","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/9780262033589.001.0001","volume-title":"Semi-Supervised Learning","author":"O Chapelle","year":"2006","unstructured":"Chapelle, O., Sch\u00f6lkopf, B., Zien, A.: Semi-Supervised Learning. MIT Press, Cambridge (2006)"},{"issue":"3","key":"3_CR8","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/j.aam.2010.11.001","volume":"47","author":"P Chebotarev","year":"2011","unstructured":"Chebotarev, P.: The graph bottleneck identity. Adv. Appl. Math. 47(3), 403\u2013413 (2011)","journal-title":"Adv. Appl. Math."},{"issue":"3","key":"3_CR9","first-page":"403","volume":"47","author":"P Chebotarev","year":"2011","unstructured":"Chebotarev, P.: A class of graph-geodetic distances generalizing the shortest-path and the resistance distances. Discrete Appl. Math. 47(3), 403\u2013413 (2011)","journal-title":"Discrete Appl. Math."},{"issue":"10\u201311","key":"3_CR10","doi-asserted-by":"crossref","first-page":"1484","DOI":"10.1016\/j.dam.2012.02.015","volume":"160","author":"P Chebotarev","year":"2012","unstructured":"Chebotarev, P.: The walk distances in graphs. Discrete Appl. Math. 160(10\u201311), 1484\u20131500 (2012)","journal-title":"Discrete Appl. Math."},{"key":"3_CR11","unstructured":"Chebotarev, P. Yu., Shamis, E.V.: On the proximity measure for graph vertices provided by the inverse Laplacian characteristic matrix. In: Abstracts of the conference \u201cLinear Algebra and its Application\u201d, 10\u201312 June 1995, The Institute of Mathematics and its Applications, in conjunction with the Manchester Center for Computational Mathematics, Manchester, UK (pp. 6\u20137), URL http:\/\/www.ma.man.ac.uk\/higham\/laa95\/abstracts.ps (1995)"},{"issue":"9","key":"3_CR12","first-page":"1505","volume":"58","author":"PY Chebotarev","year":"1997","unstructured":"Chebotarev, P.Y., Shamis, E.V.: The matrix-forest theorem and measuring relations in small social groups. Autom. Remote Control 58(9), 1505\u20131514 (1997)","journal-title":"Autom. Remote Control"},{"issue":"4","key":"3_CR13","first-page":"608","volume":"59","author":"PY Chebotarev","year":"1998","unstructured":"Chebotarev, P.Y., Shamis, E.V.: On a duality between metrics and $$\\varSigma $$ -proximities. Autom. Remote Control 59(4), 608\u2013612 (1998)","journal-title":"Autom. Remote Control"},{"issue":"10","key":"3_CR14","first-page":"1443","volume":"59","author":"PY Chebotarev","year":"1998","unstructured":"Chebotarev, P.Y., Shamis, E.V.: On proximity measures for graph vertices. Autom. Remote Control 59(10), 1443\u20131459 (1998)","journal-title":"Autom. Remote Control"},{"key":"3_CR15","doi-asserted-by":"crossref","unstructured":"Chung, F.: Spectral graph theory, vol. 92. American Math. Soc. (1997)","DOI":"10.1090\/cbms\/092"},{"issue":"50","key":"3_CR16","doi-asserted-by":"crossref","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."},{"key":"3_CR17","unstructured":"Deza, M., Chebotarev, P.: Protometrics. arXiv preprint arXiv:1112.4829 (2011)"},{"key":"3_CR18","first-page":"357","volume":"2","author":"IS Dhillon","year":"2001","unstructured":"Dhillon, I.S., Fan, J., Guan, Y.: Efficient clustering of very large document collections. Data Min. sci. Eng. Appl. 2, 357\u2013381 (2001)","journal-title":"Data Min. sci. Eng. Appl."},{"key":"3_CR19","first-page":"551","volume":"2004","author":"IS Dhillon","year":"2004","unstructured":"Dhillon, I.S., Guan, Y., Kulis, B.: Kernel k-means: spectral clustering and normalized cuts. Proc. ACM KDD 2004, 551\u2013556 (2004)","journal-title":"Proc. ACM KDD"},{"key":"3_CR20","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.cplett.2007.03.098","volume":"439","author":"E Estrada","year":"2007","unstructured":"Estrada, E., Hatano, N.: Statistical-mechanical approach to subgraph centrality in complex networks. Chem. Phys. Lett. 439, 247\u2013251 (2007)","journal-title":"Chem. Phys. Lett."},{"issue":"3","key":"3_CR21","doi-asserted-by":"crossref","first-page":"036111","DOI":"10.1103\/PhysRevE.77.036111","volume":"77","author":"E Estrada","year":"2008","unstructured":"Estrada, E., Hatano, N.: Communicability in complex networks. Phys. Rev. E 77(3), 036111 (2008)","journal-title":"Phys. Rev. E"},{"key":"3_CR22","doi-asserted-by":"crossref","first-page":"1581","DOI":"10.1016\/j.jmaa.2016.12.062","volume":"449","author":"E Estrada","year":"2017","unstructured":"Estrada, E., Silver, G.: Accounting for the role of long walks on networks via a new matrix function. J. Math. Anal. Appl. 449, 1581\u20131600 (2017)","journal-title":"J. Math. Anal. Appl."},{"key":"3_CR23","doi-asserted-by":"crossref","unstructured":"Fouss, F., Yen L., Pirotte, A., Saerens, M.: An experimental investigation of graph kernels on a collaborative recommendation task. In: Proceedings of the Sixth International Conference on Data Mining (ICDM 2006), pp. 863\u2013868, IEEE (2006)","DOI":"10.1109\/ICDM.2006.18"},{"key":"3_CR24","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781316418321","volume-title":"Algorithms and Models for Network Data and Link Analysis","author":"F Fouss","year":"2016","unstructured":"Fouss, F., Saerens, M., Shimbo, M.: Algorithms and Models for Network Data and Link Analysis. Cambridge University Press, Cambridge (2016)"},{"key":"3_CR25","volume-title":"Matrix Analysis","author":"RA Horn","year":"2013","unstructured":"Horn, R.A., Johnson, C.R.: Matrix Analysis, 2nd edn. Cambridge University Press, Cambridge (2013)","edition":"2"},{"key":"3_CR26","series-title":"Springer Proceedings in Mathematics & Statistics","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/978-3-319-56829-4_8","volume-title":"Models, Algorithms and Technologies for Network Analysis","author":"V Ivashkin","year":"2017","unstructured":"Ivashkin, V., Chebotarev, P.: Do logarithmic proximity measures outperform plain ones in graph clustering? In: Kalyagin, V.A., et al. (eds.) Models, Algorithms and Technologies for Network Analysis. Springer Proceedings in Mathematics & Statistics, vol. 197, pp. 87\u2013105. Springer, Cham (2017)"},{"key":"3_CR27","unstructured":"Jacobsen, K., Tien, J.: A generalized inverse for graphs with absorption. arXiv preprint arXiv:1611.02233 (2016)"},{"issue":"1","key":"3_CR28","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF02289026","volume":"18","author":"L Katz","year":"1953","unstructured":"Katz, L.: A new status index derived from sociometric analysis. Psychometrika 18(1), 39\u201343 (1953)","journal-title":"Psychometrika"},{"key":"3_CR29","doi-asserted-by":"crossref","DOI":"10.1201\/b13054","volume-title":"Group Inverses of M-matrices and Their Applications","author":"SJ Kirkland","year":"2012","unstructured":"Kirkland, S.J., Neumann, M.: Group Inverses of M-matrices and Their Applications. CRC Press, Boca Raton (2012)"},{"key":"3_CR30","doi-asserted-by":"crossref","first-page":"600616","DOI":"10.1016\/j.physa.2013.09.016","volume":"393","author":"I Kivim\u00e4ki","year":"2014","unstructured":"Kivim\u00e4ki, I., Shimbo, M., Saerens, M.: Developments in the theory of randomized shortest paths with a comparison of graph node distances. Phys. A 393, 600616 (2014)","journal-title":"Phys. A"},{"key":"3_CR31","unstructured":"Kondor, R.I., Lafferty, J.: Diffusion kernels on graphs and other discrete input spaces. In: Proceedings of ICML, pp. 315\u2013322 (2002)"},{"issue":"2","key":"3_CR32","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1137\/S089548019426303X","volume":"11","author":"C Lenart","year":"1998","unstructured":"Lenart, C.: A generalized distance in graphs and centered partitions. SIAM J. Discrete Math. 11(2), 293\u2013304 (1998)","journal-title":"SIAM J. Discrete Math."},{"issue":"7","key":"3_CR33","doi-asserted-by":"crossref","first-page":"1019","DOI":"10.1002\/asi.20591","volume":"58","author":"D Liben-Nowell","year":"2007","unstructured":"Liben-Nowell, D., Kleinberg, J.: The link-prediction problem for social networks. J. Assoc. Inform. Sci. Technol. 58(7), 1019\u20131031 (2007)","journal-title":"J. Assoc. Inform. Sci. Technol."},{"issue":"3","key":"3_CR34","doi-asserted-by":"crossref","first-page":"724","DOI":"10.2307\/1968654","volume":"36","author":"IJ Schoenberg","year":"1935","unstructured":"Schoenberg, I.J.: Remarks to Maurice Fr\u00e9chet\u2019s article \u201cSur la d\u00e9finition axiomatique d\u2019une classe d\u2019espace distanci\u00e9s vectoriellement applicable sur l\u2019espace de Hilbert\u201d. Ann. Math. 36(3), 724\u2013732 (1935)","journal-title":"Ann. Math."},{"issue":"3","key":"3_CR35","doi-asserted-by":"crossref","first-page":"522","DOI":"10.1090\/S0002-9947-1938-1501980-0","volume":"44","author":"IJ Schoenberg","year":"1938","unstructured":"Schoenberg, I.J.: Metric spaces and positive definite functions. Trans. Am. Math. Soc. 44(3), 522\u2013536 (1938)","journal-title":"Trans. Am. Math. Soc."},{"key":"3_CR36","unstructured":"Saerens, M.: Personal communication"},{"key":"3_CR37","unstructured":"Kandola, J., Shawe-Taylor, J., Cristianini, N.: Learning semantic similarity. In: Neural Information Processing Systems 15 (NIPS 2015). MIT Press (2002)"},{"key":"3_CR38","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511809682","volume-title":"Kernel Methods for Pattern Analysis","author":"J Shawe-Taylor","year":"2004","unstructured":"Shawe-Taylor, J., Cristianini, N.: Kernel Methods for Pattern Analysis. Cambridge University Press, Cambridge (2004)"},{"key":"3_CR39","doi-asserted-by":"crossref","unstructured":"Smola, A.J., Kondor, R.: Kernels and regularization on graphs. In: Learning Theory and Kernel Machines, pp. 144\u2013158 (2003)","DOI":"10.1007\/978-3-540-45167-9_12"},{"key":"3_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"192","DOI":"10.1007\/978-3-319-44778-0_23","volume-title":"Artificial Neural Networks and Machine Learning \u2013 ICANN 2016","author":"F Sommer","year":"2016","unstructured":"Sommer, F., Fouss, F., Saerens, M.: Comparison of graph node distances on clustering tasks. In: Villa, A.E.P., Masulli, P., Pons Rivero, A.J. (eds.) ICANN 2016. LNCS, vol. 9886, pp. 192\u2013201. Springer, Cham (2016). doi: 10.1007\/978-3-319-44778-0_23"},{"key":"3_CR41","first-page":"1201","volume":"11","author":"SVN Vishwanathan","year":"2010","unstructured":"Vishwanathan, S.V.N., Schraudolph, N.N., Kondor, R., Borgwardt, K.M.: Graph kernels. J. Mach. Learn. Res. 11, 1201\u20131242 (2010)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"3_CR42","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","volume":"17","author":"U Luxburg von","year":"2007","unstructured":"von Luxburg, U.: A tutorial on spectral clustering. Stat. Comput. 17(4), 395\u2013416 (2007)","journal-title":"Stat. Comput."},{"key":"3_CR43","unstructured":"Zhou, D., Sch\u00f6lkopf, B., Hofmann, T.: Semi-supervised learning on directed graphs. In: Proceeedings of NIPS, pp. 1633\u20131640 (2004)"},{"issue":"2","key":"3_CR44","doi-asserted-by":"crossref","first-page":"181","DOI":"10.1109\/72.914517","volume":"12","author":"K-R M\u00fcller","year":"2001","unstructured":"M\u00fcller, K.-R., Mika, S., R\u00e4tsch, G., Tsuda, K., Sch\u00f6lkopf, B.: An Introduction to kernel-based learning algorithms. IEEE Trans. Neural Networks 12(2), 181\u2013202 (2001)","journal-title":"IEEE Trans. Neural Networks"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Models for the Web Graph"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-67810-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,3]],"date-time":"2019-10-03T00:00:18Z","timestamp":1570060818000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-67810-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319678092","9783319678108"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-67810-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017]]}}}