### Estimating PageRank on Graph Streams

- Series
- ACO Student Seminar
- Time
- Wednesday, October 8, 2008 - 13:30 for 2 hours
- Location
- Skiles 269
- Speaker
- Atish Das Sarma – CS/ACO, Georgia Tech

- You are here:
- GT Home
- Home
- News & Events

- Series
- ACO Student Seminar
- Time
- Wednesday, October 8, 2008 - 13:30 for 2 hours
- Location
- Skiles 269
- Speaker
- Atish Das Sarma – CS/ACO, Georgia Tech

This study focuses on computations on large graphs (e.g., the web-graph) where the edges of the graph are presented as a stream. The objective in the streaming model is to maintain small amount of memory and perform few passes over the data.
In the streaming model, we show how to perform several graph computations including estimating the probability distribution after a random walk of certain length l, estimate the mixing time, and the conductance. We can compute the approximate PageRank values in O(nM^{-1/4}) space and O(M^{3/4}) passes (where n is the number of nodes and M is the mixing time of the graph). In comparison, a standard (matrix-vector multiplication) implementation of the PageRank algorithm will take O(n) space and O(M) passes. The main ingredient in all our algorithms is to explicitly perform several random walks of certain length efficiently in the streaming model. I shall define and motivate the streaming model and the notion of PageRank, and describe our results and techniques.
Joint work with Sreenivas Gollapudi and Rina Panigrahy from Microsoft Research.

- Series
- Mathematical Biology Seminar
- Time
- Wednesday, October 8, 2008 - 11:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Dr. John Glasser – CDC/CCID/NCIRD

**Background:** We endeavor to reproduce historical observations and to identify and remedy the cause of any disparate predictions before using models to inform public policy-making. We have no finely age- and time-stratified observations from historical pandemics, but prior exposure of older adults to a related strain is among the more compelling hypotheses for the w-shaped age-specific mortality characterizing the 1918 pandemic, blurring the distinction between annual and pandemic influenza.

** Methods:** We are attempting to reproduce patterns in annual influenza morbidity and mortality via a cross-classified compartmental model whose age class sojourns approximate the longevity of clusters of closely-related strains. In this population model, we represent effective inter-personal contacts via a generalization of Hethcote's formulation of mixing as a convex combination of contacts within and between age groups. Information about mixing has been sought in face-to-face conversations, a surrogate for contacts by which respiratory diseases might be transmitted, but could also be obtained from household and community transmission studies. We reanalyzed observations from several such studies to learn about age-specific preferences, proportions of contacts with others the same age. And we obtained age-specific forces of infection from proportions reporting illness in a prospective study of household transmission during the 1957 influenza pandemic, which we gamma distributed to correct for misclassification. Then we fit our model to weekly age-specific hospitalizations from Taiwan's National Health Insurance Program, 2000-07, by adjusting a) age-specific coefficients of harmonic functions by which we model seasonality and b) probabilities of hospitalization given influenza.

** Results:** While our model accounts for only 30% of the temporal variation in hospitalizations, estimated conditional probabilities resemble official health resource utilization statistics. Moreover, younger and older people are most likely to be hospitalized and elderly ones to die of influenza, with modeled deaths 10.6% of encoded influenza or pneumonia mortality.

** Conclusions:** Having satisfactorily reproduced recent patterns in influenza morbidity and mortality in Taiwan via a deterministic model, we will switch to a discrete event-time simulator and - possibly with different initial conditions and selected parameters - evaluate the sufficiency of projected pandemic vaccine production.

Joint work with Denis Taneri, and Jen-Hsiang Chuang

- Series
- PDE Seminar
- Time
- Tuesday, October 7, 2008 - 15:15 for 1.5 hours (actually 80 minutes)
- Location
- Skiles 255
- Speaker
- Nassif Ghoussoub – University of British Columbia, Canada

We describe how several nonlinear PDEs and evolutions including stationary and dynamic Navier-Stokes equations can be formulated and resolved variationally by minimizing energy functionalsof the form
I(u) = L(u, -\Lambda u) + \langle \Lambda u, u\rangle
and
I(u) = \Int^T_0 [L(t, u(t), -\dot u(t) - \Lambda u(t)) + \langle\Lambda u(t), u(t)\rangle]dt + \ell (u(0) - u(T)
\frac{u(T) + u(0)}{2}
where L is a time-dependent "selfdual Lagrangian" on state space, is another selfdual "boundary Lagrangian", and is a nonlinear operator (such as \Lambda u = div(u \otimes u) in the Navier-Stokes case). However, just like the selfdual Yang-Mills equations, the equations are not obtained via Euler-Lagrange theory, but from the fact that a natural infimum is attained. In dimension 2, we recover the well known solutions for the corresponding initial-value problem as well as periodic and anti-periodic ones, while in dimension 3 we get Leray solutions for the initial-value problems, but also solutions satisfying u(0) = \alpha u(T ) for any given in (-1, 1). It is worth noting that our variational principles translate into Leray's energy identity in dimension 2 (resp., inequality in dimension 3). Our approach is quite general and does apply to many other situations.

- Series
- Geometry Topology Seminar
- Time
- Monday, October 6, 2008 - 14:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 269
- Speaker
- A. Sikora – SUNY Buffalo

W. Goldman proved that the SL(2)-character variety X(F) of a closed surface F is a holonomic symplectic manifold. He also showed that the Sl(2)-characters of every 3-manifold with boundary F form an isotropic subspace of X(F). In fact, for all 3-manifolds whose SL(2)-representations are easy to analyze, these representations form a Lagrangian space. In this talk, we are going to construct explicit examples of 3-manifolds M bounding surfaces of arbitrary genus, whose spaces of SL(2)-characters have dimension as small as possible. We discuss relevance of this problem to quantum and classical low-dimensional topology.

- Series
- Analysis Seminar
- Time
- Monday, October 6, 2008 - 14:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Hrant Hakobyan – University of Toronto

A mapping F between metric spaces is called quasisymmetric (QS) if for every triple of points it distorts their relative distances in a controlled fashion. This is a natural generalization of conformality from the plane to metric spaces. In recent times much work has been devoted to the classification of metric spaces up to quasisymmetries. One of the main QS invariants of a space X is the conformal dimension, i.e the infimum of the Hausdorff dimensions of all spaces QS isomorphic to X. This invariant is hard to find and there are many classical fractals such as the standard Sierpinski carpet for which conformal dimension is not known. Tyson proved that if a metric space has sufficiently many curves then there is a lower bound for the conformal dimension. We will show that if there are sufficiently many thick Cantor sets in the space then there is a lower bound as well. "Sufficiently many" here is in terms of a modulus of a system of measures due to Fuglede, which is a generalization of the classical conformal modulus of Ahlfors and Beurling. As an application we obtain a new lower bound for the conformal dimension of self affine McMullen carpets.

- Series
- Applied and Computational Mathematics Seminar
- Time
- Monday, October 6, 2008 - 13:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Shengfu Deng – School of Mathematics, Georgia Tech

We consider the three-dimensional gravity-capillary waves on water of finite-depth which are uniformly translating in a horizontal propagating direction and periodic in a transverse direction. The exact Euler equations are formulated as a spatial dynamical system in stead of using Hamiltonian formulation method. A center-manifold reduction technique and a normal form analysis are applied to show that the dynamical system can be reduced to a system of ordinary differential equations. Using the existence of a homoclinic orbit connecting to a two-dimensional periodic solution for the reduced system, it is shown that such a generalized solitary-wave solution persists for the original system by applying a perturbation method and adjusting some appropriate constants.

- Series
- Graph Theory Seminar
- Time
- Monday, October 6, 2008 - 11:05 for 1.5 hours (actually 80 minutes)
- Location
- Skiles 255
- Speaker
- Hein van der Holst – University of Eindhoven

For an undirected graph G=(V,E) with V={1,...,n} let S(G) be the set of all symmetric n x n matrices A=[a_i,j] with a_i,j non-zero for distinct i,j if and only if ij is an edge. The inertia of a symmetric matrix is the triple (p_+,p_-,p_0), where p_+, p_-,p_0 are the number of positive, negative, and null eigenvalues respectively. The inverse inertia problem asks which inertias can be obtained by matrices in S(G). This problem has been studied intensively by Barrett, Hall, and Loewy. In this talk I will present new results on the inverse inertia problem, among them a Colin de Verdiere type invariant for the inertia set (this is the set of all possible inertias) of a graph, a formula for the inertia set of graphs with a 2-separation, and a formula for the inertia set of the join of a collection of graphs.
The Colin de Verdiere type invariant for the inertia set is joint work with F. Barioli, S.M. Fallat, H.T. Hall, D. Hershkowitz, L. Hogben, and B. Shader, and the formula for the inertia set of the join of a collection of graphs is joint work with W. Barrett and H.T. Hall.

- Series
- Combinatorics Seminar
- Time
- Friday, October 3, 2008 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Ian Goulden – University of Waterloo

This is an expository account of recent work on the enumeration of maps (graphs embedded on a surface of arbitrary genus) and branched covers of the sphere. These combinatorial and geometric objects can both be represented by permutation factorizations, in the which the subgroup generated by the factors acts transitively on the underlying symbols (these are called "transitive factorizations"). Various results and methods are discussed, including a number of methods from mathematical physics, such as matrix integrals and the KP hierarchy of integrable systems. A notable example of the results is a recent recurrence for triangulations of a surface of arbitrary genus obtained from the simplest partial differential equation in the KP hierarchy. The recurrence is very simple, but we do not know a combinatorial interpretation of it, yet it leads to precise asymptotics for the number of triangulations with n edges, of a surface of genus g.

- Series
- Probability Working Seminar
- Time
- Friday, October 3, 2008 - 15:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 168
- Speaker
- Christian Houdre – School of Mathematics, Georgia Tech

- Series
- Geometry Topology Seminar
- Time
- Friday, October 3, 2008 - 14:00 for 1 hour (actually 50 minutes)
- Location
- Skiles 269
- Speaker
- Tony Pantev – Dept of Mathematics, University of Penn

I will describe a framework which relates large N duality to the geometry of degenerating Calabi-Yau spaces and the Hitchin integrable system. I will give a geometric interpretation of the Dijkgraaf-Vafa large N quantization procedure in this context.

- Offices & Departments
- News Center
- Campus Calendar
- Special Events
- GreenBuzz
- Institute Communications
- Visitor Resources
- Campus Visits
- Directions to Campus
- Visitor Parking Information
- GTvisitor Wireless Network Information
- Georgia Tech Global Learning Center
- Georgia Tech Hotel & Conference Center
- Barnes & Noble at Georgia Tech
- Ferst Center for the Arts
- Robert C. Williams Paper Museum