9th Workshop on Algorithms and Models for the Web Graph
Dalhousie University in Halifax, Nova Scotia, Canada
June 22-23, 2012
Large scale-free networks are not disassortative
Mixing patterns in large self-organizing networks, such as the Internet, the World Wide Web, social and biological networks are often characterized by degree-degree correlations between neighbouring nodes. In this paper we propose a new way of measuring degree-degree correlations. We show that the commonly used assortativity coefficient significantly underestimates the magnitude of correlations, especially in large disassortative networks. We mathematically explain this phenomenon and validate the results on synthetic graphs and real-world network data. As an alternative, we suggest to use rank correlation measures such as the well-known Spearman's rho. Our experiments convincingly show that Spearman's rho produces consistent values in graphs of different sizes but similar structure, and it is able to reveal strong (positive or negative) correlations in large graphs. In particular, using the Spearman's rho we show that preferential attachment model exhibits significant negative degree-degree correlations. We also discover much stronger negative correlations in Web graphs than was previously thought. We conclude that rank correlations provide a suitable and informative method for uncovering network mixing patterns.
Nelly Litvak is an Associate Professor in the group Stochastic operations Research at University of Twente, The Netherlands. Nelly received her PhD in Stochastic Operations Research from Eindhoven University of Technology (EURANDOM) in 2002. Last years she has been worked on the analysis of complex networks, in particular algorithms for node ranking, analytical studies of network algorithms, and analysis of network correlations. Her other research interests are in stochastic processes, queueing theory, and probabilistic solutions for combinatorial problems. Nelly has received several grants and awards, she was an invited visitor in INRIA (France), University of South Australia, Georgia Institute of Technology, and Columbia University.
Strategic Network Models: From Building to Bargaining
We consider two game theoretic network models - one concerning network formation, and the other concerning bargaining on exchange networks. In the first case, we define the model and show that it has equilibria which support many observed network structures, including those of the web - such as triadic closure and heavy-tailed degree distributions. In the second case, we study the well-known Nash bargaining equlibria on exchange networks. We construct natural local dynamics, achievable by actual players, and show that this dynamics converges quickly to an approximate Nash bargaining equilibrium.
Jennifer Tour Chayes is Distinguished Scientist and Managing Director of Microsoft Research New England. Her research areas include phase transitions in discrete mathematics and computer science, structural and dynamical properties of self-engineered networks, and algorithmic game theory. She is the coauthor of over 110 scientific papers and the co-inventor of over 25 patents. She serves on numerous institute boards, advisory committees and editorial boards, including as the chair of the Turing Award Selection Committee. Chayes is the recipient of the NSF Postdoctoral Fellowship, the Sloan Fellowship, the UCLA Distinguished Teaching Award, and the Women of Vision Leadership Award of the Anita Borg Institute. She is a Fellow of the American Association for the Advancement of Science and the Fields Institute, and a National Associate of the National Academies.
All participants of WAW 2012 are invited to attend a lecture in the MPrime-MoMiNIS distinguished lecture series, on Thursday June 21, afternoon, by:
The Wisdom of Crowds and the Long Tail
The Web continues to grow and evolve very fast, changing our daily lives. This activity represents the collaborative work of the millions of institutions and people that contribute content to the Web as well as the one billion people that use it. In this ocean of hyperlinked data there is explicit and implicit information and knowledge. Web data mining is the task of analyzing this data and extracting information and knowledge for many different purposes. The data comes in three main flavors: content (text, images, etc.), structure (hyperlinks) and usage (navigation, queries, etc.), implying different techniques such as text, graph or log mining. Each case reflects the wisdom of some group of people that can be used to make the Web better. An important element of Web usage related to data mining is the long tail, that has a crucial role regarding data aggregation, personalization and privacy. In this talk we cover these concepts and give specific examples.
Ricardo Baeza-Yates is VP of Yahoo! Research for Europe, Middle East and Latin America, leading the labs at Barcelona, Spain and Santiago, Chile, since 2006, as well as supervising the lab in Haifa, Israel since 2008. He is also part time Professor at the Dept. of Information and Communication Technologies of the Universitat Pompeu Fabra in Barcelona, Spain, since 2005. Until 2005 he was Professor and Director of the Center for Web Research at the Department of Computer Science of the Engineering School of the University of Chile. He obtained a Ph.D. from the University of Waterloo, Canada, in 1989. Before he obtained two masters (M.Sc. CS & M.Eng. EE) and the electrical engineering degree from the University of Chile, Santiago. He is co-author of the best-seller Modern Information Retrieval textbook, published in 1999 by Addison-Wesley with a second enlarged edition in 2011, as well as co-author of the 2nd edition of the Handbook of Algorithms and Data Structures, Addison-Wesley, 1991; and co-editor of Information Retrieval: Algorithms and Data Structures, Prentice-Hall, 1992, among more than 300 other publications. He has received the Organization of American States award for young researchers in exact sciences (1993) and the CLEI Latin American distinction for contributions to CS in the region (2009). In 2003 he was the first computer scientist to be elected to the Chilean Academy of Sciences. During 2007 he was awarded the Graham Medal for innovation in computing, given by the University of Waterloo to distinguished ex-alumni. In 2009 he was named ACM Fellow and in 2011 IEEE Fellow.