{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,17]],"date-time":"2026-02-17T21:14:13Z","timestamp":1771362853905,"version":"3.50.1"},"reference-count":41,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,12,1]],"date-time":"2013-12-01T00:00:00Z","timestamp":1385856000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2013,12]]},"abstract":"<jats:p>\n            Online social networking sites have become increasingly popular over the last few years. As a result, new interdisciplinary research directions have emerged in which social network analysis methods are applied to networks containing hundreds of millions of users. Unfortunately, links between individuals may be missing either due to an imperfect acquirement process or because they are not yet reflected in the online network (i.e., friends in the real world did not form a virtual connection). The primary bottleneck in link prediction techniques is extracting the structural features required for classifying links. In this article, we propose a set of simple, easy-to-compute structural features that can be analyzed to identify missing links. We show that by using simple structural features, a machine learning classifier can successfully identify missing links, even when applied to a predicament of classifying links between individuals with at least one common friend. We also present a method for calculating the amount of data needed in order to build more accurate classifiers. The new\n            <jats:italic>Friends measure<\/jats:italic>\n            and\n            <jats:italic>Same community<\/jats:italic>\n            features we developed are shown to be good predictors for missing links. An evaluation experiment was performed on ten large social networks datasets: Academia.edu, DBLP, Facebook, Flickr, Flixster, Google+, Gowalla, TheMarker, Twitter, and YouTube. Our methods can provide social network site operators with the capability of helping users to find known, offline contacts and to discover new friends online. They may also be used for exposing hidden links in online social networks.\n          <\/jats:p>","DOI":"10.1145\/2542182.2542192","type":"journal-article","created":{"date-parts":[[2014,1,2]],"date-time":"2014-01-02T13:09:43Z","timestamp":1388668183000},"page":"1-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Computationally efficient link prediction in a variety of social networks"],"prefix":"10.1145","volume":"5","author":[{"given":"Michael","family":"Fire","sequence":"first","affiliation":[{"name":"Ben-Gurion University of the Negev, Be'er Sheva, 84105, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lena","family":"Tenenboim-Chekina","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Be'er Sheva, 84105, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rami","family":"Puzis","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Be'er Sheva, 84105, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ofrit","family":"Lesser","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Be'er Sheva, 84105, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lior","family":"Rokach","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Be'er Sheva, 84105, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuval","family":"Elovici","sequence":"additional","affiliation":[{"name":"Ben-Gurion University of the Negev, Be'er Sheva, 84105, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,1,3]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the International Biometrics Society Annual Meeting.","author":"Airoldi E."},{"key":"e_1_2_1_2_1","unstructured":"Avin C. Lotker Z. and Pignolet Y. 2011. On the elite of social networks. Arxiv preprint. http:\/\/arxiv.org\/abs\/1111.3374.  Avin C. Lotker Z. and Pignolet Y. 2011. On the elite of social networks. Arxiv preprint. http:\/\/arxiv.org\/abs\/1111.3374."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2008\/10\/P10008"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 4th International AAAI Conference on Weblogs and Social Media (ICWSM'10)","author":"Cha M."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007730.1007733"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Joint Conference on Neural Networks.","author":"Cukierski W. J."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1248547.1248548"},{"key":"e_1_2_1_10_1","first-page":"3","article-title":"A general framework for modeling tumor-immune system competition and immunotherapy: Mathematical analysis and biomedical inferences","volume":"208","author":"D'Onofrio A.","year":"2005","journal-title":"Phys. D: Nonlinear Phenomena"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the Workshop on Analyzing Networks and Learning with Graphs at NIPS Conference.","author":"Doppa J. R."},{"key":"e_1_2_1_12_1","first-page":"5784","article-title":"Tyrannosaur life tables: An example of nonavian dinosaur population biology","volume":"313","author":"Erickson G.","year":"2006","journal-title":"Sci."},{"key":"e_1_2_1_13_1","unstructured":"Facebook-Newsroom. 2013. http:\/\/www.facebook.com.  Facebook-Newsroom. 2013. http:\/\/www.facebook.com."},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Fire M. Katz G. Rokach L. and Elovici Y. 2012a. Links reconstruction attack: Using link prediction algorithms to compromise social networks privacy. In Security and Privacy in Social Networks Springer 181--196. http:\/\/proj.ise.bgu.ac.il\/sns\/papers&percnt;5Clink_reconstruction.pdf.  Fire M. Katz G. Rokach L. and Elovici Y. 2012a. Links reconstruction attack: Using link prediction algorithms to compromise social networks privacy. In Security and Privacy in Social Networks Springer 181--196. http:\/\/proj.ise.bgu.ac.il\/sns\/papers&percnt;5Clink_reconstruction.pdf.","DOI":"10.1007\/978-1-4614-4139-7_9"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Fire M. Puzis R. and Elovici Y. 2012b. Link prediction in highly fractional data sets. In Handbook of Computational Approaches to Counterterrorism Springer 283--300.  Fire M. Puzis R. and Elovici Y. 2012b. Link prediction in highly fractional data sets. In Handbook of Computational Approaches to Counterterrorism Springer 283--300.","DOI":"10.1007\/978-1-4614-5311-6_14"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 3rd IEEE International Conference on Privacy, Security, Risk and Trust (PASSAT'11) and the 3rd IEEE International Conference on Social Computing (SocialCom'11)","author":"Fire M."},{"key":"e_1_2_1_17_1","unstructured":"Gibbons A. 1985. Algorithmic Graph Theory. Cambridge University Press.  Gibbons A. 1985. Algorithmic Graph Theory. Cambridge University Press."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.122653799"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988727"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 7th Python in Science Conference (SciPy'08)","author":"Hagberg A. A."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1656274.1656278"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the SDM Workshop of Link Analysis, Counterterrorism and Security.","author":"Hasan M. A."},{"key":"e_1_2_1_23_1","unstructured":"Hasan M. A. and Zaki M. J. 2011. Social Network Data Analytics. Springer.   Hasan M. A. and Zaki M. J. 2011. Social Network Data Analytics. Springer."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065385.1065415"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_1_26_1","unstructured":"Koren Y. 2009. The bellkor solution to the netflix grand prize. http:\/\/www.stat.osu.edu\/&sim;dmsl\/GrandPrize2009_BPC_BellKor.pdf.  Koren Y. 2009. The bellkor solution to the netflix grand prize. http:\/\/www.stat.osu.edu\/&sim;dmsl\/GrandPrize2009_BPC_BellKor.pdf."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772756"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:7"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835837"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.neunet.2007.12.031"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the European Conference on Machine Learning and Knowledge Discovery in Databases (ECML-PKDD'11)","author":"Menon A."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1298306.1298311"},{"key":"e_1_2_1_33_1","unstructured":"Nachbar D. 2010. IJCNN social network challenge. http:\/\/www.kaggle.com\/c\/socialNetwork\/Data.  Nachbar D. 2010. IJCNN social network challenge. http:\/\/www.kaggle.com\/c\/socialNetwork\/Data."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE International Joint Conference on Neural Networks (IJCNN'11). 1825","author":"Narayanan A.","year":"1834"},{"key":"e_1_2_1_35_1","volume-title":"Proceedings of the 3rd International Workshop on Web and Text Intelligence.","author":"Sa H. R."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644932"},{"key":"e_1_2_1_37_1","unstructured":"Tan P. N. Steinbach M. and Kumar V. 2005. Introduction to Data Mining. Addison Wesley.   Tan P. N. Steinbach M. and Kumar V. 2005. Introduction to Data Mining. Addison Wesley."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1038\/30918"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622434.1622445"},{"key":"e_1_2_1_41_1","unstructured":"Zafarani R. and Liu H. 2009. Social computing data repository at asu. http:\/\/socialcomputing.asu.edu.  Zafarani R. and Liu H. 2009. Social computing data repository at asu. http:\/\/socialcomputing.asu.edu."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542182.2542192","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2542182.2542192","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:09:56Z","timestamp":1750234196000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2542182.2542192"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,12]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,12]]}},"alternative-id":["10.1145\/2542182.2542192"],"URL":"https:\/\/doi.org\/10.1145\/2542182.2542192","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"value":"2157-6904","type":"print"},{"value":"2157-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,12]]},"assertion":[{"value":"2012-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-01-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}