Đồ thị định nghĩa một lớp cơ chế tổng quát hơn so với tập hợp, chuỗi, lưới và cây. Có nhiều ứng dụng đồ thị trên Internet và mạng xã hội, mạng dữ liệu, mạng sinh học, sinh học tin học, hóa học tin học, thị giác máy tính và truy xuất nội dung đa phương tiện. Các ứng dụng khai thác đồ thị và mạng như sau:
Khai thác mẫu Đồ thị (Graph Pattern Mining)
Là khai thác các dưới đồ thị thường xuyên (frequent subgraphs) trong một hoặc một tập hợp đồ thị. Có nhiều phương pháp khai thác mẫu đồ thị được phân loại thành phương pháp dựa trên Apriori và phương pháp dựa trên tăng trưởng mẫu (pattern growth-based).
Có thể khai thác tập hợp các đồ thị đóng (closed graphs) nơi đồ thị g được gọi là đóng nếu không tồn tại siêu đồ thị g' phù hợp tạo ra số đếm hỗ trợ (support count) tương tự như g. Ngoài ra, có nhiều biến thể mẫu đồ thị như đồ thị thường xuyên xấp xỉ, đồ thị liên kết (coherent graphs) và đồ thị đặc (dense graphs). Ràng buộc do người dùng định nghĩa có thể được đẩy sâu vào giai đoạn khai thác mẫu đồ thị để tăng hiệu quả khai thác.
Mô hình hóa thống kê Mạng (Statistical Modeling of Networks)
Một mạng bao gồm tập hợp nút (nodes), mỗi nút tương ứng với một đối tượng liên quan đến tập thuộc tính, và tập hợp cạnh (edges/links) nối các nút đó, mô tả mối quan hệ giữa các đối tượng.
Mạng là đồng nhất (homogeneous) nếu các nút và liên kết cùng loại, ví dụ: mạng bạn bè, mạng đồng tác giả, mạng trang Internet. Mạng là dị chất (heterogeneous) nếu nút và liên kết khác loại, ví dụ: mạng ấn bản (kết nối tác giả, hội nghị, bài báo, văn bản) và mạng y tế (kết nối bác sĩ, y tá, bệnh nhân, bệnh, điều trị).
Làm sạch, Tích hợp và Xác thực Dữ liệu bằng Phân tích Mạng Thông tin
Dư thừa thông tin có thể tồn tại giữa các yếu tố dữ liệu được liên kết trong một mạng lớn. Dư thừa thông tin có thể được phân tích trong các mạng như vậy để thực hiện làm sạch dữ liệu chất lượng, tích hợp dữ liệu, xác thực dữ liệu và tìm kiếm độ tin cậy bằng phân tích mạng.
Phân cụm và Phân loại Đồ thị và Mạng Đồng nhất
Các phương pháp phân tích cụm đã được phát triển trên mạng lớn để khám phá cơ chế mạng, tìm cộng đồng ẩn, hub và giá trị ngoại lai (outliers) dựa trên cơ chế địa hình mạng và thuộc tính liên quan. Có nhiều loại phương pháp phân cụm mạng được phát triển và có thể phân loại là phân vùng (partitioning), phân cấp (hierarchical) hoặc dựa trên mật độ (density-based).
Phân cụm, Xếp hạng và Phân loại Mạng Dị chất
Mạng dị chất bao gồm các nút và liên kết liên kết chéo của nhiều loại. Cơ chế liên kết chéo như vậy chứa thông tin phong phú, có thể dùng để cải thiện lẫn nhau các nút và liên kết, và lan truyền quan sát từ loại này sang loại khác.
Phân cụm và xếp hạng mạng dị chất như vậy có thể được thực hiện gắn liền trong bối cảnh rằng các nút xếp hạng cao trong cụm đóng góp nhiều hơn so với đối tác xếp hạng thấp của chúng trong việc tính toán sự gắn kết của cụm.