Preventing unraveling in social networks: the anchored k-core problem

DOI10.1137/14097032XMaRDI QIDQ5502104zbMATH OpenOpenAlexFDO

Authors Kshipra Bhawalkar, Kevin Lewi, Tim Roughgarden, Aneesh Sharma, Jon M. Kleinberg

Publication date 17 August 2015

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/14097032x

zbMATH Keywords

social networksgraph algorithms\(k\)-core

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Social networks; opinion dynamics (91D30)

Recommendations

• Preventing unraveling in social networks: the anchored \(k\)-core problem
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Can we create large \(k\)-cores by adding few edges?
• A parameterized complexity view on collapsing \(k\)-cores
• Parameterized complexity of the anchored k-core problem for directed graphs

Cites work

• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A threshold of ln n for approximating set cover
• Automata, Languages and Programming
• Communication and Coordination in Social Networks
• Contagion
• Equilibrium pricing with positive externalities
• Learning, Local Interaction, and Coordination
• Lower bounds based on the exponential time hypothesis
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Submodularity of influence in social networks: from local to global
• The statistical mechanics of strategic interaction

Cited in

(15)

• Partial immunization of trees
• Preventing unraveling in social networks: the anchored \(k\)-core problem
• Vaccinate your trees!
• Exploring cohesive subgraphs with vertex engagement and tie strength in bipartite graphs
• Percolation on the gene regulatory network
• A parameterized complexity view on collapsing \(k\)-cores
• Mathematical programming formulations for the collapsed k-core problem
• Building large \(k\)-cores from sparse graphs
• Building large \(k\)-cores from sparse graphs
• OCSM: finding overlapping cohesive subgraphs with minimum degree
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Improving the core resilience of real-world hypergraphs
• Parameterized complexity of the anchored \(k\)-core problem for directed graphs
• Immunization in the threshold model: a parameterized complexity study
• Leave or not leave? Group members' departure prediction in dynamic information networks

This page was built for publication: Preventing unraveling in social networks: the anchored \(k\)-core problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5502104)