From: Paul Beame (beame@cs.washington.edu)
Date: Mon Feb 02 2004 - 18:40:51 PST
Immediately after theory seminar...
"Networks, power laws and phase transitions"
Raissa M. D'Souza
Theory Group, Microsoft Research
2:30pm, Tuesday February 3, 2004
Guggenheim 317
We are beginning to understand how pervasive network structures are in
natural and engineered systems, and to formulate mathematical theories
of network growth. A common observation in technological, biological
and social networks is the existence of "scale-free" probability
distributions, and of phase transitions (abrupt changes in behavior,
such as the emergence of a giant connected core). Mathematical models
of
random graphs based on the paradigm of preferential attachment (PA) have
had much success in reproducing the observed scale-free properties.
Rather than assuming PA, we begin with a more basic mechanism, of
competition between opposing forces, and show that PA can arise as the
solution to the optimization problem. In addition, certain aspects of
Internet growth, that have not been captured by previous models, emerge
from our framework. =20
I begin this talk by surveying characteristic structures of different
types of networks. Then present the formulation of our model of
"competition induced preferential attachment", including our main result
proving that the degree distribution for the resulting network
structures is scale free up to a finite threshold, and decays
exponentially above this threshold. Time permitting, I will digress to
a discussion of phase transitions, and present a computational study of
"traffic" on a lattice, which shows a sharp transition from free flowing
to fully jammed. It is a simple model whose behavior remained elusive
for over a decade.
_______________________________________________
Theory-group mailing list
Theory-group@cs.washington.edu
http://mailman.cs.washington.edu/mailman/listinfo/theory-group
This archive was generated by hypermail 2.1.6 : Mon Feb 02 2004 - 18:43:41 PST