FW: CALD Thesis Defense - TODAY at 2:00

[Frank Wimberly]

Here is a talk (thesis) at CMU that may be of interest to Friamers.  As
usual, I am sure papers etc. are available online.

 

Frank

 

---

Frank C. Wimberly      140 Calle Ojo Feliz     Santa Fe, NM 87505

[phone] or [phone] (cell)

[hidden email] or [hidden email] or
[hidden email]

 

 

 

-----Original Message-----
From: Diane Stidle [mailto:[hidden email]]
Sent: Friday, June 03, 2005 9:40 AM
To: [hidden email]
Cc: [hidden email]; [hidden email]; [hidden email]
Subject: CALD Thesis Defense - TODAY at 2:00

 

I am pleased to announce CALD's first PhD Thesis Defense!

Date: Friday, June 3, 2005
Time: 2:00pm
Place: 4623 Wean Hall

Title: Tools for Large Graph Mining
PhD Candidate: Deepayan Chakrabarti

Abstract:

Graphs show up in a surprisingly diverse set of disciplines, ranging from
computer networks to sociology, biology, ecology and many more.  How do
such "normal" graphs look like? How can we spot abnormal subgraphs
within them?  Which nodes/edges are "suspicious?" How does a virus
spread over a graph?  Answering these questions is vital for outlier
detection (such as terrorist cells, money laundering rings), forecasting,
simulations (how well will a new protocol work on a realistic computer
network?), immunization campaigns and many other applications.

We attempt to answer these questions in two parts.  First, we answer
questions targeted at applications: what patterns/properties of a
graph are important for solving specific problems? Here, we investigate
the propagation behavior of a computer virus over a network, and find a
simple formula for the epidemic threshold (beyond which any viral
outbreak might become an epidemic).  We find an "information survival
threshold" which determines whether, in a sensor or P2P network with
failing nodes and links, a piece of information will survive or not. We
also develop a scalable, parameter-free method for finding groups of
"similar" nodes in a graph, corresponding to homogeneous regions (or
CrossAssociations) in the binary adjacency matrix of the graph. This can
help navigate the structure of the graph, and find un-obvious patterns.

In the second part of our work, we investigate recurring patterns in
real-world graphs, to gain a deeper understanding of their structure. This
leads to the development of the R-MAT model of graph generation for
creating synthetic but "realistic" graphs, which match many of the
patterns found in real-world graphs, including power-law and lognormal
degree distributions, small diameter and "community" effects.

Thesis Committee:
Christos Faloutsos (Chair)
Chris Olsten
Guy Blelloch
Jon Kleinberg (Cornell)



-------------- next part --------------
An HTML attachment was scrubbed...
URL: /pipermail/friam_redfish.com/attachments/20050603/4e208ebf/attachment-0001.htm