Nâng Cao Hiệu Năng Thi Hành Các Phép Toán Trên Đồ Thị

Luận án tiến sĩ nghiên cứu nâng cao hiệu năng thi hành các phép toán trên đồ thị, góp phần phát triển lý thuyết và ứng dụng trong khoa học máy tính.

• Tác giả: Dư Phương Hạnh
• Người hướng dẫn: PGS. Nguyễn Hải Châu
• Trường học: Trường Đại Học Công Nghệ
• Chuyên ngành: Hệ thống thông tin
• Đề tài: Nâng Cao Hiệu Năng Thi Hành Các Phép Toán Trên Đồ Thị
• Loại tài liệu: Luận án tiến sỹ
• Năm xuất bản: 2019
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• LỜI CAM ĐOAN
• 1. CHƯƠNG 1: GIỚI THIỆU CHUNG
• 1.1. Động lực nghiên cứu
• 1.2. Cấu trúc dữ liệu phù hợp để nâng cao hiệu năng thi hành các phép toán trên đồ thị
• 1.3. Xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động quy mô lớn
• 1.4. Nâng cao hiệu năng tính các độ đo quan trọng trong phân tích đồ thị quy mô lớn
• 1.5. Một số nghiên cứu liên quan
• 2. CHƯƠNG 2: [Tiêu đề chương 2 không rõ trong fulltext]
• 3. CHƯƠNG 3: TỐI ƯU HOÁ TRUY VẤN KHOẢNG CÁCH NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG
• 3.1. Ý tưởng chính
• 3.2. Đặc tả bài toán
• 3.2.1. Mô hình dữ liệu và truy vấn
• 3.2.2. Bài toán tối ưu hoá truy vấn khoảng cách ngắn nhất trên đồ thị động
• 3.3. Cách tiếp cận giải quyết bài toán đặt ra
• 3.3.1. Giải pháp 1: akGroup
• 3.3.1.1. Cấu trúc dữ liệu đồ thị phù hợp
• 3.3.1.2. Tối ưu hoá các phép toán cập nhật
• 3.3.1.2.1. Thêm cạnh mới
• 3.3.1.2.2. Xoá một cạnh
• 3.3.1.3. Tối ưu các truy vấn
• 3.3.1.3.1. Giải thuật tính khoảng cách ngắn nhất
• 3.3.1.3.2. Xử lý song song truy vấn
• 3.3.1.4. Đánh giá thuật toán
• 3.3.2. Giải pháp 2: akGroupPlus
• 3.3.2.1. Tổ chức dữ liệu đồ thị kèm trạng thái
• 3.3.2.2. Xử lý các phép toán tương tranh
• 3.3.2.3. Tối ưu hoá các phép toán cập nhật
• 3.3.2.4. Tối ưu hoá các truy vấn tính khoảng cách ngắn nhất
• 3.3.2.4.1. Giải thuật tính khoảng cách ngắn nhất
• 3.3.2.4.2. Xử lý song song truy vấn
• 3.3.2.5. Đánh giá thuật toán
• 3.3.3. Giải pháp 3: bigGraph
• 3.4. Thực nghiệm và đánh giá
• 3.4.1. Môi trường và dữ liệu thực nghiệm
• 3.4.1.1. Môi trường thử nghiệm, đánh giá
• 3.4.1.2. Dữ liệu thực nghiệm
• 3.4.1.2.1. Dữ liệu từ cuộc thi SigMod Programming Contest 2016
• 3.4.1.2.2. Dữ liệu SNAP
• 3.4.2. Phương pháp thử nghiệm, đánh giá
• 3.4.2.1. Sinh các tập lịch thi hành thử nghiệm
• 3.4.2.2. Phương pháp đo
• 3.4.3. Thử nghiệm và đánh giá kết quả
• 3.4.3.1. Kết quả từ cuộc thi ACM SigMod Programming Contest 2016
• 3.4.3.2. Đánh giá giải pháp akGroup
• 3.4.3.3. Đánh giá giải pháp akGroupPlus
• 3.4.3.4. Đánh giá giải pháp bigGraph
• 3.5. Kết chương 3
• 4. CHƯƠNG 4: NÂNG CAO HIỆU NĂNG TÍNH ĐỘ TRUNG TÂM TRÊN ĐỒ THỊ
• 4.1. [Tiêu đề mục 4.1 không rõ trong fulltext]
• 4.2. Bài toán đặt ra
• 4.2.1. Tính độ trung tâm gần
• 4.2.2. Tính độ trung tâm trung gian
• 4.3. Nâng cao hiệu năng tính độ trung tâm
• 4.3.1. Cấu trúc dữ liệu phù hợp
• 4.3.2. Giải thuật song song tính độ trung tâm gần
• 4.3.3. Giải thuật song song tính độ trung tâm trung gian
• 4.4. Thực nghiệm và đánh giá
• 4.4.1. Môi trường thử nghiệm, đánh giá
• 4.4.2. Dữ liệu thực nghiệm
• 4.4.3. Kết quả thực nghiệm và đánh giá
• 4.4.3.1. Giải pháp nâng cao hiệu năng tính độ trung tâm gần
• 4.4.3.2. Giải pháp nâng cao hiệu năng tính độ trung tâm trung gian
• 4.5. Kết chương 4
• 5. CHƯƠNG 5: KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• 5.1. Các đóng góp chính
• 5.2. Hạn chế của luận án
• 5.3. Hướng phát triển tương lai
• DANH MỤC CÁC CÔNG BỐ CỦA LUẬN ÁN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về Tối Ưu Hiệu Năng Phép Toán Đồ Thị

Tối ưu hóa hiệu năng phép toán đồ thị là một lĩnh vực nghiên cứu quan trọng trong khoa học máy tính. Với sự gia tăng nhanh chóng của dữ liệu, việc xử lý và phân tích đồ thị trở nên cần thiết hơn bao giờ hết. Các phép toán trên đồ thị như tìm đường đi ngắn nhất, phân cụm và tính toán độ trung tâm đang được áp dụng rộng rãi trong nhiều lĩnh vực, từ mạng xã hội đến phân tích dữ liệu lớn. Nghiên cứu này nhằm nâng cao hiệu năng thi hành các phép toán trên đồ thị, giúp cải thiện khả năng xử lý dữ liệu quy mô lớn.

1.1. Động lực nghiên cứu về hiệu năng đồ thị

Nhu cầu xử lý dữ liệu lớn ngày càng tăng đã thúc đẩy nghiên cứu về tối ưu hóa hiệu năng phép toán đồ thị. Các mạng xã hội như Facebook và Twitter tạo ra khối lượng dữ liệu khổng lồ, yêu cầu các phương pháp hiệu quả để phân tích và xử lý. Việc áp dụng lý thuyết đồ thị giúp mô hình hóa các mối quan hệ phức tạp giữa các thực thể, từ đó nâng cao khả năng phân tích và ra quyết định.

1.2. Các ứng dụng thực tiễn của phép toán đồ thị

Phép toán đồ thị được ứng dụng trong nhiều lĩnh vực như phân tích mạng xã hội, tối ưu hóa logistics, và phân tích dữ liệu khoa học. Các thuật toán như tìm đường đi ngắn nhất và phân cụm giúp xác định các mối quan hệ và cấu trúc trong dữ liệu, từ đó hỗ trợ các quyết định chiến lược trong kinh doanh và nghiên cứu.

II. Thách thức trong Tối Ưu Hiệu Năng Phép Toán Đồ Thị

Mặc dù có nhiều tiến bộ trong nghiên cứu, nhưng vẫn tồn tại nhiều thách thức trong việc tối ưu hóa hiệu năng phép toán đồ thị. Các vấn đề như quy mô dữ liệu lớn, tính động của đồ thị và yêu cầu về thời gian thực là những yếu tố cần được giải quyết. Việc xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động quy mô lớn là một trong những thách thức lớn nhất.

2.1. Quy mô dữ liệu lớn và tính động

Đồ thị trong các ứng dụng thực tế thường có quy mô lớn với hàng triệu đỉnh và cạnh. Sự thay đổi liên tục trong mối quan hệ giữa các thực thể yêu cầu các phương pháp xử lý linh hoạt và hiệu quả. Việc cập nhật và truy vấn đồng thời trên đồ thị động là một thách thức lớn.

2.2. Thời gian thực và hiệu suất

Yêu cầu về thời gian thực trong các ứng dụng như mạng xã hội đòi hỏi các phép toán phải được thực hiện nhanh chóng và hiệu quả. Việc tối ưu hóa thuật toán và cấu trúc dữ liệu là cần thiết để đảm bảo hiệu suất cao trong các tình huống này.

III. Phương Pháp Tối Ưu Hóa Hiệu Năng Phép Toán Đồ Thị

Để nâng cao hiệu năng thi hành các phép toán trên đồ thị, nhiều phương pháp đã được đề xuất. Các phương pháp này bao gồm tối ưu hóa cấu trúc dữ liệu, áp dụng các thuật toán song song và cải tiến các thuật toán hiện có. Việc lựa chọn cấu trúc dữ liệu phù hợp là rất quan trọng để đạt được hiệu suất tối ưu.

3.1. Cấu trúc dữ liệu tối ưu cho đồ thị

Cấu trúc dữ liệu như danh sách liền kề và ma trận liên thuộc được sử dụng để biểu diễn đồ thị. Việc lựa chọn cấu trúc dữ liệu phù hợp giúp cải thiện hiệu suất truy cập và xử lý dữ liệu. Nghiên cứu cho thấy rằng danh sách liền kề là lựa chọn tốt nhất cho đồ thị có quy mô lớn.

3.2. Thuật toán song song trong xử lý đồ thị

Áp dụng các thuật toán song song giúp tăng tốc độ xử lý các phép toán trên đồ thị. Các hệ thống tính toán song song có thể xử lý nhiều truy vấn đồng thời, từ đó cải thiện hiệu suất tổng thể. Việc sử dụng GPU và các kiến trúc đa lõi cũng là một giải pháp hiệu quả.

IV. Ứng Dụng Thực Tiễn và Kết Quả Nghiên Cứu

Nghiên cứu về tối ưu hóa hiệu năng phép toán đồ thị đã cho thấy nhiều kết quả khả quan trong thực tiễn. Các ứng dụng trong mạng xã hội, phân tích dữ liệu lớn và các lĩnh vực khác đã chứng minh tính khả thi và hiệu quả của các phương pháp được đề xuất. Kết quả thực nghiệm cho thấy sự cải thiện đáng kể về thời gian xử lý và độ chính xác của các phép toán.

4.1. Kết quả từ các thử nghiệm thực tế

Các thử nghiệm thực tế cho thấy rằng việc áp dụng các phương pháp tối ưu hóa đã giúp giảm thời gian xử lý các phép toán trên đồ thị. Kết quả từ các bộ dữ liệu lớn cho thấy sự cải thiện rõ rệt trong hiệu suất, từ đó khẳng định tính hiệu quả của nghiên cứu.

4.2. Ứng dụng trong phân tích mạng xã hội

Nghiên cứu đã được áp dụng thành công trong phân tích mạng xã hội, giúp xác định các mối quan hệ và ảnh hưởng giữa các thành viên. Việc tối ưu hóa các phép toán đã giúp cải thiện khả năng phân tích và ra quyết định trong các chiến lược truyền thông xã hội.

V. Kết Luận và Hướng Phát Triển Tương Lai

Tối ưu hóa hiệu năng phép toán đồ thị là một lĩnh vực nghiên cứu quan trọng với nhiều ứng dụng thực tiễn. Nghiên cứu đã chỉ ra rằng việc áp dụng các phương pháp tối ưu hóa có thể cải thiện đáng kể hiệu suất xử lý. Hướng phát triển tương lai sẽ tập trung vào việc cải tiến các thuật toán và cấu trúc dữ liệu, cũng như mở rộng ứng dụng trong các lĩnh vực mới.

5.1. Các đóng góp chính của nghiên cứu

Nghiên cứu đã đóng góp vào việc phát triển các phương pháp tối ưu hóa hiệu năng phép toán đồ thị, từ đó nâng cao khả năng xử lý dữ liệu lớn. Các kết quả đạt được đã mở ra hướng đi mới cho các nghiên cứu tiếp theo trong lĩnh vực này.

5.2. Hướng phát triển trong tương lai

Hướng nghiên cứu trong tương lai sẽ tập trung vào việc phát triển các thuật toán mới, cải tiến cấu trúc dữ liệu và ứng dụng trong các lĩnh vực như trí tuệ nhân tạo và học máy. Việc kết hợp các công nghệ mới sẽ giúp nâng cao hiệu suất và khả năng xử lý của các phép toán trên đồ thị.

Trích đoạn nội dung tài liệu

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Dư Phương Hạnh NÂNG CAO HIỆU NĂNG THI HÀNH CÁC PHÉP TOÁN TRÊN ĐỒ THỊ LUẬN ÁN TIẾN SỸ HỆ THỐNG THÔNG TIN Hà Nội - 2019 LUAN VAN CHAT LUONG download : add [e-mail] ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Dư Phương Hạnh NÂNG CAO HIỆU NĂNG THI HÀNH CÁC PHÉP TOÁN TRÊN ĐỒ THỊ LUẬN ÁN TIẾN SỸ HỆ THỐNG THÔNG TIN Chuyên ngành: Hệ thống thông tin Mã số: 9480104.01 Người hướng dẫn khoa học: 1. Nguyễn Hải Châu 2. Nguyễn Kim Khoa Hà Nội - 2019 LUAN VAN CHAT LUONG download : add [e-mail] LỜI CẢM ƠN Luận án được thực hiện tại Trường Đại học Công nghệ - ĐHGQ Hà Nội, dưới sự hướng dẫn của PGS. Nguyễn Hải Châu và PGS. Nguyễn Kim Khoa (Trường ETS - Đại học Quebec - Canada). Trước hết, tôi xin được bày tỏ lòng biết ơn sâu sắc tới PGS. Nguyễn Hải Châu và PGS. Nguyễn Kim Khoa, những người đã hướng dẫn, đưa ra những định hướng giúp tác giả hoàn thành bản luận án này. Tôi cũng chân thành cám ơn toàn thể các thầy, cô đồng nghiệp trong Bộ môn Các hệ thống thông tin đã đồng hành trong nhiều năm, góp nhiều ý kiến quan trọng để tác giả có thể hoàn thiện các nội dung khoa học của luận án. Để có được kết quả ngày hôm nay, tôi cũng xin chân thành cảm ơn Trường Đại học Công nghệ, Khoa Công nghệ Thông tin, các Phòng chức năng của Trường, đã tạo điều kiện thuận lợi cho tôi trong quá trình nghiên cứu và công tác tại Trường. Sau cùng, tôi xin chân thành cảm ơn gia đình, những người thân và bạn bè đã giúp đỡ, động viên tôi trong suốt thời gian thực hiện luận án này! Hà Nội, tháng 08 năm 2019 Dư Phương Hạnh i LUAN VAN CHAT LUONG download : add [e-mail] LỜI CAM ĐOAN Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các nội dung viết chung với các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào Luận án. Các kết quả nêu trong luận án là trung thực và chưa từng được ai công bố trong các công trình nào khác. Tác giả Dư Phương Hạnh ii LUAN VAN CHAT LUONG download : add [e-mail] Mục lục 1 GIỚI THIỆU CHUNG 1 1.1 Động lực nghiên cứu .1 Cấu trúc dữ liệu phù hợp để nâng cao hiệu năng thi hành các phép toán trên đồ thị .2 Xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động quy mô lớn 2 1.3 Nâng cao hiệu năng tính các độ đo quan trọng trong phân tích đồ thị quy mô lớn .2 Một số nghiên cứu liên quan .3 Mục tiêu, phạm vi nghiên cứu, đóng góp và bố cục của luận án .1 Mục tiêu nghiên cứu .2 Phạm vi và phương pháp nghiên cứu .4 Các đóng góp chính của luận án .5 Tổ chức của luận án .3 Các đặc điểm chính của đồ thị .2 Biểu diễn đồ thị .1 Danh sách các cạnh .2 Ma trận liền kề .3 Danh sách liền kề .4 Ma trận liên thuộc .5 Ma trận hàng thưa nén .3 Các phép toán chính trên đồ thị .1 Duyệt theo chiều rộng trước - BFS .2 Duyệt theo chiều sâu trước - DFS .2 Phân tích đồ thị . 26 iii LUAN VAN CHAT LUONG download : add [e-mail] MỤC LỤC iv 2.1 Tính khoảng cách .2 Đường đi ngắn nhất .4 Phân cụm đồ thị .4 Tính toán song song .1 Kiến trúc hệ thống tính toán song song .1 Kiến trúc bộ nhớ chia sẻ .2 Kiến trúc bộ nhớ phân tán .3 Kiến trúc bộ nhớ lai chia sẻ-phân tán .2 Mô hình lập trình song song .3 Một số bài toán song song điển hình .5 Kết chương 2 . 40 3 TỐI ƯU HOÁ TRUY VẤN KHOẢNG CÁCH NGẮN NHẤT TRÊN ĐỒ THỊ ĐỘNG 42 3.2 Đặc tả bài toán .1 Mô hình dữ liệu và truy vấn .2 Bài toán tối ưu hoá truy vấn khoảng cách ngắn nhất trên đồ thị động 45 3.3 Cách tiếp cận giải quyết bài toán đặt ra .3 Giải pháp 1: akGroup .1 Cấu trúc dữ liệu đồ thị phù hợp .2 Tối ưu hoá các phép toán cập nhật .1 Thêm cạnh mới .2 Xoá một cạnh .3 Tối ưu các truy vấn .1 Giải thuật tính khoảng cách ngắn nhất .2 Xử lý song song truy vấn .4 Đánh giá thuật toán .4 Giải pháp 2: akGroupPlus .1 Tổ chức dữ liệu đồ thị kèm trạng thái .2 Xử lý các phép toán tương tranh .3 Tối ưu hoá các phép toán cập nhật .4 Tối ưu hoá các truy vấn tính khoảng cách ngắn nhất .1 Giải thuật tính khoảng cách ngắn nhất .2 Xử lý song song truy vấn .5 Đánh giá thuật toán .5 Giải pháp 3: bigGraph . 67 LUAN VAN CHAT LUONG download : add [e-mail] MỤC LỤC v 3.1 Ý tưởng chính .2 Giải thuật song song hoá các phép toán cập nhật .3 Đánh giá thuật toán .6 Thực nghiệm và đánh giá .1 Môi trường và dữ liệu thực nghiệm .1 Môi trường thử nghiệm, đánh giá .2 Dữ liệu thực nghiệm .1 Dữ liệu từ cuộc thi SigMod Programming Contest 2016 .2 Dữ liệu SNAP .2 Phương pháp thử nghiệm, đánh giá .1 Sinh các tập lịch thi hành thử nghiệm .2 Phương pháp đo .3 Thử nghiệm và đánh giá kết quả .1 Kết quả từ cuộc thi ACM SigMod Programming Contest 2016 75 3.2 Đánh giá giải pháp akGroup .3 Đánh giá giải pháp akGroupPlus .4 Đánh giá giải pháp bigGraph .7 Kết chương 3 . 88 4 NÂNG CAO HIỆU NĂNG TÍNH ĐỘ TRUNG TÂM TRÊN ĐỒ THỊ 91 4.2 Bài toán đặt ra .1 Tính độ trung tâm gần .2 Tính độ trung tâm trung gian .3 Nâng cao hiệu năng tính độ trung tâm .1 Cấu trúc dữ liệu phù hợp .2 Giải thuật song song tính độ trung tâm gần .3 Giải thuật song song tính độ trung tâm trung gian .4 Thực nghiệm và đánh giá .1 Môi trường thử nghiệm, đánh giá .2 Dữ liệu thực nghiệm .3 Kết quả thực nghiệm và đánh giá .1 Giải pháp nâng cao hiệu năng tính độ trung tâm gần .2 Giải pháp nâng cao hiệu năng tính độ trung tâm trung gian 105 4.5 Kết chương 4 . 109 5 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 110 5.1 Các đóng góp chính .2 Hạn chế của luận án . 112 LUAN VAN CHAT LUONG download : add [e-mail] MỤC LỤC vi 5.3 Hướng phát triển tương lai . 113 DANH MỤC CÁC CÔNG BỐ CỦA LUẬN ÁN 114 TÀI LIỆU THAM KHẢO 115 LUAN VAN CHAT LUONG download : add [e-mail] Danh sách hình vẽ 1.1 Lược đồ tổ chức luận án .1 Minh họa về đồ thị xã hội .2 Minh họa việc xuất bản thông điệp .3 Một số kiểu đồ thị cơ bản .4 Đồ thị có hướng và ma trận liền kề .5 Danh sách liền kề .6 Ma trận liên thuộc biểu diễn đồ thị .7 Ma trận hàng thưa nén .8 Ví dụ về duyệt theo chiều rộng trước .9 Ví dụ về duyệt theo chiều sâu trước .10 Một số độ đo trung tâm điển hình trên đồ thị .11 Ảnh hưởng của số CPU và tỷ lệ đoạn mã được song song đến hệ số tăng tốc 34 2.12 Kiến trúc hệ thống tính toán song song dựa trên bộ nhớ chia sẻ .13 Kiến trúc hệ thống tính toán song song dựa trên bộ nhớ phân tán .14 Kiến trúc hệ thống tính toán song song dựa trên bộ nhớ lai chia sẻ-phân tán 37 2.15 Mô hình xử lý song song trong CilkPlus .1 Các phép toán tương tranh trên đồ thị .2 Minh hoạ cấu trúc dữ liệu đồ thị .3 Phép toán bổ sung thêm cạnh trên đồ thị .4 Thi hành phép toán xoá cạnh trong đồ thị .5 Duyệt hai chiều BFS để tính khoảng cách ngắn nhất .6 Thi hành các phép toán tương tranh có thể hiện trạng thái .7 Song song các phép toán cập nhật đồ thị .8 Kết quả đánh giá với bộ dữ liệu Sigmod Dataset .9 Kết quả đánh giá với bộ dữ liệu Pokec Dataset .10 Kết quả đánh giá với bộ dữ liệu LiveJournal Dataset .11 Kết quả thực nghiệm với bộ dữ liệu SigMod 8-1-1 .12 Kết quả thực nghiệm với bộ dữ liệu Sigmod 5-4-1 .13 Kết quả thực nghiệm với bộ dữ liệu Pokec 8-1-1 . 84 vii LUAN VAN CHAT LUONG download : add [e-mail] DANH SÁCH HÌNH VẼ viii 3.14 Kết quả thực nghiệm với bộ dữ liệu Pokec 5-4-1 .15 Kết quả thực nghiệm với bộ dữ liệu LiveJournal 8-1-1 .16 Kết quả thực nghiệm với bộ dữ liệu LiveJournal 5-4-1 .1 Thời gian thi hành bigGraph khi tính độ trung tâm trung gian .2 Đánh giá hệ số tăng tốc bigGraph khi tính độ trung tâm trung gian .3 Thời gian thi hành thực nghiệm tính độ trung tâm gần .4 Thời gian thi hành tính độ đo BC của bigGraph (giây) .5 Đánh giá hệ số tăng tốc tính độ đo BC của bigGraph .6 Thời gian thi hành thực nghiệm tính độ đo BC . 108 LUAN VAN CHAT LUONG download : add [e-mail] Danh sách bảng 3.1 Thời gian thao tác bộ nhớ .2 Thống kê các đồ thị sử dụng trong SigMod 2016 .3 Thống kê các bộ dữ liệu đồ thị sử dụng trong thực nghiệm .4 Kết quả thực nghiệm trên hệ thống đánh giá của ACM SigMod 2016 (giây) .5 Kết quả đánh giá giải pháp akGroup so với một số công cụ khác .6 Thống kê hiệu năng tốt nhất .1 Thông tin thống kê về các dữ liệu mạng xã hội thử nghiệm .2 Thời gian (giây) và hệ số tăng tốc của bigGraph khi tính độ trung tâm gần .3 Thời gian tính độ trung tâm gần (giây) .4 Hệ số tăng tố của bigGraph so với TeexGraph và NetworKit khi tính độ trung tâm gần .5 Thời gian (giây) và hệ số tăng tốc của bigGraph khi tính độ trung tâm trung gian .6 Thời gian tính độ đo BC (giây) .7 Hệ số tăng tốc của bigGraph so với TeexGraph và NetworKit khi tính độ đo BC . 108 ix LUAN VAN CHAT LUONG download : add [e-mail] Danh sách thuật toán 2.1 BF S(G, v): Mã giả phương pháp duyệt theo chiều rộng trước .2 DF S(G, v): Mã giả phương pháp duyệt theo chiều sâu trước .3 Giải thuật tính khoảng cách ngắn nhất sử dụng bBFS .1 akGroup: Giải thuật thi hành lịch S .2 akGroup: Thêm cạnh (u, v) vào đồ thị G .3 akGroup: Xoá cạnh (u, v) trong đồ thị G .4 akGroup: Giải thuật tính khoảng cách ngắn nhất (u, v) .5 akGroup: Thi hành song song các truy vấn tính khoảng cách ngắn nhất trong G 57 3.6 akGroupPlus: Giải thuật thi hành lịch S .7 akGroupPlus: Cập nhật các cạnh trong lịch S .8 akGroupPlus: Ghi nhận các phép toán cập nhật .9 akGroupPlus: Tính khoảng cách ngắn nhất giữa (u, v) .10 akGroupPlus: Kiểm tra một cạnh (u, v) có được ghi nhận ở thời điểm t hay không .11 akGroupPlus: Thi hành song song các truy vấn khoảng cách ngắn nhất trên đồ thị G .