Aggarwal C.C., Wang H. (eds.) Managing and Mining Graph Data

Springer, 2010. — 622 p.The field of graph mining has seen a rapid explosion in recent years because of new applications in computational biology, software bug localization, and social and communication networking. This book is designed for studying various applications in the context of managing and mining graphs. Graph mining has been studied by the theoretical community extensively in the context of numerous problems such as graph partitioning, node clustering, matching, and connectivity analysis. However the traditional work in the theoretical community cannot be directly used in practical applications because of the following reasons:
The definitions of problems such as graph partitioning, matching and dimensionality reduction are too clean to be used with real applications. In real applications, the problem may have different variations such as a disk-resident case, a multi-graph case, or other constraints associated with the graphs. In many cases, problems such as frequent sub-graph mining and dense graph mining may have a variety of different flavors for different scenarios.
The size of the applications in real scenarios are often very large. In such cases, the graphs may not be stored in main memory, but may be available only on disk. A classic example of this is the case of web and social network graphs, which may contain millions of nodes. As a result, it is often necessary to design specialized algorithms which are sensitive to disk access efficiency constraints. In some cases, the entire graph may not be available at one time, but may be available in the form of a continuous stream. This is the case in many applications such as social and telecommunication networks in which edges are received continuously.
The book will study the problem of managing and mining graphs from an applied point of view. It is assumed that the underlying graphs are massive and cannot be held in main memory. This change in assumption has a critical impact on the algorithms which are required to process such graphs. The problems studied in the book include algorithms for frequent pattern mining, graph matching, indexing, classification, clustering, and dense graph mining. In many cases, the problem of graph management and mining has been studied from the perspective of structured and XML data. Where possible, we have clarified the connections with the methods and algorithms designed by the XML data management community. We also provide a detailed discussion of the application of graph mining algorithms in a number of recent applications such as graph privacy, web and social networks.
Many of the graph algorithms are sensitive to the application scenario in which they are encountered. Therefore, we will study the usage of many of these techniques in real scenarios such as the web, social networks, and biological data. This provides a better understanding of how the algorithms in the book apply to different scenarios. Thus, the book provides a comprehensive summary both from an algorithmic and applied perspective.An Introduction to Graph Data
Graph Data Management and Mining: A Survey of Algorithms and Applications
Graph Mining: Laws and Generators
Query Language and Access Methods for Graph Databases
Graph Indexing
Graph Reachability Queries: A Survey
Exact and Inexact Graph Matching: Methodology and Applications
A Survey of Algorithms for Keyword Search on Graph Data
A Survey of Clustering Algorithms for Graph Data
A Survey of Algorithms for Dense Subgraph Discovery
Graph Classification
Mining Graph Patterns
A Survey on Streaming Algorithms for Massive Graphs 3
A Survey of Privacy-Preservation of Graphs and Social Networks
A Survey of Graph Mining for Web Applications
Graph Mining Applications to Social Network Analysis
Software-Bug Localization with Graph Mining
A Survey of Graph Mining Techniques for Biological Datasets
Trends in Chemical Graph Data Mining