Luận văn Thạc sĩ: 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

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!
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ: 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 ĐẠI HỌC THÁI NGUYÊNTRƢỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG LUẬN VĂN THẠC SĨ ĐỀ TÀIMô 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ọcCông nghệ Thông tin và Truyền thông - Đại học Thái Nguyên, đã tận tâmtruyề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ănnà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 đồngtrê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ồngốc một cách rõ ràng từ danh mục tài liệu tham khảo trong luận văn. Trongluậ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ườikhá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 2MỤC LỤCLỜI MỞ ĐẦU……………………………………………………………………...…….……1Chương 1: MỘT SỐ KIẾN THỨC CƠ BẢN VỀ MÔ HÌNH ĐỒ THỊ……………………3Mộ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…………………...…………...….……………….…5Mộ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ề…………………………………………………………….……………7Mộ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…………………………………………….…..….…….12Kết luận chương 1……….…………………………………………………………...……..15Chương 2: MÔ HÌNH MẠNG XÃ HỘI VÀ BÀI TOÁN CỘNG ĐỒNG…………..……17Khái niệm về bài toán cộng đồng………………….…………………………….…………17Mộ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ị…………………….…………………………...………………………22 Độ đo trung gian của cạnh……………………………………………..……………….……22 Độ trung tâm véc tơ đặc trưng…………………………………………..……………….….25Thuật toán phát hiện cộng đồng…………...……………………………………….…..…..26 Giới thiệu về họ thuật toán Girvan và Newman……………….………………….…....…27 Giới thiệu về thuật toán CONGA………………………………….………………...………28Kết luận chương 2……….………………………………………………………..…...……..33Chương 3: MỘT SỐ KẾT QUẢ THIẾT KẾ VÀ THỰC NGHIỆM CÁC THUẬT TOÁNXác định độ đo trung tâm của đỉnh…………………….………………………………….34Xác định độ đo trung gian của đỉnh…………………….…………………………..….….35 3Xác định độ đo trung gian của cạnh…………………...………………………………..….36Kết luận chương 3……….………………………………………………………..…...……..41TÀI LIỆU THAM KHẢO…………………………………………………………………..42 4 DANH SÁCH CÁC HÌNH VẼHình 1.1: (a) Một đồ thị vô hướng; ……………………....………………………………………6 (b) Biểu diễn ma trận kề;……………………….………………………………………6 (c) Biểu diễn danh sách kề…………………….….……………………………………6Hình 1.2: (a) Một đồ thị có hướng; ………………….….……………………………..…………7 (b) Ma trận kề: ………………….….………………………………………..…………7 (c) Biểu diễn danh sách kề. ……………….….……………………………..…………7Hình 1.3: (a) Đồ thị trọng số; ……………….….………….…………………………..…………7 (b) Ma trận kề: …………………………….….……………………………..…………7 (c) Danh sách kề.……………….….…………………………….…………..…………7Hình 1.4: Duyệt cây theo chiều rộng BFS…………………………………………….………….9Hình 2.1: Hai đỉnh v2, v5 cùng hạng 1 và các đỉnh còn lại cùng hạng ...