Mục tiêu chính của luận văn đặt ra là nghiên cứu các đặc trưng cơ bản về mô hình đồ thị, một số các thuật toán tìm kiếm tối ưu trên mô hình đồ thị. Khái niệm về bài toán cộng đồng và một số thuật toán xác định cộng đồng trên mạng xã hội. Mời các bạn tham khảo! | ĐẠI HỌC THÁI NGUYÊN TRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LUẬN VĂN THẠC SĨ ĐỀ TÀI 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 Giáo viên hướng dẫn TS. Vũ Vinh Quang Học viên Hoàng Văn Dũng Lớp Cao học K17 Thái Nguyên tháng 9 năm 2020 LỜI CẢM ƠN Đầu tiên em xin gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy Vũ Vinh Quang người đã trực tiếp hướng dẫn tận tình và đóng góp những ý kiến quý báu trong suốt quá trình em làm luận văn tốt nghiệp này. Tiếp theo em xin gửi lời cảm ơn đến đến các thầy cô giáo trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên đã tận tâm truyền đạt những kiến thức quý báu làm nền tảng để em hoàn thành luận văn này. Học Viên Hoàng Văn Dũng 1 LỜI CAM ĐOAN Tôi xin cam đoan 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 được trình bày trong luận văn là do tôi thực hiện dưới sự hướng dẫn của thầy Vũ Vinh Quang Tất cả những tham khảo từ các nghiên cứu liên quan đều được nêu nguồn gốc một cách rõ ràng từ danh mục tài liệu tham khảo trong luận văn. Trong luận văn không có việc sao chép tài liệu công trình nghiên cứu của người khác mà không chỉ rõ về tài liệu tham khảo. Thái Nguyên ngày tháng năm 2020 Học viên Hoàng Văn Dũng 2 MỤC LỤC LỜI MỞ ĐẦU . . 1 Chƣơng 1 MỘT SỐ KIẾN THỨC CƠ BẢN VỀ MÔ HÌNH ĐỒ THỊ 3 Một số khái niệm cơ bản . . .3 Định nghĩa về đồ thị . .3 Các thuật ngữ cơ bản . 4 Đường đi chu trình. Đồ thị liên thông . . . . 5 Một số phƣơng pháp mô tả đồ thị . . . .5 Cấu trúc ma trận kề . . . .5 Cấu trúc danh sách kề . 7 Một số thuật toán trên đồ thị . . 8 Các thuật toán duyệt đồ thị . . 8 Bài toán cây khung nhỏ nhất . . . . .9 Bài toán xác định đường đi ngắn nhất . . . .12 Kết luận chương 1 . . .15 Chƣơng 2 MÔ HÌNH MẠNG XÃ HỘI VÀ BÀI TOÁN CỘNG ĐỒNG . 17 Khái niệm về bài toán cộng đồng . . 17 Một số độ đo trên đồ thị . 18 Độ đo trung tâm của đỉnh . . . .18 Độ đo trung gian của đỉnh 19 Độ đo gần nhau theo khoảng cách trắc địa . . 21 Độ đo trung tâm của đồ thị .
