{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:21:21Z","timestamp":1787322081118,"version":"build-2736575974"},"reference-count":27,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>We consider a model of user engagement in social networks, where each player incurs a cost to remain engaged but derives a benefit proportional to the number of engaged neighbors. The natural equilibrium of this model corresponds to the $k$-core of the social network---the maximal induced subgraph with minimum degree at least $k$. We introduce the problem of \u201canchoring\u201d a small number of vertices to maximize the size of the corresponding anchored $k$-core---the maximal induced subgraph in which every nonanchored vertex has degree at least $k$. This problem corresponds to preventing \u201cunraveling''---a cascade of iterated withdrawals---and it identifies the individuals whose participation is most crucial to the overall health of a social network. We classify the computational complexity of this problem as a function of $k$ and of the graph structure. We provide polynomial-time algorithms for general graphs with $k=2$ and for bounded-treewidth graphs with arbitrary $k$. We prove strong inapproximability results for general graphs and $k \\ge 3$.<\/jats:p>","DOI":"10.1137\/14097032x","type":"journal-article","created":{"date-parts":[[2015,8,11]],"date-time":"2015-08-11T12:24:23Z","timestamp":1439295863000},"page":"1452-1475","source":"Crossref","is-referenced-by-count":81,"title":["Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem"],"prefix":"10.1137","volume":"29","author":[{"given":"Kshipra","family":"Bhawalkar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jon","family":"Kleinberg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kevin","family":"Lewi","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tim","family":"Roughgarden","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aneesh","family":"Sharma","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-17572-5_34"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.01.014"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-10841-9_11"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.2307\/2234208"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"S. Bhagat, A. Goyal, and L. V. S. Lakshmanan,\n                      Maximizing product adoption in social networks\n                      , in Proceedings of the Fifth International Conference on Web Search and Web Data Mining (WSDM), 2012, pp. 603-612.","DOI":"10.1145\/2124295.2124368"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1006\/game.1993.1023"},{"key":"atypb7","first-page":"255","author":"Bodlaender H. L.","year":"2008","journal-title":"Comput. J., ("},{"key":"atypb8","first-page":"945","author":"Burke M.","year":"2009","journal-title":"Proceedings of CHI"},{"key":"atypb9","unstructured":"R. H. Chitnis, F. V. Fomin, and P. A. Golovach,\n                      Parameterized complexity of the anchored k-core problem for directed graphs\n                      , in Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2013, pp. 79-90."},{"key":"atypb10","doi-asserted-by":"crossref","first-page":"1085","DOI":"10.1609\/aaai.v27i1.8462","author":"Chitnis R. H.","year":"2013","journal-title":"Proceedings of the Twenty-Seventh AAAI Conference on Artificial Intelligence"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1086\/210269"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00118"},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Parameterized Complexity\n                      , Springer, New York, 1999.","DOI":"10.1007\/978-1-4612-0515-9"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.2307\/2951493"},{"key":"atypb15","first-page":"1143","volume":"12","author":"Ellison N. B.","year":"2007","journal-title":"Social capital and college students' use of online social network sites, Journal of Computer-Mediated Communication"},{"key":"atypb16","first-page":"321","author":"Farzan R.","year":"2011","journal-title":"Proceedings of CSCW"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285059"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"J. Hartline, V. Mirrokni, and M. Sundararajan,\n                      Optimal Marketing Strategies over Social Networks\n                      , in Proceedings of the 17th International Conference on World Wide Web, 2008, pp. 189-198.","DOI":"10.1145\/1367497.1367524"},{"key":"atypb19","first-page":"424","volume":"75","author":"Katz M. L.","year":"1985","journal-title":"Amer. Econ. Rev."},{"key":"atypb20","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1145\/956750.956769","author":"Kempe D.","year":"2003","journal-title":"Proceedings of KDD"},{"key":"atypb21","first-page":"1127","author":"Kempe D.","year":"2005","journal-title":"Proceedings of ICALP"},{"key":"atypb22","first-page":"1","author":"Leskovec J.","year":"2007","journal-title":"ACM Trans. Web"},{"key":"atypb23","first-page":"41","volume":"105","author":"Lokshtanov D.","year":"2011","journal-title":"Bull. EATCS"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1111\/1467-937X.00121"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1137\/080714452"},{"key":"atypb26","unstructured":"P. Saaskilahti,\n                      Monopoly Pricing of Social Goods\n                      , Technical report, University Library of Munich, Munich, Germany, 2007."},{"key":"atypb27","unstructured":"T. C. Schelling,\n                      Micromotives and Macrobehavior\n                      , Norton, London, 1978."}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/14097032X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:57Z","timestamp":1787318277000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/14097032X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/14097032X"],"URL":"https:\/\/doi.org\/10.1137\/14097032x","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}