A few hubs with many connections share with
many individuals with few connections.
BY BENJAMIN DOERR, MAHMOUD FOUZ, AND TOBIAS FRIEDRICH
This visualization by Miguel Rios at Twitter
shows the volume of @replies traveling into
and out of Japan and worldwide retweets
in the one-hour period just before and after
the Tōhoku earthquake on March 11, 2011.
For an animated version visit http://blog.
studied network topologies need at
least logarithmic time. Surprisingly,
nodes with few neighbors are crucial
for quick dissemination.
UNDERSTANDING STRUCTURAL AND algorithmic
properties of complex networks is important, due in
part to the Internet’s global social and commercial
importance. Our focus here is to analyze how news
spreads in social networks, simulating a simple
information-spreading process in various network
topologies and demonstrating that news spreads much
more quickly in existing social-network topologies
than in other network topologies. We support this
finding by analyzing information spreading in the
mathematically defined preferential attachment (PA)
network topology, a common model for real-world
networks, proving that sublogarithmic time suffices to
spread news to all nodes of a network. All previously
Social networks like Facebook and
Twitter are reshaping the way people
communicate and take collective action, playing a crucial role in, for example, the 2011 Arab Spring uprisings
and London riots. It has been argued
that the “instantaneous nature” of
these networks influenced the speed
Social networks grow naturally; their
graph structure is not designed for any
particular use but still allows for the
quick spread of news.
Our mathematical proof shows rumors
in social networks spread much more
quickly than in most other network
topologies, even complete graphs.
The source of the speedy spread of
information is fruitful interaction
between the few nodes with many
neighbors and the large number of
nodes with few neighbors.