Scalable algorithms for data and network analysis
Teng, Shang-Hua.
Scalable algorithms for data and network analysis / Shang-Hua Teng. - , Massachusetts Now Publishers , 2016. - xi,278p. : 24cm.
1. Scalable algorithms
1.1 Challenges of massive data
1.2 The scalability of algorithms
1.3 Complexity Class S
1.4 Scalable reduction and algorithmic primitives
1.5 Article organization 2. Networks and data
2.1 Weighted graphs and affinity networks
2.2 Possible sources of affinities
2.3 Beyond graph models for social/information networks
2.4 Basic problems in data and network analysis
2.5 Sparse networks and sparse matrices 3. Significant nodes: sampling
making data smaller
3.1 Personalized PageRank matrix
3.2 Multi-precision annealing for significant PageRank
3.3 Local approximation of personalized PageRank
3.4 Multi-precision sampling
3.5 Significant-PageRank identification 4. Clustering: local exploration of networks
4.1 Local algorithms for network analysis
4.2 Local clustering and random walks
4.3 Performance analysis of local clustering
4.4 Scalable local computation of personalized PageRank
4.5 Discussions: local exploration of networks
4.6 Interplay between dynamic processes and networks
4.7 Cheeger's inequality and its parameterization 5. Partitioning: geometric techniques for data analysis
5.1 Centerpoints and regression depth
5.2 Scalable algorithms for centerpoints
5.3 Geometric separators
5.4 Dimension reduction: random vs spectral
5.5 Scalable geometric divide-and-conquer
5.6 Graph partitioning: vertex and edge separators
5.7 Multiway partition of network and geometric data
5.8 Spectral graph partitioning: the geometry of a graph 6. Sparsification: making networks simpler
6.1 Spectral similarity of graphs
6.2 Some basic properties of spectrally similar networks
6.3 Spectral graph sparsification
6.4 Graph inequalities and low-stretch spanning trees
6.5 Edge centrality, sampling, and spectral approximation
6.6 Scalable dense-matrix computation via sparsification
6.7 PageRank completion of networks 7. Electrical flows: Laplacian paradigm for network analysis
7.1 SDD primitive and its scalability
7.2 Electrical flow and Laplacian linear systems
7.3 Spectral approximation and spectral partitioning
7.4 Learning from labeled network data
7.5 Sampling from Gaussian Markov random fields
7.6 Scalable Newton's method via spectral sparsification
7.7 Laplacian paradigm 8. Remarks and discussions
8.1 Beyond graph-based network models
8.2 Discussions: a family of scaling-invariant clusterability
8.3 Data clustering: intuition versus ground truth
8.4 Behaviors of algorithms: beyond worst-case analysis
8.5 Final remarks
Acknowledgements
References
Surveys a family of algorithmic techniques for the design of scalable algorithms. These techniques include local network exploration, advanced sampling, sparsification, and geometric partitioning. They also include spectral graph-theoretical methods, such as are used for computing electrical flows and sampling from Gaussian Markov random fields.
9781680831306
Zafaa Books & Distributors : 313/56F, 49A, Anand Nagar, Inderlok, delhi
Algorithmes
Computational geometry
Data Mining
Graphical models
005.1 TEN
Scalable algorithms for data and network analysis / Shang-Hua Teng. - , Massachusetts Now Publishers , 2016. - xi,278p. : 24cm.
1. Scalable algorithms
1.1 Challenges of massive data
1.2 The scalability of algorithms
1.3 Complexity Class S
1.4 Scalable reduction and algorithmic primitives
1.5 Article organization 2. Networks and data
2.1 Weighted graphs and affinity networks
2.2 Possible sources of affinities
2.3 Beyond graph models for social/information networks
2.4 Basic problems in data and network analysis
2.5 Sparse networks and sparse matrices 3. Significant nodes: sampling
making data smaller
3.1 Personalized PageRank matrix
3.2 Multi-precision annealing for significant PageRank
3.3 Local approximation of personalized PageRank
3.4 Multi-precision sampling
3.5 Significant-PageRank identification 4. Clustering: local exploration of networks
4.1 Local algorithms for network analysis
4.2 Local clustering and random walks
4.3 Performance analysis of local clustering
4.4 Scalable local computation of personalized PageRank
4.5 Discussions: local exploration of networks
4.6 Interplay between dynamic processes and networks
4.7 Cheeger's inequality and its parameterization 5. Partitioning: geometric techniques for data analysis
5.1 Centerpoints and regression depth
5.2 Scalable algorithms for centerpoints
5.3 Geometric separators
5.4 Dimension reduction: random vs spectral
5.5 Scalable geometric divide-and-conquer
5.6 Graph partitioning: vertex and edge separators
5.7 Multiway partition of network and geometric data
5.8 Spectral graph partitioning: the geometry of a graph 6. Sparsification: making networks simpler
6.1 Spectral similarity of graphs
6.2 Some basic properties of spectrally similar networks
6.3 Spectral graph sparsification
6.4 Graph inequalities and low-stretch spanning trees
6.5 Edge centrality, sampling, and spectral approximation
6.6 Scalable dense-matrix computation via sparsification
6.7 PageRank completion of networks 7. Electrical flows: Laplacian paradigm for network analysis
7.1 SDD primitive and its scalability
7.2 Electrical flow and Laplacian linear systems
7.3 Spectral approximation and spectral partitioning
7.4 Learning from labeled network data
7.5 Sampling from Gaussian Markov random fields
7.6 Scalable Newton's method via spectral sparsification
7.7 Laplacian paradigm 8. Remarks and discussions
8.1 Beyond graph-based network models
8.2 Discussions: a family of scaling-invariant clusterability
8.3 Data clustering: intuition versus ground truth
8.4 Behaviors of algorithms: beyond worst-case analysis
8.5 Final remarks
Acknowledgements
References
Surveys a family of algorithmic techniques for the design of scalable algorithms. These techniques include local network exploration, advanced sampling, sparsification, and geometric partitioning. They also include spectral graph-theoretical methods, such as are used for computing electrical flows and sampling from Gaussian Markov random fields.
9781680831306
Zafaa Books & Distributors : 313/56F, 49A, Anand Nagar, Inderlok, delhi
Algorithmes
Computational geometry
Data Mining
Graphical models
005.1 TEN
