Individual and collective graph mining : principles, algorithms, and applications /

Individual and collective graph mining : principles, algorithms, and applications /

Show other versions (3)

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...

Full description

Bibliographic Details
Main Authors: Koutra, Danai (Author), Faloutsos, Christos (Author)
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:
Data mining
Graph theory > Data processing
Graphic methods > Data processing
anomaly detection
brain graphs
connectomes
data mining
fast algorithms
graph matching
graph mining and exploration
graph similarity
graph summarization
models
network alignment
outlier detection
pattern mining
scalability
social networks
visualization
Electronic books
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

Similar Items