Networks and Algorithms
Summer Math Institute
Cornell University
Summer 2006
|
|
Overview
This is a project based course to study real networks,
and algorithms to analyze properties of these
networks. Graphs/Networks are use to model systems such as the web
(nodes are web pages and edges are link between pages), social
networks (links among people or other social entities), and biological
networks (metabolic networks, food webs, gene interactions). In
networks studies people are interested in understanding network
properties, and study the effect of these properties (network
structure) on the system's behavior. For example in the context of the
web, we want to answer questions like what does the link structure
tell us about content? We would like to use the link structure
of the web, for instance, to help search engines find
authoritative
pages for users' queries. Other kinds of network
studies aim to create models of networks (random graphs) that can help
us understand properties of these networks.
Sketch of Course Work :
- Find a real network (see some examples below)
- Identify some good questions/problems and algorithms to attack
the problem (we will do this together)
- Code algorithm and apply the algorithm to the selected network(s)
- Generate
random
networks with similar properties than the
real networks
Readings:
Algorithm Design. J. Kleinberg and E. Tardos. Addison-Wesley, 2005
The motivation for preparing this course came from Jon Kleinberg's
course on
The Structure of Information Networks. The web page of Kleinberg's
course has references to many recent research papers in this area.
Handouts/Syllabus
- Lecture 1: graphs, paths, connectivity (from Chapter 3 of Kleinberg and Tardos).
- Project Lab 1
- Lectures 2 and 3: connectivity, trees, algorithms to compute connected components BFS and DFS.
- Project Lab 2
- Project Lab 3
- Lecture 4 and 5: Queues, Stacks, implementing BFS,
clustering coeficients, shortest path lenght
- Project Lab 4 and 5
- Lecture 6: Clustering Methods: Neighbor Joining Algorithm
and K-Means Algorithm.
Ideas for Projects/ Network datasets
- How Search Engines Work?
Study and implement algorithms
used by search engines. What does the web graph links structure
tell us about content?
Data on Web subgraphs: There
are different datasets available for download. One set is
maintained by
Panayiotis Tsaparas.
- Small-World Phenomena.
If you choose any two people in the
world at random, how many acquaintances are needed to create a
chain between them?
Data on Small-World: Columbia Small-World
Project is an on-line experiment to text the idea that any two
people in the world can be connected via 'six degree of
separation'
.
- Community Structure in the United States House of
Representatives.
We have a very interesting data on the on
the committees and subcommittees in the U.S. House of
Representative. This data was given to us by one of the authors of
the paper A
Network Analysis of Committees in the United States House of
Representatives. There are some advantages on working with this
data: it is new so there are still many things to be explore, we
are in contact with the author, it is about politics!!! Mason's web page .
- Various
Networks Databases from Albert-László Barabási web page
These include a Cellular Network (Whole Cellular Network and
Metabolic Network), a Protein Interaction Network and others.
- Uri Alon's
collection of complex networks
These include E. coli
transcription network, Yeast transcription network, social
networks of positive sentiment
, protein structure networks,
word adjacency networks (on different languages) and others.
- Gallery of Network Images
- Semantic
Network. Results of an experiment in which participants were
asked to write the first word that came to mind that was
meaningfully related or strongly associated to the presented word.
Example BLUE was associated to SKY, GREEN, RED, EYE, COLOR, WATER,
SAD, INK, AZURE, etc
- A survey on the modeling of complex networks.
The structure and function of complex networks
SIAM Review, 45:167--256, 2003.
Yannet Interian