Rumor Spreading in Social Networks View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2009

AUTHORS

Flavio Chierichetti , Silvio Lattanzi , Alessandro Panconesi

ABSTRACT

Social networks are an interesting class of graphs likely to become of increasing importance in the future, not only theoretically, but also for its probable applications to ad hoc and mobile networking. Rumor spreading is one of the basic mechanisms for information dissemination in networks, its relevance stemming from its simplicity of implementation and effectiveness. In this paper, we study the performance of rumor spreading in the classic preferential attachment model of Bollobás et al. which is considered to be a valuable model for social networks. We prove that, in these networks: (a) The standard PUSH-PULL strategy delivers the message to all nodes within O(log2n) rounds with high probability; (b) by themselves, PUSH and PULL require polynomially many rounds. (These results are under the assumption that m, the number of new links added with each new node is at least 2. If m = 1 the graph is disconnected with high probability, so no rumor spreading strategy can work.) Our analysis is based on a careful study of some new properties of preferential attachment graphs which could be of independent interest. More... »

PAGES

375-386

References to SciGraph publications

  • 2004-01. The Diameter of a Scale-Free Random Graph in COMBINATORICA
  • Book

    TITLE

    Automata, Languages and Programming

    ISBN

    978-3-642-02929-5
    978-3-642-02930-1

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-02930-1_31

    DOI

    http://dx.doi.org/10.1007/978-3-642-02930-1_31

    DIMENSIONS

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


    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/0806", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information Systems", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Informatica, Sapienza Universit\u00e0 di Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Chierichetti", 
            "givenName": "Flavio", 
            "id": "sg:person.013712476601.91", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013712476601.91"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Informatica, Sapienza Universit\u00e0 di Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Lattanzi", 
            "givenName": "Silvio", 
            "id": "sg:person.015137567355.28", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015137567355.28"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Sapienza University of Rome", 
              "id": "https://www.grid.ac/institutes/grid.7841.a", 
              "name": [
                "Dipartimento di Informatica, Sapienza Universit\u00e0 di Roma, Italy"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Panconesi", 
            "givenName": "Alessandro", 
            "id": "sg:person.012766154071.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012766154071.70"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0166-218x(85)90059-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006274177"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0166-218x(85)90059-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006274177"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00493-004-0002-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1006336566", 
              "https://doi.org/10.1007/s00493-004-0002-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1126/science.286.5439.509", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010080128"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/15427951.2004.10129080", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010853126"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/15427951.2005.10129097", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020176545"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/41840.41841", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022752417"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/j.jctb.2006.05.007", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034540263"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/rsa.20197", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034874446"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1002/rsa.3240010406", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041604066"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1080/15427951.2004.10129084", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051315016"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/tit.2008.924648", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061651989"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1137/0147013", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1062840489"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.2003.1238178", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094135661"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/infcom.2005.1498447", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094179603"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1017/cbo9780511581274", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1098672101"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2009", 
        "datePublishedReg": "2009-01-01", 
        "description": "Social networks are an interesting class of graphs likely to become of increasing importance in the future, not only theoretically, but also for its probable applications to ad hoc and mobile networking. Rumor spreading is one of the basic mechanisms for information dissemination in networks, its relevance stemming from its simplicity of implementation and effectiveness. In this paper, we study the performance of rumor spreading in the classic preferential attachment model of Bollob\u00e1s et al. which is considered to be a valuable model for social networks. We prove that, in these networks: (a) The standard PUSH-PULL strategy delivers the message to all nodes within O(log2n) rounds with high probability; (b) by themselves, PUSH and PULL require polynomially many rounds. (These results are under the assumption that m, the number of new links added with each new node is at least 2. If m = 1 the graph is disconnected with high probability, so no rumor spreading strategy can work.) Our analysis is based on a careful study of some new properties of preferential attachment graphs which could be of independent interest.", 
        "editor": [
          {
            "familyName": "Albers", 
            "givenName": "Susanne", 
            "type": "Person"
          }, 
          {
            "familyName": "Marchetti-Spaccamela", 
            "givenName": "Alberto", 
            "type": "Person"
          }, 
          {
            "familyName": "Matias", 
            "givenName": "Yossi", 
            "type": "Person"
          }, 
          {
            "familyName": "Nikoletseas", 
            "givenName": "Sotiris", 
            "type": "Person"
          }, 
          {
            "familyName": "Thomas", 
            "givenName": "Wolfgang", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-02930-1_31", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": false, 
        "isPartOf": {
          "isbn": [
            "978-3-642-02929-5", 
            "978-3-642-02930-1"
          ], 
          "name": "Automata, Languages and Programming", 
          "type": "Book"
        }, 
        "name": "Rumor Spreading in Social Networks", 
        "pagination": "375-386", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1015749499"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-02930-1_31"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "4b0a767e29b09a8e421cd5ceed893e6d6ed4d19c0af11774e29143c42eb85a13"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-02930-1_31", 
          "https://app.dimensions.ai/details/publication/pub.1015749499"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:11", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000353_0000000353/records_45345_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-02930-1_31"
      }
    ]
     

    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-02930-1_31'

    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-02930-1_31'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-02930-1_31'

    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-02930-1_31'


     

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

    145 TRIPLES      23 PREDICATES      42 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-02930-1_31 schema:about anzsrc-for:08
    2 anzsrc-for:0806
    3 schema:author Nd1c8826656bd4362aa5159f8044f4270
    4 schema:citation sg:pub.10.1007/s00493-004-0002-2
    5 https://doi.org/10.1002/rsa.20197
    6 https://doi.org/10.1002/rsa.3240010406
    7 https://doi.org/10.1016/0166-218x(85)90059-9
    8 https://doi.org/10.1016/j.jctb.2006.05.007
    9 https://doi.org/10.1017/cbo9780511581274
    10 https://doi.org/10.1080/15427951.2004.10129080
    11 https://doi.org/10.1080/15427951.2004.10129084
    12 https://doi.org/10.1080/15427951.2005.10129097
    13 https://doi.org/10.1109/infcom.2005.1498447
    14 https://doi.org/10.1109/sfcs.2003.1238178
    15 https://doi.org/10.1109/tit.2008.924648
    16 https://doi.org/10.1126/science.286.5439.509
    17 https://doi.org/10.1137/0147013
    18 https://doi.org/10.1145/41840.41841
    19 schema:datePublished 2009
    20 schema:datePublishedReg 2009-01-01
    21 schema:description Social networks are an interesting class of graphs likely to become of increasing importance in the future, not only theoretically, but also for its probable applications to ad hoc and mobile networking. Rumor spreading is one of the basic mechanisms for information dissemination in networks, its relevance stemming from its simplicity of implementation and effectiveness. In this paper, we study the performance of rumor spreading in the classic preferential attachment model of Bollobás et al. which is considered to be a valuable model for social networks. We prove that, in these networks: (a) The standard PUSH-PULL strategy delivers the message to all nodes within O(log2n) rounds with high probability; (b) by themselves, PUSH and PULL require polynomially many rounds. (These results are under the assumption that m, the number of new links added with each new node is at least 2. If m = 1 the graph is disconnected with high probability, so no rumor spreading strategy can work.) Our analysis is based on a careful study of some new properties of preferential attachment graphs which could be of independent interest.
    22 schema:editor N122890884f83487a99acff55f9120d2f
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree false
    26 schema:isPartOf N873b977da5d74bfd9c757460593e24a8
    27 schema:name Rumor Spreading in Social Networks
    28 schema:pagination 375-386
    29 schema:productId N1cf735998e0146418da85e1525f9f30c
    30 N7c32a0876616417492b8c2468660fedf
    31 Nd44d1e67af5c41ddb8507c980b5a2a37
    32 schema:publisher Nc995c1a8164c4385946fec2a0d0b727f
    33 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015749499
    34 https://doi.org/10.1007/978-3-642-02930-1_31
    35 schema:sdDatePublished 2019-04-16T07:11
    36 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    37 schema:sdPublisher Nffe819b7d5894465991aeb8ce2e3e3b2
    38 schema:url https://link.springer.com/10.1007%2F978-3-642-02930-1_31
    39 sgo:license sg:explorer/license/
    40 sgo:sdDataset chapters
    41 rdf:type schema:Chapter
    42 N108eebc5290c4f25beecd989e7cbacd1 rdf:first sg:person.012766154071.70
    43 rdf:rest rdf:nil
    44 N11ceb9d5fb15431d9463d75be0ed91cc rdf:first N6f0cba8679cb425b8d5b2f81521baadc
    45 rdf:rest N35f5f9aadae347c9a5462d5c12e9f2d2
    46 N122890884f83487a99acff55f9120d2f rdf:first Nf2cbbe1ba6504f87bfc20ab87d9c790d
    47 rdf:rest N94c90535beeb40ec8a4e8efdad9ffcd9
    48 N1cf735998e0146418da85e1525f9f30c schema:name doi
    49 schema:value 10.1007/978-3-642-02930-1_31
    50 rdf:type schema:PropertyValue
    51 N35f5f9aadae347c9a5462d5c12e9f2d2 rdf:first N3a7ae5418f84459690115ce0adbbfd55
    52 rdf:rest Nd75204a6846a47bea8f6d01edf77be20
    53 N3a7ae5418f84459690115ce0adbbfd55 schema:familyName Nikoletseas
    54 schema:givenName Sotiris
    55 rdf:type schema:Person
    56 N4480319755b247eca5ba1d3a93b3647e rdf:first sg:person.015137567355.28
    57 rdf:rest N108eebc5290c4f25beecd989e7cbacd1
    58 N6f0cba8679cb425b8d5b2f81521baadc schema:familyName Matias
    59 schema:givenName Yossi
    60 rdf:type schema:Person
    61 N7b2508617d1e4a389123a2e675478111 schema:familyName Marchetti-Spaccamela
    62 schema:givenName Alberto
    63 rdf:type schema:Person
    64 N7c32a0876616417492b8c2468660fedf schema:name dimensions_id
    65 schema:value pub.1015749499
    66 rdf:type schema:PropertyValue
    67 N873b977da5d74bfd9c757460593e24a8 schema:isbn 978-3-642-02929-5
    68 978-3-642-02930-1
    69 schema:name Automata, Languages and Programming
    70 rdf:type schema:Book
    71 N94c90535beeb40ec8a4e8efdad9ffcd9 rdf:first N7b2508617d1e4a389123a2e675478111
    72 rdf:rest N11ceb9d5fb15431d9463d75be0ed91cc
    73 Nc995c1a8164c4385946fec2a0d0b727f schema:location Berlin, Heidelberg
    74 schema:name Springer Berlin Heidelberg
    75 rdf:type schema:Organisation
    76 Nd1c8826656bd4362aa5159f8044f4270 rdf:first sg:person.013712476601.91
    77 rdf:rest N4480319755b247eca5ba1d3a93b3647e
    78 Nd44d1e67af5c41ddb8507c980b5a2a37 schema:name readcube_id
    79 schema:value 4b0a767e29b09a8e421cd5ceed893e6d6ed4d19c0af11774e29143c42eb85a13
    80 rdf:type schema:PropertyValue
    81 Nd75204a6846a47bea8f6d01edf77be20 rdf:first Ne9a0c65a665849feaab97d370be2fd5a
    82 rdf:rest rdf:nil
    83 Ne9a0c65a665849feaab97d370be2fd5a schema:familyName Thomas
    84 schema:givenName Wolfgang
    85 rdf:type schema:Person
    86 Nf2cbbe1ba6504f87bfc20ab87d9c790d schema:familyName Albers
    87 schema:givenName Susanne
    88 rdf:type schema:Person
    89 Nffe819b7d5894465991aeb8ce2e3e3b2 schema:name Springer Nature - SN SciGraph project
    90 rdf:type schema:Organization
    91 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    92 schema:name Information and Computing Sciences
    93 rdf:type schema:DefinedTerm
    94 anzsrc-for:0806 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Information Systems
    96 rdf:type schema:DefinedTerm
    97 sg:person.012766154071.70 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    98 schema:familyName Panconesi
    99 schema:givenName Alessandro
    100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012766154071.70
    101 rdf:type schema:Person
    102 sg:person.013712476601.91 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    103 schema:familyName Chierichetti
    104 schema:givenName Flavio
    105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013712476601.91
    106 rdf:type schema:Person
    107 sg:person.015137567355.28 schema:affiliation https://www.grid.ac/institutes/grid.7841.a
    108 schema:familyName Lattanzi
    109 schema:givenName Silvio
    110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015137567355.28
    111 rdf:type schema:Person
    112 sg:pub.10.1007/s00493-004-0002-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006336566
    113 https://doi.org/10.1007/s00493-004-0002-2
    114 rdf:type schema:CreativeWork
    115 https://doi.org/10.1002/rsa.20197 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034874446
    116 rdf:type schema:CreativeWork
    117 https://doi.org/10.1002/rsa.3240010406 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041604066
    118 rdf:type schema:CreativeWork
    119 https://doi.org/10.1016/0166-218x(85)90059-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1006274177
    120 rdf:type schema:CreativeWork
    121 https://doi.org/10.1016/j.jctb.2006.05.007 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034540263
    122 rdf:type schema:CreativeWork
    123 https://doi.org/10.1017/cbo9780511581274 schema:sameAs https://app.dimensions.ai/details/publication/pub.1098672101
    124 rdf:type schema:CreativeWork
    125 https://doi.org/10.1080/15427951.2004.10129080 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010853126
    126 rdf:type schema:CreativeWork
    127 https://doi.org/10.1080/15427951.2004.10129084 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051315016
    128 rdf:type schema:CreativeWork
    129 https://doi.org/10.1080/15427951.2005.10129097 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020176545
    130 rdf:type schema:CreativeWork
    131 https://doi.org/10.1109/infcom.2005.1498447 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094179603
    132 rdf:type schema:CreativeWork
    133 https://doi.org/10.1109/sfcs.2003.1238178 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094135661
    134 rdf:type schema:CreativeWork
    135 https://doi.org/10.1109/tit.2008.924648 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061651989
    136 rdf:type schema:CreativeWork
    137 https://doi.org/10.1126/science.286.5439.509 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010080128
    138 rdf:type schema:CreativeWork
    139 https://doi.org/10.1137/0147013 schema:sameAs https://app.dimensions.ai/details/publication/pub.1062840489
    140 rdf:type schema:CreativeWork
    141 https://doi.org/10.1145/41840.41841 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022752417
    142 rdf:type schema:CreativeWork
    143 https://www.grid.ac/institutes/grid.7841.a schema:alternateName Sapienza University of Rome
    144 schema:name Dipartimento di Informatica, Sapienza Università di Roma, Italy
    145 rdf:type schema:Organization
     




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


    ...