PaperlayerView exact revision on arXiv

Source-linked AI summary

Spreading gossip in social networks

Pedro G. Lind, Luciano R. da Silva, José S. Andrade Jr., Hans J. Herrmann

arXiv:0705.3224v1physics.soc-ph

TL;DR

The paper asks how acquaintance-network structure shapes gossip’s reach. It defines measures of spread and spreading time, evaluates them on empirical and artificial networks, and reports that an optimal number of friends minimizes gossip risk in empirical and scale-free networks but not small-world networks.

  • Problem

    The paper asks whether gossip’s reach among friends reflects the structure of people’s acquaintance networks.

    Source: §I · p. 1

  • Method

    The model measures accessible neighborhood fraction and spreading time, then compares propagation across scale-free and small-world networks and an empirical school social-contact network.

    Source: §I · p. 2

  • Results

    An optimal friend count minimizes gossip risk in empirical and scale-free networks but not small-world networks; beyond nearest neighbors, that optimum disappears and logarithmic spreading-time dependence no longer holds.

    Source: §V · pp. 9–10

  • Takeaways & Limitations

    Node-wise spreading-factor distributions provide insight into network structure, with skewness indicating whether neighbors connect through paths or are grouped into separated pairs.

    Source: §V · p. 9

Abstract

from arXiv · show

We study a simple model of information propagation in social networks, where two quantities are introduced: the spread factor, which measures the average maximal fraction of neighbors of a given node that interchange information among each other, and the spreading time needed for the information to reach such fraction of nodes. When the information refers to a particular node at which both quantities are measured, the model can be taken as a model for gossip propagation. In this context, we apply the model to real empirical networks of social acquaintances and compare the underlying spreading dynamics with different types of scale-free and small-world networks. We find that the number of friendship connections strongly influences the probability of being gossiped. Finally, we discuss how the spread factor is able to be applied to other situations.

I. INTRODUCTION AND MODEL

The section frames gossip as information about a specific person that spreads among that person’s acquaintances, and introduces measures of how far and how quickly it spreads. It outlines comparisons across artificial and empirical networks, along with extensions beyond immediate neighbors and probabilistic transmission.

I. INTRODUCTION AND MODEL

  • Gossip targets details about a specific person and, as a first approximation, spreads only among people directly connected to that target-node.This distinguishes gossip from rumors or opinions that may interest neighbors regardless of their connections to a particular node.Source: §I · p. 1
  • A randomly chosen victim’s neighbor originates gossip at t = 0, then passes it to nodes connected to both the originator and victim until all reachable victim-acquaintances know it.The process resembles a burning algorithm restricted to the victim’s neighbors.Source: §I · p. 2
  • The spreading factor f = nf/k measures the fraction of a victim’s acquaintances who eventually hear gossip, while spreading time τ measures the minimum time to reach that fraction.Unlike the clustering coefficient C, f captures how bonds distribute among the victim’s acquaintances, not just the number of bonds between them.Source: §I · p. 2
  • The study compares spreading in scale-free and small-world networks with a U.S. school friendship network, then considers spread beyond first neighbors and probabilistic transmission.It also notes analytical considerations for the Apollonian network.Source: §I · p. 2

II. SPREADING INFORMATION OVER FIRST NEIGHBORS

Information spreading over first neighbors depends on network structure and node degree: empirical friendship networks show key patterns also found in scale-free networks, while hierarchical and small-world structures produce distinct spread-factor behavior.

II. SPREADING INFORMATION OVER FIRST NEIGHBORS

  • At large k, BA spreading time τ grows logarithmically, with A = −10.77 and B = 2.433; its spread factor is minimal at a middle-range degree and rises above 1/k for larger degrees.For small degrees, f remains at 1/k; the increase above 1/k at larger degrees grows with m.Source: §II · p. 2, Figure 2 · p. 2
  • For Apollonian networks, hierarchical structure gives f = 1 independently of k, while τ grows logarithmically because nth-generation vertices communicate in n steps.The analytical fit has A = −0.28 and B = 1.1.Source: §II · p. 3, Figure 4 · p. 3
  • About 7 friends is the empirical network’s optimal degree, where f ≈ 0.42; nodes with either fewer or more friends reach a larger fraction of their neighbors.In the 84-school networks, spreading time grows linearly for small k and logarithmically for large k, following the average degree of nearest neighbors.Source: §II · pp. 3–4, Figure 5 · p. 3
  • Empirical school networks and BA networks show similar spreading despite the schools’ typically exponential degree distribution; the optimal degree therefore need not depend on a power-law distribution.The relation between degree correlations and logarithmic spreading time is not straightforward: nearest-neighbor degree and spreading time have the same distribution in empirical networks, while BA and Apollonian networks have power-law nearest-neighbor degree.Source: §II · pp. 4–5
  • For large τ, school-network P(τ) decays exponentially and has a small-τ maximum; it resembles the BA network with m = 9, shifted right due to its larger minimal number of connections.The authors suggest this similarity may relate to the questionnaire’s maximum of 10 acquaintances and infer that students elected about 9 acquaintances on average.Source: §II · p. 4
  • P(f) is strongly skewed toward low values in BA and school networks, indicating that a node’s neighbors tend to form small, separated linked groups; Apollonian networks instead have f = 1 throughout.The BA and school distributions differ strongly from the symmetric distribution expected if all possible f values occurred equally often.Source: §II · pp. 4–5, Figure 6 · p. 4
  • In small-world lattices, f begins to decrease at about the same rewiring probability as the normalized clustering coefficient; the small-world range is approximately −2 ≲ log p ≲ −1.In random networks, p′ = 0.02 or lower gives approximately constant f and τ; at p′ = 0.04, f rises above 1/k and τ increases with k; at p′ = 0.08, f reaches 1 independently of k and complete-spreading time decreases with k* .Source: §II · p. 5, Figure 7 · p. 5

III. BEYOND THE FIRST NEIGHBORS

The section compares gossip propagation through the victim’s first two neighborhoods with propagation throughout the network. It finds that the effects of broader reach vary by network type, and introduces the total reached fraction FN and the maximal spreading time τmax for whole-network spreading.

Whole-network spreading

  • The model defines FN as the maximal fraction of network nodes that know and transmit the information, and τmax as the steps needed to reach FN.In whole-network spreading, f usually reaches 1, except when a neighbor of the victim has no other friends through which the information can spread.Source: §III · pp. 5–6

First two neighborhoods

  • In school networks, two-neighborhood spreading time becomes independent of k at large k, while the spread-factor minimum occurs at a much lower k0 than for common-neighbor-only spreading.The authors conjecture that this optimal k0 vanishes as network size or connection count increases.Source: Figure 8 · p. 6, §III · p. 6
  • For propagation through two neighborhoods in BA networks, the optimal degree k0 appears only at m = 3 and vanishes as m increases; at large m, f decreases as 1/k.For large m, f remains large and P(f) has a pronounced peak at f = 1.Source: Figure 9 · p. 6, §III · p. 6
  • In BA networks, two-neighborhood spreading time τ plateaus at large k, with a lower plateau at larger m; its distribution has an approximately exponential tail whose slope increases with m.At small k, τ depends approximately logarithmically on m because more links per node enable faster propagation.Source: Figure 9 · p. 6, §III · p. 6

Whole-network spreading

  • In school networks, whole-network spreading yields f ≈ 1 and FN ∼ 0.6 after rising quickly at small k, so no optimal number of friends is observed.τmax decreases with k before becoming approximately constant; the large fluctuations for k > 25 are attributed to poor statistics.Source: Figure 10 · p. 7, §III · p. 7
  • On BA networks, whole-network spreading always gives f = 1, with FN > 0.7 independently of k and FN ∼1 for k > 10.The authors conclude that all of a victim’s neighbors receive the information only when it spreads throughout the entire network.Source: Figure 11 · p. 7, §III · p. 7
  • For Apollonian networks, τmax ≥ τ grows more slowly with k, and FN equals 1 only where τ = τmax, indicating that reaching all neighbors requires network-wide spreading.The whole-network result is consistent with the near-invariance of Apollonian propagation when extending from one to two neighborhoods, attributed to hierarchical structure.Source: §III · pp. 6–7, Figure 12 · p. 7
  • For N = 103 nodes averaged over 100 realizations, τ increases almost linearly with rewiring probability p except at large p; FN increases across the small-world regime and reaches 1 very fast at p = 1.At low p, τmax is very large due to large average path length, decreases by an order of magnitude over −2 < log p < −1, and follows average path length; in the small-world regime, some node-neighborhoods isolate nodes from information spreading.Source: §III · pp. 7–8, Figure 13 · p. 8

IV. INTRODUCING A TRANSMISSION PROBABILITY

The section introduces q as a transmission probability and compares repeated-attempt spreading with a one-time, percolation-like process. It examines how q affects spreading time and spread factor across school friendship and model networks.

IV. INTRODUCING A TRANSMISSION PROBABILITY

  • To relax the assumption that every friend spreads gossip, the model treats q as a node’s transmission probability and contrasts repeated attempts with a one-time attempt after which missed recipients never receive it.The q = 1 case recovers the previously studied model; the one-time process is described as percolation through the system.Source: §IV · pp. 8–9
  • With repeated attempts, every q > 0 yields the q = 1 spread factor, while τ retains large-k logarithmic dependence and its exponent increases with 1/q.For q = 0, τ = 0 and f = 1/k.Source: §IV · p. 8, Figure 14 · p. 8
  • For the BA network with N = 1000 and m = 9, τ strongly departs from logarithmic dependence because of its many initial outgoing connections.The figure compares this network with the school friendship networks [15].Source: §IV · p. 8, Figure 14 · p. 8
  • In the Apollonian network, the logarithmic spreading-time slope B varies approximately as 1/q.The text reports a hyperbolic B-versus-q relationship.Source: Figure 15 · p. 9, §IV · p. 9
  • In the one-shot process, decreasing q shifts the school-network minimum of f to larger k and eventually removes it, while Apollonian τ peaks at qmax ≈ 0.75 before falling to zero.The large-k logarithmic law for τ remains for all q in the school networks.Source: Figure 16 · p. 9, §IV · p. 9

V. DISCUSSION AND CONCLUSIONS

The paper proposes spreading factor and spreading time to characterize information propagation, then applies them to target-focused gossip and broader rumor-like spreading. Its conclusions identify network-dependent gossip patterns, conditions that alter those patterns, and propagation regimes with probabilistic transmission.

V. DISCUSSION AND CONCLUSIONS

  • The model characterizes information propagation with spreading factor, the accessible neighborhood reached, and spreading time, the minimum time to reach it.For rumor or opinion propagation, information spreads throughout the network and all nodes are equally capable of transmitting it to neighbors.Source: §V · p. 9
  • The skewness of node-level spreading-factor distributions indicates neighbor accessibility: positive skewness means most neighbor pairs are connected by paths, while negative skewness means neighbors more often form separated connected pairs.Source: §V · p. 9
  • Empirical social networks and scale-free networks show logarithmic dependence of gossip spreading time on degree; an optimal friend count minimizes gossip risk, unlike in small-world networks.The optimal count depends on network size and the total number of acquaintances.Source: §V · pp. 9–10
  • Beyond nearest neighbors, the optimal friend count disappears as the spreading factor rapidly converges to f = 1, and spreading time is no longer logarithmic in degree.Source: §V · p. 10
  • The authors also studied propagation regimes in which information passes from one node to another with probability q.This addresses the fact that a person may not spread information to every neighbor, simultaneously or with certainty.Source: §V · p. 10
  • The authors suggest that their concepts and measures for information propagation in networks may suit other situations.Source: §V · p. 10
Loading 0705.3224v1…