{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,17]],"date-time":"2026-09-17T10:42:03Z","timestamp":1789641723977,"version":"4.0.0"},"reference-count":84,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>Much of social network analysis is---implicitly or explicitly---predicated on the assumption that individuals tend to be more similar to their friends than to strangers. Thus, an observed social network provides a noisy signal about the latent underlying \u201csocial space''---the way in which individuals are similar or dissimilar. Many research questions frequently addressed via social network analysis are in reality questions about this social space, raising the question of inverting the process: Given a social network, how accurately can we reconstruct the social structure of similarities and dissimilarities? We begin to address this problem formally. Observed social networks are usually multiplex, in the sense that they reflect (dis)similarities in several different \u201ccategories,\u201d such as geographical proximity, kinship, or similarity of professions\/hobbies. We assume that each such category is characterized by a latent metric capturing (dis)similarities in this category. Each category gives rise to a separate social network: a random graph parameterized by this metric. For a concrete model, we consider Kleinberg's small world model and some variations thereof. The observed social network is the unlabeled union of these graphs; i.e., the presence or absence of edges can be observed, but not their origins. Our main result is an efficient algorithm which reconstructs each metric with provably low distortion.<\/jats:p>","DOI":"10.1137\/130949191","type":"journal-article","created":{"date-parts":[[2015,6,2]],"date-time":"2015-06-02T12:27:38Z","timestamp":1433248058000},"page":"617-668","source":"Crossref","is-referenced-by-count":5,"title":["Low-Distortion Inference of Latent Similarities from a Multiplex Social Network"],"prefix":"10.1137","volume":"44","author":[{"given":"Ittai","family":"Abraham","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shiri","family":"Chechik","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Kempe","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aleksandrs","family":"Slivkins","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,6,2]]},"reference":[{"key":"atypb1","first-page":"49","author":"Abraham I.","year":"2005","journal-title":"New York"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(03)00009-1"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.01.007"},{"key":"atypb4","first-page":"37","author":"Arora S.","year":"2012","journal-title":"New York"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2006.174"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"L. Backstrom, E. Sun, and C. Marlow,\n                      Find me if you can: Improving geographical prediction with social and spatial proximity\n                      , in Proceedings of the 19th International World Wide Web Conference, 2010, pp. 61-70.","DOI":"10.1145\/1772690.1772698"},{"key":"atypb7","unstructured":"M.F. Balcan, C. Borgs, M. Braverman, J. Chayes, and S.H. Teng,\n                      I like her more than you: Self-determined communities\n                      , in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2012."},{"key":"atypb8","first-page":"574","author":"Barbella D.","year":"2007","journal-title":"Japan"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2010.11.002"},{"key":"atypb10","unstructured":"P. M. Blau,\n                      Inequality and Heterogeneity: A Primitive Theory of Social Structure\n                      , Free Press, New York, 1977."},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"U. Brandes and T. Erlebach, eds.\n                      Network Analysis\n                      , Springer, New York, 2005.","DOI":"10.1007\/b106453"},{"key":"atypb12","first-page":"313","author":"Butts C. T.","year":"2003","journal-title":"Washington, DC"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-9531.2006.00187.x"},{"key":"atypb14","first-page":"762","author":"Chan H. T.-H.","year":"2005","journal-title":"Philadelphia"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1038\/nature06830"},{"key":"atypb16","first-page":"15","author":"Dabek F.","year":"2004","journal-title":"New York"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2005\/09\/P09008"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"D. P. Dubhashi and A. Panconesi,\n                      Concentration of Measure for the Analysis of Randomized Algorithms\n                      , Cambridge University Press, Cambridge, UK, 2009.","DOI":"10.1017\/CBO9780511581274"},{"key":"atypb19","first-page":"225","author":"Duchon P.","year":"2006","journal-title":"New York"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1985.10477129"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"key":"atypb22","doi-asserted-by":"crossref","unstructured":"S. Fortunato and C. Castellano,\n                      Community structure in graphs\n                      , in Encyclopedia of Complexity and System Science, R. Meyers, ed., Springer, New York, 2009.","DOI":"10.1007\/978-0-387-30440-3_76"},{"key":"atypb23","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud,\n                      Small worlds as navigable augmented networks: Model, analysis, and validation\n                      , in Proceedings of the 15th European Symposium on Algorithms, 2007, pp. 2-11.","DOI":"10.1007\/978-3-540-75520-3_2"},{"key":"atypb24","first-page":"62","author":"Fraigniaud P.","year":"2008","journal-title":"New York"},{"key":"atypb25","first-page":"1","author":"Fraigniaud P.","year":"2007","journal-title":"New York"},{"key":"atypb26","first-page":"169","author":"Fraigniaud P.","year":"2004","journal-title":"New York"},{"key":"atypb27","first-page":"240","author":"Fraigniaud P.","year":"2009","journal-title":"New York"},{"key":"atypb28","first-page":"389","author":"Fraigniaud P.","year":"2010","journal-title":"New York"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"P. Fraigniaud, E. Lebhar, and Z. Lotker,\n                      A doubling dimension threshold $\\Theta(\\log \\log n)$ for augmented graph navigability\n                      , in Proceedings of the 14th European Symposium on Algorithms, 2006, pp. 376-386.","DOI":"10.1007\/11841036_35"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.01.009"},{"key":"atypb31","first-page":"393","author":"Giakkoupis G.","year":"2011","journal-title":"New York"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1287\/mksc.2013.0817"},{"key":"atypb33","first-page":"534","author":"Gupta A.","year":"2003","journal-title":"Washington, DC"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-985X.2007.00471.x"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1198\/016214502388618906"},{"key":"atypb36","first-page":"177","author":"Indyk P.","year":"2004","journal-title":"Boca Raton, FL"},{"key":"atypb37","first-page":"741","author":"Karger D. R.","year":"2002","journal-title":"New York"},{"key":"atypb38","first-page":"471","author":"Kempe D.","year":"2002","journal-title":"Washington, DC"},{"key":"atypb39","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039491"},{"key":"atypb40","first-page":"1209","author":"Kermarrec A.-M.","year":"2011","journal-title":"New York"},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1038\/35022643"},{"key":"atypb42","first-page":"163","author":"Kleinberg J.","year":"2000","journal-title":"New York"},{"key":"atypb43","first-page":"431","author":"Kleinberg J.","year":"2001","journal-title":"Canada"},{"key":"atypb44","unstructured":"J. Kleinberg,\n                      Complex networks and decentralized search algorithms\n                      , in Proceedings of the International Congress of Mathematicians (ICM), 2006."},{"key":"atypb45","doi-asserted-by":"publisher","DOI":"10.1145\/1568318.1568322"},{"key":"atypb46","first-page":"798","author":"Krauthgamer R.","year":"2004","journal-title":"Philadelphia"},{"key":"atypb47","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2009.04.001"},{"key":"atypb48","doi-asserted-by":"crossref","unstructured":"R. Kumar, D. Liben-Nowell, and A. Tomkins,\n                      Navigating low-dimensional and hierarchical population networks\n                      , in Proceedings of the 14th European Symposium on Algorithms, 2006, pp. 480-491.","DOI":"10.1007\/11841036_44"},{"key":"atypb49","first-page":"18","author":"Lazarsfeld P.","year":"1954","journal-title":"New York"},{"key":"atypb50","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.019"},{"key":"atypb51","doi-asserted-by":"crossref","unstructured":"E. Lebhar and N. Schabanel,\n                      Graph augmentation via metrics embedding\n                      , in Proceedings of the 12th International Conference on Principles of Distributed Systems (OPODIS), 2008, pp. 217-225.","DOI":"10.1007\/978-3-540-92221-6_15"},{"key":"atypb52","first-page":"435","author":"D","year":"2010","journal-title":"New York"},{"key":"atypb53","doi-asserted-by":"publisher","DOI":"10.1002\/asi.20591"},{"key":"atypb54","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0503018102"},{"key":"atypb55","first-page":"1815","author":"Liu K.","year":"2011","journal-title":"New York"},{"key":"atypb56","first-page":"54","author":"Manku G. S.","year":"2004","journal-title":"New York"},{"key":"atypb57","first-page":"127","volume":"22","author":"Marsden P.","year":"1993","journal-title":"Sociolog. Measures Res."},{"key":"atypb58","first-page":"213","author":"McFarland D. D.","year":"1973","journal-title":"New York"},{"key":"atypb59","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"key":"atypb60","first-page":"223","author":"Minor M. J.","year":"1983","journal-title":"New York"},{"key":"atypb61","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2007.01.009"},{"key":"atypb62","first-page":"170","author":"Ng T. S. E.","year":"2002","journal-title":"Washington, DC"},{"key":"atypb63","first-page":"311","author":"Nguyen V.","year":"2005","journal-title":"Philadelphia"},{"key":"atypb64","doi-asserted-by":"publisher","DOI":"10.1080\/10618600.2012.679240"},{"key":"atypb65","unstructured":"E. Rogers,\n                      Diffusion of Innovations\n                      , 4th ed., Free Press, New York, 1995."},{"key":"atypb66","first-page":"295","author":"Sarkar P.","year":"2010","journal-title":"Israel"},{"key":"atypb67","unstructured":"P. Sarkar and A. W. Moore,\n                      Dynamic social network analysis using latent space models\n                      , in Proceedings of the 17th Conference on Advances in Neural Information Processing Systems, 2005."},{"key":"atypb68","doi-asserted-by":"publisher","DOI":"10.1016\/j.cosrev.2007.05.001"},{"key":"atypb69","doi-asserted-by":"publisher","DOI":"10.1145\/163381.163402"},{"key":"atypb70","doi-asserted-by":"publisher","DOI":"10.1111\/j.0081-1750.2003.00134.x"},{"key":"atypb71","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-006-0015-8"},{"key":"atypb72","first-page":"89","author":"Slivkins A.","year":"2007","journal-title":"New York"},{"key":"atypb73","first-page":"129","volume":"37","author":"T. A.","year":"2011","journal-title":"Ann. Rev. Sociol."},{"key":"atypb74","first-page":"766","author":"A","year":"2006","journal-title":"Philadelphia"},{"key":"atypb75","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1004008107"},{"key":"atypb76","first-page":"281","author":"Talwar K.","year":"2004","journal-title":"New York"},{"key":"atypb77","first-page":"817","author":"Tang L.","year":"2009","journal-title":"New York"},{"key":"atypb78","doi-asserted-by":"publisher","DOI":"10.1126\/science.1070120"},{"key":"atypb79","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"atypb80","first-page":"207","volume":"9","author":"Wellman B.","year":"1992","journal-title":"Adv. Group Processes"},{"key":"atypb81","doi-asserted-by":"publisher","DOI":"10.1086\/229572"},{"key":"atypb82","first-page":"85","author":"Wong B.","year":"2005","journal-title":"New York"},{"key":"atypb83","doi-asserted-by":"publisher","DOI":"10.1137\/090772009"},{"key":"atypb84","doi-asserted-by":"crossref","unstructured":"U. Zwick,\n                      Exact and approximate distances in graphs-a survey\n                      , in Proceedings of the 9th European Symposium on Algorithms, 2001, pp. 33-48.","DOI":"10.1007\/3-540-44676-1_3"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130949191","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:04:02Z","timestamp":1787339042000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130949191"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":84,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/130949191"],"URL":"https:\/\/doi.org\/10.1137\/130949191","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}