{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,26]],"date-time":"2026-08-26T05:27:48Z","timestamp":1787722068006,"version":"build-2784847793"},"publisher-location":"Berlin, Heidelberg","reference-count":50,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642342127","type":"print"},{"value":"9783642342134","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-34213-4_13","type":"book-chapter","created":{"date-parts":[[2012,11,6]],"date-time":"2012-11-06T00:59:15Z","timestamp":1352163555000},"page":"191-206","source":"Crossref","is-referenced-by-count":12,"title":["A Survey on Proximity Measures for Social Networks"],"prefix":"10.1007","author":[{"given":"Sara","family":"Cohen","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Benny","family":"Kimelfeld","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Georgia","family":"Koutrika","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"13_CR1","unstructured":"Adamic, L., Adar, E.: How to search a social network. In: VLDB, pp. 217\u2013225 (1987)"},{"issue":"2","key":"13_CR2","doi-asserted-by":"publisher","first-page":"890","DOI":"10.1137\/050643799","volume":"45","author":"K. Avrachenkov","year":"2007","unstructured":"Avrachenkov, K., Litvak, N., Nemirovsky, D., Osipova, N.: Monte carlo methods in pagerank computation: When one iteration is sufficient. SIAM J. Numer. Anal.\u00a045(2), 890\u2013904 (2007)","journal-title":"SIAM J. Numer. Anal."},{"key":"13_CR3","doi-asserted-by":"crossref","unstructured":"Bahmani, B., Chakrabarti, K., Xin, D.: Fast personalized pagerank on mapreduce. In: SIGMOD Conference, pp. 973\u2013984 (2011)","DOI":"10.1145\/1989323.1989425"},{"issue":"3","key":"13_CR4","first-page":"173","volume":"4","author":"B. Bahmani","year":"2010","unstructured":"Bahmani, B., Chowdhury, A., Goel, A.: Fast incremental and personalized pagerank. PVLDB\u00a04(3), 173\u2013184 (2010)","journal-title":"PVLDB"},{"issue":"3","key":"13_CR5","doi-asserted-by":"publisher","first-page":"289","DOI":"10.1109\/TR.2003.816403","volume":"52","author":"A.O. Balan","year":"2003","unstructured":"Balan, A.O., Traldi, L.: Preprocessing minpaths for sum of disjoint products. IEEE Trans. Reliability\u00a052(3), 289\u2013295 (2003)","journal-title":"IEEE Trans. Reliability"},{"issue":"3-4","key":"13_CR6","doi-asserted-by":"publisher","first-page":"590","DOI":"10.1016\/S0378-4371(02)00736-7","volume":"311","author":"A.L. Barabasi","year":"2002","unstructured":"Barabasi, A.L., Jeong, H., Neda, Z., Ravasz, E., Schubert, A., Vicsek, T.: Evolution of the social network of scientific collaborations. Physica A\u00a0311(3-4), 590\u2013614 (2002)","journal-title":"Physica A"},{"key":"13_CR7","doi-asserted-by":"crossref","unstructured":"Brander, A., Sinclair, M.: A comparative study of k-shortest path algorithms. In: Proc. 11th UK Performance Engineering Workshop for Computer and Telecommunications Systems (1995)","DOI":"10.1007\/978-1-4471-1007-1_25"},{"key":"13_CR8","doi-asserted-by":"publisher","first-page":"1227","DOI":"10.1145\/1645953.1646109","volume-title":"Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM 2009","author":"D. Carmel","year":"2009","unstructured":"Carmel, D., Zwerdling, N., Guy, I., Ofek-Koifman, S., Har\u2019el, N., Ronen, I., Uziel, E., Yogev, S., Chernov, S.: Personalized social search based on the user\u2019s social network. In: Proceedings of the 18th ACM Conference on Information and Knowledge Management, CIKM 2009, pp. 1227\u20131236. ACM, New York (2009), http:\/\/doi.acm.org\/10.1145\/1645953.1646109"},{"key":"13_CR9","unstructured":"Cohen, S., Kimelfeld, B., Koutrika, G., Vondr\u00e1k, J.: On principles of egocentric person search in social networks. In: First International Workshop on Searching and Integrating New Web Data Sources, Seattle, Washington (2011)"},{"key":"13_CR10","volume-title":"Communication Networks for Computers","author":"D. Davies","year":"1973","unstructured":"Davies, D., Barber, D.: Communication Networks for Computers. John Wiley, London (1973)"},{"key":"13_CR11","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1007\/BF01386390","volume":"1","author":"E.W. Dijkstra","year":"1959","unstructured":"Dijkstra, E.W.: A note on two problems in connexion with graphs. Numerische Mathematik\u00a01, 269\u2013271 (1959)","journal-title":"Numerische Mathematik"},{"issue":"10","key":"13_CR12","doi-asserted-by":"publisher","first-page":"855","DOI":"10.1109\/TCS.1979.1084573","volume":"26","author":"W.P. Dotson","year":"1979","unstructured":"Dotson, W.P., Gobien, J.O.: A new analysis technique for probabilistic graphs. IEEE Trans. Circuits and Systems\u00a026(10), 855\u2013865 (1979)","journal-title":"IEEE Trans. Circuits and Systems"},{"key":"13_CR13","doi-asserted-by":"crossref","unstructured":"Doyle, P., Snell, J.: Random walks and electical networks. The Mathematical Association of America (1984)","DOI":"10.5948\/UPO9781614440222"},{"issue":"2","key":"13_CR14","doi-asserted-by":"publisher","first-page":"652","DOI":"10.1137\/S0097539795290477","volume":"28","author":"D. Eppstein","year":"1998","unstructured":"Eppstein, D.: Finding the k shortest paths. SIAM J. Comput.\u00a028(2), 652\u2013673 (1998)","journal-title":"SIAM J. Comput."},{"key":"13_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"132","DOI":"10.1007\/978-3-642-18009-5_13","volume-title":"Algorithms and Models for the Web-Graph","author":"P. Esfandiar","year":"2010","unstructured":"Esfandiar, P., Bonchi, F., Gleich, D.F., Greif, C., Lakshmanan, L.V.S., On, B.-W.: Fast Katz and Commuters: Efficient Estimation of Social Relatedness in Large Networks. In: Kumar, R., Sivakumar, D. (eds.) WAW 2010. LNCS, vol.\u00a06516, pp. 132\u2013145. Springer, Heidelberg (2010)"},{"issue":"2","key":"13_CR16","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1109\/TR.1986.4335388","volume":"35","author":"G.S. Fishman","year":"1986","unstructured":"Fishman, G.S.: A comparison of four monte carlo methods for estimating the probability of s-t connectedness. IEEE Trans. Reliability\u00a035(2), 145\u2013155 (1986)","journal-title":"IEEE Trans. Reliability"},{"issue":"6","key":"13_CR17","doi-asserted-by":"publisher","first-page":"345","DOI":"10.1145\/367766.368168","volume":"5","author":"R.W. Floyd","year":"1962","unstructured":"Floyd, R.W.: Algorithm 97: Shortest path. Communications of the ACM\u00a05(6), 345 (1962)","journal-title":"Communications of the ACM"},{"key":"13_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"105","DOI":"10.1007\/978-3-540-30216-2_9","volume-title":"Algorithms and Models for the Web-Graph","author":"D. Fogaras","year":"2004","unstructured":"Fogaras, D., R\u00e1cz, B.: Towards Scaling Fully Personalized PageRank. In: Leonardi, S. (ed.) WAW 2004. LNCS, vol.\u00a03243, pp. 105\u2013117. Springer, Heidelberg (2004)"},{"key":"13_CR19","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1023\/A:1013470632383","volume":"7","author":"K.C. Foster","year":"2001","unstructured":"Foster, K.C., Muth, S.Q., Potterat, J.J., Rothenberg, R.B.: A faster katz status score algorithm. Computational and Mathematical Organization Theory\u00a07, 275\u2013285 (2001)","journal-title":"Computational and Mathematical Organization Theory"},{"key":"13_CR20","volume-title":"Communication, Transmission and Transportation Networks","author":"H. Frank","year":"1971","unstructured":"Frank, H., Frisch, I.: Communication, Transmission and Transportation Networks. Addison Wesley, Reading (1971)"},{"issue":"4","key":"13_CR21","first-page":"358","volume":"5","author":"J. Gao","year":"2012","unstructured":"Gao, J., Jim, R., Zhou, J., Yu, J.X., Jiang, X., Wang, T.: Relational approach for shortest path discovery over large graphs. PVLDB\u00a05(4), 358\u2013369 (2012)","journal-title":"PVLDB"},{"key":"13_CR22","unstructured":"Goldberg, A., Harrelsons, C.: Computing the shortest path: A* search meets graph theory. In: SODA (2005)"},{"key":"13_CR23","doi-asserted-by":"crossref","unstructured":"Gubichev, A., Bedathur, S.J., Seufert, S., Weikum, G.: Fast and accurate estimation of shortest paths in large graphs. In: CIKM, pp. 499\u2013508 (2010)","DOI":"10.1145\/1871437.1871503"},{"key":"13_CR24","doi-asserted-by":"crossref","first-page":"1373","DOI":"10.1145\/1978942.1979145","volume-title":"Proceedings of the 2011 Annual Conference on Human Factors in Computing Systems, CHI 2011","author":"I. Guy","year":"2011","unstructured":"Guy, I., Perer, A., Daniel, T., Greenshpan, O., Turbahn, I.: Guess who?: enriching the social graph through a crowdsourcing game. In: Proceedings of the 2011 Annual Conference on Human Factors in Computing Systems, CHI 2011, pp. 1373\u20131382. ACM, New York (2011), http:\/\/doi.acm.org\/10.1145\/1978942.1979145"},{"key":"13_CR25","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1002\/(SICI)1097-0037(199909)34:2<88::AID-NET2>3.0.CO;2-1","volume":"34","author":"E. Hadjiconstantinou","year":"1999","unstructured":"Hadjiconstantinou, E., Christofides, N.: An efficient implementation of an algorithm for finding k shortest simple paths. Networks\u00a034, 88\u2013101 (1999)","journal-title":"Networks"},{"key":"13_CR26","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1145\/775152.775191","volume-title":"Proceedings of the 12th International Conference on World Wide Web, WWW 2003","author":"G. Jeh","year":"2003","unstructured":"Jeh, G., Widom, J.: Scaling personalized web search. In: Proceedings of the 12th International Conference on World Wide Web, WWW 2003, pp. 271\u2013279. ACM, New York (2003), http:\/\/doi.acm.org\/10.1145\/775152.775191"},{"key":"13_CR27","doi-asserted-by":"crossref","unstructured":"Katoh, N., Ibaraki, T., Mine, H.: An efficient algorithm for k shortest simple paths. Networks\u00a012 (1982)","DOI":"10.1002\/net.3230120406"},{"key":"13_CR28","unstructured":"Katz, G.J., Kider Jr., J.T.: All-pairs shortest-paths for large graphs on the gpu. In: Graphics Hardware, pp. 47\u201355 (2008)"},{"issue":"1","key":"13_CR29","doi-asserted-by":"publisher","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\u00a018(1), 39\u201343 (1953)","journal-title":"Psychometrika"},{"key":"13_CR30","doi-asserted-by":"crossref","unstructured":"Koren, Y., North, S.C., Volinsky, C.: Measuring and extracting proximity graphs in networks. TKDD\u00a01(3) (2007)","DOI":"10.1145\/1297332.1297336"},{"key":"13_CR31","doi-asserted-by":"crossref","unstructured":"Liben-Nowell, D., Kleinberg, J.M.: The link-prediction problem for social networks. In: CIKM (2003)","DOI":"10.1145\/956863.956972"},{"issue":"7","key":"13_CR32","doi-asserted-by":"publisher","first-page":"1019","DOI":"10.1002\/asi.20591","volume":"58","author":"D. Liben-Nowell","year":"2007","unstructured":"Liben-Nowell, D., Kleinberg, J.M.: The link-prediction problem for social networks. JASIST\u00a058(7), 1019\u20131031 (2007)","journal-title":"JASIST"},{"key":"13_CR33","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511809071","volume-title":"Introduction to Information Retrieval","author":"C.D. Manning","year":"2008","unstructured":"Manning, C.D., Raghavan, P., Schtze, H.: Introduction to Information Retrieval. Cambridge University Press, New York (2008)"},{"issue":"2","key":"13_CR34","doi-asserted-by":"publisher","first-page":"226","DOI":"10.1080\/15427951.2004.10129088","volume":"1","author":"M. Mitzenmacher","year":"2004","unstructured":"Mitzenmacher, M.: A brief history of generative models for power law and lognormal distributions. Internet Mathematics\u00a01(2), 226\u2013251 (2004)","journal-title":"Internet Mathematics"},{"key":"13_CR35","unstructured":"Page, L., Brin, S., Motwani, R., Winograd, T.: The pagerank citation ranking: Bringing order to the web. Tech. rep., Stanford University (1998)"},{"key":"13_CR36","doi-asserted-by":"crossref","unstructured":"Potamias, M., Bonchi, F., Castillo, C., Gionis, A.: Fast shortest path distance estimation in large networks. In: CIKM (2009)","DOI":"10.1145\/1645953.1646063"},{"issue":"4","key":"13_CR37","doi-asserted-by":"publisher","first-page":"523","DOI":"10.1007\/BF02476440","volume":"15","author":"A. Rapoport","year":"1953","unstructured":"Rapoport, A.: Spread of information through a population with socio-structural bias i: Assumption of transitivity. Bulletin of Mathematical Biophysics\u00a015(4), 523\u2013533 (1953)","journal-title":"Bulletin of Mathematical Biophysics"},{"key":"13_CR38","doi-asserted-by":"crossref","unstructured":"Sarl\u00f3s, T., Bencz\u00far, A.A., Csalog\u00e1ny, K., Fogaras, D., R\u00e1z, B.: To randomize or not to randomize: space optimal summaries for hyperlink analysis. In: World Wide Web, pp. 297\u2013306 (2006)","DOI":"10.1145\/1135777.1135823"},{"key":"13_CR39","doi-asserted-by":"crossref","unstructured":"Song, H.H., Cho, T.W., Dave, V., Zhang, Y., Qiu, L.: Scalable proximity estimation and link prediction in online social networks. In: IMC (2009)","DOI":"10.1145\/1644893.1644932"},{"key":"13_CR40","unstructured":"Terruggia, R.: A comparison of four monte carlo methods for estimating the probability of s-t connectedness. Thesis. Universit\u00e0 degli Studi di Torino (2010)"},{"issue":"3","key":"13_CR41","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1137\/0208032","volume":"8","author":"L.G. Valiant","year":"1979","unstructured":"Valiant, L.G.: The complexity of enumeration and reliability problems. SIAM J. Comput.\u00a08(3), 410\u2013421 (1979)","journal-title":"SIAM J. Comput."},{"key":"13_CR42","doi-asserted-by":"crossref","unstructured":"Vieira, M.V., Fonseca, B.M., Damazio, R., Golgher, P.B., de Castro Reis, D., Ribeiro-Neto, B.A.: Efficient search ranking in social networks. In: CIKM, pp. 563\u2013572 (2007)","DOI":"10.1145\/1321440.1321520"},{"key":"13_CR43","doi-asserted-by":"crossref","unstructured":"Wang, C., Satuluri, V., Parthasarathy, S.: Local probabilistic models for link prediction. In: ICDM, pp. 322\u2013331 (2007)","DOI":"10.1109\/ICDM.2007.108"},{"key":"13_CR44","doi-asserted-by":"publisher","first-page":"981","DOI":"10.1145\/1772690.1772790","volume-title":"Proceedings of the 19th International Conference on World Wide Web, WWW 2010","author":"R. Xiang","year":"2010","unstructured":"Xiang, R., Neville, J., Rogati, M.: Modeling relationship strength in online social networks. In: Proceedings of the 19th International Conference on World Wide Web, WWW 2010, pp. 981\u2013990. ACM, New York (2010), http:\/\/doi.acm.org\/10.1145\/1772690.1772790"},{"key":"13_CR45","doi-asserted-by":"crossref","unstructured":"Xiao, Y., Wu, W., Pei, J., Wang, W., He, Z.: Efficiently indexing shortest paths by exploiting symmetry in graphs. In: EDBT (2009)","DOI":"10.1145\/1516360.1516418"},{"key":"13_CR46","doi-asserted-by":"crossref","unstructured":"Yen, J.Y.: Finding the k shortest loopless paths in a network. Management Science\u00a017 (1971)","DOI":"10.1287\/mnsc.17.11.712"},{"key":"13_CR47","unstructured":"Yen, J.Y.: Another algorithm for finding the k shortest loopless network paths. In: Proc. of 41st Mtg. Operations Research Society of America 20 (1972)"},{"key":"13_CR48","unstructured":"Zhao, X., Salaa, A., Wilson, C., Zheng, H., Zhao, B.Y.: Orion: Shortest path estimation for large social graphs. In: Proceedings of the 3rd Workshop on Online Social Networks, WOSN (2010)"},{"key":"13_CR49","doi-asserted-by":"crossref","unstructured":"Zhao, X., Salaa, A., Zheng, H., Zhao, B.Y.: Efficient shortest paths on massive social graphs. In: Proceedings of 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing, CollaborateCom (2011)","DOI":"10.4108\/icst.collaboratecom.2011.247162"},{"issue":"4","key":"13_CR50","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1140\/epjb\/e2009-00335-8","volume":"71","author":"T. Zhou","year":"2009","unstructured":"Zhou, T., L\u00fc, L., Zhang, Y.C.: Predicting missing links via local information. The European Physical Journal B\u2014Condensed Matter and Complex Systems\u00a071(4), 623\u2013630 (2009)","journal-title":"The European Physical Journal B\u2014Condensed Matter and Complex Systems"}],"container-title":["Lecture Notes in Computer Science","Search Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-34213-4_13.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,1,30]],"date-time":"2022-01-30T22:48:07Z","timestamp":1643582887000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-34213-4_13"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642342127","9783642342134"],"references-count":50,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-34213-4_13","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012]]}}}