Mining Graph Data

Cover......Page 1
Copyright......Page 7
Contents......Page 10
Preface......Page 16
Acknowledgments......Page 18
Contributors......Page 20
1 Introduction......Page 24
1.1 Terminology......Page 25
1.2 Graph Databases......Page 26
1.3 Book Overview......Page 33
References......Page 34
Part I Graphs......Page 38
2.1 Introduction......Page 40
2.2 Definitions and Graph Matching Methods......Page 41
2.3 Learning Edit Costs......Page 47
2.4 Experimental Evaluation......Page 51
2.5 Discussion and Conclusions......Page 54
References......Page 55
3.1 Introduction......Page 58
3.2 Graph Drawing Techniques......Page 61
3.3 Examples of Visualization Systems......Page 71
3.4 Conclusions......Page 78
References......Page 80
4.1 Introduction......Page 88
4.2 Background and Related Work......Page 90
4.3 NetMine and R-MAT......Page 102
4.4 Experiments......Page 105
4.5 Conclusions......Page 109
References......Page 115
Part II Mining Techniques......Page 120
5.1 Introduction......Page 122
5.2 Preliminary Concepts......Page 123
5.3 Apriori-based Approach......Page 124
5.4 Pattern Growth Approach......Page 126
5.5 Variant Substructure Patterns......Page 130
5.6 Experiments and Performance Study......Page 132
5.7 Conclusions......Page 135
References......Page 136
6.1 Introduction......Page 140
6.2 Background Definitions and Notation......Page 141
6.3 Frequent Pattern Discovery from Graph Datasets--Problem Definitions......Page 145
6.4 FSG for the Graph-Transaction Setting......Page 150
6.5 SIGRAM for the Single-Graph Setting......Page 154
6.6 GREW --Scalable Frequent Subgraph Discovery Algorithm......Page 164
6.7 Related Research......Page 172
6.8 Conclusions......Page 174
References......Page 177
7.1 Introduction......Page 182
7.2 Mining Graph Data Using Subdue......Page 183
7.4 Comparison to Frequent Substructure Mining Approaches......Page 188
7.5 Comparison to ILP Approaches......Page 193
References......Page 202
8.1 Introduction......Page 206
8.2 Related Work......Page 207
8.3 Graph Grammar Learning......Page 208
8.4 Empirical Evaluation......Page 216
References......Page 222
9.1 Introduction......Page 226
9.2 Graph-Based Induction Revisited......Page 228
9.3 Problem Caused by Chunking in B-GBI......Page 230
9.4 Chunkingless Graph-Based Induction (Cl-GBI)......Page 231
9.5 Decision Tree Chunkingless Graph-Based Induction (DT-ClGBI)......Page 237
References......Page 247
10.1 Presentation......Page 250
10.2 Basic Concepts and Notation......Page 251
10.3 Formal Concept Analysis......Page 252
10.4 Extension Lattice and Description Lattice Give Concept Lattice......Page 254
10.5 Graph Description and Galois Lattice......Page 258
10.6 Graph Mining and Formal Propositionalization......Page 263
10.7 Conclusion......Page 272
References......Page 273
11.1 Introduction......Page 276
11.2 Graph Classification......Page 277
11.3 Vertex Classification......Page 289
11.4 Conclusions and Future Work......Page 302
References......Page 303
12.1 Introduction......Page 306
12.2 Preliminaries......Page 307
12.3 Kernel-based Unified Framework for Importance and Relatedness......Page 309
12.4 Laplacian Kernels as a Relatedness Measure......Page 313
12.5 Practical Issues......Page 320
12.6 Related Work......Page 322
12.7 Evaluation with Bibliographic Citation Data......Page 323
References......Page 331
13.1 Introduction......Page 334
13.2 Related Work......Page 337
13.3 Motivating Example for Graph-Based Entity Resolution......Page 341
13.4 Graph-Based Entity Resolution: Problem Formulation......Page 345
13.5 Similarity Measures for Entity Resolution......Page 348
13.6 Graph-Based Clustering for Entity Resolution......Page 353
13.7 Experimental Evaluation......Page 356
13.8 Conclusion......Page 364
References......Page 365
Part III Applications......Page 368
14.1 Introduction and Representation of Molecules......Page 370
14.2 Issues for Mining......Page 378
14.3 CASE: A Prototype Mining System in Chemistry......Page 379
14.4 Quantitative Estimation Using Graph Mining......Page 381
14.5 Extension of Linear Fragments to Graphs......Page 385
14.6 Combination of Conditions......Page 389
14.7 Concluding Remarks......Page 398
References......Page 400
15.1 Introduction......Page 404
15.2 Preliminaries......Page 405
15.3 Related Work......Page 407
15.4 Generating Candidate Subtrees......Page 408
15.5 Frequency Computation......Page 415
15.6 Counting Distinct Occurrences......Page 420
15.7 The SLEUTH Algorithm......Page 422
15.8 Experimental Results......Page 424
15.9 Tree Mining Applications in Bioinformatics......Page 428
References......Page 432
16.1 Introduction......Page 434
16.2 Related Work......Page 437
16.3 Finding the densest subgraph......Page 439
16.4 Trawling......Page 441
16.5 Graph Shingling......Page 444
16.6 Connection Subgraphs......Page 452
References......Page 461
17.2 Social Network Analysis......Page 466
17.4 Terrorist Modus Operandi Detection System......Page 475
17.5 Computational Experiments......Page 488
17.6 Conclusion......Page 490
References......Page 491
Index......Page 492