A few hubs with many connections share with many individuals with few connections

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 studied network topologies need at least logarithmic time. Surprisingly, nodes with few neighbors are crucial for quick dissemination.