Individual and collective graph mining : principles, algorithms, and applications /
Graphs naturally represent information ranging from links between web pages, to communication in email networks, to connections between neurons in our brains. These graphs often span billions of nodes and interactions between them. Within this deluge of interconnected data, how can we find the most...
Main Authors: | , |
---|---|
Format: | Book |
Language: | English |
Published: |
[San Rafael, California] :
Morgan & Claypool,
2018
|
Series: | Synthesis digital library of engineering and computer science
Synthesis lectures on data mining and knowledge discovery #14 |
Subjects: |
Table of Contents:
- 1. Introduction
- 1.1 Overview
- 1.2 Organization of this book
- 1.2.1 Part I: Individual graph mining
- 1.2.2 Part II: Collective graph mining
- 1.2.3 Code and supporting materials on the web
- 1.3 Preliminaries
- 1.3.1 Graph definitions
- 1.3.2 Graph-theoretic data structures
- 1.3.3 Linear algebra concepts
- 1.3.4 Select graph properties
- 1.4 Common symbols
- Part I. Individual graph mining
- 2. Summarization of static graphs
- 2.1 Overview and motivation
- 2.2 Problem formulation
- 2.2.1 MDL for graph summarization
- 2.2.2 Encoding the model
- 2.2.3 Encoding the errors
- 2.3 VoG: vocabulary-based summarization of graphs
- 2.3.1 Subgraph generation
- 2.3.2 Subgraph labeling
- 2.3.3 Summary assembly
- 2.3.4 Toy example
- 2.3.5 Time complexity
- 2.4 Empirical results
- 2.4.1 Quantitative analysis
- 2.4.2 Qualitative analysis
- 2.4.3 Scalability
- 2.5 Discussion
- 2.6 Related work
- 3. Inference in a graph
- 3.1 Guilt-by-association techniques
- 3.1.1 Random walk with restarts (RWR)
- 3.1.2 Semi-supervised learning (SSL)
- 3.1.3 Belief propagation (BP)
- 3.1.4 Summary
- 3.2 FaBP: fast belief propagation
- 3.2.1 Derivation
- 3.2.2 Analysis of convergence
- 3.2.3 Algorithm
- 3.3 Extension to multiple classes
- 3.4 Empirical results
- 3.4.1 Accuracy
- 3.4.2 Convergence
- 3.4.3 Robustness
- 3.4.4 Scalability
- Part II. Collective graph mining
- 4. Summarization of dynamic graphs
- 4.1 Problem formulation
- 4.1.1 MDL for dynamic graph summarization
- 4.1.2 Encoding the model
- 4.1.3 Encoding the errors
- 4.2 TimeCrunch: vocabulary-based summarization of dynamic graphs
- 4.2.1 Generating candidate static structures
- 4.2.2 Labeling candidate static structures
- 4.2.3 Stitching candidate temporal structures
- 4.2.4 Composing the summary
- 4.3 Empirical results
- 4.3.1 Quantitative analysis
- 4.3.2 Qualitative analysis
- 4.3.3 Scalability
- 4.4 Related work
- 5. Graph similarity
- 5.1 Intuition
- 5.1.1 Overview
- 5.1.2 Measuring node affinities
- 5.1.3 Leveraging belief propagation
- 5.1.4 Desired properties for similarity measures
- 5.2 DeltaCon: "[theta]" connectivity change detection
- 5.2.1 Algorithm description
- 5.2.2 Faster computation
- 5.2.3 Desired properties
- 5.3 DeltaCon-ATTR: adding node and edge attribution
- 5.3.1 Algorithm description
- 5.3.2 Scalability analysis
- 5.4 Empirical results
- 5.4.1 Intuitiveness of DeltaCon
- 5.4.2 Intuitiveness of DeltaCon-ATTR
- 5.4.3 Scalability
- 5.4.4 Robustness
- 5.5 Applications
- 5.5.1 Enron
- 5.5.2 Brain connectivity graph clustering
- 5.5.3 Recovery of connectome correspondences
- 5.6 Related work
- 6. Graph alignment
- 6.1 Problem formulation
- 6.2 BiG-align: bipartite graph alignment
- 6.2.1 Mathematical formulation
- 6.2.2 Problem-specific optimizations
- 6.2.3 Algorithm description
- 6.3 Uni-align: extension to unipartite graph alignment
- 6.4 Empirical results
- 6.4.1 Accuracy and runtime of BiG-align
- 6.4.2 Accuracy and runtime of INI-align
- 6.5 Discussion
- 6.6 Related work
- 7. Conclusions and further research problems
- Bibliography
- Authors' biographies