Preventing Unraveling in Social Networks: The Anchored k-Core Problem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Kshipra Bhawalkar , Jon Kleinberg , Kevin Lewi , Tim Roughgarden , Aneesh Sharma

ABSTRACT

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 study the problem of “anchoring” a small number of vertices to maximize the size of the corresponding anchored k-core — the maximal induced subgraph in which every non-anchored vertex has degree at least k. This problem corresponds to preventing “unraveling” — a cascade of iterated withdrawals. 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 ≥ 3. More... »

PAGES

440-451

Book

TITLE

Automata, Languages, and Programming

ISBN

978-3-642-31584-8
978-3-642-31585-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_40

DOI

http://dx.doi.org/10.1007/978-3-642-31585-5_40

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1018659884


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0806", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information Systems", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Stanford University, Stanford, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Stanford University, Stanford, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bhawalkar", 
        "givenName": "Kshipra", 
        "id": "sg:person.011054421305.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011054421305.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Cornell University, Ithaca, NY, USA", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Cornell University, Ithaca, NY, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kleinberg", 
        "givenName": "Jon", 
        "id": "sg:person.011522233557.04", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Stanford University, Stanford, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Stanford University, Stanford, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lewi", 
        "givenName": "Kevin", 
        "id": "sg:person.012713270305.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012713270305.39"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Stanford University, Stanford, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.168010.e", 
          "name": [
            "Stanford University, Stanford, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Roughgarden", 
        "givenName": "Tim", 
        "id": "sg:person.016435375611.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016435375611.40"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Twitter, Inc., USA", 
          "id": "http://www.grid.ac/institutes/grid.480429.3", 
          "name": [
            "Twitter, Inc., USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Sharma", 
        "givenName": "Aneesh", 
        "id": "sg:person.014415375161.41", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014415375161.41"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "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 \u2014 the maximal induced subgraph with minimum degree at least\u00a0k.We study the problem of \u201canchoring\u201d a small number of vertices to maximize the size of the corresponding anchored k-core \u2014 the maximal induced subgraph in which every non-anchored vertex has degree at least\u00a0k. This problem corresponds to preventing \u201cunraveling\u201d \u2014 a cascade of iterated withdrawals. We provide polynomial-time algorithms for general graphs with k\u2009=\u20092, and for bounded-treewidth graphs with arbitrary\u00a0k. We prove strong inapproximability results for general graphs and k\u2009\u2265\u20093.", 
    "editor": [
      {
        "familyName": "Czumaj", 
        "givenName": "Artur", 
        "type": "Person"
      }, 
      {
        "familyName": "Mehlhorn", 
        "givenName": "Kurt", 
        "type": "Person"
      }, 
      {
        "familyName": "Pitts", 
        "givenName": "Andrew", 
        "type": "Person"
      }, 
      {
        "familyName": "Wattenhofer", 
        "givenName": "Roger", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-31585-5_40", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-31584-8", 
        "978-3-642-31585-5"
      ], 
      "name": "Automata, Languages, and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "social networks", 
      "general graphs", 
      "polynomial time algorithm", 
      "bounded-treewidth graphs", 
      "user engagement", 
      "strong inapproximability results", 
      "core problem", 
      "inapproximability results", 
      "network", 
      "graph", 
      "subgraphs", 
      "algorithm", 
      "vertices", 
      "neighbors", 
      "small number", 
      "model", 
      "cost", 
      "number", 
      "players", 
      "minimum degree", 
      "core", 
      "benefits", 
      "withdrawal", 
      "results", 
      "degree", 
      "engagement", 
      "cascade", 
      "size", 
      "unraveling", 
      "problem", 
      "equilibrium", 
      "natural equilibrium"
    ], 
    "name": "Preventing Unraveling in Social Networks: The Anchored k-Core Problem", 
    "pagination": "440-451", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1018659884"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-31585-5_40"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-31585-5_40", 
      "https://app.dimensions.ai/details/publication/pub.1018659884"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_273.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-31585-5_40"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_40'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_40'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_40'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-31585-5_40'


 

This table displays all metadata directly associated to this object as RDF triples.

141 TRIPLES      23 PREDICATES      58 URIs      51 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-31585-5_40 schema:about anzsrc-for:08
2 anzsrc-for:0806
3 schema:author Nb9168b126a7a43c3a686ffd8fae84103
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description 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 study the problem of “anchoring” a small number of vertices to maximize the size of the corresponding anchored k-core — the maximal induced subgraph in which every non-anchored vertex has degree at least k. This problem corresponds to preventing “unraveling” — a cascade of iterated withdrawals. 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 ≥ 3.
7 schema:editor N24ae1c87491645c695cb639b9525dbd9
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nfbc51e05026b4cfebbc6596e7e854f02
12 schema:keywords algorithm
13 benefits
14 bounded-treewidth graphs
15 cascade
16 core
17 core problem
18 cost
19 degree
20 engagement
21 equilibrium
22 general graphs
23 graph
24 inapproximability results
25 minimum degree
26 model
27 natural equilibrium
28 neighbors
29 network
30 number
31 players
32 polynomial time algorithm
33 problem
34 results
35 size
36 small number
37 social networks
38 strong inapproximability results
39 subgraphs
40 unraveling
41 user engagement
42 vertices
43 withdrawal
44 schema:name Preventing Unraveling in Social Networks: The Anchored k-Core Problem
45 schema:pagination 440-451
46 schema:productId N07c0e6392e7448c2be099504df13c25e
47 Nf8597ea8480b4603a61119e1ebea0721
48 schema:publisher N66162815a9fb431a94cc4e25423d145b
49 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018659884
50 https://doi.org/10.1007/978-3-642-31585-5_40
51 schema:sdDatePublished 2022-05-20T07:45
52 schema:sdLicense https://scigraph.springernature.com/explorer/license/
53 schema:sdPublisher N9ed38c46923848f196a4e47125327684
54 schema:url https://doi.org/10.1007/978-3-642-31585-5_40
55 sgo:license sg:explorer/license/
56 sgo:sdDataset chapters
57 rdf:type schema:Chapter
58 N07c0e6392e7448c2be099504df13c25e schema:name dimensions_id
59 schema:value pub.1018659884
60 rdf:type schema:PropertyValue
61 N0e2309fe7f904907846f8cc7f316ec20 schema:familyName Czumaj
62 schema:givenName Artur
63 rdf:type schema:Person
64 N24ae1c87491645c695cb639b9525dbd9 rdf:first N0e2309fe7f904907846f8cc7f316ec20
65 rdf:rest Ne869da3a9e8448a0a07b1b288201ab8b
66 N4de4a920958b43aba1ab6b1a2191dced schema:familyName Mehlhorn
67 schema:givenName Kurt
68 rdf:type schema:Person
69 N5fcaad5e3ceb44b9a0591feef598ec34 schema:familyName Pitts
70 schema:givenName Andrew
71 rdf:type schema:Person
72 N66162815a9fb431a94cc4e25423d145b schema:name Springer Nature
73 rdf:type schema:Organisation
74 N70f45cf9d45d4a4da96bb83859b112f2 rdf:first sg:person.016435375611.40
75 rdf:rest N83e05761bc884fe9935e727b0bc13037
76 N7ac098d6b71b45c3b90dd1dfc5845f4a rdf:first Nf0ff649427c34a9fb77311688d293d9c
77 rdf:rest rdf:nil
78 N83e05761bc884fe9935e727b0bc13037 rdf:first sg:person.014415375161.41
79 rdf:rest rdf:nil
80 N9ed38c46923848f196a4e47125327684 schema:name Springer Nature - SN SciGraph project
81 rdf:type schema:Organization
82 Naf11fbd509ac4fe48be5780c860495ea rdf:first N5fcaad5e3ceb44b9a0591feef598ec34
83 rdf:rest N7ac098d6b71b45c3b90dd1dfc5845f4a
84 Nb9168b126a7a43c3a686ffd8fae84103 rdf:first sg:person.011054421305.39
85 rdf:rest Neddbe5a4089041cf802ee26096c491d9
86 Ndb05325ba1d147b887fa6ce8c627efd2 rdf:first sg:person.012713270305.39
87 rdf:rest N70f45cf9d45d4a4da96bb83859b112f2
88 Ne869da3a9e8448a0a07b1b288201ab8b rdf:first N4de4a920958b43aba1ab6b1a2191dced
89 rdf:rest Naf11fbd509ac4fe48be5780c860495ea
90 Neddbe5a4089041cf802ee26096c491d9 rdf:first sg:person.011522233557.04
91 rdf:rest Ndb05325ba1d147b887fa6ce8c627efd2
92 Nf0ff649427c34a9fb77311688d293d9c schema:familyName Wattenhofer
93 schema:givenName Roger
94 rdf:type schema:Person
95 Nf8597ea8480b4603a61119e1ebea0721 schema:name doi
96 schema:value 10.1007/978-3-642-31585-5_40
97 rdf:type schema:PropertyValue
98 Nfbc51e05026b4cfebbc6596e7e854f02 schema:isbn 978-3-642-31584-8
99 978-3-642-31585-5
100 schema:name Automata, Languages, and Programming
101 rdf:type schema:Book
102 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
103 schema:name Information and Computing Sciences
104 rdf:type schema:DefinedTerm
105 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
106 schema:name Information Systems
107 rdf:type schema:DefinedTerm
108 sg:person.011054421305.39 schema:affiliation grid-institutes:grid.168010.e
109 schema:familyName Bhawalkar
110 schema:givenName Kshipra
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011054421305.39
112 rdf:type schema:Person
113 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.5386.8
114 schema:familyName Kleinberg
115 schema:givenName Jon
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
117 rdf:type schema:Person
118 sg:person.012713270305.39 schema:affiliation grid-institutes:grid.168010.e
119 schema:familyName Lewi
120 schema:givenName Kevin
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012713270305.39
122 rdf:type schema:Person
123 sg:person.014415375161.41 schema:affiliation grid-institutes:grid.480429.3
124 schema:familyName Sharma
125 schema:givenName Aneesh
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014415375161.41
127 rdf:type schema:Person
128 sg:person.016435375611.40 schema:affiliation grid-institutes:grid.168010.e
129 schema:familyName Roughgarden
130 schema:givenName Tim
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016435375611.40
132 rdf:type schema:Person
133 grid-institutes:grid.168010.e schema:alternateName Stanford University, Stanford, CA, USA
134 schema:name Stanford University, Stanford, CA, USA
135 rdf:type schema:Organization
136 grid-institutes:grid.480429.3 schema:alternateName Twitter, Inc., USA
137 schema:name Twitter, Inc., USA
138 rdf:type schema:Organization
139 grid-institutes:grid.5386.8 schema:alternateName Cornell University, Ithaca, NY, USA
140 schema:name Cornell University, Ithaca, NY, USA
141 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...