ed in a random, “rich-get-richer”
fashion; a newly entering node connects to m existing nodes chosen randomly but gives preference to nodes
that are already popular; that is, they
have many neighbors. Note that the
parameter m controls the density of
the graph, or the ratio of the number
of present edges to the number of
all possible edges. For these graphs,
Barabási and Albert3 empirically discovered a power law of k− 3 later proved
mathematically by Bollobás et al.
11
Similar models emerged at the time,
all leading to a power-law distribution. Also known is the PA model does
figure 1. how a rumor progresses from
a large-degree node A to another node B;
due to their having large number of
neighbors, A and B need more time to
push or pull the rumor.
With fewer neighbors, C pulls the rumor
from A and quickly pushes it to B.
A
B
C
not share all properties observed in
real-world networks; for example, it is
less clustered.
Still, the PA model has helped deduce many interesting properties of
social networks. Famous structural
results prove small diameters for such
graphs,
10 determine their degree (in
terms of number of neighbors) distribution,
11 and show high expansion
properties24 and robustness against
random damage, along with vulnerability against malicious attacks.
8, 9, 15, 18
Algorithmic work shows that in such
networks, viruses spread more easily
than in many other network topologies5 and that gossip-based decentralized algorithms are better at approximating averages.
12
Here, we assume a rumor is sufficiently interesting so people learn it
when talking to someone who knows
it. This is substantially different from
the probabilistic virus-spreading
model5 where the probability of being
infected is proportional to the number of neighbors infected. Two types
of rumor-spreading mechanisms have
been identified in the literature: In the
push model, only nodes that know the
rumor contact neighbors to inform
them, and is used to transmit information in computer networks.
16, 21 In
contrast, to capture the effect of gossiping in social networks, it is more
figure 2. Average number of informed nodes as a function of time for the orkut network
and preferential attachment, random attachment, and complete graphs of the same size
n = 3,072,441 nodes and density parameter m = 38.
101
the real network and the mathematical model
for social networks are both characterized by
significantly quicker rumor dissemination.
107
average number of informed nodes
106
105
104
103
102
Orkut network
pref. attachment
random-attachment
complete graph
appropriate for uninformed nodes to
actively ask for new information. We
use the push-pull model of Demers
et al.
16 (see also Karp et al.
20) in which
all nodes regularly contact a neighbor
and exchange all the information they
have.
We assume nodes choose their
communication partners uniformly
at random from their neighbors, excluding the person they contacted
immediately before. In this model,
we regard the spread of a single piece
of information initially present at a
single node. For simplicity, as in most
previous work, the rumor-spreading
process is synchronized; that is, it
takes place at discrete points over
time and each time step, with each
node contacting a neighbor to exchange information. This simplifies
a real-world scenario where users act
at different speeds, but in sufficiently
large networks these differences balance out and thus assume an average
speed used by all nodes.
Note that the communications
process is different in each social
network. The push-pull model we
analyze is naturally best at capturing
personal communication between
two individuals by, say, phone, text
message, email message, or other
directed communication. Many online social networks also allow other
ways to communicate (such as posts
on personal Web pages), possibly resulting in friends being notified of a
post when they next log in and then
forwarding the news, given that it is
of sufficient interest. Such forms of
communication can be modeled only
by more complicated means than the
push-pull protocol.
0
100
2
4
68
time steps
10
12
14
experimental Results
Supporting the notion that news
spreads quickly in social networks, we
have simulated the rumor-spreading
process on samples from the Twitter and Orkut social networks (from
Bhattacharjee et al.
6, 23), as well as on
PA graphs. As most social networks
have roughly similar structure, we
chose these large networks (data readily available) as instances of social
networks. For comparison, we also
included complete graphs and random-attachment graphs (also called
the m-out model, as in, for example,
