actual real-world events unfolded.
4
Social networks spreading news so
quickly is remarkable; the structure of
social networks and the process that
distributes news were not designed
for this purpose. On the contrary, they
were not designed at all but evolved in
a random and decentralized manner.
VIsualIzatIon by MIGuel rIos at t WItter
Is it correct to assume social networks ease the spread of information
(“rumors”)? And, if they do, which of
their properties make it possible? To
answer, we simulated a simple rumor-spreading process on several graphs
reflecting the structure of existing
large social networks (see Figure
1). For example, a rumor begun at a
random node of the Twitter network
reaches on average 45. 6 million of the
total of 51. 2 million members within
only eight rounds of communication.
We also analyzed this process on
an abstract model of social networks,
the so-called PA graphs introduced in
1999 by Barabási and Albert.
3 In Do-
err et al.,
17 we devised a mathematical
proof that rumors in these networks
spread much more quickly than in
many other network topologies—even
quicker than in networks with a com-
munication link between any two
nodes (complete graphs). As an ex-
planation, we observe that nodes with
relatively few neighbors build a short-
cut between nodes with large degree
(hubs) that, due to their large number
of possible communication partners,
talk less often to each other directly.
Rumor spreading
Social networks arise in a variety of
contexts, formed by people connected by knowing each other, Facebook
members agreeing to be friends (in
Facebook), scientific authors having a
joint publication, and actors appearing in the same production.
Despite this diversity, many differ-
ent types of networks share charac-
teristic properties. Well known is that
any two individuals are connected
through just “six degrees of separa-
tion,” as first formulated in 2003 by
Frigyes Karinthy (see Barabási2) and
became known to a broad audience
through Stanley Milgram’s “small
world study.”
25 Likewise, for the
Web, Albert et al.
1 predicted a diam-
eter (maximum distance between two
nodes in the graph) of only 19 connec-
tions in the network formed by Web
pages and the links between them.
