Influential Nodes in a Diffusion Model for Social Networks View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2005

AUTHORS

David Kempe , Jon Kleinberg , Éva Tardos

ABSTRACT

We study the problem of maximizing the expected spread of an innovation or behavior within a social network, in the presence of “word-of-mouth” referral. Our work builds on the observation that individuals’ decisions to purchase a product or adopt an innovation are strongly influenced by recommendations from their friends and acquaintances. Understanding and leveraging this influence may thus lead to a much larger spread of the innovation than the traditional view of marketing to individuals in isolation.In this paper, we define a natural and general model of influence propagation that we term the decreasing cascade model, generalizing models used in the sociology and economics communities. In this model, as in related ones, a behavior spreads in a cascading fashion according to a probabilistic rule, beginning with a set of initially “active” nodes. We study the target set selection problem: we wish to choose a set of individuals to target for initial activation, such that the cascade beginning with this active set is as large as possible in expectation. We show that in the decreasing cascade model, a natural greedy algorithm is a 1-1/ e-ε approximation for selecting a target set of size k. More... »

PAGES

1127-1138

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11523468_91

DOI

http://dx.doi.org/10.1007/11523468_91

DIMENSIONS

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


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/15", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Commerce, Management, Tourism and Services", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1503", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Business and Management", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, University of Southern California", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Department of Computer Science, University of Southern California"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kempe", 
        "givenName": "David", 
        "id": "sg:person.01217776320.77", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01217776320.77"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science, Cornell University", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Department of Computer Science, Cornell University"
          ], 
          "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": "Department of Computer Science, Cornell University", 
          "id": "http://www.grid.ac/institutes/grid.5386.8", 
          "name": [
            "Department of Computer Science, Cornell University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Tardos", 
        "givenName": "\u00c9va", 
        "id": "sg:person.07751643335.12", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07751643335.12"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2005", 
    "datePublishedReg": "2005-01-01", 
    "description": "We study the problem of maximizing the expected spread of an innovation or behavior within a social network, in the presence of \u201cword-of-mouth\u201d referral. Our work builds on the observation that individuals\u2019 decisions to purchase a product or adopt an innovation are strongly influenced by recommendations from their friends and acquaintances. Understanding and leveraging this influence may thus lead to a much larger spread of the innovation than the traditional view of marketing to individuals in isolation.In this paper, we define a natural and general model of influence propagation that we term the decreasing cascade model, generalizing models used in the sociology and economics communities. In this model, as in related ones, a behavior spreads in a cascading fashion according to a probabilistic rule, beginning with a set of initially \u201cactive\u201d nodes. We study the target set selection problem: we wish to choose a set of individuals to target for initial activation, such that the cascade beginning with this active set is as large as possible in expectation. We show that in the decreasing cascade model, a natural greedy algorithm is a 1-1/ e-\u03b5 approximation for selecting a target set of size k.", 
    "editor": [
      {
        "familyName": "Caires", 
        "givenName": "Lu\u00eds", 
        "type": "Person"
      }, 
      {
        "familyName": "Italiano", 
        "givenName": "Giuseppe F.", 
        "type": "Person"
      }, 
      {
        "familyName": "Monteiro", 
        "givenName": "Lu\u00eds", 
        "type": "Person"
      }, 
      {
        "familyName": "Palamidessi", 
        "givenName": "Catuscia", 
        "type": "Person"
      }, 
      {
        "familyName": "Yung", 
        "givenName": "Moti", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11523468_91", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-27580-0", 
        "978-3-540-31691-6"
      ], 
      "name": "Automata, Languages and Programming", 
      "type": "Book"
    }, 
    "keywords": [
      "innovation", 
      "social networks", 
      "cascading fashion", 
      "cascade beginning", 
      "individual decisions", 
      "Economic Community", 
      "selection problem", 
      "traditional view", 
      "decisions", 
      "marketing", 
      "diffusion model", 
      "set of individuals", 
      "influence propagation", 
      "natural greedy algorithm", 
      "expectations", 
      "general model", 
      "spread", 
      "model", 
      "influential nodes", 
      "behavior", 
      "view", 
      "sociology", 
      "recommendations", 
      "mouth", 
      "paper", 
      "products", 
      "large spread", 
      "rules", 
      "set", 
      "words", 
      "influence", 
      "individuals", 
      "network", 
      "acquaintance", 
      "community", 
      "problem", 
      "work", 
      "active set", 
      "probabilistic rules", 
      "friends", 
      "one", 
      "beginning", 
      "cascade model", 
      "fashion", 
      "target", 
      "size k.", 
      "observations", 
      "referral", 
      "presence", 
      "isolation", 
      "algorithm", 
      "nodes", 
      "approximation", 
      "propagation", 
      "greedy algorithm", 
      "initial activation", 
      "activation", 
      "k."
    ], 
    "name": "Influential Nodes in a Diffusion Model for Social Networks", 
    "pagination": "1127-1138", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036764720"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11523468_91"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11523468_91", 
      "https://app.dimensions.ai/details/publication/pub.1036764720"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:11", 
    "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_190.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11523468_91"
  }
]
 

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/11523468_91'

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/11523468_91'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11523468_91'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11523468_91'


 

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

155 TRIPLES      23 PREDICATES      84 URIs      77 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11523468_91 schema:about anzsrc-for:15
2 anzsrc-for:1503
3 schema:author N8e03a20500254e64ab317a283d691005
4 schema:datePublished 2005
5 schema:datePublishedReg 2005-01-01
6 schema:description We study the problem of maximizing the expected spread of an innovation or behavior within a social network, in the presence of “word-of-mouth” referral. Our work builds on the observation that individuals’ decisions to purchase a product or adopt an innovation are strongly influenced by recommendations from their friends and acquaintances. Understanding and leveraging this influence may thus lead to a much larger spread of the innovation than the traditional view of marketing to individuals in isolation.In this paper, we define a natural and general model of influence propagation that we term the decreasing cascade model, generalizing models used in the sociology and economics communities. In this model, as in related ones, a behavior spreads in a cascading fashion according to a probabilistic rule, beginning with a set of initially “active” nodes. We study the target set selection problem: we wish to choose a set of individuals to target for initial activation, such that the cascade beginning with this active set is as large as possible in expectation. We show that in the decreasing cascade model, a natural greedy algorithm is a 1-1/ e-ε approximation for selecting a target set of size k.
7 schema:editor Na65b02e719834e859beb374c59e48a07
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N123f8995a78b43f8b512783cc214be05
12 schema:keywords Economic Community
13 acquaintance
14 activation
15 active set
16 algorithm
17 approximation
18 beginning
19 behavior
20 cascade beginning
21 cascade model
22 cascading fashion
23 community
24 decisions
25 diffusion model
26 expectations
27 fashion
28 friends
29 general model
30 greedy algorithm
31 individual decisions
32 individuals
33 influence
34 influence propagation
35 influential nodes
36 initial activation
37 innovation
38 isolation
39 k.
40 large spread
41 marketing
42 model
43 mouth
44 natural greedy algorithm
45 network
46 nodes
47 observations
48 one
49 paper
50 presence
51 probabilistic rules
52 problem
53 products
54 propagation
55 recommendations
56 referral
57 rules
58 selection problem
59 set
60 set of individuals
61 size k.
62 social networks
63 sociology
64 spread
65 target
66 traditional view
67 view
68 words
69 work
70 schema:name Influential Nodes in a Diffusion Model for Social Networks
71 schema:pagination 1127-1138
72 schema:productId Nd2bc300af0db4c11af71ad598c003385
73 Nd3100406821548078cc3d8129a9dd507
74 schema:publisher Naf994844503b4770984c37f8884cbc59
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036764720
76 https://doi.org/10.1007/11523468_91
77 schema:sdDatePublished 2022-01-01T19:11
78 schema:sdLicense https://scigraph.springernature.com/explorer/license/
79 schema:sdPublisher N8b99c79c5b02470784a637e8d406dd52
80 schema:url https://doi.org/10.1007/11523468_91
81 sgo:license sg:explorer/license/
82 sgo:sdDataset chapters
83 rdf:type schema:Chapter
84 N123f8995a78b43f8b512783cc214be05 schema:isbn 978-3-540-27580-0
85 978-3-540-31691-6
86 schema:name Automata, Languages and Programming
87 rdf:type schema:Book
88 N1bee88f529b54555836d79b292b12fd6 schema:familyName Monteiro
89 schema:givenName Luís
90 rdf:type schema:Person
91 N2a18a070d5d5499191e575db9fbd2f5c schema:familyName Yung
92 schema:givenName Moti
93 rdf:type schema:Person
94 N2fbc5a0ec53243d5a5e69e3fde20c5cb rdf:first sg:person.07751643335.12
95 rdf:rest rdf:nil
96 N373fea66af77459c8e70f200a01773c1 schema:familyName Caires
97 schema:givenName Luís
98 rdf:type schema:Person
99 N571dbd8803184034bcd2b0f130ad73ba rdf:first N1bee88f529b54555836d79b292b12fd6
100 rdf:rest N8b848cb027a44d00a45f476045efdded
101 N6abc411981c64a8b93f6ded28da35d96 rdf:first sg:person.011522233557.04
102 rdf:rest N2fbc5a0ec53243d5a5e69e3fde20c5cb
103 N704afb3a9d7f4628af0a66400bdd6324 rdf:first N2a18a070d5d5499191e575db9fbd2f5c
104 rdf:rest rdf:nil
105 N71fe4116f3304bd089bbd40fc441c5d9 schema:familyName Palamidessi
106 schema:givenName Catuscia
107 rdf:type schema:Person
108 N8b848cb027a44d00a45f476045efdded rdf:first N71fe4116f3304bd089bbd40fc441c5d9
109 rdf:rest N704afb3a9d7f4628af0a66400bdd6324
110 N8b99c79c5b02470784a637e8d406dd52 schema:name Springer Nature - SN SciGraph project
111 rdf:type schema:Organization
112 N8bf23f92d482428c938b1d1154aa37b9 rdf:first Nc11a850c3542403989bb86260c6eb09a
113 rdf:rest N571dbd8803184034bcd2b0f130ad73ba
114 N8e03a20500254e64ab317a283d691005 rdf:first sg:person.01217776320.77
115 rdf:rest N6abc411981c64a8b93f6ded28da35d96
116 Na65b02e719834e859beb374c59e48a07 rdf:first N373fea66af77459c8e70f200a01773c1
117 rdf:rest N8bf23f92d482428c938b1d1154aa37b9
118 Naf994844503b4770984c37f8884cbc59 schema:name Springer Nature
119 rdf:type schema:Organisation
120 Nc11a850c3542403989bb86260c6eb09a schema:familyName Italiano
121 schema:givenName Giuseppe F.
122 rdf:type schema:Person
123 Nd2bc300af0db4c11af71ad598c003385 schema:name dimensions_id
124 schema:value pub.1036764720
125 rdf:type schema:PropertyValue
126 Nd3100406821548078cc3d8129a9dd507 schema:name doi
127 schema:value 10.1007/11523468_91
128 rdf:type schema:PropertyValue
129 anzsrc-for:15 schema:inDefinedTermSet anzsrc-for:
130 schema:name Commerce, Management, Tourism and Services
131 rdf:type schema:DefinedTerm
132 anzsrc-for:1503 schema:inDefinedTermSet anzsrc-for:
133 schema:name Business and Management
134 rdf:type schema:DefinedTerm
135 sg:person.011522233557.04 schema:affiliation grid-institutes:grid.5386.8
136 schema:familyName Kleinberg
137 schema:givenName Jon
138 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011522233557.04
139 rdf:type schema:Person
140 sg:person.01217776320.77 schema:affiliation grid-institutes:None
141 schema:familyName Kempe
142 schema:givenName David
143 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01217776320.77
144 rdf:type schema:Person
145 sg:person.07751643335.12 schema:affiliation grid-institutes:grid.5386.8
146 schema:familyName Tardos
147 schema:givenName Éva
148 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07751643335.12
149 rdf:type schema:Person
150 grid-institutes:None schema:alternateName Department of Computer Science, University of Southern California
151 schema:name Department of Computer Science, University of Southern California
152 rdf:type schema:Organization
153 grid-institutes:grid.5386.8 schema:alternateName Department of Computer Science, Cornell University
154 schema:name Department of Computer Science, Cornell University
155 rdf:type schema:Organization
 




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


...