Xem trước tài liệu

Đang tải tài liệu...

Thông tin chi tiết tài liệu

Định dạng: PDF
Số trang: 59 trang
Dung lượng: 650 KB

Giới thiệu nội dung

Mô hình đồ thị và ứng dụng đối với bài toán cộng đồng trên mạng xã hội

Tác giả: Hoàng Văn Dũng

Giáo viên hướng dẫn: TS. Vũ Vinh Quang

Lĩnh vực: Khoa học Máy tính

Nội dung tài liệu:

Luận văn Thạc sĩ này tập trung nghiên cứu về mô hình đồ thị, một cấu trúc dữ liệu kinh điển trong tin học, và ứng dụng của nó trong việc giải quyết bài toán cộng đồng trên mạng xã hội. Nội dung đề cập đến các khái niệm cơ bản về đồ thị, các phương pháp biểu diễn đồ thị (ma trận kề, danh sách kề), cùng với các thuật toán tìm kiếm và tối ưu trên đồ thị, đặc biệt là thuật toán tìm đường đi ngắn nhất.

Luận văn cũng đi sâu vào khái niệm mạng xã hội, các bài toán cộng đồng, và các độ đo liên quan đến đỉnh và cạnh trong đồ thị. Các thuật toán phát hiện cộng đồng, bao gồm họ thuật toán Girvan-Newman và thuật toán CONGA, được trình bày chi tiết. Cuối cùng, luận văn đưa ra kết quả cài đặt và thực nghiệm các thuật toán đã nghiên cứu.

Mục lục chi tiết:

  • Lời mở đầu
  • Chương 1: Một số kiến thức cơ bản về mô hình đồ thị
    • Một số khái niệm cơ bản
    • Định nghĩa về đồ thị
    • Các thuật ngữ cơ bản
    • Đường đi, chu trình. Đồ thị liên thông.
    • Một số phương pháp mô tả đồ thị.
      • Cấu trúc ma trận kề
      • Cấu trúc danh sách kề
    • Một số thuật toán trên đồ thị.
      • Các thuật toán duyệt đồ thị
      • Bài toán cây khung nhỏ nhất
      • Bài toán xác định đường đi ngắn nhất
    • Kết luận chương 1
  • Chương 2: Mô hình mạng xã hội và bài toán cộng đồng.
    • Khái niệm về bài toán cộng đồng.
    • Một số độ đo trên đồ thị.
      • Độ đo trung tâm của đỉnh.
      • Độ đo trung gian của đỉnh.
      • Độ đo gần nhau theo khoảng cách trắc địa.
      • Độ đo trung tâm của đồ thị.
      • Độ đo trung gian của cạnh.
      • Độ trung tâm véc tơ đặc trưng.
    • Thuật toán phát hiện cộng đồng.
      • Giới thiệu về họ thuật toán Girvan và Newman.
      • Giới thiệu về thuật toán CONGA
    • Kết luận chương 2.
  • Chương 3: Một số kết quả thiết kế và thực nghiệm các thuật toán
    • Xác định độ đo trung tâm của đỉnh.
    • Xác định độ đo trung gian của đỉnh.
    • Xác định độ đo trung gian của cạnh.
    • Kết luận chương 3.
  • Tài liệu tham khảo.