Plücker Lecture 2011

Models and Behavior of the Internet, the World Wide Web and Online Social Networks & Convergent Sequences of Networks

Podcast of the Plücker lecture 1, see here

Podcast of the Plücker lecture 2, see here

Prof. Jennifer T. Chayes, Director of Microsoft Research New England

Date: November 9, 3:15 PM

LECTURE 1: Models and Behavior of the Internet, the World Wide Web and Online Social Networks

Date: November 11, 5:00 PM

LECTURE 2: Convergent Sequences of Networks

Venue: Lipschitz Saal, Mathematics Center, Endenicher Allee 60

 

Abstract

THE MATHEMATICS OF DYNAMIC RANDOM NETWORKS

During the past decade, dynamic random networks have become increasingly important in communication and information technology. Vast, self-engineered networks, like the Internet, the World Wide Web, and online social networks, have facilitated the flow of information, and served as media for social and economic interaction.
I will discuss both the mathematical challenges and opportunities that exist in describing these networks: How do we model these networks - taking into account both observed features and incentives? What processes occur on these networks, again motivated by strategic interactions and incentives, and how can we influence or control these processes? What algorithms can we construct on these networks to make them more valuable to the participants? In this talk, I will review the general classes of mathematical problems which arise on these networks, and present a few results which take into account mathematical, computer science and economic considerations. I will also present a general theory of limits of sequences of networks, and discuss what this theory may tell us about dynamically growing networks.

LECTURE 1: Models and Behavior of the Internet, the World Wide Web and Online Social Networks
Although the Internet, the World Wide Web and online social networks have many distinct features, all have a self-organized structure, rather than the engineered architecture of previous networks, such as phone or transportation systems. As a consequence of this self-organization, these networks have a host of properties which differ from those encountered in engineered structures: a broad "power-law" distribution of connections (so-called "scale-invariance"), short paths between two given points (so-called "small world phenomena" like "six degrees of separation"), strong clustering (leading to so-called "communities and subcultures"), robustness to random errors, but vulnerability to malicious attack, etc. During this lecture, I will first review some of the distinguishing observed features of these networks, and then discuss some of the models which have been devised to explain these features. I will also discuss processes and algorithms on these networks, focusing on a few particular examples.

LECTURE 2: Convergent Sequences of Networks
In the second lecture of this series, I will abstract some of the lessons of the first lecture. Inspired by dynamically growing networks, I will ask how we can characterize general sequences of graphs in which the number of nodes grows without bound. In particular, I will define various natural notions of convergence for a sequence of graphs, and show that, in the case of dense graphs and even some sparse graphs, many of these notions are equivalent. I will also give a construction for a function representing the limit of a sequence of graphs. I will review examples of some simple growing network models, and illustrate the corresponding limit functions. I will also discuss the relationship between these convergent sequences and some notions from mathematical statistical physics.