until A contacts B; thus A pushes the
news to B. Likewise, it takes an expect-
ed number of approximately dB time
steps until B calls A, pulling the rumor
from there. If dA and dB are large (such
as n1/3), then it would take an expected
number of almost 1/2n1/3 rounds to
propagate the rumor from A to B along
the direct link.
figure 3. Average number of informed nodes over time for the Twitter network and
comparable preferential attachment, random attachment, and complete graphs (size
n = 51,217,936 nodes, density parameter m = 32).
101
the two plots modeling social networks
again outperform the random attachment
and complete graph.
108
average number of informed nodes
107
106
105
104
103
102
Twitter network
pref. attachment
random-attachment
complete graph
0
100
2
4
6
8
10
12
time steps
14
16
18
20
figure 4. Average time needed to inform all nodes of different networks of varying size;
the data shows logarithmic dependence for random-attachment and complete graphs.
pref. attachment (m = 10) random-attachment (m = 10) complete graph
For preferential attachment graph (a mathematical model for social networks), the times appear to
be of lower order. note that the generally speedy propagation partially obscures the advantage of the
preferential attachment network structure. Alternatively, if one is willing to include 16 rounds of rumor-spreading communications between people (on average), then one can share a rumor with more than
300,000 others, as in the preferential attachment model, but with only around 30,000 people organized
in random-attachment fashion.
20
time steps to inform all nodes
18
16
14
12
10
8
6
4
101
102
103
104
105
number of nodes n
106
107
a third node C that is a neighbor of
both A and B and has a small degree
dC of, say, only four neighbors. After
an expected number of roughly dC =
4 rounds, C will have contacted A and
thus learned the news from A. Likewise, after another expected number
of dC = 4 rounds, C will have contacted
B and told it the news. That is, in 2 ·
dC = 8 time steps, the rumor went from
A to B through C. Fortunately, such a
node C exists with high probability;
the PA rule ensures newly entering
nodes put enough preference on connecting with A and B.
One mechanism enabling the
spread of rumors in social networks is
that small-degree nodes learn the rumor from an informed neighbor, then
quickly forward it to all other neighbors. In a sense, they act as an automatic link between their neighbors;
once one neighbor is informed, then
all other neighbors are informed—
without doing anything. Such a mechanism is missing (such as in complete
graphs) because all nodes have a high
degree of n − 1. Consequently, all
neighbors of the starting-node A have
a small probability of calling A and
asking for the news; A is just one of
their n – 1 neighbors.
Also note that such high-speed
links are abundant in PA graphs. To
clarify, call a node popular if it has
a degree of Θ(log(n)
2) or higher. We
can now show that between any two
popular nodes, there is a path of
length O(log(n)/log(log(n))) such that
every second node on the path has
the minimal possible degree of m. As
per our assumptions, equations, and
observations these nodes function as
quick links, propagating rumors in
an expected number of roughly 2·m
rounds. Consequently, the expected
time a rumor must traverse the whole
path is about m times its length. With
extra care, namely by showing there
is a huge number of such paths between any two popular nodes, we can
even show that once a popular node is
informed, after O(log(n)/log(log(n)))
rounds with high probability, all popular nodes are informed.
Since nodes tend to attach to popular nodes, a rumor started in a small-degree node is propagated to some
popular node even quicker, namely in
O(log(n)3/4 log(log(n))) rounds. Once all
