Luận án: Kỹ thuật phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội - Nguyễn Hiền Trinh

ĐẠ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 Ngành: Khoa học máy tính Mã số: 9. 01 LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: 1. 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ả luận án 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! Tác giả luận án 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 .2 Mạng xã hội và đồ thị mạng xã hội .2 Một số đặc tính của mạng xã hội .3 Đồ thị mạng xã hội và cấu trúc cộng đồng của mạng xã hội .3 Một số độ đo quan trọng trên đồ thị mạng xã hội .1 Độ đo trung tâm theo bậc .3 Độ đo trung tâm theo vector riêng .4 Hệ số phân cụm của đỉnh trên đồ thị .4 Bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội .1 Nhóm thuật toán phát hiện cấu trúc cộng đồng truyền thống .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ể .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 .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 .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 .6 Đánh giá chung về bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội và lựa chọn hướng nghiên cứu .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 .2 Thông tin tương hỗ chuẩn NMI .6 Tổng kết chương 1. 44 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) .1 Những vấn đề cơ bản trong phương pháp phân cụm phổ (Spectral Clustering) .2 Bài toán và phương pháp phân cụm phổ .3 Thuật toán đề xuất .4 Các kết quả thực nghiệm .2 Cải tiến thuật toán lan truyền nhãn LPA .1 Thuật toán lan truyền nhãn LPA .2 Thuật toán lan truyền nhãn LPAMD với hàm f đề xuất .3 Kết quả thực nghiệm thuật toán LPAMD .3 Kết hợp rút gọn đồ thị và thuật toán lan truyền nhãn .1 Thuật toán LPARLV (LPA Reduce Leaf Vertex) .3 Kết quả thực nghiệm .4 Tổng kết chương 2. 97 3 Phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội 98 3.1 Khái quát về vấn đề cộng đồng chồng chéo .2 Hệ số phân cụm của đỉnh trên đồ thị và hệ số thuộc về cộng đồng .1 Hệ số phân cụm của đỉnh trên đồ thị .2 Hệ số thuộc về cộng đồng .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 .4 Độ phức tạp thuật toán COPA-BC .5 Kết quả thực nghiệm .3 Tổng kết chương 3. 122 Kết luận và hướng phát triển của luận án 123 Danh mục các công trình khoa học có liên quan đến luận án126 Tài liệu tham khảo 128 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 CLPA Controlled Label Propagation Algorithm 5 CNN Convolution Neural Network 6 CONGA Cluster Overlap Newman-Girvan Algorithm 7 CONGO CONGA Optimized 8 COPRA Community Overlap Propagation Algorithm Community Overlap Propagation Algorithm 9 COPA-BC Based on New Belonging Coefficient 10 DBLP Digital Bibliographic Library Project 11 DFS Depth-first search 12 DSF Deep Sparse Filtering 13 GAN Generative Adversarial Network 14 GCN Graph Convolutional Networks 15 GN Girvan-Newman 16 GNN Graph neural networks 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 đủ IVIC- Improved Vertex Imitation Co-efficient based 17 COPRA COPRA 18 LPA Label propagation algorithm Label Propagation Algorithm with 19 LPAMD Modularity and Density 20 LPARLV LPA Reduce Leaf Vertex 21 MCG Make Compact Graph 22 MLE Maximum-likelihood estimation New Label Propagation algorithm with 23 NLPPC Pairwise Constraints 24 NMI Normalized mutual information 25 NMF Deep Nonnegative Ma-trix Factorization 26 OLP Optimized label propagation 27 PCB Belief Propagation and Conflict 28 RCL ReClustering 29 RE Remove edge 30 SC Stanford large network dataset collection 31 SCN Spectral Clustering New 32 SN Social network 33 SNAP Stanford Network Analysis Platform Spectral clustering combining information on 34 SpcSA both the network Structure and node Attributes 35 UVonLB Ulrike Von Luxburg Algorithm 36 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 Hệ số phân cụm của đỉnh trên 11 Clustering Coefficient đồ thị 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 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 19 Diameter Đường kính 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 lấp 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 .2 Tính độ đo trung gian cho các đỉnh của đồ thị hình 1.1 Kết quả phân cụm .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ừ [60] .3 Kết quả thực nghiệm về chất lượng cộng đồng (Modular- ity)với SCN, SpcSA và UVonLB .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 .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 [60], Musae - wiki [46] .7 Kết quả thực nghiệm về chất lượng cộng đồng (Modular- ity)với LPAMD .8 Kết quả thực nghiệm về độ đo thông tin tương hỗ chuẩn (NMI) với LPAMD .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 [60] .10 Kết quả thực nghiệm về chất lượng cộng đồng với LPARLV 95 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 .1 Quá trình gắn nhãn ở các bước t = 1, 2, 3, 4 .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 [60]; Email-Eu- core, DBLP, Amazon, Youtube [46] .3 Kết quả thực nghiệm về chất lượng cộng đồng qua chỉ số Modularity với COPA-BC .4 Kết quả thực nghiệm về thông tin tương hỗ chuẩn hóa NMI với COPA-BC. 120 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, .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ổ .3 Đồ thị vô hướng 7 nút và độ đo trung tâm theo bậc .4 Đồ thị vô hướng 6 nút .1 Minh họa đồ thị phân thành 2 cụm .