CENTER Carnegie Mellon UniversityCarnegie Mellon Computer Science DepartmentSchool of Computer Science
Web Structure and Algorithms
Related Activities
Outreach Roadshow

Carnegie Mellon University, Pittsburgh, PA
April 9-10, 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 peer-to-peer 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 out-of-town visitors at the Holiday Inn Select, 100 Lytton Avenue, Pittsburgh, PA 15213. To take advantage of the pre-negotiated rate of $95 per night ($108.30 including taxes), you should call the Holiday Inn at 412-682-6200 by Friday, March 26th to make your reservations and be sure to ask for the ALADDIN Web Workshop meeting rate.


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 on-line and off-line 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



This material is based upon work supported by National Science Foundation under Grant No. 0122581.
Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the
National Science Foundation