Dr. Tuhin Sahai, a Staff Research Scientist at United Technologies Research Center, will be visiting the research group on

**Wed, May 4, 2011**. His research interest is in managing uncertainty, nonlinear dynamics and control, and scientific and distributed computation. [website]Dr. Sahai will present a lecture at

**11am in E2 2243 (old CAD lab)**, with the title**"Hearing the Clusters in a Graph and other Scalable Algorithms for Complex Networks"**. All group members are encouraged to attend. The talk summary can be found in the remainder of this announcement.**Lecture summary:**

Complex networks such as building systems, UAV swarms and communication networks are of paramount importance to modern day applications. In this talk, which is divided into two parts, we construct efficient algorithms to design, analyze and propagate uncertainty in these networks.

In the first part, to design the dynamics of complex networks, we propose a novel decentralized algorithm to partition graphs. The algorithm recovers the solution of a popular approach called spectral clustering without the need for centralized eigenvector computations.

We prove that propagating waves through the graph followed by a Fast Fourier Transform at every node yields the local component of every eigenvector of the graph Laplacian, thus assigning the nodes to clusters. For large graphs, our algorithm is orders of magnitude faster than random walk based approaches. We prove that our algorithm is equivalent to spectral clustering and derive convergence rates. We use this decentralized clustering algorithm to accelerate distributed estimation in building systems.

In the second part, for the distributed simulation and analysis of complex networks, we propose a new algorithm called Adaptive Waveform Relaxation (AWR). AWR is significantly faster than Waveform Relaxation (WR), an algorithm to simulate high-dimensional differential-algebraic equations. The speed-up is obtained by using error bounds to adaptively compute the time window for simulation. This algorithm is demonstrated on a communication network example.

We will conclude the talk by merging distributed clustering with Adaptive Waveform Relaxation to construct a complete framework for decentralized simulation of dynamical systems. We show how one can apply this framework to propagate uncertainty through complex networks and illustrate the method on a simple example.

In the first part, to design the dynamics of complex networks, we propose a novel decentralized algorithm to partition graphs. The algorithm recovers the solution of a popular approach called spectral clustering without the need for centralized eigenvector computations.

We prove that propagating waves through the graph followed by a Fast Fourier Transform at every node yields the local component of every eigenvector of the graph Laplacian, thus assigning the nodes to clusters. For large graphs, our algorithm is orders of magnitude faster than random walk based approaches. We prove that our algorithm is equivalent to spectral clustering and derive convergence rates. We use this decentralized clustering algorithm to accelerate distributed estimation in building systems.

In the second part, for the distributed simulation and analysis of complex networks, we propose a new algorithm called Adaptive Waveform Relaxation (AWR). AWR is significantly faster than Waveform Relaxation (WR), an algorithm to simulate high-dimensional differential-algebraic equations. The speed-up is obtained by using error bounds to adaptively compute the time window for simulation. This algorithm is demonstrated on a communication network example.

We will conclude the talk by merging distributed clustering with Adaptive Waveform Relaxation to construct a complete framework for decentralized simulation of dynamical systems. We show how one can apply this framework to propagate uncertainty through complex networks and illustrate the method on a simple example.