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

Nội dung tài liệu: 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

1. ĐẠ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
2. 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.
3. 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
4. 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
5. 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
6. 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
7. • 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
8. 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
9. 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
10. 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 2 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
11. Đầu vào: Đồ thị m¤ng x¢ hëi G = (V; E) gồm tªp đỉnh V = fv1; v2; : : : ; vng và tªp c¤nh E = f(u; v)j u; v 2 V g. Đầ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 X kikj Q = (a − )δ(C ;C ) (1.11) 2m ij 2m i j 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
12. C C PA PB Nij × n −2 Nij log i=1 j=1 NiNj NMI(A; B) = (1.14) C C PA Ni PB 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
13. đồ 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
14. 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 2 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 = fPi jPi 2 Cj ; i = 1::N; j = 1::kg 1. for Pi 2 P (i 2 1 :::N) if Pi có k¸t nèi với Pj then kP − P k A(i; j) = exp(− i j ); i; j 2 1::N 2 2. AWTG WTG(A); 3. A; S1;S2 MCG(A); 4. for Pi 2 P (i 2 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. fu1;u2;:::; ukg fu1;u2;:::; ung 9. w = (w1; w2;:::; wn) fu1; u2; : : : ; ukg // chọn w tø tªp c¡c vecto ri¶ng u1; u2; : : : ; uk 10
15. w 10. y // chu©n hóa w được y, kwk = pw2 + w2+ ··· +w2 kwk 1 2 n 11. Cj = k_means(y) , j = 1::k 12. Zj = fyi jyi 2 Cj g; // Zj = fPi jPi 2 Cj ; i = 1::n; j = 1::kg 0 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: " và " Leskovec J, and Krevl.A - SNAP Datasets tanford large network dataset collection; 2014. [Online]. Avail- able: [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
16. 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
17. 2.2.2 Thuªt to¡n lan truy·n nh¢n LPAMD với hàm f đề xu§t  fT _max = fx(t + 1) = maxt+1 dQy jy 2 N(x) (2.1) với K K m m dQ = xC1− xC0 − K xC1− xC0 y 2m x 2m Trong đó: + fC0g là cëng đồng mà nút x đang thuëc v·, + fC1g 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 fC0g + KxC1 : Bªc cõa nút l¡ng gi·ng y trong fC1g + mxC0 : Têng sè c¤nh cõa fC0g + mxC1 : Têng sè c¤nh cõa fC1g + 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 2 V 2. Cx(0) = x; 3. do { 4. t = 1; 5. X = fRandom(x 2 V )g; 13
18. 6. for each x 2 V  7. fx(t + 1) = Cx(t + 1) = max dQy jy 2 N(x) K K m m 8. with dQ = xC1− xC0 − K xC1− xC0 y 2m i 2m 9. if Cx(t) = Cv(t); x 2 V; v 2 N(x) then stop 10. else t = t + 1; } 11. while (t is the last executed step: stop); 12. C = fx 2 Vjfxg; 13. NC = jfxj; 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
19. 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 2 V 3. Cx(0) = x; 4. do 15
20. 5. t = 1; 6. X = fRandom(x 2 V )g ; 7. for each x 2 V  8. f x(t + 1) = Cx(t + 1) = max dQy jy 2 N(x) K K m m with dQ = xC1− xC0 − K xC1− xC0 y 2m i 2m 9. if Cx(t) = Cv(t); x 2 V; v 2 N(x) 10. Stop 11. else 12. t = t + 1; 13. while t is the last executed step; 14. C = fx 2 V jfxg; 15. NC = jfxj; 16. return C; NC ; End. - Độ phùc t¤p thuªt to¡n LPARLV: maxfO(n);O(k1n1;O(k2n1)g, 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
21. H¼nh 2.21 So s¡nh thời gian thực hi»n (gi¥y) H¼nh 2.22 So s¡nh ch§t lượng cëng đồng (Modularity) H¼nh 2.23 So s¡nh v· thông tin tương hé chu©n (NMI) 2.4 Têng k¸t chương 2 Chương này tr¼nh bày mët sè c£i ti¸n và đề xu§t mới. Thuªt to¡n SCN nh¬m gi£m sè chi·u cõa không gian dú li»u gèc giúp gi£m khèi 17
22. lượng t½nh to¡n khi xû lý ph¡t hi»n c§u trúc cëng đồng rời nhau. Thuªt to¡n LPAMD ph¡t hi»n nhanh c§u trúc cëng đồng với kỹ thuªt lan truy·n nh¢n dựa vào t½nh ch§t cơ b£n tr¶n đồ thị v· c¡c nút l¥n cªn k· và đề xu§t hàm x¡c định nh¢n tr¶n đồ thị m¤ng x¢ hëi k¸t hñp với t½nh đơn thº hóa. Thuªt to¡n LPARLV k¸t hñp rút gọn c¡c đỉnh treo cõa m¤ng ban đầu với kỹ thuªt lan truy·n nh¢n dựa vào đơn thº hóa. C¡c k¸t qu£ thực nghi»m kh¯ng định ưu điểm cõa c¡c thuªt to¡n đề xu§t. 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 3.1 Kh¡i qu¡t v· v§n đề cëng đồng chồng ch²o C¡c nghi¶n cùu ban đầu v· ph¡t hi»n cëng đồng chõ y¸u tªp trung vào c§u trúc cëng đồng không chồng ch²o. Tuy nhi¶n, vi»c ph¡t hi»n c¡c c§u trúc cëng đồng chồng ch²o trong c¡c m¤ng phùc t¤p càng ngày càng có ý nghĩa thi¸t thực. Nhi·u thuªt to¡n đã được đưa ra, song không thº dung háa giúa hi»u qu£ và độ ch½nh x¡c cho c¡c m¤ng lớn và dày đặc.Với mong muèn kh­c phục nhúng h¤n ch¸ tr¶n, luªn ¡n tªp trung nghi¶n cùu c£i ti¸n h» sè ph¥n cụm đồ thị và ùng dụng nó để ph¡t triºn thuªt to¡n ph¡t hi»n c§u trúc cëng đồng chồng ch²o nhanh dựa tr¶n kỹ thuªt lan truy·n nh¢n cùng với h» sè ph¥n cụm đồ thị c£i ti¸n thành h» sè thuëc v· cëng đồng (belonging coefficient). 3.2 H» sè ph¥n cụm đồ thị và h» sè thuëc v· cëng đồng Với đồ thị m¤ng G = (V; E) biºu di¹n bởi ma trªn k· A, h» sè ph¥n cụm cõa nút vi được x¡c định: Sè tam gi¡c li¶n k¸t với vi Ci = (3.1) Sè bë ba nút li¶n k¸t với vi 18
23. 8Sè tam gi¡c li¶n k¸t với v > i ; n¸u d > 1 :0 n¸u di ≤ 1 8 n > P a × a × a > ij jk ki > j;k=1 1 Ci = (di − 1) (3.3) > di × > 2 > :0 n¸u di ≤ 1 n P Trong đó di = aij, i = 1 : : : n j=1 - Thuªt to¡n 3.1: ACCA Input: Ma trªn k· A cõa m¤ng G = (V; E), x 2 V; k Output: Cx // Thuªt to¡n này t½nh h» sè ph¥n cụm cõa nút x - H» sè thuëc v· cëng đồng 8 0 Bi = (3.4) :1; n¸u Ci = 0 i = 1 : : : n; Tham sè đầu vào v cho thuªt to¡n đề xu§t:  1  1 ≤ v ≤ Maxi2V f g (3.5) Bi Thuªt to¡n 3.2: COPA-BC Input: Đồ thị G = (V; E) và h» sè v thỏa m¢n đi·u ki»n (3.5) Output: C¡c cëng đồng chồng ch²o. 1. CO = fg; 2. t = 1; 3. for each x 2 V do { 4. Bx = ACCA(x; k); 19
24. 1 5. if (B > ) then L (x) = f(x; 1)g; x v t 6. else Lt(x) = f(x; Bx)g; 7.} 1 8. w = Maxx2V [ ]; Bx 9. if (v > w) then v = w; 10. t = t + 1; 11. do { 12. for each x 2 V do { 13. N(x) = fy 2 V j(x; y) 2 Eg; 14. Propagate(N(x);Lt−1;Lt); } 15. } while(Lt−1 6= Lt); 16. SplitCommunities(Lt); 17. return CO; Thuªt to¡n 3.3: Propagate(N(x);Lt−1;Lt) 1. for each y 2 N(x) do { 2. if (Lt−1(y) == f(s; 1)g&&Bx == 1) then { 3. Lt(x) = Lt−1(s); 4. return; } 5. if (Bx ≤ 1=v&&(w; 1) 2 Lt−1(y)&&(w; 1) 2= Lt−1(x)&&jLtj < v) then { 6. Lt(x) = Lt−1(x) [ f(w; 1)g; 20
25. 7. return; //stop : k¸t thúc Propagate() 8.}} Thuªt to¡n 3.4: SplitCommunities(Lt){ 1 1. for each x 2 V do if (L (x) == (x; B )&&B ≤ ) then delete(L (x)); t x x v t 2. for each x 2 V do { COx = fg; // Tªp réng if (Lt(x) == f(x; Bx)g&&Bx == 1) then { COx = COx [ fxg; CO = CO [ COx;}} 3. for each y 2 V − fxg do 4. if (L(y) == L(x)&&(y; Bx) == (x; Bx)) then {COx = COx [ fyg; V = V − fxg; CO = CO [ COx;} else {COy = COy [ fyg; V = V − fyg; CO = CO [ COy;} - Độ phùc t¤p thuªt to¡n COPA-BC: O(n:v) với n là sè nút và v là tham sè cõa đồ thị (sè cëng đồng tèi đa méi nút có thº có) - K¸t qu£ thực nghi»m (So s¡nh COPA-BC với COPRA và IVICCO- PRA) K¸t qu£ thực nghi»m cho th§y COPA-BC tèt hơn c¡c thuªt to¡n kh¡c (COPRA, IVICCOPRA) v¼ thời gian lặp l¤i đã được gi£m xuèng nhờ có tham sè v như đã ph¥n t½ch. Ch§t lượng cëng đồng cũng được c£i thi»n do vi»c kh£o s¡t và quy¸t định lựa chọn cëng đồng theo Q (Modularity) được thực hi»n ngay trong méi bước lặp. Gi¡ trị thông tin tương hé chu©n 21
26. H¼nh 3.4 So s¡nh thời gian thực hi»n (gi¥y) H¼nh 3.5 So s¡nh ch§t lượng cëng đồng (Modularity) H¼nh 3.6 So s¡nh v· thông tin tương hé chu©n (NMI) hóa NMI g¦n b¬ng 1 và lớn hơn so với thuªt to¡n phê bi¸n g¦n đây. So với c¡c thuªt to¡n ph¡t hi»n c§u trúc cëng đồng chồng ch²o kh¡c, lñi th¸ cõa COPA-BC là tèc độ thực hi»n và độ ch½nh x¡c. 22
27. 3.3 Têng k¸t chương 3 Chương này tr¼nh bày v· v§n đề c§u trúc cëng đồng chồng ch²o, 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, phương ph¡p xû lý cëng đồng chồng ch²o dựa tr¶n thuëc t½nh cõa c¡c nút tr¶n đồ thị m¤ng x¢ hëi. Tø gi¡ trị cõa c¡c thuëc t½nh này, có thº d¹ dàng ph¥n chia cëng đồng. Ti¸p theo là ph¡t triºn thuªt to¡n ph¡t hi»n c§u trúc cëng đồng chồng ch²o COPRA-BC tr¶n cơ sở thuªt to¡n COPRA và ph¡t triºn h» sè thuëc v· cëng đồng tø h» sè ph¥n cụm đồ thị. K¸t luªn và hướng ph¡t triºn cõa luªn ¡n M¤ng x¢ hëi là mët c§u trúc x¢ hëi được t¤o ra tø r§t nhi·u thực thº, t¡c nh¥n hay c¡c tê chùc li¶n k¸t với nhau theo mët hay nhi·u mèi quan h», chúng thường được biºu di¹n bởi đồ thị m¤ng x¢ hëi và luôn có xu hướng h¼nh thành n¶n c§u trúc cëng đồng. Vi»c ph¡t hi»n c§u trúc cëng đồng (cëng đồng) tr¶n đồ thị m¤ng x¢ hëi là mët lĩnh vực mang nhi·u ý nghĩa quan trọng c£ trong lý thuy¸t l¨n thực ti¹n. Kh¡m ph¡ c¡c cëng đồng không nhúng hé trñ tèt qu¡ tr¼nh mô t£ và ph¥n t½ch c¡c mèi quan h» giúa c¡c t¡c nh¥n trong m¤ng, mà cán giúp t¼m ra c¡c qui luªt h¼nh thành và kh£ n«ng bi¸n đổi cõa nhúng mèi quan h» đó, qua đó làm nêi bªt nhúng £nh hưởng tương quan cõa c¡c mèi quan h» trong đồ thị đối với hành vi cõa c¡c t¡c nh¥n tham gia Luªn ¡n nghi¶n cùu, c£i ti¸n 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, bao gồm c£ c§u trúc cëng đồng rời nhau và c§u trúc cëng đồng chồng ch²o. C¡c k¸t qu£ ch½nh cõa luªn ¡n: 1. Đề xu§t thuªt to¡n SCN 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 ph¥n cụm phê, gi£m sè chi·u cõa dú li»u (đa chi·u) xuèng ch¿ cán ở d¤ng v²c tơ (chuéi sè thực), phèi hñp với ý tưởng tèi ưu hóa hàm Min-cut nhờ sû dụng ma trªn Laplace, hi»u qu£ cho qu¡ tr¼nh xû lý ph¡t hi»n c§u trúc cëng đồng tr¶n đồ thị m¤ng x¢ hëi. 23
28. 2. Đề xu§t hàm fT _ max x¡c định nh¢n và lan truy·n nh¢n tr¶n đồ thị m¤ng x¢ hëi. C£i ti¸n thuªt to¡n lan truy·n nh¢n têng qu¡t, x¥y dựng thuªt to¡n LPAMD dựa tr¶n sự k¸t hñp ưu điểm giúa ch§t lượng cõa cëng đồng theo ti¶u ch½ Modularity cõa Newman và đo t½nh n«ng c§u trúc cõa cëng đồng thông qua mªt độ cëng đồng. 3. Đề xu§t thuªt to¡n LPARLV k¸t hñp giúa thuªt to¡n rút gọn đồ thị m¤ng ban đầu v· đồ thị rút gọn RLVG 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¢nfT _ max để x¡c định c§u trúc cëng đồng rời nhau. 4. Đề xu§t thuªt to¡n COPA-BC ph¡t hi»n c§u trúc cëng đồng chồng ch²o trong đồ 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 tø h» sè ph¥n cụm đồ thị. Hướng ph¡t triºn và ki¸n nghị 1. Vªn dụng nhúng ti¸n bë trong kỹ thuªt m¤ng nơ ron và học s¥u 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. 2. Phèi hñp với vi»c nghi¶n cùu, vªn dụng nhúng v§n đề lý thuy¸t và mô h¼nh thèng k¶ vào vi»c ph¥n t½ch, ph¡t triºn hoàn thi»n c¡c thuªt to¡n. 3. Nghi¶n cùu c¡c phương ph¡p và kỹ thuªt xû lý song song để ph¡t triºn nhúng thuªt to¡n ph¡t hi»n c¡c c§u trúc cëng đồng tr¶n đồ thị m¤ng x¢ hëi. 24
29. Danh mục c¡c công tr¼nh khoa học có li¶n quan đến luªn ¡n [CT1]. Nguy¹n Hi·n Trinh, Tr¦n H£i Thanh, C¡p Thanh Tùng (2017), “Sử dụng độ đo trung gian cõa c¡c c¤nh ph¡t hi»n cëng đồng gèi nhau”, T¤p ch½ Khoa học và công ngh» Đại học Th¡i Nguy¶n-Chuy¶n san khoa học tự nhiên-kỹ thuªt, ISSN: 1859-2171, tªp 162, trang 73-80. [CT2]. Nguy¹n Hi·n Trinh, Vũ Vinh Quang (2020), “Ứng dụng phương ph¡p ph¥n cụm phê trong bài to¡n ph¡t hi»n cëng đồng”, T¤p ch½ Khoa học và công ngh» Đại học Th¡i Nguy¶n-Chuy¶n san khoa học tự nhiên-kỹ thuªt-công ngh», eISSN:2615-9562, ISSN:1859-2171, 2734-9098, T.255 06, trang 303-310. [CT3]. Nguy¹n Hi·n Trinh, Vũ Vinh Quang, C¡p Thanh Tùng (2020), “Kết qu£ đề xu§t thuªt to¡n ph¡t hi»n cëng đồng tr¶n m¤ng x¢ hội”, T¤p ch½ Khoa học và công ngh» Đại học Th¡i Nguy¶n-Chuy¶n san khoa học tự nhiên-kỹ thuªt-công ngh», eISSN:2615-9562, ISSN:1859-2171, 2734-9098, T.255 S 09, trang 103-111. [CT4]. Nguy¹n Hi·n Trinh, Vũ Vinh Quang, C¡p Thanh Tùng (2021), “Thuªt to¡n ph¡t hi»n cëng đồng tr¶n m¤ng x¢ hëi theo phương ph¡p lan truy·n nh¢n có sû dụng Modularity và Density”, Kỷ y¸u hëi th£o Quèc gia l¦n thù XXIV: mët sè v§n đề chọn lọc cõa Công ngh» Thông tin và Truy·n thông (VNICT), Th¡i Nguy¶n, 2021, trang 528-532. [CT5]. Nguyen Hien Trinh, Doan Van Ban, Vu Vinh Quang, Cap Thanh Tung (2022), “A Fast overlapping community detection algorithm based on label propagation and social network graph clustering coeffi- cient”, Journal of Computer Science and Cybernetics, V.38, N.1(2022), 31-46DOI no.10.15625/1813-9663/38/1/16537 . i