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", 
      "engaged neighbors", 
      "non-anchored vertex", 
      "Anchored k"
    ], 
    "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-01-01T19:06", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_103.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.

144 TRIPLES      23 PREDICATES      61 URIs      54 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 Nd1a5a638d1184a1cbcf6dafd73c00784
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 Ne37c8ecc566f4f058f570dabc15e16c1
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N8e4aec8df94a4b04b490e61a8ceeae03
12 schema:keywords Anchored k
13 algorithm
14 benefits
15 bounded-treewidth graphs
16 cascade
17 core
18 core problem
19 cost
20 degree
21 engaged neighbors
22 engagement
23 equilibrium
24 general graphs
25 graph
26 inapproximability results
27 minimum degree
28 model
29 natural equilibrium
30 neighbors
31 network
32 non-anchored vertex
33 number
34 players
35 polynomial time algorithm
36 problem
37 results
38 size
39 small number
40 social networks
41 strong inapproximability results
42 subgraphs
43 unraveling
44 user engagement
45 vertices
46 withdrawal
47 schema:name Preventing Unraveling in Social Networks: The Anchored k-Core Problem
48 schema:pagination 440-451
49 schema:productId N81385e63516c4ba29dbb1821487e416a
50 Ncbe44e9da7e24e6aa7c16b45bcda4261
51 schema:publisher N270d30cdac5c4909b28ca0a2218ae34c
52 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018659884
53 https://doi.org/10.1007/978-3-642-31585-5_40
54 schema:sdDatePublished 2022-01-01T19:06
55 schema:sdLicense https://scigraph.springernature.com/explorer/license/
56 schema:sdPublisher Ndb7fb335e1414ce3bc82eea1409b64ef
57 schema:url https://doi.org/10.1007/978-3-642-31585-5_40
58 sgo:license sg:explorer/license/
59 sgo:sdDataset chapters
60 rdf:type schema:Chapter
61 N1a5e0bd57d114fd79dd2624ce3ecdfc6 rdf:first N5b22be65e19b4196b084b26db23dbb74
62 rdf:rest N755ccbd9a06a40039cfd6a72af707cfe
63 N270d30cdac5c4909b28ca0a2218ae34c schema:name Springer Nature
64 rdf:type schema:Organisation
65 N5b22be65e19b4196b084b26db23dbb74 schema:familyName Mehlhorn
66 schema:givenName Kurt
67 rdf:type schema:Person
68 N755ccbd9a06a40039cfd6a72af707cfe rdf:first N772b4721ec2043a49e85c80907f80b04
69 rdf:rest N7e5da318c5ef4d7da9de2ad2529026f1
70 N772b4721ec2043a49e85c80907f80b04 schema:familyName Pitts
71 schema:givenName Andrew
72 rdf:type schema:Person
73 N7e5da318c5ef4d7da9de2ad2529026f1 rdf:first Nf0c3eb6c1ee84b50bb71d7f380c4b396
74 rdf:rest rdf:nil
75 N81385e63516c4ba29dbb1821487e416a schema:name doi
76 schema:value 10.1007/978-3-642-31585-5_40
77 rdf:type schema:PropertyValue
78 N8e4aec8df94a4b04b490e61a8ceeae03 schema:isbn 978-3-642-31584-8
79 978-3-642-31585-5
80 schema:name Automata, Languages, and Programming
81 rdf:type schema:Book
82 Nbed9f2dad41c495e942233cf7ae7fdfa rdf:first sg:person.014415375161.41
83 rdf:rest rdf:nil
84 Nc6250e6acd8341eaad1b93354a38c79d schema:familyName Czumaj
85 schema:givenName Artur
86 rdf:type schema:Person
87 Nc91a87c2de6841fbb636ae3665f0416f rdf:first sg:person.012713270305.39
88 rdf:rest Ne027b786d6e4486b8cb300bb1db57ddb
89 Ncbe44e9da7e24e6aa7c16b45bcda4261 schema:name dimensions_id
90 schema:value pub.1018659884
91 rdf:type schema:PropertyValue
92 Nd1a5a638d1184a1cbcf6dafd73c00784 rdf:first sg:person.011054421305.39
93 rdf:rest Nfb7191df4fb4476aa4b088dbd4fa73e3
94 Ndb7fb335e1414ce3bc82eea1409b64ef schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 Ne027b786d6e4486b8cb300bb1db57ddb rdf:first sg:person.016435375611.40
97 rdf:rest Nbed9f2dad41c495e942233cf7ae7fdfa
98 Ne37c8ecc566f4f058f570dabc15e16c1 rdf:first Nc6250e6acd8341eaad1b93354a38c79d
99 rdf:rest N1a5e0bd57d114fd79dd2624ce3ecdfc6
100 Nf0c3eb6c1ee84b50bb71d7f380c4b396 schema:familyName Wattenhofer
101 schema:givenName Roger
102 rdf:type schema:Person
103 Nfb7191df4fb4476aa4b088dbd4fa73e3 rdf:first sg:person.011522233557.04
104 rdf:rest Nc91a87c2de6841fbb636ae3665f0416f
105 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
106 schema:name Information and Computing Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
109 schema:name Information Systems
110 rdf:type schema:DefinedTerm
111 sg:person.011054421305.39 schema:affiliation grid-institutes:grid.168010.e
112 schema:familyName Bhawalkar
113 schema:givenName Kshipra
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011054421305.39
115 rdf:type schema:Person
116 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.5386.8
117 schema:familyName Kleinberg
118 schema:givenName Jon
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
120 rdf:type schema:Person
121 sg:person.012713270305.39 schema:affiliation grid-institutes:grid.168010.e
122 schema:familyName Lewi
123 schema:givenName Kevin
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012713270305.39
125 rdf:type schema:Person
126 sg:person.014415375161.41 schema:affiliation grid-institutes:grid.480429.3
127 schema:familyName Sharma
128 schema:givenName Aneesh
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014415375161.41
130 rdf:type schema:Person
131 sg:person.016435375611.40 schema:affiliation grid-institutes:grid.168010.e
132 schema:familyName Roughgarden
133 schema:givenName Tim
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016435375611.40
135 rdf:type schema:Person
136 grid-institutes:grid.168010.e schema:alternateName Stanford University, Stanford, CA, USA
137 schema:name Stanford University, Stanford, CA, USA
138 rdf:type schema:Organization
139 grid-institutes:grid.480429.3 schema:alternateName Twitter, Inc., USA
140 schema:name Twitter, Inc., USA
141 rdf:type schema:Organization
142 grid-institutes:grid.5386.8 schema:alternateName Cornell University, Ithaca, NY, USA
143 schema:name Cornell University, Ithaca, NY, USA
144 rdf:type schema:Organization
 




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


...