{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:52:04Z","timestamp":1750308724821,"version":"3.41.0"},"reference-count":24,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2013,6,1]],"date-time":"2013-06-01T00:00:00Z","timestamp":1370044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"JCT","award":["#963"],"award-info":[{"award-number":["#963"]}]},{"name":"MAFAT"},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2014,6,2]]},"abstract":"<jats:p>\n            In recent years, social networks have surged in popularity. One key aspect of social network research is identifying important missing information that is not explicitly represented in the network, or is not visible to all. To date, this line of research typically focused on finding the connections that are missing between nodes, a challenge typically termed as the\n            <jats:italic>link prediction problem<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>This article introduces the missing node identification problem, where missing members in the social network structure must be identified. In this problem, indications of missing nodes are assumed to exist. Given these indications and a partial network, we must assess which indications originate from the same missing node and determine the full network structure.<\/jats:p>\n          <jats:p>Toward solving this problem, we present the missing node identification by spectral clustering algorithm (MISC), an approach based on a spectral clustering algorithm, combined with nodes\u2019 pairwise affinity measures that were adopted from link prediction research. We evaluate the performance of our approach in different problem settings and scenarios, using real-life data from Facebook. The results show that our approach has beneficial results and can be effective in solving the missing node identification problem. In addition, this article also presents R-MISC, which uses a sparse matrix representation, efficient algorithms for calculating the nodes\u2019 pairwise affinity, and a proprietary dimension reduction technique to enable scaling the MISC algorithm to large networks of more than 100,000 nodes. Last, we consider problem settings where some of the indications are unknown. Two algorithms are suggested for this problem: speculative MISC, based on MISC, and missing link completion, based on classical link prediction literature. We show that speculative MISC outperforms missing link completion.<\/jats:p>","DOI":"10.1145\/2536775","type":"journal-article","created":{"date-parts":[[2014,7,7]],"date-time":"2014-07-07T14:46:44Z","timestamp":1404744404000},"page":"1-35","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":12,"title":["Predicting and Identifying Missing Node Information in Social Networks"],"prefix":"10.1145","volume":"8","author":[{"given":"Ron","family":"Eyal","sequence":"first","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Avi","family":"Rosenfeld","sequence":"additional","affiliation":[{"name":"Jerusalem College of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sigal","family":"Sina","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sarit","family":"Kraus","sequence":"additional","affiliation":[{"name":"Bar-Ilan University, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2013,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0378-8733(03)00009-1"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2008.12"},{"volume-title":"Proceedings of the 5th European Workshop on Advances in Case-Based Reasoning (EWCBR\u201900)","author":"Bunke Horst","key":"e_1_2_1_3_1"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1038\/nature06830"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/PASSAT\/SocialCom.2011.85"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.11.002"},{"volume-title":"Proceedings of the Neural Information Processing Systems Workshop on Choice Models and Preference Learning. http:\/\/hal.inria.fr\/hal-00641419","year":"2011","author":"Freno Antonino","key":"e_1_2_1_7_1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/1833515.1833840"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2086737.2086741"},{"key":"e_1_2_1_10_1","unstructured":"Neil Zhenqiang Gong Ameet Talwalkar Lester W. Mackey Ling Huang Eui Chul Richard Shin Emil Stefanov Elaine Shi and Dawn Song. 2011. Predicting links and inferring attributes using a social-attribute network (SAN). CoRR abs\/1112.3265.  Neil Zhenqiang Gong Ameet Talwalkar Lester W. Mackey Ling Huang Eui Chul Richard Shin Emil Stefanov Elaine Shi and Dawn Song. 2011. Predicting links and inferring attributes using a social-attribute network (SAN). CoRR abs\/1112.3265."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0908366106"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972818.5"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.07.002"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1982185.1982509"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835855"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.v58:7"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2187836.2187883"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.soc.27.1.415"},{"volume-title":"Advances in Neural Information Processing Systems 14","author":"Ng Andrew Y.","key":"e_1_2_1_20_1"},{"key":"e_1_2_1_21_1","first-page":"1082","article-title":"Communities in networks","volume":"56","author":"Porter Mason A.","year":"2009","journal-title":"Notices of the American Mathematical Society"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1935826.1935844"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1162\/153244303321897735"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2536775","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2536775","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:14:42Z","timestamp":1750277682000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2536775"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,6]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,6,2]]}},"alternative-id":["10.1145\/2536775"],"URL":"https:\/\/doi.org\/10.1145\/2536775","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2013,6]]},"assertion":[{"value":"2012-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}