{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:13:32Z","timestamp":1750306412091,"version":"3.41.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2015,4,1]],"date-time":"2015-04-01T00:00:00Z","timestamp":1427846400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"111 International Collaboration Program of China"},{"name":"ARO under MURI W911NF-08-1-0233"},{"name":"Prospective Research Project on Future Networks of Jiangsu Future Networks Innovation Institute"},{"name":"Application Foundation Research Program of SuZhou (SYG201311)"},{"name":"ARL Cooperative Agreement W911NF-09-2-0053"},{"name":"National Natural Science Foundation of China","award":["61103240, 61103241, 61221063, 91118005, 61221063, U1301254"],"award-info":[{"award-number":["61103240, 61103241, 61221063, 91118005, 61221063, U1301254"]}]},{"name":"NSF","award":["CNS-1065133"],"award-info":[{"award-number":["CNS-1065133"]}]},{"name":"863 High Tech Development Plan (2012AA011003)"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2015,4,13]]},"abstract":"<jats:p>Characterizing user pair relationships is important for applications such as friend recommendation and interest targeting in online social networks (OSNs). Due to the large-scale nature of such networks, it is infeasible to enumerate all user pairs and thus sampling is used. In this article, we show that it is a great challenge for OSN service providers to characterize user pair relationships, even when they possess the complete graph topology. The reason is that when sampling techniques (i.e., uniform vertex sampling (UVS) and random walk (RW)) are naively applied, they can introduce large biases, particularly for estimating similarity distribution of user pairs with constraints like existence of mutual neighbors, which is important for applications such as identifying network homophily. Estimating statistics of user pairs is more challenging in the absence of the complete topology information, as an unbiased sampling technique like UVS is usually not allowed and exploring the OSN graph topology is expensive. To address these challenges, we present unbiased sampling methods to characterize user pair properties based on UVS and RW techniques. We carry out an evaluation of our methods to show their accuracy and efficiency. Finally, we apply our methods to three OSNs\u2014Foursquare, Douban, and Xiami\u2014and discover that significant homophily is present in these networks.<\/jats:p>","DOI":"10.1145\/2700393","type":"journal-article","created":{"date-parts":[[2015,4,3]],"date-time":"2015-04-03T20:29:44Z","timestamp":1428092984000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Unbiased Characterization of Node Pairs over Large Graphs"],"prefix":"10.1145","volume":"9","author":[{"given":"Pinghui","family":"Wang","sequence":"first","affiliation":[{"name":"Noah\u2019s Ark Lab, Huawei, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Junzhou","family":"Zhao","sequence":"additional","affiliation":[{"name":"Xi\u2019an Jiaotong University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"John C. S.","family":"Lui","sequence":"additional","affiliation":[{"name":"Chinese University of Hong Kong, Shatin, Hong Kong"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Don","family":"Towsley","sequence":"additional","affiliation":[{"name":"University of Massachusetts Amherst, MA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiaohong","family":"Guan","sequence":"additional","affiliation":[{"name":"Xi\u2019an Jiaotong University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060693"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242685"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-18009-5_10"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144503423264"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","first-page":"327","DOI":"10.1080\/00031305.1995.10476177","article-title":"Understanding the Metropolis-Hastings algorithm","volume":"49","author":"Chib Siddhartha","year":"1995","unstructured":"Siddhartha Chib and Edward Greenberg . 1995 . Understanding the Metropolis-Hastings algorithm . American Statistician 49 , 4, 327 -- 335 . Siddhartha Chib and Edward Greenberg. 1995. Understanding the Metropolis-Hastings algorithm. American Statistician 49, 4, 327--335.","journal-title":"American Statistician"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111012"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833840"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.peva.2005.01.002"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1011122126881"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1093\/biomet\/57.1.97"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1525\/sp.2002.49.1.11"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1214\/154957804100000051"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972818.11"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993744.1993773"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the International Teletraffic Congress. 1--8.","author":"Kurant Maciej","year":"2010","unstructured":"Maciej Kurant , Athina Markopoulou , and Patrick Thiran . 2010 . On the bias of BFS (breadth first search) and of other graph sampling techniques . In Proceedings of the International Teletraffic Congress. 1--8. Maciej Kurant, Athina Markopoulou, and Patrick Thiran. 2010. On the bias of BFS (breadth first search) and of other graph sampling techniques. In Proceedings of the International Teletraffic Congress. 1--8."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSAC.2011.111005"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254756.2254795"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150479"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367620"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772756"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1753326.1753532"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_26_1","first-page":"1","article-title":"Random walks on graphs: A survey","volume":"2","author":"Lov\u00e1sz Laszlo","year":"1993","unstructured":"Laszlo Lov\u00e1sz . 1993 . Random walks on graphs: A survey . Combinatorics 2 , 1 -- 46 . Laszlo Lov\u00e1sz. 1993. Random walks on graphs: A survey. Combinatorics 2, 1--46.","journal-title":"Combinatorics"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1146381.1146402"},{"key":"e_1_2_1_28_1","first-page":"1087","article-title":"Equations of state calculations by fast computing machines","volume":"21","author":"Metropolis Nicholas","year":"2011","unstructured":"Nicholas Metropolis , Arianna W. Rosenbluth , Marshall N. Rosenbluth , Augusta H. Teller , and Edward Teller . 2011 . Equations of state calculations by fast computing machines . IEEE Journal on Selected Areas in Communications 21 , 6, 1087 -- 1092 . Nicholas Metropolis, Arianna W. Rosenbluth, Marshall N. Rosenbluth, Augusta H. Teller, and Edward Teller. 2011. Equations of state calculations by fast computing machines. IEEE Journal on Selected Areas in Communications 21, 6, 1087--1092.","journal-title":"IEEE Journal on Selected Areas in Communications"},{"key":"e_1_2_1_29_1","volume-title":"Tweedie","author":"Meyn Sean","year":"2009","unstructured":"Sean Meyn and Richard L . Tweedie . 2009 . Markov Chains and Stochastic Stability. Cambridge University Press . Sean Meyn and Richard L. Tweedie. 2009. Markov Chains and Stochastic Stability. Cambridge University Press."},{"key":"e_1_2_1_30_1","first-page":"60","article-title":"The small world problem","volume":"2","author":"Milgram Stanley","year":"1967","unstructured":"Stanley Milgram . 1967 . The small world problem . Psychology Today 2 , 1, 60 -- 67 . Stanley Milgram. 1967. The small world problem. Psychology Today 2, 1, 60--67.","journal-title":"Psychology Today"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879191"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2009.5062215"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879192"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2012.6195540"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39718-2_23"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/4236.978369"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1214\/154957804100000024"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.0081-1750.2004.00152.x"},{"key":"e_1_2_1_40_1","volume-title":"Strauss","author":"Shi Xiaolin","year":"2007","unstructured":"Xiaolin Shi , Lada A. Adamic , and Martin J . Strauss . 2007 . Networks of strong ties. Physica A: Statistical Mechanics and its Applications 378, 1, 33--47. Xiaolin Shi, Lada A. Adamic, and Martin J. Strauss. 2007. Networks of strong ties. Physica A: Statistical Mechanics and its Applications 378, 1, 33--47."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367586"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNET.2008.2001730"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544874"},{"key":"e_1_2_1_45_1","volume-title":"Proceedings of IEEE Conference on Computer Communications Workshops. 941--946","author":"Zhao Junzhou","year":"2011","unstructured":"Junzhou Zhao , John C. S. Lui , Don Towsley , Xiaohong Guan , and Yadong Zhou . 2011 . Empirical analysis of the evolution of follower network: A case study on Douban . In Proceedings of IEEE Conference on Computer Communications Workshops. 941--946 . Junzhou Zhao, John C. S. Lui, Don Towsley, Xiaohong Guan, and Yadong Zhou. 2011. Empirical analysis of the evolution of follower network: A case study on Douban. In Proceedings of IEEE Conference on Computer Communications Workshops. 941--946."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1151374.1151386"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700393","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2700393","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T05:07:44Z","timestamp":1750223264000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2700393"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,4]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,4,13]]}},"alternative-id":["10.1145\/2700393"],"URL":"https:\/\/doi.org\/10.1145\/2700393","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2015,4]]},"assertion":[{"value":"2014-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-04-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}