Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem

DOI10.1137/14097032XzbMath1327.68173OpenAlexW1154358131MaRDI QIDQ5502104

Aneesh Sharma, Tim Roughgarden, Kevin Lewi, Kshipra Bhawalkar, 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

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

Related Items (11)

A parameterized complexity view on collapsing \(k\)-cores ⋮ Vaccinate your trees! ⋮ Building large \(k\)-cores from sparse graphs ⋮ 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 ⋮ Unnamed Item ⋮ Partial immunization of trees ⋮ Percolation on the gene regulatory network

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The statistical mechanics of strategic interaction
• Equilibrium pricing with positive externalities
• Parameterized Complexity of the Anchored k-Core Problem for Directed Graphs
• Submodularity of Influence in Social Networks: From Local to Global
• Learning, Local Interaction, and Coordination
• A threshold of ln n for approximating set cover
• Communication and Coordination in Social Networks
• Contagion
• Automata, Languages and Programming

This page was built for publication: Preventing Unraveling in Social Networks: The Anchored $k$-Core Problem