Mining Graph Data

This text takes a focused and comprehensive look at mining data represented as a graph, with the latest findings and applications in both theory and practice provided. Even if you have minimal background in analyzing graph data, with this book you'll be able to represent data as graphs, extract patterns and concepts from the data, and apply the methodologies presented in the text to real datasets. There is a misprint with the link to the accompanying Web page for this book. For those readers who would like to experiment with the techniques found in this book or test their own ideas on graph data, the Web page for the book should be http://www.eecs.wsu.edu/MGD.

DIANE J. COOK, PhD, is the Huie-Rogers Chair Professor in the School of Electrical Engineering and Computer Science at Washington State University. Her extensive research in artificial intelligence and data mining has been supported by grants from the National Science Foundation, NASA, DARPA, and Texas Instruments. Dr. Cook is the coauthor of Smart Environments: Technology, Protocols, and Applications (Wiley).

LAWRENCE B. HOLDER, PhD, is Professor in the School of Electrical Engineering and Computer Science at Washington State University, where he teaches and conducts research in artificial intelligence, machine learning, data mining, graph theory, parallel and distributed processing, and cognitive architectures.

Preface

xiii

Acknowledgments

xv

Contributors

xvii

Introduction

1

(14)

Lawrence B. Holder

Diane J. Cook

Terminology

2

(1)

Graph Databases

3

(7)

Book Overview

10

(5)

References

11

(4)

Part I GRAPHS

15

(82)

Graph Matching---Exact and Error-Tolerant Methods and the Automatic Learning of Edit Costs

17

(18)

Horst Bunke

Michel Neuhaus

Introduction

17

(1)

Definitions and Graph Matching Methods

18

(6)

Learning Edit Costs

24

(4)

Experimental Evaluation

28

(3)

Discussion and Conclusions

31

(4)

References

32

(3)

Graph Visualization and Data Mining

35

(30)

Walter Didimo

Giuseppe Liotta

Introduction

35

(3)

Graph Drawing Techniques

38

(10)

Examples of Visualization Systems

48

(7)

Conclusions

55

(10)

References

57

(8)

Graph Patterns and the R-Mat Generator

65

(32)

Deepayan Chakrabarti

Christos Faloutsos

Introduction

65

(2)

Background and Related Work

67

(12)

NetMine and R-MAT

79

(3)

Experiments

82

(4)

Conclusions

86

(11)

References

92

(5)

Part II MINING TECHNIQUES

97

(248)

Discovery of Frequent Substructures

99

(18)

Xifeng Yan

Jiawei Han

Introduction

99

(1)

Preliminary Concepts

100

(1)

Apriori-based Approach

101

(2)

Pattern Growth Approach

103

(4)

Variant Substructure Patterns

107

(2)

Experiments and Performance Study

109

(3)

Conclusions

112

(5)

References

113

(4)

Finding Topological Frequent Patterns from Graph Datasets

117

(42)

Michihiro Kuramochi

George Karypis

Introduction

117

(1)

Background Definitions and Notation

118

(4)

Frequent Pattern Discovery from Graph Datasets---Problem Definitions

122

(5)

FSG for the Graph-Transaction Setting

127

(4)

SiGraM for the Single-Graph Setting

131

(10)

Grew---Scalable Frequent Subgraph Discovery Algorithm

141

(8)

Related Research

149

(2)

Conclusions

151

(8)

References

154

(5)

Unsupervised and Supervised Pattern Learning in Graph Data

159

(24)

Diane J. Cook

Lawrence B. Holder

Nikhil Ketkar

Introduction

159

(1)

Mining Graph Data Using Subdue

160

(5)

Comparison to Other Graph-Based Mining Algorithms

165

(1)

Comparison to Frequent Substructure Mining Approaches

165

(5)

Comparison to ILP Approaches

170

(9)

Conclusions

179

(4)

References

179

(4)

Graph Grammar Learning

183

(20)

Istvan Jonyer

Introduction

183

(1)

Related Work

184

(1)

Graph Grammar Learning

185

(8)

Empirical Evaluation

193

(6)

Conclusion

199

(4)

References

199

(4)

Constructing Decision Tree Based on Chunkingless Graph-Based Induction

203

(24)

Kouzou Ohara

Phu Chien Nguyen

Akira Mogi

Hiroshi Motoda

Takashi Washio

Introduction

203

(2)

Graph-Based Induction Revisited

205

(2)

Problem Caused by Chunking in B-GBI

207

(1)

Chunkingless Graph-Based Induction (CI-GBI)

208

(6)

Decision Tree Chunkingless Graph-Based Induction (DT-ClGBI)

214

(10)

Conclusions

224

(3)

References

224

(3)

Some Links Between Formal Concept Analysis and Graph Mining

227

(26)

Michel Liquiere

Presentation

227

(1)

Basic Concepts and Notation

228

(1)

Formal Concept Analysis

229

(2)

Extension Lattice and Description Lattice Give Concept Lattice

231

(4)

Graph Description and Galois Lattice

235

(5)

Graph Mining and Formal Propositionalization

240

(9)

Conclusion

249

(4)

References

250

(3)

Kernel Methods for Graphs

253

(30)

Thomas Gartner

Tamas Horvath

Quoc V. Le

Alex J. Smola

Stefan Wrobel

Introduction

253

(1)

Graph Classification

254

(12)

Vertex Classification

266

(13)

Conclusions and Future Work

279

(4)

References

280

(3)

Kernels as Link Analysis Measures

283

(28)

Masashi Shimbo

Takahiko Ito

Introduction

283

(1)

Preliminaries

284

(2)

Kernel-based Unified Framework for Importance and Relatedness

286

(4)

Laplacian Kernels as a Relatedness Measure

290

(7)

Practical Issues

297

(2)

Related Work

299

(1)

Evaluation with Bibliographic Citation Data

300

(8)

Summary

308

(3)

References

308

(3)

Entity Resolution in Graphs

311

(34)

Indrajit Bhattacharya

Lise Getoor

Introduction

311

(3)

Related Work

314

(4)

Motivating Example for Graph-Based Entity Resolution

318

(4)

Graph-Based Entity Resolution: Problem Formulation

322

(3)

Similarity Measures for Entity Resolution

325

(5)

Graph-Based Clustering for Entity Resolution

330

(3)

Experimental Evaluation

333

(8)

Conclusion

341

(4)

References

342

(3)

Part III APPLICATIONS

345

(124)

Mining from Chemical Graphs

347

(34)

Takashi Okada

Introduction and Representation of Molecules

347

(8)

Issues for Mining

355

(1)

CASE: A Prototype Mining System in Chemistry

356

(2)

Quantitative Estimation Using Graph Mining

358

(4)

Extension of Linear Fragments to Graphs

362

(4)

Combination of Conditions

366

(9)

Concluding Remarks

375

(6)

References

377

(4)

Unified Approach to Rooted Tree Mining: Algorithms and Applications

381

(30)

Mohammed Zaki

Introduction

381

(1)

Preliminaries

382

(2)

Related Work

384

(1)

Generating Candidate Subtrees

385

(7)

Frequency Computation

392

(5)

Counting Distinct Occurrences

397

(2)

The SLEUTH Algorithm

399

(2)

Experimental Results

401

(4)

Tree Mining Applications in Bioinformatics

405

(4)

Conclusions

409

(2)

References

409

(2)

Dense Subgraph Extraction

411

(32)

Andrew Tomkins

Ravi Kumar

Introduction

411

(3)

Related Work

414

(2)

Finding the densest subgraph

416

(2)

Trawling

418

(3)

Graph Shingling

421

(8)

Connection Subgraphs

429

(9)

Conclusions

438

(5)

References

438

(5)

Social Network Analysis

443

(26)

Sherry E. Marcus

Melanie Moy

Thayne Coffman

Introduction

443

(1)

Social Network Analysis

443

(9)

Group Detection

452

(1)

Terrorist Modus Operandi Detection System

452

(13)

Computational Experiments

465

(2)

Conclusion

467

(2)

References

468

(1)

Index

469

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Summary

Author Biography

Table of Contents

Supplemental Materials