Graph Algorithms in the Language of Linear Algebra (Software, Environments, and Tools)
PDF
 eBook:Graph Algorithms in the Language of Linear Algebra (Software, Environments, and Tools)
 Author:July 14, 2011
 Edition:
 Categories:
 Data:375 pages
 ISBN:0898719909
 ISBN13:9780898719901
 Language:English
 Pages:389 pages
 Format:PDF
The current exponential growth in graph data has forced a shift to parallel computing for executing graph algorithms. Implementing parallel graph algorithms and achieving good parallel performance have proven difficult. This book addresses these challenges by exploiting the wellknown duality between a canonical representation of graphs as abstract collections of vertices and edges and a sparse adjacency matrix representation. This linear algebraic approach is widely accessible to scientists and engineers who may not be formally trained in computer science. The authors show how to leverage existing parallel matrix computation techniques and the large amount of software infrastructure that exists for these computations to implement efficient and scalable parallel graph algorithms. The benefits of this approach are reduced algorithmic complexity, ease of implementation, and improved performance.
Graph Algorithms in the Language of Linear Algebrais the first book to cover graph algorithms accessible to engineers and scientists not trained in computer science but having a strong linear algebra background, enabling them to quickly understand and apply graph algorithms. It also covers arraybased graph algorithms, showing readers how to express canonical graph algorithms using a highly elegant and efficient array notation and how to tap into the large range of tools and techniques that have been built for matrices and tensors; parallel arraybased algorithms, demonstrating with examples how to easily implement parallel graph algorithms using arraybased approaches, which enables readers to address much larger graph problems; and arraybased theory for analyzing graphs, providing a template for using arraybased constructs to develop new theoretical approaches for graph analysis.

Content
1. Graphs and Matrices
2. Linear Algebraic Notation and Definitions
3. Connected Components and Minimum Paths
4. Some Graph Algorithms in an ArrayBased Language
5. Fundamental Graph Algorithms
6. Complex Graph Algorithms
7. Multilinear Algebra for Analyzing Data with Multiple Linkages
8. Subgraph Detection
II  Data
9. Kronecker Graphs
10. The Kronecker Theory of Power Law Graphs
11. Visualizing Large Kronecker Graphs
III  Computation
12. LargeScale Network Analysis
13. Im plementing Sparse Matrices for Graph Algorithms
14. New Ideas in Sparse Matrix Matrix Multiplication
15. Parallel Mapping of Sparse Computations
16. Fundamental Questions in the Analysis of Large Graphs
Free sample
