SIAM AN10 Minisymposium on Analyzing Massive Real-World Graphs

http://www.graphanalysis.org/workshop2010.html

10:30-10:55 People You May Know
Lars Backstrom, Facebook
Facebook's friend recommendation system helps people connect with their friends. Our system, called People You May Know, uses a combination of results from sociology and machine learning to make the best suggestions possible. We will look at some of the challenges involved in building a system that can handle the scale of Facebook and provide high quality recommendations. In this talk I will discuss both the algorithmic and machine learning challenges that we have faced and overcome in building this system.


11:00-11:25 Modularity and Graph Algorithms
Joe McCloskey, National Security Agency; David A. Bader, Georgia Institute of Technology
A number of graph partitioning algorithms are based on the concept of modularity. In particular Clauset, Newman and Moore (CNM) have developed a greedy agglomerative graph partitioning algorithm that scales well but is known to have several flaws. Fortunato and Barthelemy have performed a rigorous analysis of the CNM algorithm that elucidates it problems. More recently Berry, Hendrickson, Laviolette, and Phillips have derived a weighted variant of CNM that performs much better in practice. This talk will focus on a different version of the parent CNM algorithm based on a statistical re-interpretation of CNM that also addresses some of the issues with the original algorithm.
11:30-11:55 Exploiting Sparsity in the Statistical Analysis of Gene Expression Data
Padma Raghavan, Anirban Chatterjee, and Francesca Chiaromonte, Pennsylvania State University

12:00-12:25 Scalable Methods for Representing, Characterizing, and Generating Large Graphs
Ali Pinar, Sandia National Laboratories

Monday, July 12
4:00 PM - 6:00 PM
Room: Spirit of Pittsburgh B - Level 3

4:00-4:25 Hybrid Parallel Programming for Massive Graph Analysis
Kamesh Madduri, Lawrence Berkeley National Laboratory

4:30-4:55 Tools and Primitives for High-performance Graph Computation
John Gilbert, University of California, Santa Barbara

5:00-5:25 Practical Heuristics for Inexact Subgraph Isomorphism
Jon Berry, Sandia National Laboratories

5:30-5:55 Spectral Methods for Subgraph Detection
Nadya Bliss and Benjamin A. Miller, Massachusetts Institute of Technology; Patrick J. Wolfe, Harvard University
We describe a statistical test for subgraph detection and localization using spectral properties of the so-called modularity matrix, a type of residual under the Chung-Lu random graph model. We show that the resultant algorithmic procedure can be applied to very large graphs ($< 10^6$ vertices), with complexity dominated by that of standard sparse eigensolver methods, and can successfully isolate anomalous vertices in real data examples.
Workshop Organizer: