Advanced Networks Colloquium: Dmitri Krioukov, "Popularity vs. Similarity in Growing Networks"
Friday, November 11, 2011
1146 A.V. Williams Building
301 405 6579
Advanced Networks Colloquium
Popularity vs. Similarity in Growing Networks
University of California, San Diego
| Video |
Preferential attachment is a powerful mechanism explaining the emergence of scaling in growing networks. If new connections are established preferentially to more popular nodes in a network, then the network is scale-free. Here we show that not only popularity but also similarity is a strong force shaping the network structure and dynamics. We develop a framework where new connections, instead of preferring popular nodes, optimize certain trade-offs between popularity and similarity. The framework admits a geometric interpretation, in which preferential attachment emerges from local optimization processes. As opposed to preferential attachment, the optimization framework accurately describes large-scale Internet evolution, predicting new links in the Internet with a remarkable precision. The developed framework can thus be used for predicting new links in evolving networks, and provides a different perspective on preferential attachment as an emergent phenomenon.
Dmitri Krioukov graduated from St. Petersburg State University with Diploma in Physics in 1993. In 1998 he received his Ph.D. in Physics from Old Dominion University, and joined the networking industry at Dimension Enterprises. After their acquisition, he accepted a research scientist position with Nortel Networks. He has been with Cooperative Association for Internet Data Analysis (CAIDA) at the University of California, San Diego (UCSD), as a senior research scientist since 2004. His interests include complex network topology, geometry, and evolution. His recent application of geometric network mapping methods to the Internet resolved the longstanding problem of designing optimal Internet routing, and was featured in the news world-wide.