Fundamental Questions in the Analysis of Large Graphs

Graphs are a general approach for representing information that spans the widest possible range of computing applications. They are particularly important to computational biology, web search, and knowledge discovery. As the sizes of graphs increase, the need to apply advanced mathematical and computational techniques to solve these problems is growing dramatically. Examining the mathematical and computational foundations of the analysis of large graphs generally leads to more questions than answers. This book concludes with a discussion of some of these questions. ∗MIT Lincoln Laboratory, 244 Wood Street, Lexington, MA 02420 (kepner@ll.mit.edu, rbond@ll.mit.edu, nt@ll.mit.edu, erobinson@ll.mit.edu). †College of Computing, Georgia Institute of Technology, Atlanta, GA 30332 (bader@cc. gatech.edu). ‡School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213-3891 (christos@cs.cmu.edu). §Discrete Algorithms & Math Department Sandia National Laboratories Albuquerque, NM 87185 (bahendr@sandia.gov). ¶Computer Science Department, University of California, Santa Barbara, CA 93106-5110 (gilbert@cs.ucsb.edu). This work is sponsored by the Department of the Air Force under Air Force Contract FA872105-C-0002. Opinions, interpretations, conclusions, and recommendations are those of the authors and are not necessarily endorsed by the United States Government.