Carnegie Mellon University, Pittsburgh, PA
April 910, 2004
Online
Registration Form
The explosive use of the World Wide Web as a communication medium
has led to significant research interest in analyzing and developing
algorithms for complex networks. This workshop will bring together
several researchers who have been working in this general area
to discuss current topics such as random graph models of the Web,
trust networks, modeling content and connectivity, and decentralized
information access.
Web Structure: The World Wide Web is
a large and complex network, evolving in a way that is difficult
to describe with any precision. Several concrete investigations
of the structure of the Web have yielded interesting and surprising
facts, including power laws for degree, existence of small dense
subgraphs, and strong component structure. Given the complexity
of the Web, several researchers have attempted to explain its
structure as the outcome of a random process. New random graph
models, for example using preferential attachment rules, have
led to new problems not found in traditional random graph analysis.
However, at the moment these simple models only "explain'"
the link structure; it would be most exciting to try to model
page content in some useful way. In general, the models must be
developed much further to produce useful tools for predicting
future growth of the Web, and for estimating the performance of
algorithms related to tasks such as searching.
Webs of Trust: A web of trust is a graph
whose nodes represent people, with weights on directed edges conveying
the level of trust that one person confers on another. In some
cases, we additionally have data on the opinions some of these
people have about certain items. A number of interesting questions
has been raised by the growth of large webs of trust, such as
those that exist within eBay and Epinions. For example, how does
one propagate trust, so as to infer trust values between nodes
with no edge between them? What is the economic value of a unit
of trust? The answers to these questions will involve research
that spans a number of disciplines including game theory, linear
algebra, and machine learning.
Content and Connectivity: Early investigations
into the problem of searching the Web led to algorithms for exploiting
the hyperlink structure of the Web to find "authoritative"
Web sites, or popular pages. Advances in this direction have typically
used eigenvector methods, combinatorial analysis, or random walk
techniques. Separately, researchers have advanced techniques for
modeling the distribution of topics in document collections using
probabilistic modeling, which has led to improved methods for
document classification and collaborative filtering. However,
there is currently no realistic model of how content and connectivity
evolve together on the Web which does not assume a fixed, static
set of topics. Advances in this direction have the potential to
improve search technology, as well as to inform other areas such
as social networks, for example in studying the evolution of scientific
topics, or even in biology where protein interaction networks
can be studied together with the information contained in genetic
expression profiles.
Distributed Information Access: Access
of information using local rather than global information occurs
in many areas. For example, in human social networks information
may often spread by "word of mouth." Stanley Milgram's
famous study in the 1960s was an early attempt to understand how
local connectivity can lead to efficient communication in social
networks. More recently, the emergence of peertopeer computer
networks, where data files are distributed without a global index,
has prompted interest in studying decentralized information access
on the Web. A rudimentary understanding of the efficiency of simple
protocols for distributed search has been achieved, but there
is significant potential for improved models, which may in turn
lead to more efficient algorithms and distributed communication
protocols.
Organizing Committee:
Colin
Cooper, King's College
London
Christos
Faloutsos, Carnegie
Mellon University
Alan Frieze,
Carnegie Mellon University
John
Lafferty, Carnegie
Mellon University
Registration Is Required
Anyone
planning to attend this workshop (including CMU faculty and students)
should register online.
Online
Registration Form
Hotel Accommodations  Deadline Extended to March 26th
We are holding hotel rooms for outoftown visitors at the Holiday
Inn Select, 100 Lytton Avenue, Pittsburgh, PA 15213. To take advantage
of the prenegotiated rate of $95 per night ($108.30 including
taxes), you should call the Holiday Inn at 4126826200 by Friday, March 26th to make your reservations and be sure to ask for the ALADDIN
Web Workshop meeting rate.
Program
All sessions will be held in Newell Simon Hall 3305
Walking
directions from the Holiday Inn to Newell Simon Hall 3305
Friday April 9 
10.00A.M. 
Coffee 
10.20A.M. 
Guy Blelloch, Carnegie
Mellon
Welcome and Introductions 
10.30A.M. 
Michael Kearns, University
of Pennsylvania
The Economics of Social Networks (abs) 
11.30A.M. 
Milena Mihail, Georgia
Tech
Conductance of Power Law and Scale Free Graphs (abs) 
12.30P.M. 
Lunch 
2.00P.M. 
Lincoln Lu, UC
San Diego
Spectra of random power law graphs (abs),
(pdf1),
(pdf2,)
(pdf3)

3.00P.M. 
Sanjeev Arora, Princeton
University
Expander flows and a sqrt{log n}approximation for graph expansion/sparsest
cut (abs) 
4.00P.M. 
Coffee 
4.30P.M. 
Andrei Broder, IBM
Research
Sic Transit Gloria Telae: Towards an Understanding of the
Webs Decay (abs)
(pdf)

7.00P.M. 
Workshop Dinner 

Saturday April 10 
8.45A.M. 
Coffee 
9.15A.M. 
Andrew Tomkins, IBM
Almaden
Online Conversations: Aliases, Topics, and Propagation Networks
(abs), (pdf1)
(pdf2)

10.15A.M. 
Coffee 
10.30A.M. 
Fan Chung Graham, UC San Diego
Coupling online and offline analyses for random power law
graphs (abs) 
11.30A.M. 
Peter Dodds, Columbia
University
Social Search and the Small World Phenomenon: Experiment and
Theory (abs),
(pdf1),
(pdf2),
(pdf3,)
(pdf4)

12.30P.M. 
Lunch 
1.30P.M. 
Pedro Domingos, University
of Washington
Modeling and optimizing word of mouth (abs),
(pdf1),
(pdf2)

2.30P.M. 
David Kempe, University of Washington
Maximizing the Spread of Influence in a Social Network (abs),
(pdf) 
3.30P.M. 
Marcio Menezes, University
of Notre Dame
Hot Spots and Universality in Network Dynamics (abs) 
Read
the Abstracts