{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,15]],"date-time":"2026-04-15T00:31:43Z","timestamp":1776213103829,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,11,1]],"date-time":"2012-11-01T00:00:00Z","timestamp":1351728000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["IIS-847925IIS-0916307CAREER CNS-0546216"],"award-info":[{"award-number":["IIS-847925IIS-0916307CAREER CNS-0546216"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000145","name":"Division of Information and Intelligent Systems","doi-asserted-by":"publisher","award":["IIS-847925IIS-0916307CAREER CNS-0546216"],"award-info":[{"award-number":["IIS-847925IIS-0916307CAREER CNS-0546216"]}],"id":[{"id":"10.13039\/100000145","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Web"],"published-print":{"date-parts":[[2012,11]]},"abstract":"<jats:p>Social networks are popular platforms for interaction, communication, and collaboration between friends. Researchers have recently proposed an emerging class of applications that leverage relationships from social networks to improve security and performance in applications such as email, Web browsing, and overlay routing. While these applications often cite social network connectivity statistics to support their designs, researchers in psychology and sociology have repeatedly cast doubt on the practice of inferring meaningful relationships from social network connections alone. This leads to the question: \u201cAre social links valid indicators of real user interaction? If not, then how can we quantify these factors to form a more accurate model for evaluating socially enhanced applications?\u201d In this article, we address this question through a detailed study of user interactions in the Facebook social network. We propose the use of \u201cinteraction graphs\u201d to impart meaning to online social links by quantifying user interactions. We analyze interaction graphs derived from Facebook user traces and show that they exhibit significantly lower levels of the \u201csmall-world\u201d properties present in their social graph counterparts. This means that these graphs have fewer \u201csupernodes\u201d with extremely high degree, and overall graph diameter increases significantly as a result. To quantify the impact of our observations, we use both types of graphs to validate several well-known social-based applications that rely on graph properties to infuse new functionality into Internet applications, including Reliable Email (RE), SybilGuard, and the weighted cascade influence maximization algorithm. The results reveal new insights into each of these systems, and confirm our hypothesis that to obtain realistic and accurate results, ongoing research on social network applications studies of social applications should use real indicators of user interactions in lieu of social graphs.<\/jats:p>","DOI":"10.1145\/2382616.2382620","type":"journal-article","created":{"date-parts":[[2012,12,4]],"date-time":"2012-12-04T20:10:57Z","timestamp":1354651857000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":121,"title":["Beyond Social Graphs"],"prefix":"10.1145","volume":"6","author":[{"given":"Christo","family":"Wilson","sequence":"first","affiliation":[{"name":"University of California Santa Barbara"}]},{"given":"Alessandra","family":"Sala","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara"}]},{"given":"Krishna P. N.","family":"Puttaswamy","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara"}]},{"given":"Ben Y.","family":"Zhao","sequence":"additional","affiliation":[{"name":"University of California Santa Barbara"}]}],"member":"320","published-online":{"date-parts":[[2012,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5210\/fm.v8i6.1057"},{"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":"crossref","unstructured":"Amaral L. A. N. Scala A. Barthelemy M. and Stanley H. E. 2000. Classes of small-world networks. Proc. Nat. Acad. Sci. 11149--11152. Amaral L. A. N. Scala A. Barthelemy M. and Stanley H. E. 2000. Classes of small-world networks. Proc. Nat. Acad. Sci. 11149--11152.","DOI":"10.1073\/pnas.200327197"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Conference on Weblogs and Social Media (ICWSM\u201911)","author":"Backstrom L.","unstructured":"Backstrom , L. , Bakshy , E. , Kleinberg , J. M. , Lento , T. M. , and Rosenn , I . 2011. Center of attention: How facebook users allocate attention across friends . In Proceedings of the International Conference on Weblogs and Social Media (ICWSM\u201911) . Backstrom, L., Bakshy, E., Kleinberg, J. M., Lento, T. M., and Rosenn, I. 2011. Center of attention: How facebook users allocate attention across friends. In Proceedings of the International Conference on Weblogs and Social Media (ICWSM\u201911)."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Barabasi A.-L. and Albert R. 1999. Emergence of scaling in random networks. Science 286. Barabasi A.-L. and Albert R. 1999. Emergence of scaling in random networks. Science 286 .","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644900"},{"key":"e_1_2_1_7_1","unstructured":"Boe B. and Wilson C. 2008. Crawl-E: Highly distributed web crawling framework written in python. Google Code. Boe B. and Wilson C. 2008. Crawl-E: Highly distributed web crawling framework written in python. Google Code."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Conference on the World Wide Web (WWW\u201900)","author":"Broder A.","unstructured":"Broder , A. , Kumar , R. , Maghoul , F. , Raghavan , P. , Rajagopalan , S. , Stata , R. , Tomkins , A. , and Wiener , J . 2000. Graph structure in the web: Experiments and models . In Proceedings of the International Conference on the World Wide Web (WWW\u201900) . Broder, A., Kumar, R., Maghoul, F., Raghavan, P., Rajagopalan, S., Stata, R., Tomkins, A., and Wiener, J. 2000. Graph structure in the web: Experiments and models. In Proceedings of the International Conference on the World Wide Web (WWW\u201900)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1526709.1526806"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the International Conference on the Weblogs and Social Media (ICWSM\u201910)","author":"Cha M.","unstructured":"Cha , M. , Haddadi , H. , Benevenuto , F. , and Gummadi , K. P . 2010. Measuring user influence in twitter: The million follower fallacy . In Proceedings of the International Conference on the Weblogs and Social Media (ICWSM\u201910) . Cha, M., Haddadi, H., Benevenuto, F., and Gummadi, K. P. 2010. Measuring user influence in twitter: The million follower fallacy. In Proceedings of the International Conference on the Weblogs and Social Media (ICWSM\u201910)."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the International Conference on the Weblogs and Social Media (ICWSM\u201911)","author":"Chang J.","unstructured":"Chang , J. and Sun , E . 2011. Location3: How users share and respond to location-based data on social networking sites . In Proceedings of the International Conference on the Weblogs and Social Media (ICWSM\u201911) . Chang, J. and Sun, E. 2011. Location3: How users share and respond to location-based data on social networking sites. In Proceedings of the International Conference on the Weblogs and Social Media (ICWSM\u201911)."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557047"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772722"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1452520.1452528"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/070710111"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:BTTJ.0000047585.06264.cc"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/646334.687813"},{"key":"e_1_2_1_18_1","unstructured":"Facebook. 2008. Statistics. facebook.com. Facebook . 2008. Statistics. facebook.com."},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201906)","author":"Garriss S.","unstructured":"Garriss , S. , Kaminsky , M. , Freedman , M. J. , Karp , B. , Mazi\u2018eres , D. , and Yu , H . 2006. Re: Reliable email . In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201906) . Garriss, S., Kaminsky, M., Freedman, M. J., Karp, B., Mazi\u2018eres, D., and Yu, H. 2006. Re: Reliable email. In Proceedings of the USENIX Symposium on Networked Systems Design and Implementation (NSDI\u201906)."},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Conference on Communities and Technologies.","author":"Golder S. A.","unstructured":"Golder , S. A. , Wilkinson , D. , and Huberman , B. A . 2007. Rhythms of social interaction: Messaging within a massive online network . In Proceedings of the Conference on Communities and Technologies. Golder, S. A., Wilkinson, D., and Huberman, B. A. 2007. Rhythms of social interaction: Messaging within a massive online network. In Proceedings of the Conference on Communities and Technologies."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1879141.1879190"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956769"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150476"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772751"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1367497.1367620"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30183-7_10"},{"key":"e_1_2_1_27_1","first-page":"62","article-title":"The small world problem","volume":"6","author":"Milgram S.","year":"1967","unstructured":"Milgram , S. 1967 . The small world problem . Psychol. Today 6 , 62 -- 67 . Milgram, S. 1967. The small world problem. Psychol. Today 6, 62--67.","journal-title":"Psychol. Today"},{"key":"e_1_2_1_28_1","volume-title":"The Familiar Stranger: An Aspect of Urban Anonymity","author":"Milgram S.","unstructured":"Milgram , S. 1977. The Familiar Stranger: An Aspect of Urban Anonymity . Addison-Wesley . Milgram, S. 1977. The Familiar Stranger: An Aspect of Urban Anonymity. Addison-Wesley."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the ACM Workshop on Hot Topics in Networks (HotNets\u201906)","author":"Mislove A.","unstructured":"Mislove , A. , Gummadi , K. P. , and Druschel , P . 2006. Exploiting social networks for internet search . In Proceedings of the ACM Workshop on Hot Topics in Networks (HotNets\u201906) . Mislove, A., Gummadi, K. P., and Druschel, P. 2006. Exploiting social networks for internet search. In Proceedings of the ACM Workshop on Hot Topics in Networks (HotNets\u201906)."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1397735.1397742"},{"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.1103\/PhysRevE.67.026126"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the ACM Workshop on Online Networks (WOSN\u201910)","author":"Scellato S.","unstructured":"Scellato , S. , Mascolo , C. , Musolesi , M. , and Latora , V . 2010. Distance matters: Geo-social metrics for online social networks . In Proceedings of the ACM Workshop on Online Networks (WOSN\u201910) . Scellato, S., Mascolo, C., Musolesi, M., and Latora, V. 2010. Distance matters: Geo-social metrics for online social networks. In Proceedings of the ACM Workshop on Online Networks (WOSN\u201910)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644899"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1397735.1397737"},{"key":"e_1_2_1_37_1","unstructured":"Sweney M. 2008. Facebook sees first dip in uk users. guardian.co.uk. Sweney M. 2008. Facebook sees first dip in uk users. guardian.co.uk."},{"key":"e_1_2_1_38_1","unstructured":"Ugander J. Karrer B. Backstrom L. and Marlow C. 2011. The anatomy of the facebook social graph. Arxiv online pre-print abs\/1111.4503v1. Ugander J. Karrer B. Backstrom L. and Marlow C. 2011. The anatomy of the facebook social graph. Arxiv online pre-print abs\/1111.4503v1."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592672"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the Annual Conference on Neural Information Procesing Systems (NIPS\u201904)","author":"Vert J.-P.","unstructured":"Vert , J.-P. and Yamanishi , Y . 2004. Supervised graph inference . In Proceedings of the Annual Conference on Neural Information Procesing Systems (NIPS\u201904) . Vert, J.-P. and Yamanishi, Y. 2004. Supervised graph inference. In Proceedings of the Annual Conference on Neural Information Procesing Systems (NIPS\u201904)."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519089"},{"key":"e_1_2_1_44_1","unstructured":"Worthen B. 2008. Bill Gates quits facebook. Wall St. J. Online. Worthen B. 2008. Bill Gates quits facebook. Wall St. J. Online ."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772790"},{"key":"e_1_2_1_46_1","volume-title":"Proceedings of the International Conference on Weblogs and Social Media (ICWSM\u201910)","author":"Yang J.","unstructured":"Yang , J. and Counts , S . 2010. Predicting the speed, scale, and range of information diffusion in twitter . In Proceedings of the International Conference on Weblogs and Social Media (ICWSM\u201910) . Yang, J. and Counts, S. 2010. Predicting the speed, scale, and range of information diffusion in twitter. In Proceedings of the International Conference on Weblogs and Social Media (ICWSM\u201910)."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159913.1159945"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2008.13"},{"key":"e_1_2_1_49_1","unstructured":"Zuckerberg M. 2009. 200 million strong. The Facebook Blog. Zuckerberg M. 2009. 200 million strong. The Facebook Blog."}],"container-title":["ACM Transactions on the Web"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2382616.2382620","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2382616.2382620","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:34:38Z","timestamp":1750239278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2382616.2382620"}},"subtitle":["User Interactions in Online Social Networks and their Implications"],"short-title":[],"issued":{"date-parts":[[2012,11]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,11]]}},"alternative-id":["10.1145\/2382616.2382620"],"URL":"https:\/\/doi.org\/10.1145\/2382616.2382620","relation":{},"ISSN":["1559-1131","1559-114X"],"issn-type":[{"value":"1559-1131","type":"print"},{"value":"1559-114X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,11]]},"assertion":[{"value":"2010-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-07-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}