图像数据挖掘技术课程.ppt

Introduction to Graph Mining Gaolin School of Computer Science and Technology Xidian University Course Information Instructors: Lin Gao Office: Main building I-427 Email: lgao@mail.xidian.edu.cn Phone:Course Information Prerequisites Database systems, Introduction to Data Mining Methods of instruction Teaching Students are expected to read some research papers Evaluation Attendance and participation 20% Presentation and talks 80% Outline Why graph mining Graph theoretic concepts Graph pattern mining Graph clustering Graph classification Application and exploration with graph mining Future work Why Graph Mining and Searching? Graphs are ubiquitous Chemical compounds (Cheminformatics) Protein structures, biological pathways/networks (Bioinformactics) Program control flow, traffic flow, and workflow analysis XML databases, Web, and social network analysis Graph is a general model Trees, lattices, sequences, and items are degenerated graphs the graph easily represents entities, attributes, and relationships Diversity of graphs Directed vs. undirected, labeled vs. unlabeled (edges vertices), weighted, with angles geometry (topological vs. 2-D/3-D) Complexity of algorithms: many problems are of high complexity Graph, Graph, Everywhere Graph theoretic concepts Basic concept: distance, diameter, path, neighborhood, clique, degree, cut, core, adjacency matrix Advanced measurement Density of a graph Clustering coefficient Centrality Connectivity Degree of a node vi The number of links from vi to other nodes Incoming degree and outgoing degree for directed networks Adjacent neighbors, N(vi), of a node vi A set of nodes linked from vi Degree distribution, P(k) Probability that a node has exactly k links The number of nodes whose degree is k over the total number of nodes * Connectivity may be of interest for a single node (e.g., degree or clustering coefficient) as well as the entire netw