Luận án Tiến sĩ Khoa học máy tính: Một số kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:146

Thêm vào BST

Báo xấu

17
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận án Tiến sĩ Khoa học máy tính "Một số kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội" trình bày các nội dung chính sau: Tổng quan về đồ thị mạng xã hội và bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội; Phát hiện cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội; Phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận án Tiến sĩ Khoa học máy tính: Một số kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Hiền Trinh MỘT SỐ KỸ THUẬT PHÁT HIỆN CẤU TRÚC CỘNG ĐỒNG TRÊN ĐỒ THỊ MẠNG XÃ HỘI LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN, NĂM 2023
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG Nguyễn Hiền Trinh MỘT SỐ KỸ THUẬT PHÁT HIỆN CẤU TRÚC CỘNG ĐỒNG TRÊN ĐỒ THỊ MẠNG XÃ HỘI Chuyên ngành: Khoa học máy tính Mã số: 9. 48. 01. 01 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. PGS.TS. Đoàn Văn Ban 2. TS. Vũ Vinh Quang THÁI NGUYÊN, NĂM 2023
Lời cam đoan Tôi xin cam đoan những nội dung được đề xuất trong luận án là hoàn toàn mới, chưa có tác giả nào công bố. Các kết quả đạt được trong quá trình nghiên cứu là hoàn toàn trung thực khách quan. Tác giả: NCS Nguyễn Hiền Trinh i
Lời cảm ơn Tôi xin chân thành cảm ơn PGS.TS Đoàn Văn Ban và TS. Vũ Vinh Quang đã tận tình giúp đỡ, động viên, định hướng, hướng dẫn tôi nghiên cứu và hoàn thành luận án này. Tôi xin chân thành cảm ơn Ban lãnh đạo Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên, Ban chủ nhiệm khoa Khoa Công nghệ thông tin đã giúp đỡ tôi trong quá trình thực hiện luận án. Tôi chân thành cảm ơn những ý kiến đóng góp, tư vấn, hỗ trợ từ các thầy, cô giáo, các nhà khoa học và bạn bè đồng nghiệp để hoàn thiện luận án này. Trân trọng cám ơn! NCS. Nguyễn Hiền Trinh ii
Mục lục Lời cam đoan i Lời cảm ơn ii Danh mục các ký hiệu, các chữ viết tắt vi Danh mục các thuật ngữ viii Mở đầu 1 1 Tổng quan về đồ thị mạng xã hội và bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội 9 1.1 Giới thiệu chung . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2 Mạng xã hội và đồ thị mạng xã hội . . . . . . . . . . . . . 11 1.2.1 Mạng xã hội . . . . . . . . . . . . . . . . . . . . . . 11 1.2.2 Một số đặc tính của mạng xã hội . . . . . . . . . . . 12 1.2.3 Đồ thị mạng xã hội và cấu trúc cộng đồng của mạng xã hội . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3 Một số độ đo quan trọng trên đồ thị mạng xã hội . . . . . . 16 1.3.1 Độ đo trung tâm theo bậc . . . . . . . . . . . . . . 16 1.3.2 Độ đo trung gian . . . . . . . . . . . . . . . . . . . 19 1.3.3 Độ đo trung tâm theo vector riêng . . . . . . . . . . 23 1.3.4 Hệ số phân cụm đồ thị . . . . . . . . . . . . . . . . 24 1.4 Bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 iii
1.4.1 Nhóm thuật toán phát hiện cấu trúc cộng đồng truyền thống . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.4.2 Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa trên tối ưu hóa độ đo đơn thể . . . . . . . . . . . . . 30 1.4.3 Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa vào độ đo trung gian . . . . . . . . . . . . . . . . . 32 1.4.4 Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa trên lan truyền nhãn . . . . . . . . . . . . . . . . . 35 1.4.5 Nhóm thuật toán phát hiện cấu trúc cộng đồng dựa vào mạng học sâu . . . . . . . . . . . . . . . . . . . 37 1.5 Các độ đo đánh giá thuật toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội . . . . . . . . . . . . . . . . . . . . 43 1.5.1 Độ đo đơn thể Modularity . . . . . . . . . . . . . . 43 1.5.2 Thông tin tương hỗ chuẩn NMI . . . . . . . . . . . 44 1.6 Tổng kết chương 1 . . . . . . . . . . . . . . . . . . . . . . 45 2 Phát hiện cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội 46 2.1 Phát hiện cấu trúc cộng đồng rời nhau bằng phương pháp phân cụm phổ (Spectral) . . . . . . . . . . . . . . . . . . . 46 2.1.1 Những vấn đề cơ bản trong phương pháp phân cụm phổ (Spectral Clustering) . . . . . . . . . . . . . . 47 2.1.2 Bài toán và phương pháp phân cụm phổ . . . . . . . 50 2.1.3 Thuật toán đề xuất . . . . . . . . . . . . . . . . . . 52 2.1.4 Các kết quả thực nghiệm . . . . . . . . . . . . . . . 64 2.2 Cải tiến thuật toán lan truyền nhãn LPA . . . . . . . . . . 67 2.2.1 Thuật toán lan truyền nhãn LPA . . . . . . . . . . . 67 2.2.2 Thuật toán lan truyền nhãn LPAMD với hàm f đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.2.3 Kết quả thực nghiệm thuật toán LPAMD . . . . . . 76 2.2.4 Nhận xét . . . . . . . . . . . . . . . . . . . . . . . 82 2.3 Kết hợp rút gọn đồ thị và thuật toán lan truyền nhãn . . . 83 iv
2.3.1 Thuật toán LPARLV (LPA Reduce Leaf Vertex) . . 83 2.3.2 Nhận xét . . . . . . . . . . . . . . . . . . . . . . . . 88 2.3.3 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . 88 2.4 Tổng kết chương 2 . . . . . . . . . . . . . . . . . . . . . . . 93 3 Phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội 94 3.1 Khái quát về vấn đề cộng đồng chồng chéo . . . . . . . . . 94 3.2 Hệ số phân cụm đồ thị và hệ số thuộc về cộng đồng . . . . 96 3.2.1 Hệ số phân cụm đồ thị . . . . . . . . . . . . . . . . 96 3.2.2 Hệ số thuộc về cộng đồng . . . . . . . . . . . . . . 99 3.2.3 Phát hiện cấu trúc cộng đồng chồng chéo theo lan truyền nhãn và dựa vào hệ số thuộc về cộng đồng . . 101 3.2.4 Độ phức tạp thuật toán COPA-BC . . . . . . . . . 108 3.2.5 Kết quả thực nghiệm . . . . . . . . . . . . . . . . . 109 3.2.6 Nhận xét . . . . . . . . . . . . . . . . . . . . . . . . 112 3.3 Tổng kết chương 3 . . . . . . . . . . . . . . . . . . . . . . . 114 Kết luận và hướng phát triển của luận án 115 Danh mục các công trình khoa học có liên quan đến luận án118 Tài liệu tham khảo 120 v
Danh mục các ký hiệu, các chữ viết tắt STT Từ viết tắt Dạng đầy đủ 1 AE Auto Encoder Balanced iterative reducing and clustering 2 BIRCH using hierarchies 3 BFS Breadth first search 4 CNN Convolution Neural Network 5 CONGA Cluster Overlap Newman-Girvan Algorithm 6 CONGO CONGA Optimized 7 COPRA Community Overlap Propagation Algorithm Community Overlap Propagation Algorithm 8 COPA-BC Based on New Belonging Coefficient 9 DFS Depth-first search 10 DSF Deep Sparse Filtering 11 GAN Generative Adversarial Network 12 GCN Graph Convolutional Networks 13 GN Girvan-Newman 14 GNN Graph neural networks IVIC- Improved Vertex Imitation Co-efficient based 15 COPRA COPRA Bảng tiếp tục ở trang sau vi
Tiếp tục từ trang trước STT Từ viết tắt Dạng đầy đủ 16 LPA Label propagation algorithm Label Propagation Algorithm with 17 LPAMD Modularity and Density 18 LPARLV LPA Reduce Leaf Vertex 19 MCG Make Compact Graph 20 MLE Maximum-likelihood estimation 21 NMI Normalized mutual information 22 NMF Deep Nonnegative Ma-trix Factorization 23 OLP Optimized label propagation 24 PCB Belief Propagation and Conflict 25 RCL ReClustering 26 RE Remove edge 27 SC Stanford large network dataset collection 28 SCN Spectral Clustering New 29 SN Social network 30 SNAP Stanford Network Analysis Platform Spectral clustering combining information on 31 SpcSA both the network Structure and node Attributes 32 WTG Weight Triangle vii
Danh mục các thuật ngữ STT Thuật ngữ Tiếng Anh Thuật ngữ Tiếng Việt 1 Actor Tác nhân 2 Adjacency list Danh sách liền kề (lân cận kề) 3 Adjacency matrix Ma trận liền kề (lân cận kề) 4 Betweenness Độ đo trung gian 5 Betweenness centrality Độ đo trung tâm trung gian 6 Big data Dữ liệu lớn 7 Bio-logical networks Mạng sinh học 8 Breadth first search Duyệt theo chiều rộng 9 Closeness Độ gần nhau 10 Closeness centrality Hệ số trung tâm gần nhau 11 Clustering Coefficient Hệ số phân cụm 12 Chemical compound Hợp chất hóa học Mạng cộng tác trong nghiên cứu 13 Collaborative Networks khoa học 14 Communication network Mạng truyền thông 15 Community detection Phát hiện cấu trúc cộng đồng 16 Community social structure Cấu trúc cộng đồng mạng xã hội 17 Degree Bậc 18 Degree centrality Độ đo trung tâm theo bậc 19 Diameter Đường kính Bảng tiếp tục ở trang sau viii
Tiếp tục từ trang trước STT Thuật ngữ Tiếng Anh Thuật ngữ Tiếng Việt 20 Direction Có hướng 21 Dynamic Động 22 Edge Cạnh 23 Edge betweenness centrality Độ đo trung gian của cạnh 24 Eigenvector centrality Độ đo theo vecto đặc trưng 25 Evolutionary algorithms Thuật toán tiến hóa 26 Extremal Optimization Tối ưu hóa mở rộng 27 Frequent subgraph Đồ thị con phổ biến 28 Graph Đồ thị 29 Graph clustering Phân cụm đồ thị 30 Graph partitioning Phân vùng đồ thị 31 Graph evolution Tiến hóa đồ thị 32 Graph Mining Khai phá đồ thị 33 Greedy techniques Tìm kiếm tham lam 34 Ground truth Cộng đồng thực Hierarchical Agglomerative 35 Phân cụm phân cấp có thứ bậc Clustering 36 Information theory Lý thuyết thông tin 37 Isomorphism Đẳng cấu K-Nearest Neighbors Phương pháp phân loại k-hàng 38 Classifier xóm gần nhất Label Propagation 39 Thuật toán lan truyền nhãn Algorithm 40 Leaf vertex Đỉnh treo 41 Network Mạng 42 Measure Độ đo 43 Modularity Modul Bảng tiếp tục ở trang sau ix
Tiếp tục từ trang trước STT Thuật ngữ Tiếng Anh Thuật ngữ Tiếng Việt Modularity Optimisation Thuật toán phát hiện cấu trúc 44 Based Community cộng đồng dựa trên tối ưu hóa Detection Techniques modul 45 Overlapping Chồng chéo⧸ Chồng chéo 46 Pair betweenness Độ đo trung gian cặp 47 Pair-counting Tính toán cặp 48 Partitional clustering Phân cụm phân hoạch 49 Pattern Mẫu 50 Protein structure Cấu trúc protein 51 Run times Thời gian chạy/thực hiện 52 Simulated annealing Mô phỏng luyện kim 53 Social Networks Mạng xã hội 54 Social Network Analysis Phân tích mạng xã hội Social network community 55 Cấu trúc cộng đồng mạng xã hội structure 56 Social network community Cộng đồng mạng xã hội 57 Sparse graph Đồ thị thưa 58 Spectral clustering Phân cụm phổ 59 Support Độ độ hỗ trợ/ phổ biến Support Vector Machine 60 Máy học vectơ hỗ trợ learning 61 Supervised Neural Networks Mạng neural có giám sát Traditional Community Thuật toán phát hiện cấu trúc 62 Detection Techniques cộng đồng truyền thống 63 Triangle Tam giác x
Danh sách bảng 1.1 Độ đo trung tâm theo bậc và độ đo theo bậc chuẩn hóa . . 17 1.2 Tính độ đo trung gian cho các đỉnh của đồ thị hình 1.4 . . . 22 2.1 Kết quả phân cụm . . . . . . . . . . . . . . . . . . . . . . . 63 2.2 Kết quả thực nghiệm về thời gian thực hiện SCN, SpcSA và UVonLB trên mạng thực, đơn vị tính s (giây). Với các bộ dữ liệu: AdjNoun, Caltech36, Simmons81, Pages tvshow, Lehigh96 lấy từ [64] . . . . . . . . . . . . . . . . . . . . . . 64 2.3 Kết quả thực nghiệm về chất lượng cộng đồng (Modular- ity)với SCN, SpcSA và UVonLB . . . . . . . . . . . . . . . 65 2.4 Kết quả thực nghiệm về độ đo thông tin tương hỗ chuẩn (NMI) với SCN, SpcSA và UVonLB . . . . . . . . . . . . . 66 2.6 Kết quả thực nghiệm về thời gian thực hiện LPAMD, đơn vị tính s (giây) Với các bộ dữ liệu Page - food, Hamsterster, Hepth Oregon_2 , Email - Enron, Brightkite [64], Musae - wiki [43] . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.7 Kết quả thực nghiệm về chất lượng cộng đồng (Modular- ity)với LPAMD . . . . . . . . . . . . . . . . . . . . . . . . 81 2.8 Kết quả thực nghiệm về độ đo thông tin tương hỗ chuẩn (NMI) với LPAMD . . . . . . . . . . . . . . . . . . . . . . 82 2.9 Kết quả thực nghiệm về thời gian thực hiện LPARLV . Với các bộ dữ liệu: Dolphin Group, Les Misérables Group, Wiki- Vote, Youtube, Wiki-Elec lấy theo [64] . . . . . . . . . . . 90 2.10 Kết quả thực nghiệm về chất lượng cộng đồng với LPARLV 91 xi
2.11 Kết quả thực nghiệm về thông tin tương hỗ chuẩn hóa NMI với LPARLV . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.1 Quá trình gắn nhãn ở các bước t = 1, 2, 3, 4 . . . . . . . . 104 3.2 Kết quả thực nghiệm về thời gian thực hiện. Với các bộ dữ liệu: Karate Club, Dolphin Group lấy theo [64]; Email-Eu- core, DBLP, Amazon, Youtube [43] . . . . . . . . . . . . . 110 3.3 Kết quả thực nghiệm về chất lượng cộng đồng qua chỉ số Modularity với COPA-BC . . . . . . . . . . . . . . . . . . . 111 3.4 Kết quả thực nghiệm về thông tin tương hỗ chuẩn hóa NMI với COPA-BC . . . . . . . . . . . . . . . . . . . . . . . . . 112 xii
Danh sách hình vẽ 1.1 Cấu trúc dữ liệu đồ thị có mặt ở khắp nơi: Mạng đồng biểu hiện; mạng xã hội; các luồng chương trình; trong hợp chất hóa học và cấu trúc protein, . . . . . . . . . . . . . . . . . . 10 1.2 Cấu trúc cộng đồng trong mạng thể hiện mối quan hệ giữa các nhân vật trong tác phẩm Những người khốn khổ . . . . 15 1.3 Đồ thị vô hướng 7 nút và độ đo trung tâm theo bậc . . . . 17 1.4 Đồ thị vô hướng 6 nút . . . . . . . . . . . . . . . . . . . . . 21 2.1 Minh họa đồ thị phân thành 2 cụm . . . . . . . . . . . . . 48 2.2 Mạng 8 đỉnh, các liên kết và trọng số . . . . . . . . . . . . 61 2.3 Hình ảnh phân 3 cộng đồng . . . . . . . . . . . . . . . . . . 63 2.4 Đánh giá thời gian thực hiện giữa SCN, SpcSA và UVonLB 65 2.5 Đánh giá Modularity giữa SCN, SpcSA và UVonLB . . . . 66 2.6 Đánh giá NMI giữa SCN, SpcSA và UVonLB . . . . . . . . 67 2.7 Minh họa các đỉnh láng giềng . . . . . . . . . . . . . . . . . 71 2.8 Mạng giả định 2.8 với 12 đỉnh . . . . . . . . . . . . . . . . 73 2.9 Minh họa thuật toán ở vòng lặp thứ nhất, đỉnh chọn ngẫu nhiên x = 5 . . . . . . . . . . . . . . . . . . . . . . . . . . 73 2.10 Minh họa thuật toán ở vòng lặp thứ nhất, đỉnh chọn ngẫu nhiên x = 2 . . . . . . . . . . . . . . . . . . . . . . . . . . 74 2.11 Minh họa thuật toán ở vòng lặp thứ nhất, đỉnh chọn ngẫu nhiên x = 3 . . . . . . . . . . . . . . . . . . . . . . . . . . 75 2.12 Kết quả phát hiện cộng đồng của mạng giả định 2.8 . . . . 76 2.13 Mạng Karate Club ban đầu . . . . . . . . . . . . . . . . . . 77 2.14 Mạng Karate Club với cộng đồng được hình thành . . . . . 78 xiii
2.15 Mạng Karate Club sau 5 lần lặp với các cộng đồng kết quả . 78 2.16 Mạng Karate Club với 2 cộng đồng khi chạy LPAMD với hàm gắn nhãn theo công thức (2.10) . . . . . . . . . . . . . 79 2.17 Đánh giá thời gian thực hiện giữa LPAMD với LPA, CLPA và NLPPC . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 2.18 Đánh giá Modularity giữa LPAMD với LPA, CLPA và NLPPC 81 2.19 Đánh giá giữa LPAMD với LPA, CLPA và NLPPC dựa trên đo đo thông tin tương hỗ chuẩn (NMI) . . . . . . . . . . . 82 2.20 Kết quả các cộng đồng của mạng Les Misérables . . . . . . 89 2.21 So sánh thời gian thực hiện giữa LPARLV, OLP, LPA . . . 90 2.22 So sánh chất lượng cộng đồng (Modularity) giữa LPARLV, OLP, LPA . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 2.23 So sánh thông tin tương hỗ chuẩn hóa NMI giữa LPARLV, OLP, LPA . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 3.1 Đồ thị mạng xã hội đơn giản 4 nút có 2 cộng đồng C, D . . 95 3.2 Đồ thị mạng G có 14 nút thành viên . . . . . . . . . . . . . 98 3.3 Mạng G có 3 cộng đồng chồng chéo với hai nút chồng chéo 2, 5 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 3.4 So sánh thời gian thực hiện thuật toán COPA-BC trên 6 mạng thực với COPRA, IVIC-COPRA . . . . . . . . . . . . 110 3.5 So sánh chất lượng cộng đồng được phát hiện trên 6 mạng thực giữa COPA-BC, COPRA, IVICCOPRA . . . . . . . . 111 3.6 So sánh NMI của các cộng đồng được phát hiện trên 6 mạng thực giữa COPA-BC, COPRA, IVICCOPRA . . . . . . . . 113 xiv
Mở đầu 1. Tính cấp thiết của luận án Mạng xã hội là một tập hợp các thực thể được kết nối với nhau bằng một tập hợp các mối quan hệ hay liên kết, như mối quan hệ bạn bè, gia đình, mối quan hệ kinh doanh, quá trình lây lan bệnh tật, sự phát tán tin tức, các biểu đồ cộng tác, mạng ngữ nghĩa cho mô tả ngôn ngữ, . . . Mạng xã hội thường được biểu diễn dưới dạng đồ thị, trong đó các nút (đỉnh) biểu diễn cho các thực thể và các cạnh biểu diễn cho mối quan hệ giữa các thực thể với nhau. Khai phá đồ thị là quá trình phát hiện, truy xuất và phân tích các mẫu không tầm thường trong dữ liệu dưới dạng cấu trúc đồ thị. Ngày nay, khai phá dữ liệu đồ thị nổi lên như một kỹ thuật quan trọng trong xã hội học hiện đại, đã có những đóng góp vô cùng quan trọng trong nhiều lĩnh vực như: nhân chủng học, sinh học, nhân khẩu học, nghiên cứu truyền thông, kinh tế, địa lý, lịch sử, khoa học thông tin, khoa học máy tính, . . . Trong lĩnh vực khai phá đồ thị, việc phân tích và phát hiện cấu trúc cộng đồng mang nhiều ý nghĩa quan trọng và có rất nhiều ứng dụng cả trong lý thuyết lẫn thực tiễn. Cấu trúc cộng đồng (cộng đồng) được hiểu là một nhóm các thực thể trong mạng có những tính chất tương tự nhau, liên kết chặt chẽ với nhau và cùng đóng một vai trò nhất định đối với mỗi bài toán thực tế. Việc phát hiện và phân tích các cộng đồng trên đồ thị mạng xã hội sẽ cung cấp cho chúng ta những thông tin quý giá để hiểu 1
biết sâu sắc hơn và hình dung rõ ràng hơn những cấu trúc của mạng. Trong những năm gần đây, việc phân tích và phát hiện cấu trúc cộng đồng là một trong những lĩnh vực nghiên cứu chính trong khai thác, phân tích dữ liệu đồ thị nói chung và đồ thị mạng xã hội nói riêng. Đặc biệt, trong bối cảnh bùng nổ thông tin, vấn đề này lại càng thu hút các học giả nối tiếng của nhiều lĩnh vực khoa học khác nhau. Nhiều thuật toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội được nhiều người tập trung nghiên cứu và phát triển ứng dụng. Song hầu hết các thuật toán trên đều có độ phức tạp khá lớn do phải tính các độ đo khác nhau ở mỗi bước xử lý. Một cách tiếp cận mới là thuật toán lan truyền nhãn (LPA) [74], có ưu điểm: thời gian tính toán gần tuyến tính và chỉ cần dựa vào một chút thông tin tiên nghiệm ban đầu về cấu trúc mạng. Nhưng nhược điểm chính của phương pháp này là sử dụng hàm heuristic, không tạo ra lời giải duy nhất, kết quả chỉ mang tính gần đúng. LPA phù hợp với loại bài toán có dữ liệu cực kỳ lớn. Nhiều cải tiến đã được thực hiện trên LPA để cải thiện tính ổn định và nâng cao hiệu quả của các thuật toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội. Ngoài ra, trong thời gian gần đây, các nghiên cứu bắt đầu tập trung vào vấn đề cấu trúc cộng đồng chồng chéo, bởi đó tuy là vấn đề phức tạp song lại mang nhiều ý nghĩa thực tiễn: phần nhiều các cấu trúc cộng đồng không rời nhau hoàn toàn mà chúng có thể gối lên nhau, chồng chéo hay giao nhau trong một phạm vi nào đấy, nghĩa là một số nút có thể thuộc nhiều hơn một cộng đồng. Để xác định các cấu trúc cộng đồng chồng chéo, các thuật toán sử dụng nhiều kỹ thuật, bao gồm việc loại bỏ các cạnh có độ trung gian cao [30], phát hiện đồ thị con dày đặc [38], tối ưu hóa modul [16, 76], phương pháp heuristic dựa vào vai trò của các nút [33, 84] và nhất là phương pháp lan truyền nhãn [5, 25, 32, 74, 76, 83, 100] . . . Hầu hết các phương pháp phát hiện cấu trúc cộng đồng chồng chéo không thể cân bằng giữa hiệu quả và độ chính xác cho các mạng lớn và dày đặc. Để nhanh chóng xác định các cấu trúc cộng đồng chồng chéo cho các mạng như vậy, Fu và các cộng sự [25] đề xuất thuật toán PCB (Belief Propagation and Conflict) sử dụng phương pháp lan truyền dựa vào niềm tin và tránh xung 2
đột để xác định các cấu trúc cộng đồng chồng chéo. Độ phức tạp thời gian của thuật toán PCB gần như tuyến tính và độ phức tạp không gian của nó là tuyến tính. Mới đây (2020), Saradha và cộng sự [76] tập trung vào kỹ thuật phát hiện cấu trúc cộng đồng chồng chéo và tối ưu hóa rời rạc bằng cách áp dụng thuật toán lan truyền chồng chéo theo đơn thể để phân chia mạng thành các cộng đồng chồng chéo. Nhìn chung, các phương pháp lan truyền nhãn thực hiện nhanh, hay hiệu quả về cơ bản đều phụ thuộc vào việc xác định cơ chế lan truyền nhãn. Tại Việt Nam, những nghiên cứu về mạng xã hội và phân tích mạng xã hội đã và đang là một xu hướng phát triển mạnh mẽ, hình thành nhiều nhóm nghiên cứu khác nhau. Hồ Trung Thành [3] (Đại học quốc gia thành phố Hồ Chí Minh) nghiên cứu phân tích mạng xã hội dựa theo mô hình chủ đề và ứng dụng (2017), nội dung chủ yếu là phát hiện cấu trúc cộng đồng dựa trên mô hình chủ đề có yếu tố thời gian. Dư Phương Hạnh [2] (Đại học quốc gia Hà Nội) đề xuất phương pháp nâng cao hiệu năng xử lý giao tác trong kho dữ liệu không gian (2018), nội dung chủ yếu là tối ưu hóa truy vấn tương tranh trên đồ thị động và nâng cao hiệu năng quá trình tính độ trung tâm trên độ thị mạng dựa trên giải thuật song song. Nguyễn Xuân Dũng [1] (Học viện Công nghệ BCVT) nghiên cứu rút gọn đồ thị và áp dụng để phát hiện cấu trúc cộng đồng mạng xã hội rời nhau (2021). Nhìn chung, các công trình nghiên cứu trong nước tập trung phân tích mạng xã hội dựa theo mô hình chủ đề, tối ưu hóa truy vấn tương tranh trên đồ thị động, nghiên cứu rút gọn đồ thị và áp dụng để phát hiện cấu trúc cộng đồng mạng xã hội rời nhau. Qua phân tích và đánh giá các thuật toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội, nghiên cứu sinh đã lựa chọn đề tài là nghiên cứu và đề xuất một số kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội. Cụ thể là các phương pháp: phân cụm phổ sử dụng vectơ riêng, phương pháp lan truyền nhãn với các hàm xác định nhãn để phát hiện nhanh các cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội và phương pháp phát hiện nhanh các cấu trúc cộng đồng chồng chéo trên cơ sở sử dụng hệ số phân cụm cải tiến để phát hiện cấu trúc cộng đồng trên đồ thị 3
mạng xã hội có cấu trúc tự do và kích thước lớn. 2. Mục tiêu của luận án Mục tiêu của luận án là nghiên cứu và đề xuất một số kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội. Cụ thể là: • Nghiên cứu phân cụm phổ sử dụng vectơ riêng và ứng dụng để phát triển thuật toán phát hiện nhanh các cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội. • Phát triển thuật toán phát hiện nhanh cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội sử dụng phương pháp lan truyền nhãn với các hàm xác định nhãn lan truyền tối ưu. • Phát triển thuật toán phát hiện nhanh, hiệu quả các cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội theo phương pháp lan truyền nhãn dựa vào hệ số phụ thuộc về cộng đồng được cải tiến từ hệ số phân cụm đồ thị. 3. Đối tượng nghiên cứu của luận án • Các phương pháp phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội. • Các độ đo trong phân tích mạng xã hội và đánh giá chất lượng thuật toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội. • Các thuật toán phát hiện cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội. • Các thuật toán phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội, tập trung vào phương pháp lan truyền nhãn. 4