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

\(k\)-coregraph algorithmssocial networks

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

• 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
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• 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

(17)

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

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)