Bohman and Frieze7) in which each
node chooses m neighbors uniformly
at random from all nodes.
Note that in both the random attachment (RA) and the PA graph model, we are able to control the density
of the graph through the parameter
m, allowing us to run experiments
on graphs with the same number of
nodes and density as equivalent real-world graphs.
Figures 2 and 3 reflect how a rumor
begun in a random node spreads in
graphs corresponding to the Orkut
and Twitter social networks. News
spreads much more quickly in real-world networks and in PA graphs than
in complete and RA graphs. In the
Twitter experiment, a considerable
difference is apparent between the PA
model and the real-world graph, indicating the Twitter graph is captured
less well by the theoretical model.
To determine how graph size might
influence the speed a rumor spreads,
we ran the process on PA graphs, RA
graphs, and complete graphs of varying size. The results (see Figure 4) indicate logarithmic time is needed for
RA and complete graphs, whereas for
PA graphs time is needed of a slightly
smaller order of magnitude.
We supported this empirical finding
through mathematical analysis, proving the rumor-spreading process disseminates news in sublogarithmic
time, or the time needed to inform all
nodes, as well as any constant fraction
(such as 1%, 10%, or 50%).
We denote by Gn m the PA graph on
n nodes with density parameter m.
Since the graph Gn m is a random graph,
none of the statements mentioned
earlier holds with certainty. However,
the probability that the random graph
Gn m does not satisfy our assumptions
and observations tends to zero for n
growing to infinity. In the following
paragraphs, when we make a statement concerning a random object,
that statement is meant to hold with
high probability. For the PA graph Gn m,
with m being any constant larger than
one, we were able to prove that after
a surprisingly short time any given
news item spreads to all nodes.
Theorem 1. There is a constant K
such that the rumor-spreading pro-
with few neighbors
are crucial for quick
cess we described spreads a rumor
from any starting node to all other
nodes in at most K · log(n)/log(log(n))
time steps. This result improves
the previous best bound for rumor
spreading in PA graphs14 of order
2. Theorem 1 showed for the first
time (in 2011) that rumor spreading
in PA graphs is much quicker than for
the other network topologies covered
here so far. For RA graphs, it is easy to
see that the diameter is of order log(n),
which is also clearly a lower bound for
rumor-spreading time. Similar reasoning also shows that, independent
of starting node, a constant fraction of
all nodes has distance Θ(log(n)) from
the starting node. Hence a logarithmic number of rounds is needed to
inform any constant fraction of the
nodes. Similar bounds follow for hy-percube networks common in computer science applications.
However, the diameter of the network does not always reveal the time
needed to spread a rumor. The complete graph has a diameter of exactly
one, but time to all other networks is
of logarithmic order. This result was
proved in 2000 by Karp et al.
20 for a
rumor-spreading process in which
nodes were allowed to choose their
random communication partners
from among all neighbors, including
the one they might have just talked to.
It is not difficult to see the Karp et al.
proof is valid in our setting. That proof
also shows that a logarithmic number
of rounds is still necessary to inform
any constant fraction of the nodes.
Similar results hold for the classical
Erdös-Rényi random graphs as might
be deduced from Fountoulakis et al.
and Karp et al.
20 All these results were
proved through mathematical means;
that is, they did not rely on experiments conducted for certain graph
sizes n but are valid for all graph sizes.
For the proof of Theorem 1 see Doerr
17 though here we outline a main
argument that also explains why rumor spreading in social networks is
Toward this goal, let A and B be
neighboring nodes in Gn m. We denote
their degrees by dA and dB. Assume that
A is informed and B is not. How does
the rumor progress from A to B Since
A contacts its neighbors randomly,
it will take approximately dA rounds