NIPS 2003 Workshop on
Robust Communication Dynamics in Complex Networks 

Whistler, Canada, December 12-13 2003

 

 

 

internet

 

 

 

Overview   Speakers  Abstracts  Topics   Submission  CFP (.pdf, .doc)   Organizers    References   Schedule

Overview and Goals

Large-scale networks with complex patterns of communication between elements abound in both nature and in man-made systems (e.g., genetic pathways, ecological networks, social networks, networks of scientific collaboration, Internet, World Wide Web, phone-call networks, power grid etc.). The main objective of this workshop is to explore how various local communication schemes in distributed systems (e.g., gossip-style/epidemic protocols) and message-passing schemes for inference (e.g., Belief Propagation) may robustly achieve global objectives, such as accurate global computation, in the presence of various forms of noise, errors and attacks, and how their performance is affected by network dynamics and topology. 

 

The workshop aims at cross-fertilization among several research areas that has attracted an immense current interest. The first builds upon last year's highly successful NIPS workshop on Propagation Algorithms on Graphs with Cycles, which focused primarily on the theory of Belief Propagation in Bayesian Networks. The second research area is distributed machine learning which was touched upon in last year's NIPS workshop on Multi-Agent Learning. The final research area, statistical dynamics of complex network phenomena, is a rapidly burgeoning multi-disciplinary research topic that combines methods from computer science, statistical physics, nonlinear dynamics, econometrics and social network theory to study common problems in many systems exhibiting complex network structure. This topic has attracted much recent attention in the scientific literature as well as in popular publications (e.g., D. Watts, "Six Degrees: The Science of a Connected Age", 2003), but so far has not been presented at NIPS. 

Invited Talks

 

Contributed Talks

 

Tutorials

Posters

 

Abstracts (invited talks)

Kenneth Birman, Cornell University

 

Title: The Surprising Power of Epidemic Protocols

 

The gap between theory and practice has bedeviled distributed computing for decades. However, a new class of epidemic protocols has overcome this traditional problem. Gossip-styled communication systems (I'll give a number of examples) are so rapidly convergent that even if one simplifies the network model to facilitate analysis, the resulting theory seems to be highly predictive of real-world behavior. In effect, these protocols are robust not just to failures, but even to rather extreme oversimplification in the models used. Even very preliminary steps are letting us design systems in a new and much more intellectually satisfying way. Yet many problems remain open, inviting further dialog between theoreticians and practitioners.

 

Related papers:

 

 

Christos Faloutsos, Carnegie Mellon University

 

Title: Finding Patterns in Large Graphs

 

How does a 'normal' computer (or social) network look like? How can we spot `abnormal' sub-networks in the Internet, or web graph?

The answer to such questions is vital for outlier detection (terrorist networks, or illegal money-laundering rings), forecasting, and simulations ("how will a computer virus spread?").

 

The heart of the problem is to find which are the properties of real graphs that seem to persist over multiple disciplines. We list such "laws" and, more importantly, we propose a simple, parsimonious model, the "recursive matrix" (R-MAT) model, which can quickly generate realistic graphs, capturing the essence of each graph in only a few parameters. Contrary to existing generators, our model can trivially generate weighted, directed and bipartite graphs; it subsumes the celebrated Erdos-Renyi model as a special case; it can match the power law behaviors, as well as the deviations from them (like the "winner does not take it all" model of Pennock et al, 2002). We also present three parameter estimation techniques for R-MAT, and choose one called AutoMAT-fast, which gives the best fits with very low cost. We present results on multiple, large real graphs, where we show that the AutoMAT-fast parameters fit them very well.

 

Joint work with Deepay Chakrabarti.

 

Related Papers:

 

 

 

Michelle Girvan, Cornell University

 

Title: Community Structure in Complex Networks

 

A number of recent studies have focused on the statistical properties of networked systems such as social networks and the World Wide Web. Researchers have concentrated particularly on a few properties which seem to be common to many networks: the small-world property, power-law degree distributions, and network transitivity. Here, we highlight another property which is found in many networks, the property of community structure, in which network nodes are joined together in tightly-knit groups between which there are only looser connections. We propose a new method for detecting such communities, built around the idea of using centrality indices to find community boundaries. We also propose a measure for the strength of the community structure found by our algorithm, which gives us an objective metric for choosing the number of communities into which a network should be divided. We test our method on computer generated and real-world graphs whose community structure is already known, and find that it detects this known structure with high sensitivity and reliability. We also apply the method to several social and biological networks whose community structure is not well-known and find that it detects significant and informative community divisions in both cases.

 

Bert Kappen, University of Nijmegen 

 

Title: Validity Estimates for Belief Propagation on Random Graphs

 

Belief propagation and its generalizations, such as CVM, are a powerful method for inference and optimization. The methods are exact

on trees and structures with one loop, but also yield surprisingly good results for many other graphs that arise in concrete application domains. It is well-known, that real-world graphs are far from uniformly random and possess structure such as clustering and power-law behavior. In addition, links in the graph of opposite sign may cause frustration. In this presentation, we compute the domains of

validity of BP for numerous architectures for a simple, but interesting, special case: binary networks with pair-wise interaction and pair-wise approximation.

 

The results show, that the approximations are in 1) general good for sparse networks and scale well with network size 2) are rather insensitive to the amount of 'clustering' in the networks (local structures of highly interconnected nodes).

 

Joint work with Joris Mooij.

 

David Kempe (Univ. of Washington, Seattle)

 

Title: Epidemic Models of Communication in Networks

 

The flow of information through a large, decentralized network can be thought of as unfolding with the dynamics of an epidemic: nodes become ``infected'' with new information or updates, and subsequently they may spread this to their neighbors. This perspective has proved to be valuable from a technical point of view, both in the design of robust communication mechanisms for distributed computing systems, and for understanding the ways in which information propagates through systems over which we have limited control, such as social networks.

This talk will examine the dynamics of information flow in both these contexts. In the setting of distributed algorithms, we consider robust algorithms for spreading information when geographic locality is an issue; we find that subtle changes in the underlying rules used by such spreading algorithms -- particularly the balance between short-range and long-range communication -- can have qualitative global effects on the overall dynamics. By identifying the right balance of communication at different distance scales, one can obtain resilient algorithms for problems in which proximity-based look-up is an issue, such as locating the nearest copy of a resource in a distributed environment.

In the setting of social networks, we consider a collection of models developed in the mathematical social sciences to capture the communication processes at work in the diffusion of medical and technological innovations, the sudden and widespread adoption of various strategies in game-theoretic settings, and the effects of ``word of mouth'' in the promotion of new products. In particular, we develop algorithms with provable performance guarantees for a question recently raised by Domingos and Richardson in the context of viral marketing: if we can try to convince a subset of individuals to adopt a new product or innovation, and the goal is to trigger a large cascade of further adoptions, which set of individuals should we target?

 

The talk is based on joint work with Alan Demers, Jon Kleinberg, and Eva Tardos.

 

Related papers: 

 

Other (background) papers:

Other relevant (background) papers:

 

Title: Extreme Fluctuations in Small-Worlds with Relaxational Dynamics

 

Synchronization is a fundamental problem in natural and artificial coupled multi-component systems. We discuss to what extent small-world couplings (extending the same local relaxational dynamics through the random links) lead to the suppression of extreme fluctuations in such systems. In addition to the average `load' in the network, knowing the typical size and the distribution of the extreme fluctuations can be important from a system design viewpoint, since failures and delays are triggered by extreme events occurring on an individual node. We use the framework of non-equilibrium surface growth phenomena to test the collective properties of the small-world network and to characterize the degree of synchronization in the system. In the absence of the random links, the surface in the steady state is `rough' (strongly de-synchronized state) and the average and the extreme height fluctuations diverge in the same power-law fashion with the system size (number of nodes). With small-world links present, the average size of the fluctuations becomes finite (synchronized state)and the extreme heights diverge only logarithmically in the large system-size limit. This latter property can ensure synchronization in a practical sense in coupled multi-component autonomous systems with short-tailed noise and local relaxation through small-world links. The statistics of the extreme heights is governed by the Fisher-Tippett-Gumbel distribution. We illustrate our findings through a prototype synchronization problem in the context of scalable parallel computing.

 

Related papers: 

 

Marc Mezard, CNRS and Universite Paris Sud

 

Title: Constraint Satisfaction Networks: Belief Propagation and Beyond

 

General constraint satisfaction problems can be studied through belief propagation. This talk reviews this approach and underlines the basic underlying hypotheses. It is shown how a 'tiny' modification of belief propagation leads to the survey propagation algorithm, which shows a better ability to handle the effect of clustering in solution space.

 

Jared Saia, University of New Mexico

 

Title: Scalable and Attack Resistant Peer-to-peer Networks

 

This talk will discuss preliminary work on a project to design large-scale attack-resistant distributed networks. Our notion of attack-resistance depends on the idea of protecting critical invariants from adversarial attack. Some important critical invariants include: (i) an arbitrarily large fraction (e.g. 99%) of the unattacked peers can access an arbitrarily large fraction (e.g. 99%) of the content stored in the network, (ii) an arbitrarily large fraction of the unattacked peers remain connected in the network, and (iii) an arbitrarily large fraction of the peers must either follow a fixed set of rules, or be disconnected from the network.

We propose to maintain these invariants under attack by an omniscient adversary, i.e. we assume that the adversary knows, for example, the topology of the network, where content is stored in the network, and the network protocols. We further assume that the adversary can attack a constant fraction of the peers in the network. In a simple model of attack, the attacked peers will simply drop out of the network(i.e. the fail-stop fault model).In a more complicated model, the attacked peers can collude, and try to disrupt the functioning of the network by sending false information to other peers (i.e. the Byzantine fault model).We will discuss strategies for handling both types of attack.

 

Related papers: 

 

Max Welling, University of California, Irvine

 

Title: On the Choice of Clusters for Generalized Belief Propagation

 

Belief propagation on cyclic graphs has recently been extended to include messages between clusters that contain more than two nodes [Yedidia et al '00]. This method has its roots in physics where the highly regular graphs make it possible to choose those clusters in a sensible way. However, the graphs considered  in applications such as error-correcting-decoding or medical diagnosis are highly irregular and a principled procedure to choose the clusters is missing.

 

In this talk I will address this issue and propose a sequential scheme for adding clusters a few at a time. In contrast to the usual top-down construction of region graphs, this method proposes to build region graph bottom-up. The class of clusters to be considered is reduced by formulating a "region graph reduction method". This organizes clusters in equivalence classes such that each member of the class has exactly the same solutions under generalized belief propagation. An entropy based measure, dependent on quantities local to the cluster under consideration only, is introduced to evaluate the quality of a cluster for inclusion in the approximation. Some preliminary experiments show encouraging results but also emphasize the difficulty of this problem.

 

Related papers: 

 

Jonathan Yedidia, MERL

 

Title: Belief Propagation and Transform Codes

 

Related papers:  

 

Format

This is going to be a 2-day workshop. There will be eight invited talks (roughly 40 minutes each) and shorter contributed talks from researchers in industry and academia, as well as a panel discussion. We will hold a poster session if we receive a sufficient number of good submissions. The workshop will emphasize relatively high-level perspectives, including surveys of sub-fields and problem domains. The workshop is intended to be accessible to the broader NIPS community and to encourage communication between sub-fields. 

Suggested Topics

The list of possible topics includes (but is not limited to) the following: 

  • Dynamics and topological properties (e.g., small-world, scale-free, clustering) of real-world large-scale networks (e.g., Internet, World Wide Web, peer-to-peer networks, biological pathways, social networks) 
  • Communication protocols and information propagation algorithms on such networks (e.g., epidemic/gossip-based protocols) 
  • Propagation algorithms for inference on various graphical models such as Markov and/or Bayesian networks, constraint networks 
  • Free energy (Kikuchi approximations) and related cost functions 
  • Variants of propagation algorithms (e.g., belief propagation and its generalizations, constraint propagation, survey propagation) 
  • Efficiency and accuracy of propagation algorithms, convergence results 
  • Applications of propagation algorithms to various problems (e.g., web search, communication, peer-to-peer, error-correcting coding, image analysis, probabilistic diagnosis, collaborative learning, etc.) 

Submission Instructions

We invite submissions of extended abstracts (up to 2 pages, not including bibliography) for the short contributed talks and/or posters. The submission should present a high-level description of recent or ongoing work related to the topics above. We will also explore the possibility of publishing papers based on invited and submitted talks in a special issue of an appropriate journal. Email submissions to nips03workshop@watson.ibm.com as attachments in Postscript or PDF, no later than October 22, 2003. 

Important Dates and Deadlines

  • October 22, 2003: Deadline for the submission of extended abstracts (1-2 pages not including bibliography) 
  • October 28, 2003: Notification of acceptance/rejection 

Organizing Committee

Dr. Rajarshi Das

IBM T. J. Watson Research Center

19 Skyline Drive 
Hawthorne, NY 10532, USA
rajarshi@us.ibm.com
http://www.research.ibm.com/people/r/rajarshi

Prof. Cristopher Moore
University of New Mexico 
Computer Science Department and Department of Physics and Astronomy 
Albuquerque, NM 87131, USA 
moore@cs.unm.edu
http://www.cs.unm.edu/~moore/

Dr. Irina Rish (primary contact)
IBM T. J. Watson Research Center  
19 Skyline Drive, 
Hawthorne, NY 10532, USA
rish@us.ibm.com
http://www.research.ibm.com/people/r/rish

Dr. Gerry Tesauro
IBM T. J. Watson Research Center   
19 Skyline Drive, 
Hawthorne, NY 10532, USA
gtesauro@us.ibm.com

 

Information

 

Workshop Schedule

·        Friday, Dec. 12

·        Saturday, Dec. 13