Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Part of: Synthesis digital library of engineering and computer science.

Includes bibliographical references (pages 171-192).

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.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

INSPEC

Google scholar

Google book search

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 important structures and summarize them? How can we efficiently visualize them? How can we detect anomalies that indicate critical events, such as an attack on a computer system, disease formation in the human brain, or the fall of a company? This book presents scalable, principled discovery algorithms that combine globality with locality to make sense of one or more graphs. In addition to fast algorithmic methodologies, we also contribute graph-theoretical ideas and models, and real-world applications in two main areas : Individual Graph Mining and Collective Graph Mining.

Also available in print.

Title from PDF title page (viewed on October 25, 2017).