Note. From now on (May 2011) this is an archival page,
i.e. will not be modified. In particular the lecture notes may have errors
and certainly have much omitted relevant work. See the page
FMIE processes
(under construction) for any more recent lectures or papers.
STAT 260, Spring 2011: David Aldous
STAT 260, with catalog description Topics in Probability and Statistics,
is intended to have a different subject each semester.
My topic is (to invent a name)
Finite Markov Information-Exchange Processes.
The general set-up, outlined below, is directly or indirectly related to models
treated in literally thousands of papers over the last ten years, in fields such as
statistical physics and interacting particle systems; epidemic theory; broadcast algorithms on graphs;
ad hoc networks; social learning theory.
The general set-up: FMIE processes
There are n "agents".
Each agent has some "information" at time t.
Each pair (ij) meets at random times of rate \nu_{ij}, at which times they can update
their information according to some rule.
So it's a two-level modeling framework.
The bottom level is the "geometry", specified by the rate matrix (\nu_{ij}),
of how agents meet. The top level is the "content" of whatever phenomenon we are trying to model.
Existing literature tends to focus on specific geometries,
building up from simple to more
complex interaction rules.
A future research focus would be to attempt a more thorough analysis of
simple interaction rules used with general geometries,
analogous to the standard theory of finite Markov chains.
Much of the present course will
involve looking at existing literature which might be meaningfully translated
into the FMIE context. In particular one can
take algorithmic questions, interpretable as concerning ``spread of information",
which have been studied
in the traditional n-vertex graph context, and reconsider them in the
FMIE context.
Slides from lectures
Lectures are a mixture of slides and blackboard work.
Student talks
Nominally 25-minute talks, but you can over-run if there are only 2 that day.
Wednesday 20 April
Monday 25 April
- Jack Reilly: More about the rank-based game. (course project).
- Miki Racz: Combining voter and exclusion dynamics.
- Anupam Prakash: COMPUTING SYMMETRIC FUNCTIONS ON MEMORY BOUNDED SOCIAL
NETWORKS.
Wednesday 27 April
Wednesday 4 May
Papers
Here is an unorganized list of possibly relevant papers.
Offline books
- M. O. Jackson,
Social and Economic Networks (2008)
and David Easley and Jon Kleinberg
Networks, Crowds, and Markets (2010)
provide the best "big picture", but do not engage graduate-level mathematical probability.
- Rick Durrett,
Random Graph Dynamics (2006) and Mark Newman,
Networks: An Introduction (2010)
focus on models of network formation.
- Moez Draief and Laurent Massoulie,
Epidemics and Rumours in Complex Networks, (2010).
- A. Barrat, M. Barthelemy, and A. Vespignani,
Dynamical Processes on Complex Networks,
(2008).
Similar courses elsewhere
Here are some other courses on the broad "information and networks" theme which have interesting material accessible online.
These courses tend to cover a much broader range of topics at a less sophisticated mathematical level.
(Kleinberg; Cornell)
The Structure of Information Networks
(Leskovec; Stanford)
Social and
Information Network Analysis
(Saberi; Stanford)
Information Networks
(Kearns; U. Penn)
Social networks and algorithmic game theory
More advanced and specialized than the above is
(Mossel; Berkeley)
Social Choice and Networks.
Our course does not focus on models of network formation, which is a major topic
of other courses; see e.g.
my old course
Random graphs and complex networks.
Administration
Lecture times:
MW 5.00 - 6.30pm room 332 EVANS
Office Hours: Mondays 12.30 - 2.30 in 351 Evans.
If you email me (aldous@stat) put "STAT 260" in subject line.
Requirements for students.
Students taking course for credit need to do one of the following.
- Read a recent paper and give a 20-minute talk
during last 2 weeks of semester.
- Do one of the projects which will be mentioned in class (and then listed here).
These range from theory (proving something) to simulations to "literature search"
(what is known relevant to some vague question?).