Tóm tắt 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:29

Thêm vào BST

Báo xấu

17
lượt xem 4
download

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

Tóm tắt 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" được nghiên cứu với mục tiêu 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, 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ị.

Chủ đề:

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

Lưu

Nội dung Text: Tóm tắt 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 ——————–o0o——————– 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 TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH THÁI NGUYÊN- NĂM 2023
Công trình được hoàn thành tại: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên Người hướng dẫn khoa học : 1. PGS.TS. Đoàn Văn Ban 2. TS. Vũ Vinh Quang Phản biện 1: ......................................................................... Phản biện 2: ......................................................................... Phản biện 3: ......................................................................... Luận án được bảo vệ trước Hội đồng chấm luận án cấp Đại học Thái Nguyên họp tại ......................................................................... Vào hồi . . . giờ . . . ngày . . . tháng . . . năm Có thể tìm hiểu luận án tại: - Trung tâm học liệu Đại học Thái Nguyên - Thư viện Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên.
Mục lục 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 4 1.1 Giới thiệu chung . . . . . . . . . . . . . . . . . . . . . . . 4 1.2 Mạng xã hội và đồ thị mạng xã hội . . . . . . . . . . . . . 5 1.2.1 Mạng xã hội . . . . . . . . . . . . . . . . . . . . . 5 1.2.2 Một số đặc tính của mạng xã hội . . . . . . . . . . 5 1.2.3 Đồ thị mạng xã hội và cấu trúc cộng đồng của mạng xã hội . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Một số độ đo quan trọng trên đồ thị mạng xã hội . . . . . 6 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 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 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 . . . . . . . . . . . . . . . . 7 1.6 Tổng kết chương 1 . . . . . . . . . . . . . . . . . . . . . . 8 2 Phát hiện cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội 8 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) . . . . . . . . . . . . . . . . . . . 8 2.1.1 Những vấn đề cơ bản trong phương pháp phân cụm phổ (Spectral Clustering) . . . . . . . . . . . . . . 8 2.1.2 Bài toán và phương pháp phân cụm phổ . . . . . . 9 2.1.3 Thuật toán đề xuất . . . . . . . . . . . . . . . . . 9 2.2 Cải tiến thuật toán lan truyền nhãn LPA . . . . . . . . . 12 2.2.1 Thuật toán lan truyền nhãn LPA . . . . . . . . . . 12 2.2.2 Thuật toán lan truyền nhãn LPAMD với hàm f đề xuất . . . . . . . . . . . . . . . . . . . . . . . . . . 13 i
2.3 Kết hợp rút gọn đồ thị và thuật toán lan truyền nhãn . . 15 2.4 Tổng kết chương 2 . . . . . . . . . . . . . . . . . . . . . . 17 3 Phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội 18 3.1 Khái quát về vấn đề cộng đồng chồng chéo . . . . . . . . 18 3.2 Hệ số phân cụm đồ thị và hệ số thuộc về cộng đồng . . . 18 3.3 Tổng kết chương 3 . . . . . . . . . . . . . . . . . . . . . . 23 Kết luận và hướng phát triển của luận án 23 Danh mục các công trình khoa học có liên quan đến luận án i ii
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 các mối quan hệ hay liên kết. 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. Một cách rất tự nhiên, các đỉnh trong đồ thị mạng xã hội luôn thể hiện tính cấu trúc cộng đồng (gọi tắt là cộng đồng) mạnh mẽ. Đó là, một nhóm những đỉnh có xu hướng tương tác với nhau nhiều hơn những đỉnh bên ngoài nhóm. Phát hiện các nhóm gắn kết trong một đồ thị mạng xã hội (được gọi là phát hiện cấu trúc cộng đồng) là một vấn đề quan trọng và cốt lõi trong khai phá dữ liệu đồ thị. Phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội đã thu hút được nhiều học giả nối tiếng trên thế giới 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ộng đồng trên đồ thị mạng xã hội đã được tập trung nghiên cứu và phát triển ứng dụng. Ngoài ra, thời gian gần đây, các nghiên cứu bắt đầu tập trung vào vấn đề 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. Nhưng dù là nghiên cứu trên cộng đồng chồng chéo hay cộng đồng rời rạc, hầu như các thuật toán đều có độ phức tạp khá lớn, khó cân bằng giữa hiệu quả và độ chính xác, đặc biệt trên các mạng lớn và phức tạp. Tại Việt Nam, những nghiên cứu về mạng xã hội và phát hiện cấu trúc cộng đồng trên đồ thị 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, nhưng 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á chung, nghiên cứu sinh đã lựa chọn đề tài 1
nghiên cứu là khảo sát các vấn đề lý thuyết có liên quan và đề xuất một số kỹ thuật (thuật toán) mới nhằm phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội, bao gồm cả phát hiện cấu trúc cộng đồng rời nhau và cấu trúc cộng đồng chồng chéo. 2. Mục tiêu của luận án • 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 • Các thuật toán phát hiện cấu trúc cộng đồng chồng chéo 4. Phạm vi nghiên cứu • Các phương pháp và kỹ thuật phát hiện cấu trúc cộng đồng rời nhau trong đồ thị mạng xã hội theo phân cụm phổ và hàm phân phối Gauss. 2
• Các phương pháp và kỹ thuật phát hiện cấu trúc cộng đồng rời nhau theo độ đo trung gian, tính modul hóa đặc trưng và lan truyền nhãn. • Các phương pháp phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội theo hệ số phân cụm cải tiến và lan truyền nhãn. 5. Phương pháp nghiên cứu Phương pháp nghiên cứu của luận án là nghiên cứu lý thuyết và nghiên cứu thực nghiệm. 6. Các đóng góp chính của luận án • Đề xuất thuật toán SCN (Spectral Clustering New) xử lý phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội với nền tảng là kỹ thuật Spectrum (phân cụm phổ). • Đề xuất hàm xác định nhãn và lan truyền nhãn trên đồ thị mạng xã hội, xây dựng thuật toán LPAMD (Label Propagation Algorithm with Modularity and Density) phát hiện nhanh cộng đồng rời nhau. • Đề xuất thuật toán LPARLV (LPA Reduce Leaf Vertex) kết hợp giữa thuật toán rút gọn đồ thị mạng xã hội ban đầu về đồ thị rút gọn RLVG (Reduce Leaf Vertex Graph) nhằm giảm kích thước của mạng sau đó sử dụng thuật toán LPAMD với hàm gắn nhãn fT _ max để xác định cấu trúc cộng đồng rời nhau. • Đề xuất thuật toán COPA-BC (Community Overlap Propagation Algorithm Based on New Beloging Coefficient) phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội theo cách kết hợp giữa thuật toán lan truyền nhãn và hệ số thuộc về cộng đồng cải tiến. 7. Bố cục của luận án Luận án được tổ chức thành 3 chương, trong đó: Chương 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 3
Chương 2. Phát hiện cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội Chương 3. Phát hiện cấu trúc cộng đồng chồng chéo trên đồ thị mạng xã hội 8. Ý nghĩa khoa học và thực tiễn Về mặt khoa học: Đã đề xuất một số kỹ thuật (thuật toán) mới phát hiện nhanh cấu trúc cộng đồng trên đồ thị mạng xã hội lớn, phức tạp theo phương pháp tối ưu hoặc xây dựng riêng các hàm heuristic lan truyền nhãn, phương pháp rút gọn đồ thị, đề xuất hệ số thuộc về cộng đồng, ... giải quyết hiệu quả bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội, bao gồm cả cộng đồng rời nhau và cộng đồng chồng chéo. Về mặt thực tiễn: Những kết quả nghiên cứu giúp hình thành cơ sở lý luận, các kỹ năng và kinh nghiệm để triển khai phát hiện cộng đồng trên đồ thị mạng xã hội, phân tích mạng xã hội lớn. Đồng thời, có thể áp dụng trong việc phân tích mạng xã hội tại Việt Nam, hỗ trợ cho nhiều bài toán phân loại xu thế phát triển kinh tế, chính trị, xã hội, . . . Ngoài ra, các kết quả nghiên cứu có thể là tài liệu phục vụ giảng dạy, học tập, nghiên cứu về phân tích, khai phá đồ thị, mạng xã hội và tạo cơ hội trao đổi học hỏi với các nhà nghiên cứu trong nước và trên thế giới. Chương 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 1.1 Giới thiệu chung Đồ thị là công cụ đơn giản và hiệu quả, giúp đặc tả thế giới vô cùng phong phú xung quanh ta. Ta có thể gặp hình thức biểu diễn bằng đồ thị cho hầu hết các sự vật, hiện tượng trong tự nhiên và xã hội. Có thể 4
nói đồ thị là cấu trúc dữ liệu quan trọng và phổ biến nhất, được sử dụng trong vô vàn lĩnh vực nghiên cứu và ứng dụng. Bản thân mỗi đồ thị có thể hàm chứa rất nhiều thông tin giá trị, bởi vậy khai phá dữ liệu hoặc tìm kiếm tri thức từ đó cũng là đòi hỏi đặt ra hết sức hấp dẫn và cấp thiết. Trong khai phá dữ liệu đồ thị, phát hiện cấu trúc cộng đồng mạng xã hội là một nhiệm vụ phổ biến và quan trọng bậc nhất. Vấn đề càng trở nên thách thức khi quy mô của mạng xã hội ngày càng trở nên to lớn và phức tạp. Để giải quyết vấn đề này, 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 đề xuất. 1.2 Mạng xã hội và đồ thị mạng xã hội 1.2.1 Mạng xã hội Mạng xã hội là một cấu trúc xã hội được tạo ra từ các thực thể, các tác nhân hoặc các tổ chức được liên kết, kết nối bởi một hoặc nhiều quan hệ với nhau. Các mối quan hệ giữa các thực thể có thể mang nhiều nội dung khác nhau từ sự tương trợ, trao đổi thông tin cho đến việc trao đổi hàng hóa, dịch vụ, . . . Mạng xã hội cung cấp nhiều cách khác nhau để các tổ chức thu thập thông tin, dự báo, phân tích tình hình, hoạch định chính sách, . . . 1.2.2 Một số đặc tính của mạng xã hội • Dựa vào người dùng (User-based). • Tính tương tác (Interactive). • Hướng đến cộng đồng (Community-driven). • Các mối quan hệ (Relationships). • Cảm xúc về nội dung (Emotion over content). 1.2.3 Đồ thị mạng xã hội và cấu trúc cộng đồng của mạng xã hội Luận án trình bày những vấn đề lý thuyết cơ bản về đồ thị, thống nhất hệ thống ký hiệu và các cách biểu diễn thông thường cho một mạng 5
xã hội, để chuẩn bị cho các nghiên cứu 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 đó. Mạng xã hội thường được biểu diễn dưới dạng đồ thị liên thông, trong đó các tác nhân (cá nhân hoặc một tổ chức) được biểu diễn bằng các nút (đỉnh) và các kết nối giữa các tác nhân được thể hiện bằng liên kết hoặc các cạnh (cung). Theo lý thuyết đồ thị, cho mạng xã hội G = (V, E), cấu trúc cộng đồng (community structure) là một đồ thị con của G, có tập đỉnh C là tập con các đỉnh của V, sao cho với mỗi đỉnh v ∈ C, có nhiều cạnh kết nối v với những đỉnh khác trong C (liên thông mạnh) và ít cạnh kết nối v với những đỉnh w khác thuộc V-C (liên thông yếu). Phát hiện cấu trúc cộng đồng trên mạng xã hội có thể giúp ta khái quát ra những nét đặc trưng cho các tác nhân của cộng đồng đó. Phát hiện cấu trúc cộng đồng trên mạng xã hội là một lĩnh vực quan trọng trong khai phá dữ liệu đồ thị. Thường người ta chia làm hai loại cộng đồng: các cộng đồng rời nhau và các cộng đồng chồng chéo. Những cộng đồng rời nhau khi mỗi tác nhân chỉ thuộc về một cộng đồng, còn những cộng đồng chồng chéo nhau khi có một tác nhân thuộc về nhiều hơn một cộng đồng. 1.3 Một số độ đo quan trọng trên đồ thị mạng xã hội Các độ đo quan trọng trên đồ thị mạng xã hội được sử dụng trong luận án là: Độ đo trung tâm theo bậc, độ đo trung gian, độ đo trung tâm theo vector đặc trưng, hệ số phân cụm đồ thị. 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 Mục tiêu của bài toán là từ các mạng xã hội cho trước (được biểu diễn bởi các đồ thị mạng xã hội), phát hiện được các cấu trúc cộng đồng nằm trong đó và tìm hiểu về mối liên hệ bên trong các cộng đồng cũng như giữa các cộng đồng với nhau, mối liên hệ đó có ảnh hưởng thế nào đến cấu trúc của toàn mạng xã hội. 6
Đầu vào: Đồ thị mạng xã hội G = (V, E) gồm tập đỉnh V = {v1 , v2 , . . . , vn } và tập cạnh E = {(u, v)| u, v ∈ V }. Đầu ra: Tập C các cộng đồng. 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 nghiên cứu và công bố, mang đến nhiều ý nghĩa khoa học và được áp dụng hiệu quả trong thực tế. Về cơ bản, các thuật toán này được chia thành 5 nhóm thuật toán chính: - Nhóm thuật toán phát hiện cấu trúc cộng đồng truyền thống. - Nhóm thuật toán dựa trên tối ưu hóa độ đo đơn thể. - Nhóm thuật toán dựa vào độ đo trung gian. - Nhóm thuật toán dựa trên kỹ thuật lan truyền nhãn. - Nhóm thuật toán dựa trên kỹ thuật học sâu. 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 Độ đo được dùng để đo sự tương đồng hay giống nhau giữa kết quả phát hiện cộng đồng của các thuật toán so với các cộng đồng có trong thực tế, và được dùng để đánh giá hiệu quả, chất lượng của thuật toán phát hiện cộng đồng. Luận án trình bày hai độ đo thông dụng được sử dụng để đánh giá tính hiệu quả của các thuật toán phát hiện cộng đồng trên đồ thị mạng xã hội đề xuất trong chương 2 và 3 của luận án. Đó là: - Độ đo đơn thể Modularity 1 ki kj Q= (aij − )δ(Ci , Cj ) (1.11) 2m 2m i,j Trong đó A là ma trận kề, hàm δ(Ci , Cj ) = 1 nếu i, j thuộc cùng cộng đồng và δ(Ci , Cj ) = 0 nếu ngược lại. ki , kj là bậc của nút i và nút j, m là số cạnh của đồ thị. - Độ đo thông tin tương hỗ chuẩn NMI 7
CA CB Nij × n −2 Nij log i=1 j=1 Ni Nj N M I(A, B) = CA CB (1.14) Ni Nj Ni log + Nj log i=1 n j=1 n Trong đó: n là số đỉnh của đồ thị mạng xã hội đang xét; CA , CB tương ứng là số cộng đồng thực (ground-truth) và số cộng đồng được phát hiện bởi thuật toán phát hiện cộng đồng trong mạng, Ni và Nj đại diện cho tổng số phần tử trên hàng i và cột j tương ứng của ma trận sai số N . Giá trị của NMI nằm trong khoảng từ 0 đến 1. Chỉ số NMI bằng 1 nếu cộng đồng tìm kiếm trùng với cộng đồng thực, ngược lại NMI bằng 0. 1.6 Tổng kết chương 1 Chương này giới thiệu tổng quan những vấn đề lý thuyết về dữ liệu đồ thị, về mạng xã hội, đồ thị mạng xã hội và các vấn đề liên quan, trong đó tập trung vào bài toán phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội. Luận án đã giới thiệu năm nhóm thuật toán chính phát hiện các cấu trúc cộng đồng trên đồ thị mạng xã hội và nêu một số tiêu chuẩn đánh giá chất lượng phát hiện cộng đồng được sử dụng trong thực nghiệm đánh giá hiệu quả các thuật toán đề xuất trong chương 2 và chương 3. Chương 2 Phát hiện cấu trúc cộng đồng rời nhau trên đồ thị mạng xã hội 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) 2.1.1 Những vấn đề cơ bản trong phương pháp phân cụm phổ (Spectral Clustering) Sử dụng một số công cụ quan trọng từ lý thuyết ma trận (phương pháp quang phổ của ma trận) để hình thành bài toán phân hoạch một 8
đồ thị nhằm giảm thiểu số lượng các cạnh kết nối các thành phần khác nhau. Việc phân hoạch đồ thị được xem như thực hiện một (hoặc một số) “vết cắt” ngang qua đồ thị, nhằm phân chia đồ thị thành các vùng đáp ứng yêu cầu đề ra. Số lượng các cạnh bị cắt ngang (loại bỏ) được coi là kích thước cắt. Việc giảm thiểu kích thước “cắt” cũng là mục tiêu được nghiên cứu kỹ trước khi tiến hành. - Phân vùng tốt - Cắt chuẩn hóa - Ma trận Laplace và khái niệm phổ Ma trận Laplace là một dạng tương tự rời rạc của toán tử Laplace trong phép tính đa biến và phục vụ một mục đích tương tự bằng cách đo lường mức độ khác nhau của đồ thị tại một đỉnh so với các giá trị của nó tại các đỉnh lân cận. Ma trận Laplace L có thể được xác định: L = D − A 1 1 hoặc L = I − D− 2 AD− 2 , trong đó A là ma trận kề, D là ma trận bậc của đồ thị; D = Diag (D1 , D2 , . . . , Dn ); Di là bậc của đỉnh i = 1 . . . n. Phổ là một tập các giá trị riêng của ma trận Laplace L: λ1 . . . λt Spec(L) = trong đó λ1 . . . λt là các giá trị khác nhau của m1 . . . mt giá trị riêng và m1 . . . mt là các hệ số điều chỉnh. 2.1.2 Bài toán và phương pháp phân cụm phổ Phân cụm phổ bao gồm tất cả các kỹ thuật sử dụng ma trận Laplace, tính véc tơ riêng để phân chia dữ liệu dựa trên sự tương đồng về cặp giữa chúng. Có các phương pháp: phân cụm theo phổ không chuẩn hoá và phân cụm theo phổ chuẩn. -Thuật toán 2.1 phân cụm phổ của UlrikeVon Luxburg -Một số thuật toán khác 2.1.3 Thuật toán đề xuất - Giảm số chiều của không gian dữ liệu - Khoảng cách phân biệt giữa các đối tượng - Rút gọn đồ thị: Thuật toán 2.2 WTG: xác định số láng giềng chung 9
Thuật toán 2.3 RE: loại bỏ cạnh có trọng số nhỏ hơn ngưỡng Thuật toán 2.4 MCG: thu gọn đồ thị Thuật toán 2.5 RCL: hoàn thiện phân cụm Thuật toán 2.6 DE: tính giá trị riêng và vector riêng Thuật toán 2.7: SCN (Spectral Clustering New) Input: Tập dữ liệu P ∈ RN ×F , N : số điểm dữ liệu, F số chiều không gian, k số cộng đồng, sai số ε Output: Các cộng đồng Z1 , Z2 , . . . , Zk với Zj = {Pi |Pi ∈ Cj , i = 1..N, j = 1..k} 1. for Pi ∈ P (i ∈ 1 . . . N ) if Pi có kết nối với Pj then ∥Pi − Pj ∥ A(i, j) = exp(− ); i, j ∈ 1..N 2 2. AW T G ← W T G(A); 3. A, S1 , S2 ← M CG(A); 4. for Pi ∈ P (i ∈ 1..n) deg(vi ) = deg(Pi ) 5. for i, j = 1..n (Dij ) = diag(v1 , v2 , . . . , vn ) // Tính Ma trận bậc 6. for i, j = 1..n (Lij ) = (Dij ) − (Aij ) // Tính Ma trận Laplace 7. λ, u ← DE(L, ε) 8. {u1 ,u2 , . . . , uk } ← {u1 ,u2 , . . . , un } 9. w = (w1 , w2 , . . . , wn ) ← {u1 , u2 , . . . , uk } // chọn w từ tập các vecto riêng u1 , u2 , . . . , uk 10
w 2 2 10. y ← // chuẩn hóa w được y, ∥w∥ = w1 + w2 + · · · +w2 n ∥w∥ 11. Cj = k_means(y) , j = 1..k 12. Zj = {yi |yi ∈ Cj }; // Zj = {Pi |Pi ∈ Cj , i = 1..n, j = 1..k} ′ 13. Zj ← RCL(Zj , S1 , S2 ); 14. return Zj , Q; - Thực nghiệm: Để đánh giá hiệu quả của các thuật toán đề xuất, nghiên cứu sinh thực hiện tiến hành thực nghiệm trên cùng các bộ dữ liệu đã được công bố công khai tại "Network repository. [Online]. Available: https://networkrepository.com." và " Leskovec J, and Krevl.A - SNAP Datasets tanford large network dataset collection; 2014. [Online]. Avail- able: https://snap.stanford.edu. [Accessed Oct. 19, 2021]". Môi trường thực nghiệm với cấu hình máy: Intel(R) Core i7, CPU @ 2.50 GHz, RAM 8.0 GB, Win 10, 64 bit. Hệ điều hành Windows 10. Công cụ lập trình thực hiện thuật toán là ngôn ngữ lập trình Matlab 2019, Python. Các thuật toán thực nghiệm được luận án thực hiện riêng lẻ với từng bộ dữ liệu và trên máy tính chỉ thực hiện duy nhất một chương trình. Các kết quả: So sánh SCN với SpcSA và UVonLB. Hình 2.4 So sánh thời gian thực hiện (giây) 11
Hình 2.5 So sánh chất lượng cộng đồng (Modularity) Hình 2.6 So sánh về thông tin tương hỗ chuẩn (NMI) Từ kết quả thực nghiệm trên các bộ dữ liệu thực với kích thước lớn cho thấy rằng SCN đã thực hiện xác định các cộng đồng là khá tốt, thời gian thực hiện của thuật toán đề xuất là nhanh hơn 1.9% so với SpcSA và 7.5% so với UVonLB. Chất lượng các cộng đồng thu được cũng cao hơn 6% , thông tin tương hỗ chuẩn hóa (NMI) gần bằng 1 và tăng hơn7% so với UVonLB. Điều này khẳng định tính hiệu quả của thuật toán đề xuất. 2.2 Cải tiến thuật toán lan truyền nhãn LPA 2.2.1 Thuật toán lan truyền nhãn LPA Một trong những thuật toán hiệu quả để phát hiện cấu trúc cộng đồng rời nhau là thuật toán LPA (Label Propagation Algorithm) được đề xuất bởi Raghavan và các cộng sự. Thuật toán 2.8: lan truyền nhãn LPA 12
2.2.2 Thuật toán lan truyền nhãn LPAMD với hàm f đề xuất f T _max = fx (t + 1) = maxt+1 dQy |y ∈ N(x) (2.1) với KxC1 − KxC0 mxC1 − mxC0 dQy = − Kx 2m 2m Trong đó: + {C0 } là cộng đồng mà nút x đang thuộc về, + {C1 } là cộng đồng mà nút láng giềng y của x đang thuộc về + KxC0 : Bậc của nút x trong {C0 } + KxC1 : Bậc của nút láng giềng y trong {C1 } + mxC0 : Tổng số cạnh của {C0 } + mxC1 : Tổng số cạnh của {C1 } + Kx là tổng số cạnh láng giềng của nút x + N (x): Tập các nút láng giềng của nút x - Thuật toán 2.9 LPAMD (Label Propagation Algorithm with Modu- larity and Density) Input: G = (V, E), biểu diễn bởi ma trận kề A Ouput: Tập các cộng đồng C của G, NC: Số cộng đồng được phát hiện. Begin 1. for each x ∈ V 2. Cx (0) = x; 3. do { 4. t = 1; 5. X = {Random(x ∈ V )}; 13
6. for each x ∈ V 7. f x (t + 1) = Cx (t + 1) = max dQy |y ∈ N(x) KxC1 − KxC0 mxC1 − mxC0 8. with dQy = − Ki 2m 2m 9. if Cx (t) = Cv (t), x ∈ V, v ∈ N(x) then stop 10. else t = t + 1; } 11. while (t is the last executed step: stop); 12. C = {x ∈ V|fx }; 13. NC = |fx |; 14. return C, NC ; 15. End. - Các kết quả thực nghiệm (So sánh LPAMD với LPA gốc, CLPA và NLPPC) Hình 2.17 So sánh thời gian thực hiện (giây) Thuật toán cải tiến được thực hiện với bộ dữ liệu thực. LPAMD giảm hơn 3.72% so với LPA về thời gian thực hiện. Chất lượng cộng đồng và độ đo thông tin tương hỗ NMI: Modularity của LPAMD tăng hơn 11%; NMI tăng hơn 7% so với LPA. Có thể thấy rõ chất lượng của cộng đồng được đảm bảo do hàm fx được xây dựng dựa trên ưu điểm của tiêu chí Modularity. 14
Hình 2.18 So sánh chất lượng cộng đồng (Modularity) Hình 2.19 So sánh về thông tin tương hỗ chuẩn (NMI) 2.3 Kết hợp rút gọn đồ thị và thuật toán lan truyền nhãn - Đỉnh treo và lớp đỉnh treo tương đương - Thuật toán 2.10 RLVG (Reduce Leaf Vertex In Graph): Rút gọn các đỉnh treo trên đồ thị) - Thuật toán 2.11. LPARLV Input: G = (V, E), biểu diễn bởi ma trận kề A Ouput: Tập các cộng đồng C của G, NC : Số cộng đồng được phát hiện. Begin 1. G1 = RLVG(G)// Thủ tục rút gọn các đỉnh treo 2. for each x ∈ V 3. Cx (0) = x; 4. do 15
5. t = 1; 6. X = {Random(x ∈ V )} ; 7. for each x ∈ V 8. f x (t + 1) = Cx (t + 1) = max dQy |y ∈ N(x) KxC1 − KxC0 mxC1 − mxC0 with dQy = − Ki 2m 2m 9. if Cx (t) = Cv (t), x ∈ V, v ∈ N(x) 10. Stop 11. else 12. t = t + 1; 13. while t is the last executed step; 14. C = {x ∈ V |fx }; 15. NC = |fx |; 16. return C, NC ; End. - Độ phức tạp thuật toán LPARLV: max{O(n), O(k1 n1 , O(k2 n1 )}, với n là số đỉnh của đồ thị mạng ban đầu G, n1 là số đỉnh của G1 (n1 < n), k1 là số láng giềng lớn nhất của đỉnh trong G1 và k2 là số lần lặp lan truyền nhãn (ki ≥ 1, i = 1, 2). - Kết quả đánh giá thực nghiệm (So sánh LPARLV với OLP và LPA gốc) Về thời gian thực hiện trung bình của LPARLV giảm 4.9% so với OLP và giảm 11.9% so với LPA. Như vậy tốc độ thực hiện của LPARLV là khá tốt, hơn hẳn các thuật toán được đánh giá trên các bộ dữ liệu thực nghiệm.Về chất lượng của cộng đồng phát hiện được khi dùng thuật toán LPARLV được cải thiện đáng kể, đã có sự kết nối chặt chẽ hơn trong mỗi cộng đồng kết quả. Cộng đồng được phát hiện bởi thuật toán LPARLV có khả năng trùng với cộng đồng thực cao hơn các thuật toán còn lại. 16