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 N9ffa22c8d0344d5a9f233c0b3edd5ea8
    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 N7aa1f27e85534edc847f8ffb78508bc7
    23 schema:genre chapter
    24 schema:inLanguage en
    25 schema:isAccessibleForFree false
    26 schema:isPartOf N719f14682a824a1b8fbff7b0181ac879
    27 schema:name Rumor Spreading in Social Networks
    28 schema:pagination 375-386
    29 schema:productId N0096a9f976594fc7bb1d7f0752ab3ec4
    30 N891d341b13084f66917f14cab5057544
    31 Neb6f38865c3c422b9b15d641ceba235c
    32 schema:publisher N280f17aacce048128fdbfa4b0fa484b4
    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 N0ad925d2cede438c8eab432061d2aa1d
    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 N0096a9f976594fc7bb1d7f0752ab3ec4 schema:name doi
    43 schema:value 10.1007/978-3-642-02930-1_31
    44 rdf:type schema:PropertyValue
    45 N0ad925d2cede438c8eab432061d2aa1d schema:name Springer Nature - SN SciGraph project
    46 rdf:type schema:Organization
    47 N0c303cbe40764a0ea6626584a942d327 rdf:first sg:person.012766154071.70
    48 rdf:rest rdf:nil
    49 N170226bb032444579f0e1529a3a0eded rdf:first Nb52cbf234f554f89b438d058ea3bf43b
    50 rdf:rest N524ff484390c44f6b240e866f00a8dab
    51 N280f17aacce048128fdbfa4b0fa484b4 schema:location Berlin, Heidelberg
    52 schema:name Springer Berlin Heidelberg
    53 rdf:type schema:Organisation
    54 N2ef0f91217824256b318b83e7a19f878 schema:familyName Matias
    55 schema:givenName Yossi
    56 rdf:type schema:Person
    57 N2f3b5331c7894bd79c8bf5ae1a72ca3b schema:familyName Thomas
    58 schema:givenName Wolfgang
    59 rdf:type schema:Person
    60 N524ff484390c44f6b240e866f00a8dab rdf:first N2f3b5331c7894bd79c8bf5ae1a72ca3b
    61 rdf:rest rdf:nil
    62 N5ba5c5d8dc3e4ccb98d35028f848c8da rdf:first N2ef0f91217824256b318b83e7a19f878
    63 rdf:rest N170226bb032444579f0e1529a3a0eded
    64 N719f14682a824a1b8fbff7b0181ac879 schema:isbn 978-3-642-02929-5
    65 978-3-642-02930-1
    66 schema:name Automata, Languages and Programming
    67 rdf:type schema:Book
    68 N772ad230e9cc48adaeb75590cea7be67 schema:familyName Marchetti-Spaccamela
    69 schema:givenName Alberto
    70 rdf:type schema:Person
    71 N7aa1f27e85534edc847f8ffb78508bc7 rdf:first N8609451dbbf348f2866637fbdce0adc2
    72 rdf:rest Nc06ed6e629c344f08e69ca058bdd4a37
    73 N8609451dbbf348f2866637fbdce0adc2 schema:familyName Albers
    74 schema:givenName Susanne
    75 rdf:type schema:Person
    76 N891d341b13084f66917f14cab5057544 schema:name readcube_id
    77 schema:value 4b0a767e29b09a8e421cd5ceed893e6d6ed4d19c0af11774e29143c42eb85a13
    78 rdf:type schema:PropertyValue
    79 N9ffa22c8d0344d5a9f233c0b3edd5ea8 rdf:first sg:person.013712476601.91
    80 rdf:rest Nc158771e3b0a40caad6a271675116ac0
    81 Nb52cbf234f554f89b438d058ea3bf43b schema:familyName Nikoletseas
    82 schema:givenName Sotiris
    83 rdf:type schema:Person
    84 Nc06ed6e629c344f08e69ca058bdd4a37 rdf:first N772ad230e9cc48adaeb75590cea7be67
    85 rdf:rest N5ba5c5d8dc3e4ccb98d35028f848c8da
    86 Nc158771e3b0a40caad6a271675116ac0 rdf:first sg:person.015137567355.28
    87 rdf:rest N0c303cbe40764a0ea6626584a942d327
    88 Neb6f38865c3c422b9b15d641ceba235c schema:name dimensions_id
    89 schema:value pub.1015749499
    90 rdf:type schema:PropertyValue
    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)


    ...