Artificial Intelligence

AI Seminar-Popularity versus similarity in growing networks.

Friday, November 30, 2012, 3:00pm - 4:00pm PDTiCal
11th Floor Conf. Room (#1135)
Dmitri Krioukov


Popularity is attractive -- this is the formula underlying preferential attachment, a popular explanation for the emergence of scaling in growing networks. If new connections are made preferentially to more popular nodes, then the resulting distribution of the number of connections that nodes have follows power laws observed in many real networks. Preferential attachment has been directly validated for some real networks, including the Internet. Preferential attachment can also be a consequence of different underlying processes based on node fitness, ranking, optimization, random walks, or duplication. Here we show that popularity is just one dimension of attractiveness. Another dimension is similarity. We develop a framework where new connections, instead of preferring popular nodes, optimize certain trade-offs between popularity and similarity. The framework maps to a model of random geometric graph growing in hyperbolic spaces, explaining popularity preference as a local optimization process. As opposed to preferential attachment, the optimization framework accurately describes large-scale evolution of technological (Internet), social (web of trust), and biological (E.coli metabolic) networks, predicting the probability of new links in them 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 span computer science, physics, and mathematics of massive networks. Statistical analysis of large networks; transport and signaling processes, such as navigation and routing in the Internet and other complex networks; geometric approaches to modeling and analysis of the structure and dynamics of massive networks and other big data -- are examples of more specific areas of his research. The results of his research get often published in top journals in interdisciplinary science, physics, and computer science and engineering, periodically attracting massive media attention and coverage. He is best known for his results on network navigability, routing, and statistical analysis of networks. His recent research focuses on large-scale network geometry, modeling real networks ascertain ``discretizations'' of hyperbolic spaces and de Sitter spacetimes.

Home Page:

« Return to Events