Tài liệu Phân nhóm người dùng dựa vào hành vi tương tác trong mạng xã hội

MỤC LỤC TRANG BÌA LỜI CAM ĐOAN MỤC LỤC TRANG TÓM TẮT LUẬN VĂN DANH MỤC CÁC HÌNH MỞ ĐẦU ......................................................................................................................... 1 1. Đặt vấn đề ............................................................................................................... 1 2. Lý do chọn đề tài ..................................................................................................... 1 3. Mục tiêu của đề tài .................................................................................................. 3 4. Đối tượng và phạm vi nghiên cứu ........................................................................... 3 5. Phương pháp luận và phương pháp nghiên cứu ...................................................... 3 CHƯƠNG 1: GIỚI THIỆU TỔNG QUAN VÀ MỘT SỐ THUẬT TOÁN PHÂN NHÓM ................................................................................................................. 5 1.1. Các mạng xã hội và cấu trúc đồ thị .......................................................................... 5 1.1.1. Giới thiệu khái quát về mạng xã hội ................................................................. 5 1.1.2. Mối liên hệ giữa mạng xã hội và cấu trúc đồ thị............................................... 6 1.2. Một số loại mạng xã hội ........................................................................................... 7 1.3. Các tính chất của mạng xã hội .................................................................................. 7 1.3.1. Phân phối bậc .................................................................................................... 7 1.3.2. Cấu trúc nhóm ................................................................................................... 8 1.3.3. Độ đo trung gian................................................................................................ 9 1.3.4. Phổ của đồ thị .................................................................................................... 9 1.4. Phân nhóm trong các mạng xã hội ......................................................................... 10 1.4.1. Bài toán phân nhóm ........................................................................................ 10 1.4.2. Ví dụ về mạng xã hội và các sự phân nhóm ................................................... 12 1.5. Các phương pháp phân cụm truyền thống .............................................................. 14 1.5.1. Phân cụm phân hoạch...................................................................................... 14 1.5.2. Phân cụm phân cấp.......................................................................................... 15 1.5.3. Phân vùng đồ thị.............................................................................................. 16 1.6. Các giải thuật di truyền........................................................................................... 17 1.6.1. Giải thuật di truyền truyền thống .................................................................... 17 1.6.2. Giải thuật di truyền phân nhóm của Falkenauer ............................................. 18 1.6.3. Giải thuật di truyền phân nhóm của Tasgin .................................................... 18 1.7. Giải thuật Girvan-Newman .................................................................................... 19 1.7.1. Giới thiệu về độ đo modularity ....................................................................... 19 1.7.2. Thuật toán phân chia nhóm Girvan-Newman ................................................. 20 1.8. Giải thuật CONGA ................................................................................................. 23 1.9. Giải thuật CNM (Clauset-Newman-Moore)........................................................... 26 1.10. Kết luận chương 1 ................................................................................................ 29 CHƯƠNG 2: THUẬT TOÁN CẢI TIẾN INC (INCRE-COMM-EXTRACTION) .... 30 2.1. Giới thiệu ................................................................................................................ 30 2.2. Mô hình hóa dữ liệu................................................................................................ 31 2.3. Thuật toán cải tiến INC .......................................................................................... 33 2.3.1. Nội dung thuật toán ......................................................................................... 33 2.3.2. Độ phức tạp của thuật toán .............................................................................. 35 2.3.3. Độ đo chất lượng phân nhóm của thuật toán .................................................. 36 2.4. Kết luận chương 2 .................................................................................................. 36 CHƯƠNG 3. CÀI ĐẶT CHƯƠNG TRÌNH, THỰC NGHIỆM VÀ ĐÁNH GIÁ............ 38 3.1. Xây dựng dữ liệu .................................................................................................... 38 3.1.1. Thu thập tập dữ liệu từ mạng xã hội với Facebook API ................................. 38 3.1.2. Tiền xử lý dữ liệu và xây dựng cấu trúc mạng xã hội ..................................... 41 3.2. Các chức năng chính của chương trình .................................................................. 42 3.2.1. Tự động thu thập và xây dựng dữ liệu ............................................................ 42 3.2.2. Phân nhóm với thuật toán INC và CNM ......................................................... 43 3.2.3. Biểu diễn trực quan kết quả phân nhóm với thuật toán INC .......................... 44 3.3. Các kết quả thực nghiệm và đánh giá ..................................................................... 45 3.3.1. Thời gian thực thi thuật toán ........................................................................... 45 3.3.2. Số lượng nhóm tìm được ................................................................................. 46 3.3.3. Chất lượng phân chia nhóm ............................................................................ 47 3.3.4. Đánh giá trực quan trên biểu đồ kết quả ......................................................... 48 3.4. Kết luận chương 3. ................................................................................................. 51 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .................................................................... 53 TÀI LIỆU THAM KHẢO ............................................................................................. 55 U ẾT Đ NH GIAO Đ TÀI LUẬN VĂN THẠC S (BẢN SAO BẢN SAO KẾT LUẬN CỦA HỘI ĐỒNG, BẢN SAO NHẬN XÉT CỦA CÁC PHẢN BIỆN. TRANG TÓM TẮT LUẬN VĂN PHÂN NHÓM NGƯỜI DÙNG DỰA VÀO HÀNH VI TƯƠNG TÁC TRONG MẠNG XÃ HỘI Học viên: Lê Anh Ngọc - Chuyên ngành: Khoa học máy tính Mã số: 8480101 Khóa: K34 - Trường Đại học Bách khoa - Đại học Đà Nẵng TÓM TẮT Hiện nay mạng xã hội được sử dụng rộng rãi trên thế giới nói chung và tại Việt Nam nói riêng. Vì vậy trong nhiều lĩnh vực của đời sống xã hội như khoa học máy tính, sinh học, kinh tế, chính trị… việc phát hiện nhóm người dùng trong mạng xã hội có một vai trò quan trọng. Nhằm mục đích phát hiện và phân nhóm người dùng trong mạng xã hội đã có nhiều thuật toán được phát triển, tiêu biểu có các thuật toán: thuật toán di truyền, thuật toán Kernighan-Lin, họ thuật toán Girvan-Newman, thuật toán tham lam Newman, thuật toán Clauset-Newman-Moore (CNM). Trong số các thuật toán đó, thuật toán CNM được đánh giá là tốt nhất, khá phù hợp với các mô hình thực tế với độ phức tạp cỡ O(mdlogn trong đó d là độ sâu của dữ liệu “dendrogram” mô tả cấu trúc của nhóm mạng, m là số đỉnh và n là số cạnh. Nhưng mặc dù thuật toán CNM cho thời gian chạy nhanh và độ đo chất lượng phân chia khá phù hợp với các mô hình thực tế tuy nhiên vẫn còn hạn chế đó là cho ra kết quả nhiều nhóm có cấu trúc lớn đồng thời việc cực đại hoá giá trị modularity chưa thể khẳng định là đồ thị có cấu trúc nhóm trừ khi các nhóm tìm được là clique. Để khắc phục các hạn chế và tận dụng được lợi thế về thời gian thực thi của thuật toán CNM thì thuật toán INC được phát triển dựa vào nó, để đưa ra các cấu trúc nhóm có kích thước nhỏ hơn thể hiện mối quan hệ mật thiết hơn giữa các đối tượng trong cùng nhóm. Để phù hợp với thực tế hơn trong luận văn này tác giả đã xây dựng mạng xã hội dựa vào hành vi tương tác của người dùng so với các mô hình xây dựng mạng xã hội dựa trên mối quan hệ xã hội hay là lượng theo dõi như các đề tài nghiên cứu trước đây. Từ tập dữ liệu tự thu thập là 1500 tài khoản Facebook, luận văn xây dựng được một đồ thị mạng xã hội gồm 1500 đỉnh, 101.537 cạnh và 2.400.534 người dùng bình luận. Kết quả thực nghiệm cho thấy INC cho thời gian chạy chậm hơn CNM không đáng kể (0.24 giây của INC so với 0.18 giây của CNM , trong khi số lượng nhóm lớn hơn rất nhiều (321 nhóm của INC so với 2 nhóm của CNM và chất lượng phân chia nhóm là vượt trội (độ đo chất lượng là 2480,0 4 của INC so với 1212,408 của CNM . Kết quả thực nghiệm cho thấy tính khả quan cao của INC khi áp dụng để phân nhóm người dùng trong các mạng xã hội. ABSTRACT GROUPING USERS BASED ON INTERACTIVE BEHAVIOR IN SOCIAL NETWORKS Social networking is now widely used in the world in general and in Vietnam in particular. So in many areas of social life such as computer science, biology, economics, politics ... the discovery of user groups in social networking has an important role. For the purpose of identifying and grouping users in social networks, many algorithms have been developed, including algorithms: genetic algorithm, Kernighan-Lin algorithm, Girvan-Newman algorithm, greedy algorithms Newman, algorithmic Clauset-Newman-Moore (CNM). Among these algorithms, the CNM algorithm is best suited for real-world models with a size O (mdlogn) complex where d is the depth of the "dendrogram" data describing the structure of the network group, m is the number of vertices and n is the number of edges. But although the CNM algorithm for fast-paced and split-quality metrics is well suited to real-world models, it is still limited by the fact that many large structured groups and maximal the modularity value can not be asserted as a clustered graph unless the found groups are clique. In order to overcome the limitations and take advantage of the real-time performance advantage of the CNM algorithm, the INC algorithm was developed based on it, to produce smaller-sized group structures that express the bile relationship. It is more important than the objects in the same group. To be more realistic in this thesis, the author has built a social network based on user interaction behavior versus social networking models based on social relationships or track amounts. Like previous research topics. From the self-collected dataset of 1500 Facebook accounts, the thesis builds a social network graph of 1500 peaks, 101.537 edges and 2,400,534 user comments. The empirical results show that INC is much slower than CNM (0.24 seconds of INC versus 0.18 seconds of CNM), while the number of groups is much larger (321 groups of INCs compared to 92 groups of CNMs). ) and the quality of grouping is superior (quality is 2480,094 of INC versus 1212,408 of CNM). The empirical results show that INC is highly applicable when used to group users in social networks. DANH MỤC CÁC HÌNH Hình 1.1: Mô hình các thành viên của mạng xã hội Facebook và Twitter ......................6 Hình 1.2: Ví dụ về một mạng xã hội thu nhỏ có 3 nhóm. ...............................................8 Hình 1.3: Ví dụ về độ đo trung gian ................................................................................9 Hình 1.4: Mô hình câu lạc bộ karate của Zachary.........................................................12 Hình 1.5: Mô hình biểu diễn mạng lưới cộng tác của các nhà khoa học tại SFI ..........13 Hình 1.6: Mạng Lusseau biểu diễn loài cá heo ở Doubtful Sound, New Zealand ........14 Hình 1.7: Cây phân cấp (dendrogram cho mô hình câu lạc bộ karate của Zachary ....15 Hình 1.8: Phân cụm phân cấp với một mạng xã hội nhỏ ..............................................16 Hình 1.9: Ví dụ phát hiện nhóm sử dụng thuật toán Girvan - Newman .......................21 Hình 1.10: Ví dụ về phép phân chia một đỉnh trong đồ thị ...........................................24 Hình 1.11: Ví dụ trường hợp không phân tách đỉnh v trong đồ thị ...............................24 Hình 1.12: Phép phân chia tối ưu trong trường hợp hình 1.10 ......................................25 Hình 2.1: Ví dụ về một nội dung và các hành vi tương tác của người dùng .................32 Hình 3.1: Một phần tập dữ liệu tài khoản Facebook .....................................................38 Hình 3.2: Giao diện sau khi tạo một ứng dụng trên Facebook API thành công ...........39 Hình 3.3: Sử dụng Graph API Explorer thu thập bình luận của một Facebook ............39 Hình 3.4: Thu thập dữ liệu với Facebook SDK .............................................................40 Hình 3.5: Một phần tập dữ liệu được lưu trữ trên SQL Server 2017 ............................40 Hình 3.6: Một phần danh sách ID và số lượng người dùng đã bình luận được lưu trữ trong CSDL ................................................................................................41 Hình 3.7: Một phần dữ liệu đồ thị mạng xã hội ............................................................42 Hình 3.8: Giao diện tự động thu thập bộ dữ liệu ...........................................................43 Hình 3. : Kết quả chạy chương trình phân nhóm với INC và CNM. ...........................44 Hình 3.10: Một phần biểu đồ dendrogram kết quả phân nhóm với INC ......................45 Hình 3.11: Đồ thị so sánh thời gian thực thi INC và CNM ...........................................46 Hình 3.12: Đồ thị so sánh số lượng nhóm theo INC và CNM ......................................46 Hình 3.13: Đồ thị tương quan số lượng nhóm với giá trị s ...........................................47 Hình 3.14: Đồ thị so sánh chất lượng phân nhóm theo INC và CNM ..........................47 Hình 3.15: Đồ thị tương quan chất lượng nhóm với giá trị s ........................................48 Hình 3.16: Kết quả phân chia nhóm lớn thành các nhóm con (bất động sản, chứng khoán, ô tô, mô tô...). .................................................................................49 Hình 3.17: Kết quả phân chia nhóm lớn thành các nhóm con (thời trang, nội thất… . 50 Hình 3.18: Kết quả phân nhóm lớn thành các nhóm con (Phật giáo) ...........................50 Hình 3.19: Kết quả phân nhóm lớn thành các nhóm con (mỹ phẩm, thẩm mỹ, bệnh viện… ........................................................................................................51 1 MỞ ĐẦU 1. Đặt vấn đề Mạng xã hội là một cấu trúc xã hội được cấu tạo từ các đối tượng có thể là một người, một tổ chức, một quốc gia…được gọi là các nút và từ các mối quan hệ như người thân, bạn bè, đồng nghiệp… hay là các trao đổi tài chính, các giao dịch…được gọi là các cung, các nút liên kết với nhau bởi một hoặc nhiều cung. Mối liên kết giữa các nút dùng để biểu diễn mối liên hệ giữa các nút, các liên kết này có thể là liên kết vô hướng trong đó mối quan hệ giữa hai nút là mối quan hệ qua lại, ví dụ nút A là đồng nghiệp với nút B và nút B cũng là đồng nghiệp với nút A…các liên kết này cũng có thể là liên kết có hướng, ví dụ nút A thích nút B nhưng nút B có thể không thích nút A…đồng thời các liên kết này còn có thể được đánh trọng số để biểu diễn độ mạnh yếu của liên kết giữa hai nút. Có hai cách để biểu diễn mạng xã hội mà các nhà phân tích mạng xã hội sử dụng đó là đồ thị và ma trận kề, trong đó lý thuyết đồ thị thường được sử dụng để tính toán và phân tích các liên kết trong mạng. Để biểu diễn mạng xã hội trong lý thuyết đồ thị đó là các nút chính là các đỉnh, các liên kết giữa các nút là các cạnh và các cạnh trong đồ thị có thể vô hướng hoặc có hướng hay cũng có thể được đánh trọng số phụ thuộc vào nhu cầu biểu diễn. Khi biểu diễn đồ thị của các mạng xã hội ta thấy rằng một số nhóm các đỉnh có liên kết chặt chẽ với nhau tạo thành các cụm và giữa các cụm này được nối với nhau chỉ bằng một hoặc vài cạnh khác, tính chất này được gọi là sự phân nhóm. Đây là một tính chất quan trọng nhất của mạng xã hội chính vì vậy rất nhiều nghiên cứu mục tiêu hướng đến việc phát hiện các nhóm này. 2. Lý do chọn đề tài Hiện nay trên thế giới có rất nhiều trang mạng xã hội khác nhau tiêu biểu có Facebook, Twitter, outube, Instagram…hay tại Việt Nam có Zalo, Zing Me thu hút hàng triệu người dùng. Trên các trang mạng xã hội này người dùng có thể giao lưu, kết bạn, bày tỏ cảm xúc của mình hoặc có thể được sử dụng với mục đích kinh doanh, giải trí, tuyên truyền…Nếu chúng ta có thể phân nhóm người dùng cùng quan tâm đến một vấn đề nào đó trên các mạng xã hội thì nó có ý nghĩa rất to lớn giúp cho việc truyền tải thông tin, tiếp thị bán hàng cũng như các hoạt động khác…đến đúng đối tượng hơn. Đã có nhiều thuật toán được phát triển phục vụ mục đích phát hiện và phân nhóm trong mạng xã hội. Tiêu biểu có giải thuật di truyền, thuật toán Kernighan- 2 Lin, họ thuật toán Girvan-Newman, thuật toán tham lam Newman, thuật toán Clauset-Newman-Moore (CNM). Về cơ bản thì các thuật toán di truyền, Kernighan-Lin [1], họ thuật toán Girvan-Newman [5, 9, 10, 11, 12] đều có những điểm hạn chế như chỉ áp dụng được cho một số mạng nào đó mà không mang tính tổng quát, hay Girvan-Newman áp dụng được cho rất nhiều mạng nhưng lại gặp vấn đề với thời gian thực thi thuật toán (độ phức tạp là O(m2n trong các mạng bất kỳ với m là số đỉnh và n là số cạnh, độ phức tạp O(n3 trong trường hợp đồ thị thưa - một dạng mô hình mạng rất hay gặp trong thế giới thực . Vì những hạn chế đó mà các thuật toán này thường chỉ chạy được với số đỉnh cỡ vài ngàn đỉnh. Xuất phát từ thực tế đó, Newman [13] đã độc lập phát triển một thuật toán tối ưu tham lam với việc đưa vào độ đo chất lượng phân chia nhóm, gọi là modularity, và cách cài đặt để thực thi thuật toán này của Newman có độ phức tạp cỡ O((m+n n với đồ thị bất kỳ và O(n2 với đồ thị thưa. Thuật toán CNM [4] là thuật toán tốt nhất hiện nay, được dựa trên đúng ý tưởng của thuật toán tối ưu tham lam do Newman đề xuất ở trên, tuy nhiên cách thức cài đặt của CNM lại khác so với Newman bởi việc đưa vào một số cấu trúc dữ liệu đặc biệt, giúp cho việc tìm kiếm tối ưu được nhanh hơn và thuật toán này chỉ chạy với độ phức tạp cỡ O(mdlogn trong đó d là độ sâu của cấu trúc dữ liệu "dendrogram" mô tả cấu trúc nhóm của mạng, m là số đỉnh và n là số cạnh. Trên thực tế đa số các mạng có cấu trúc thưa, tức là m~n và d~logn, dẫn đến thuật toán CNM chạy rất nhanh (tuyến tính với độ phức tạp chỉ O(nlog2n). Mặc dù thuật toán CNM cho thời gian chạy nhanh và độ đo chất lượng phân chia nhóm khá phù hợp với các mô hình thực tế, tuy nhiên kết quả cho ra khá nhiều nhóm có cấu trúc lớn, đồng thời việc cực đại hóa giá trị modularity chưa thể giúp ta khẳng định đồ thị có cấu trúc nhóm trừ khi các nhóm tìm được là các clique (tồn tại cạnh nối giữa hai đỉnh bất kỳ trong đồ thị . Trên thực tế, có nhiều công việc đòi hỏi phải phân chia nhóm ở mức độ chi tiết hơn. Ví dụ: với một lượng lớn các người dùng trong nhóm giải trí, cần phân chia thành các nhóm con như: đam mê ca nhạc, thể thao, phim ảnh, du lịch, mua sắm ... Ngoài ra, các cách tiếp cận của các tác giả trước đây khi xây dựng mô hình mạng xã hội thường chỉ dựa trên các mối quan hệ xã hội (mô hình tĩnh của các người dùng trong mạng như bạn bè, gia đình, đồng nghiệp... mà không để ý đến việc các người dùng này có cùng mối quan tâm đến các chủ đề, lĩnh vực nào đó hay không (cụ thể với Facebook thể hiện ở việc cùng vào comment hay like, share, 3 post... - đây là mô hình động , do đó chất lượng phân nhóm trong mạng là không cao. Xuất phát từ những hạn chế ở trên, luận văn nghiên cứu "Phân nhóm người dùng dựa vào hành vi tương tác trong mạng xã hội". Luận văn nghiên cứu thuật toán cải tiến dựa trên thuật toán CNM cũng như cách thức xây dựng một cấu trúc mạng xã hội dựa trên hành vi tương tác của người dùng (mô hình mạng động với đồ thị vô hướng có trọng số , nhằm nâng cao chất lượng phân nhóm người dùng trong các mạng xã hội thực tế như Facebook, Twitter... 3. Mục tiêu của đề tài Xây dựng cấu trúc mạng xã hội dựa trên hành vi tương tác của người dùng Xây dựng thuật toán phát hiện các nhóm người dùng nhỏ bên trong mạng xã hội với độ tin cậy cao. Thời gian thực thi thuật toán nhanh, tiết kiệm bộ nhớ nhằm phù hợp với cấu trúc mạng xã hội rất lớn trong thực tế (hàng triệu đỉnh, cạnh). 4. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu là dữ liệu trên mạng xã hội: người dùng trên các mạng xã hội, các trao đổi nội dung thông tin, bình luận, chia sẻ,... trên các mạng xã hội. Phạm vi nghiên cứu  Nắm bắt và sử dụng Facebook API lấy thông tin người dùng, các chia sẻ, bình luận, like... trong mạng xã hội Facebook.  Nắm bắt lý thuyết đồ thị vận dụng vào việc biểu diễn mạng xã hội.  Nắm bắt các tiêu chí để phát hiện cấu trúc nhóm.  Nắm bắt một số thuật toán phát hiện nhóm nhằm cải tiến, nâng cao chất lượng phân nhóm, tối ưu về thời gian thực thi và dung lượng bộ nhớ. 5. Phương pháp luận và phương pháp nghiên cứu Từ những lý thuyết được công bố từ các bài báo, tài liệu và các công trình nghiên cứu liên quan được kết hợp để phát triển và xây dựng ứng dụng với mục đích thử nghiệm và đánh giá hiệu quả của mô hình đã đề xuất. Cấu trúc luận văn được bố cục bao gồm phần mở đầu, kết luận và 03 chương, cụ thể như sau: 4 Chương 1. Giới thiệu tổng quan và một số thuật toán phân nhóm Nghiên cứu các cơ sở lý thuyết về mạng xã hội, sự liên quan giữa mạng xã hội và cấu trúc đồ thị, các tính chất của mạng xã hội và bài toán phân nhóm người dùng trong mạng xã hội. Nghiên cứu, trình bày một số thuật toán phổ biến sử dụng để phân nhóm người dùng trong mạng xã hội như: các phương pháp phân cụm truyền thống, giải thuật di truyền, giải thuật Girvan - Newman, giải thuật tham lam Newman, giải thuật CNM (Clauset-Newman-Moore) với các khái niệm như độ đo modularity, độ phức tạp thuật toán... để đánh giá chất lượng phân nhóm của các thuật toán. Chương 2. Thuật toán cải tiến INC(Incre-Comm-Extraction) Đề xuất cách tiếp cận xây dựng cấu trúc mạng xã hội dựa vào hành vi tương của người dùng (các bình luận của người dùng trên mạng xã hội Facebook . Giới thiệu thuật toán INC để phân nhóm với mức độ phân hoạch chi tiết hơn (tìm được nhiều nhóm hơn dựa trên thuật toán CNM áp dụng cho đồ thị mạng xã hội có trọng số. Đánh giá độ phức tạp của thuật toán cũng như chất lượng thuật toán dựa trên độ đo đề xuất. Chương 3. Cài đặt chương trình, thực nghiệm, đánh giá Tiến hành xây dựng bộ dữ liệu thử nghiệm sử dụng công cụ Facebook API, tiến hành thu thập dữ liệu bình luận của người dùng trên một tập 1500 trang facebook khác nhau. Cài đặt thuật toán CNM trên đồ thị có trọng số, thuật toán INC áp dụng cho đồ thị đầu vào có trọng số. Xây dựng chức năng hiển thị trực quan bằng đồ họa kết quả phân nhóm người dùng. Đánh giá kết quả đạt được: chất lượng phân nhóm người dùng, thời gian thực thi chương trình, số nhóm... 5 Chương 1: GIỚI THIỆU TỔNG QUAN VÀ MỘT SỐ THUẬT TOÁN PHÂN NHÓM 1.1. Các mạng xã hội và cấu trúc đồ thị 1.1.1. Giới thiệu khái quát về mạng xã hội Trong thập kỉ qua đã có một mối quan tâm ngày càng lớn với sự “kết nối” phức tạp của xã hội hiện đại. Tâm điểm của mối quan tâm này là ý tưởng về một mạng xã hội - một mô hình kết nối giữa một tập hợp các sự vật, sự việc. Trong các chủ đề của các cuộc hội thảo và bình luận trên phạm vi lớn mạng xã hội ngày càng xuất hiện nhiều, theo David Easley và Jon Kleinberg [6]. Vào những năm 1 50, các nhà nghiên cứu thuộc khoa Nhân chủng học và Xã hội đã chú ý đến cấu hình hiệu quả của các mối quan hệ xuất phát từ quyền lực và xung đột giữa các cá nhân, thay vì thiết lập các định mức và thể chế của một xã hội. Nhóm này, dẫn đầu bởi John Barnes, Elizabeth Bott và sau đó là J. Clyde Mitchell, bắt đầu điều tra cách cấu trúc quan hệ giữa những người bị ảnh hưởng không chỉ cá nhân mà cả xã hội nói chung. Thuật ngữ “Mạng xã hội” lần đầu tiên được giới thiệu vào năm 1 54 bởi John Barnes, đã đánh dấu sự phát triển chính thức đáng kể trong phân tích cấu trúc xã hội. Vào năm 1 55 lần đầu tiên mô hình mạng xã hội thực tế xuất hiện đó là trang Classmate với mục đích kết nối bạn học. Garton và các cộng sự cho rằng mạng xã hội là một tập hợp những người được liên kết với nhau bằng các mối quan hệ như tình bạn, đồng nghiệp hay là trao đổi thông tin [6]. Trong xã hội hiện đại ngày nay, mạng xã hội trở thành một nhu cầu không thể thiếu của con người, nó được coi là một cuộc sống ảo. Ở trên đó con người có thể giao lưu, kết nối với rất nhiều bạn bè, là nơi để trao đổi thông tin hay giải trí và cũng là một kênh cung cấp những tin tức hằng ngày. Rất nhiều tính năng được tích hợp vào trong mạng xã hội như tán gẫu, phim ảnh, chia sẻ tập tin….và đặc biệt mạng xã hội đã thay đổi cách liên kết con người với nhau trở thành một phần tất yếu của con người. Việc tìm kiếm bạn bè, đối tác cũng rất dễ dàng bởi các mạng xã hội này đã cung cấp rất nhiều phương cách như: dựa vào vị trí địa lý, dựa vào thông tin của cá nhân (ví dụ học trường đại học nào, đang làm việc ở đâu, sở thích là gì… … Hiện có rất nhiều mạng xã hội khác nhau nhưng nổi bật lên các cái tên như Facebook, Twitter, Instagram, outube…ở Việt Nam có Zalo. 6 Hình 1.1: Mô hình các thành viên của mạng xã hội Facebook và Twitter [6] 1.1.2. Mối liên hệ giữa mạng xã hội và cấu trúc đồ thị Cấu trúc mạng xã hội được cấu tạo nên từ các nút mạng và các liên kết trong đó nút mạng là một thực thể (có thể là một cá nhân, một tổ chức hay là một quốc gia… còn liên kết là mối quan hệ giữa các thực thể đó (có thể là mối quan hệ bạn bè, đồng nghiệp hay là khách hàng... . Có nhiều kiểu liên kết trong mạng như liên kết vô hướng, liên kết có hướng (một chiều hoặc hai chiều … Mạng xã hội ở dạng đơn giản nhất được biểu diễn dưới dạng một đồ thị vô hướng có các mối liên kết phù hợp giữa các nút, khi đó các nút được biểu diễn bởi các điểm còn các liên kết biểu diễn bởi các đoạn thẳng, trong đó các điểm nút có mối quan hệ qua lại, ví dụ: A ở cùng nhà với B, B ở cùng nhà với A. Mạng xã hội phức tạp hơn thì các mối liên hệ còn có thể biểu diễn liên kết có hướng (một chiều hoặc hai chiều), ví dụ: A biết B nhưng B không biết A… hoặc các liên kết còn có thể được đánh trọng số để thể hiện độ mạnh yếu của mối liên kết. Thông thường để biểu diễn mạng xã hội có hai dạng đó là ma trận kề và đồ thị, nhưng dạng đồ thị được ưu tiên sử dụng nhiều trong bài toán phân tích mạng. Để biểu diễn mạng xã hội trong đồ thị thì các đỉnh là các nút mạng còn các cạnh là các mối liên kết, phụ thuộc vào đặc điểm của từng liên kết mà cạnh có thể là vô hướng hay có hướng, có trọng số hay không. Trong thực tế việc phân bố các cạnh của mạng xã hội là không đều, trong một số nhóm đỉnh đặc biệt có mức độ tập trung cao của các cạnh và liên kết chặt chẽ với nhau thành các cụm, giữa các cụm đó số lượng cạnh tập trung là thấp đây gọi là sự phân cụm. Sự phân cụm là một tính chất quan trọng của mạng xã hội được nhiều [5] nhà khoa học quan tâm. 7 1.2. Một số loại mạng xã hội Mặc dù mô hình mạng xã hội bạn bè được biết đến nhiều nhất, tuy nhiên vẫn có một số mạng khác cũng là những ví dụ điển hình cho các mạng xã hội. Một số kiểu mạng xã hội phổ biến: Mạng bạn bè: ở đây các nút mạng biểu diễn bởi các người khác nhau, các cạnh biểu diễn mối quan hệ giữa hai người đó. Các cạnh ở đây thông thường không đánh trọng số và thể hiện họ có là bạn hay không. Nếu chúng ta cần quan tâm đến mức độ thân thiết của các mối quan hệ này thì có thể đưa vào các trọng số cho các cạnh, khi đó đồ thị trở thành đồ thị có trọng số. Mạng điện thoại: trao đổi thông tin giữa mọi người qua điện thoại có thể được mô hình hóa thành một mạng xã hội trong đó các số điện thoại chính là các cá thể và được thể hiện bởi các nút mạng. Các cuộc gọi trong một khoảng thời gian giữa hai số điện thoại có thể được biểu diễn bởi các cạnh của đồ thị. Ví dụ: mạng cuộc gọi trong một công ty trong 2 tháng gần nhất. Mạng email: trong loại mạng này, các nút biểu diễn các địa chỉ email là các thực thể đơn nhất. Nếu có một cạnh nối hai địa chỉ này tức là đã có sự trao đổi tối thiểu một email theo tối thiểu một chiều giữa hai địa chỉ email đó. Một cách định nghĩa khác đó là một cạnh được thiết lập khi có tối thiểu một trao đổi email hai chiều giữa hai địa chỉ email này. Với việc thiết lập này, chúng ta có thể ngăn chặn được việc gửi các thư rác. Mạng cộng tác: các nút mạng biểu diễn các cá thể cùng thực hiện các công việc chung như xuất bản các bài báo nghiên cứu. Ví dụ: nếu hai tác giả cùng xuất bản một bài báo, một cạnh sẽ được thiết lập giữa hai tác giả này. Ngoài ra, chúng ta có thể đánh trọng số cạnh bởi số các bài báo mà hai tác giả này đã xuất bản chung. Các cộng đồng trong mạng này chính là các tác giả cùng nghiên cứu một chủ đề cụ thể nào đó. 1.3. Các tính chất của mạng xã hội Trong mục này tôi giới thiệu một số tính chất cơ bản và phổ biến của các mạng xã hội trong thế giới thực. Các tính chất này rất quan trọng cho việc nghiên cứu, phân tích và khai thác cấu trúc các mạng xã hội với các mục đích nào đó. 1.3.1. Phân phối bậc Bậc của một đỉnh là số lượng các cạnh nối tới đỉnh đó. Ta có thể xây dựng công thức tính bậc ki cho một đỉnh i của đồ thị đã biểu diễn dưới dạng ma trận kề như sau: 8 ∑ Trong đồ thị có hướng, có hai kiểu liên kết gọi là liên kết đi vào và liên kết đi ra, tổng bậc của đỉnh chính là tổng bậc đi vào và đi ra của đỉnh đó. Tuy nhiên, trong khuôn khổ luận văn, tác giả chỉ nghiên cứu các đồ thị vô hướng tức là không có khái niệm các cạnh đi vào và đi ra của một đỉnh. Phân phối bậc P(k là xác suất bậc của một đỉnh được chọn ngẫu nhiên là k hay một phân hoạch các đỉnh của đồ thị có cùng bậc k. Phân phối bậc là một đặc tính rất quan trọng liên quan đến hình trạng của một đồ thị. Trong một mạng vô hướng, phân phối của các bậc theo các đỉnh có thể nhận được bởi một đồ thị của P(k hoặc thông qua việc tính toán các mô men của phân phối. P(k cho một mô men của n được định nghĩa như sau: ∑ Trong đó, các kết nối giữa các đỉnh của mạng là ngẫu nhiên, phân phối bậc cho ta tất cả các đặc trưng thống kê của mạng. 1.3.2. Cấu trúc nhóm Trong một mạng xã hội mà tập các thực thể có tính chất tương tự nhau hoặc cùng đóng một vai trò thì được gọi là nhóm. Trong thực tế các nhóm đề cập một bối cảnh xã hội xác định, việc con người thường có xu hướng kết hợp lại với nhau chính vì vậy đã hình thành các nhóm. Hình 1.2 dưới đây chỉ ra một ví dụ về đồ thị mạng xã hội thu nhỏ với 03 cấu trúc nhóm trong đó. Hình 1.2: Ví dụ về một mạng xã hội thu nhỏ có 3 nhóm [7]. Ngày nay, trong xã hội đã xuất hiện nhiều nhóm có kích cỡ khác nhau (ví dụ như gia đình, nhóm bạn bè, đồng nghiệp… và sự phát triển của Internet cũng góp 9 phần sản sinh ra nhiều nhóm ảo. Các nhóm này cũng được nghiên cứu một thời gian dài và thường xuyên xuất hiện trong nhiều hệ thống mạng trong khoa học máy tính, công nghệ, kinh tế, chính trị… Nếu xem xét mạng xã hội dưới dạng cấu trúc đồ thị thì các cạnh nối các đỉnh bên trong một nhóm sẽ dày hơn so với các cạnh nối giữa các đỉnh thuộc các nhóm khác nhau. Gọi G' là một đồ thị con của mạng xã hội G, khi đó nếu tổng các bậc của các đỉnh bên trong G' lớn hơn tổng toàn bộ các bậc đi ra các đỉnh thuộc phần còn lại của đồ thị G thì G' được gọi là một nhóm. 1.3.3. Độ đo trung gian Đường đi ngắn nhất trong một đồ thị là đường đi giữa hai đỉnh mà đi qua số cạnh ít nhất. Nếu gọi AB là đường đi ngắn nhất giữa hai đỉnh VA và VB thì khi đó không thể tìm được đường đi khác sử dụng ít cạnh hơn đường đi AB này. Đường đi ngắn nhất là một khái niệm rất quan trọng trong lý thuyết đồ thị và độ đo trung gian được dựa trên các đường đi ngắn nhất giữa các đỉnh trong đồ thị. Độ đo trung gian của một đỉnh Vi hoặc một cạnh Ei là tổng đường đi ngắn nhất giữa tất cả các cặp đỉnh trong mạng có đi qua đỉnh Vi hoặc cạnh Ei. Nếu một đỉnh có độ đo trung gian lớn hơn thì nó có tầm ảnh hưởng cao hơn. Độ đo trung gian của một đỉnh còn được gọi là độ đo trung gian trung tâm. Hình 1.3: Ví dụ về độ đo trung gian 1.3.4. Phổ của đồ thị Một đồ thị G cấu thành bởi N đỉnh có N trị riêng ( i=1, 2, 3, ...) và N véc tơ riêng (i = 1, 2, 3, ...). Phổ của đồ thị [8] là tập hợp của các trị riêng của nó. Do chúng ta đang xét các đồ thị vô hướng, tức là chúng chỉ có một một ma trận kề đối xứng. Đặc tính kết nối của đồ thị G có thể được trích rút từ ma trận chuẩn hóa, N = D-1A với D là một ma trận đường chéo và A là ma trận kề, và ma trận Laplacian, L 10 = D - A. Tất cả các trị riêng của L là các giá trị thực và không âm. Do tổng tất cả các hàng của L bằng 0, trị riêng đầu tiên và véc tơ riêng của nó là . Do đó, sử dụng giá trị riêng nhỏ nhất thứ hai, sẽ là lát cắt tốt hơn để chia đồ thị thành các phần khác nhau. Các nghiên cứu chỉ ra rằng nếu lớn hơn, việc cắt G thành các phần trở nên phức tạp hơn. 1.4. Phân nhóm trong các mạng xã hội 1.4.1. Bài toán phân nhóm Bài toán: Phân nhóm trong mạng xã hội và đưa ra danh sách những nút mạng thuộc từng nhóm đó. Đầu vào: Đồ thị mạng xã hội G = (V, E gồm tập V có các đỉnh: v1, v2, ..., vn và tập E các cạnh liên kết E = {(vi, vj)}. Đầu ra: Tập các nhóm C = {C1, C2, ...,Cm} và tập hợp các đỉnh thuộc nhóm đó: Ci = {vi1, vi2, ..., vik} với i =1, 2, ...,m. Mục tiêu của bài toán là từ các mạng xã hội cho trước, phát hiện được các cấu trúc nhóm nằm trong đó và tìm hiểu về mối liên hệ bên trong các nhóm cũng như giữa các nhóm 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. Với sự phát triển nhanh chóng của các nhóm trong thời điểm hiện tại và nhu cầu cần thiết về tìm hiểu sự phân nhóm trong các mạng xã hội, bài toán phát hiện nhóm trở thành một bài toán phổ biến trong các nghiên cứu về 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, phát hiện được các nhóm nằm trong đó và tìm hiểu về mối liên hệ bên trong các nhóm cũng như giữa các nhóm 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. Việc phát hiện nhóm có rất nhiều ứng dụng cụ thể. Ví dụ như phân cụm các Web client có sở thích tương tự nhau và gần nhau về mặt địa lý có thể cải thiện hiệu suất của việc cung cấp dịch vụ trên World Wide Web, trong đó mỗi cụm khách hàng được phục vụ bởi một server chuyên dụng. Một ứng dụng khác đó là việc xác định các cụm khách hàng có chung sở thích trong một mạng thể hiện quan hệ giữa người mua và sản phẩm trên một trang web bán hàng trực tuyến (ví dụ www.amazon.com có thể giúp xây dựng hệ thống tư vấn mua bán một cách hiệu quả. Ngoài ra, sự phân cụm trong các đồ thị cỡ lớn có thể được sử dụng trong việc lưu trữ các dữ liệu của đồ thị một cách thuận tiện. Một ứng dụng khác nữa là nhóm thành cụm các nút trong mạng lưới giao thông có thể giúp ích trong việc xây dựng các bảng định tuyến nhỏ gọn giúp ích trong việc tham gia giao thông thuận tiện. 11 Ngoài ra, việc phát hiện nhóm có ý nghĩa rất quan trọng vì một lý do khác. Việc xác định các môđun và ranh giới của chúng cho phép ta phân lớp các đỉnh dựa trên cấu trúc vị trí của chúng trong môđun. Từ đó, các đỉnh ở vị trí trung tâm trong môđun của chúng (có nhiều kết nối cạnh đến các đỉnh khác trong môđun có thể đóng vai trò quan trọng trong việc điều khiển và giữ ổn định trong cụm. Mặt khác, các đỉnh ở vùng biên có thể giữ vai trò quan trọng trong việc dẫn dắt mối quan hệ và giao lưu giữa các cụm khác nhau trong mạng. Các phân lớp như thế mang một ý nghĩa nhất định trong việc nghiên cứu mạng xã hội. Cuối cùng, ta có thể nghiên cứu về đồ thị rút gọn, trong đó các đỉnh là các cụm và các cạnh là các liên kết giữa các cụm trong đồ thị ban đầu (nếu có từ đó ta thu được một đồ thị biểu diễn mối quan hệ của các môđun trong mạng. Một khía cạnh quan trọng khác nữa trong sự phân nhóm là cách tổ chức phân cấp, cách tổ chức này có thể nhìn thấy trong hầu hết các mạng xã hội trong thực tế. Một mạng trong thực tế thường bao gồm các nhóm mà trong đó mỗi nhóm lại được cấu tạo từ một tập các nhóm khác, các nhóm con đó lại được cấu tạo bằng một tập các nhóm con khác nữa,…Một ví dụ dễ thấy nhất cho điều này là cơ thể con người được cấu tạo bởi các cơ quan, mỗi cơ quan được cấu tạo bởi các mô tế bào, các mô tế bào lại được cấu tạo bởi các tế bào, …Herbert A.Simon đã nhấn mạnh vai trò quan trọng của hệ thống phân cấp và sự tiến hóa của các hệ thống phức tạp. Sự sinh ra và tiến hóa của các hệ thống tổ chức bởi các hệ thống con ổn định là nhanh chóng hơn rất nhiều so với các hệ thống không cấu trúc, bởi vì ta có thể xây dựng các phần nhỏ trước và sau đó sử dụng chúng để xây dựng các thành phần lớn hơn và cứ thế cho đến khi toàn bộ hệ thống được xây dựng. Phương pháp này khó có thể xảy ra lỗi trong quá trình xây dựng hệ thống. Việc xác định nhóm trong đồ thị cũng là một chủ đề phổ biến trong khoa học máy tính, trong đó có 2 lĩnh vực điển hình là học máy và khai phá quan điểm. Ví dụ trong tính toán song song, việc xác định phương pháp giao các công việc cho các bộ xử lý sao cho giảm thiểu tối đa sự liên lạc giữa chúng và tối đa hóa hiệu suất tính toán là rất quan trọng. Điều này có thể thực hiện được bằng cách chia các cụm máy tính thành các nhóm có số lượng bộ xử lý gần tương tự nhau, như vậy số lượng kết nối vật lý giữa các vi xử lý của các nhóm khác nhau là tối thiểu. Tên gọi chính thức của vấn đề này là “phân vùng đồ thị”, được đề xuất lần đầu tiên vào năm 1 70. Riêng trong lĩnh vực khai phá dữ liệu, bài toán khai phá nhóm trong mạng xã hội cũng có một ứng dụng tương đối rộng rãi [7]. Khai phá nhóm ứng dụng trực tiếp vào các bài toán chính của khai phá dữ liệu như nhận dạng thực thể, phân cụm, xếp 12 hạng thực thể hay phân lớp thực thể, dự đoán các liên kết hay phát hiện các đồ thị con…, trong đó các nhà khoa học quan tâm nhất đến phân cụm thực thể và xếp hạng các thực thể có liên quan đến nhau trong các cụm vừa được phân. Các bài toán này mang lại các lợi ích trực tiếp trong thực tế như trong các máy tìm kiếm, các dịch vụ phục vụ khách hàng, hay các trang web buôn bán trực tuyến. Tóm lại, nhóm trong các mạng xã hội có một vai trò quan trọng trong nhiều lĩnh vực của đời sống xã hội, như khoa học máy tính, sinh học, kinh tế, chính trị,…Điều này dẫn đến nhu cầu bức thiết của bài toán phát hiện nhóm trong mạng xã hội vì các lý do đã được nêu ở trên. 1.4.2. Ví dụ về mạng xã hội và các sự phân nhóm Ví dụ đầu tiên là mô hình câu lạc bộ karate được Zachary đề xuất vào năm 1977. Đây là một trong những mô hình mạng xã hội thường được sử dụng như một mô hình chuẩn để đánh giá và thử nghiệm các thuật toán phát hiện nhóm. Đồ thị bao gồm 34 đỉnh, đại diện cho các thành viên của một câu lạc bộ karate ở Mỹ, được quan sát trong chu kỳ 3 năm, trong đó các cạnh biểu diễn sự tương tác giữa các cá nhân mà ngoài khuôn khổ hoạt động của câu lạc bộ. Câu lạc bộ được phân thành hai phần riêng biệt, một phần gồm những người ủng hộ người hướng dẫn của câu lạc bộ, một phần gồm những người ủng hộ chủ tịch của câu lạc bộ đó, được biểu thị tương ứng bằng các hình vuông và tròn. Đỉnh số 34 đại diện cho chủ tịch câu lạc bộ karate, trong khi đỉnh số1 đại diện cho người hướng dẫn. Hình 1.4: Mô hình câu lạc bộ karate của Zachary [7] Ví dụ tiếp theo miêu tả một thành phần có kích thước lớn nhất trong mạng lưới cộng sự của các nhà khoa học làm việc tại viện Santa Fe (SFI . Có tất cả 118 đỉnh, biểu diễn cho các nhà khoa học ở viện và các cộng sự của họ. Một cạnh được đặt giữa 2 đỉnh nếu hai nhà khoa học được đại diện bởi 2 đỉnh đó có viết chung một 13 bài báo. Ở mạng này ta quan sát được rất nhiều clique, mỗi clique biểu hiện cho các tất cả tác giả của một bài báo. Mặt khác ta cũng thấy tồn tại chỉ một vài kết nối giữa hầu hết các nhóm trong mạng trên. Các đỉnh cùng màu là kết quả phân tích và phát hiện nhóm sử dụng thuật toán Girvan và Newman, kết quả này cũng gần tương tự so với sự phân chia theo các lĩnh vực nghiên cứu của viện. Hình 1.5: Mô hình biểu diễn mạng lưới cộng tác của các nhà khoa học tại SFI [7] Ví dụ cuối cùng ta xét đến ở đây đó là mạng biểu diễn loài cá heo sống ở Doubtful Sound, New Zealand được phân tích bởi Lusseau năm 2003. Có tất cả 62 đỉnh và một cạnh trong đồ thị nối giữa 2 đỉnh biểu diễn cho 2 con cá heo xuất hiện thường xuyên với nhau hơn so với mức độ bình thường dự kiến. Các con cá heo chia thành 2 nhóm sau khi một con cá heo bỏ đi khỏi nơi ở hiện tại một khoảng thời gian (được biểu diễn bởi hình vuông và hình tròn trong hình vẽ . Mỗi nhóm trong đồ thị là tương đối gắn kết, với một vài clique trong đó và chỉ có 6 cạnh nối giữa các nhóm khác nhau. Mạng nói trên giống như mạng của Zachary cũng thường được sử dụng để cài đặt và đánh giá các thuật toán phát hiện nhóm trong mạng xã hội. 14 Hình 1.6: Mạng Lusseau biểu diễn loài cá heo ở Doubtful Sound, New Zealand [7] 1.5. Các phương pháp phân cụm truyền thống 1.5.1. Phân cụm phân hoạch Những nghiên cứu ban đầu trong lĩnh vực khoa học máy tính để tìm kiếm các nhóm của các đối tượng tương tự nhau được dựa trên các mô hình thống kê và khai phá dữ liệu. Một trong những phương pháp phổ biến nhất trong số các nghiên cứu này đó là sử dụng phương pháp phân cụm phân hoạch như phân cụm với thuật toán k-means, phân cụm với mạng nơ ron [9]. Khi các cạnh của đồ thị có trọng số hoặc một số thuộc tính của đồ thị được sử dụng trọng số, khi đó các trọng số này sẽ được sử dụng như độ đo khoảng cách, phụ thuộc vào cách thức biểu diễn của chúng. Các phương pháp phân cụm truyền thống dựa trên khoảng cách như K-Means đã cho thấy sự hiệu quả, đặc biệt trên các mạng vật lý như bản đồ các thành phố. Tuy nhiên, khi các cạnh không được đánh trọng số, chẳng hạn như đồ thị bạn bè, chúng ta sẽ rất khó trong việc định nghĩa một khoảng cách hợp lý. Chính vì thế mà việc áp dụng phương pháp dựa trên độ đo khoảng cách truyền thống cho các mạng xã hội sẽ không được tiện lợi. Thuật toán K-Means có thể mô tả chi tiết như sau: Khởi tạo một số lượng nhóm cho trước. Ở bước đầu tiên, chúng ta phân bố các điểm trọng tâm, chính là trung tâm của các nhóm và số lượng trọng tâm chính là số lượng nhóm đề xuất, sao cho chúng cách xa nhau nhất có thể. Mỗi đỉnh sẽ được chỉ định tới một trọng tâm gần nhất với nó. Ở bước 2, các trọng tâm được tính toán lại và được thay thế bởi trọng tâm mới được tìm thấy. Sau một số bước lặp, vị trí của các trọng tâm này không thay đổi nữa. 15 Phương án trên là không tối ưu và phụ thuộc vào sự lựa chọn khởi tạo ban đầu của số lượng nhóm và vị trí của các trọng tâm. 1.5.2. Phân cụm phân cấp Phân cụm phân cấp là một trong số các phương pháp phân nhóm phổ biến nhất cho các mạng xã hội. Cho một đồ thị với N đỉnh và ma trận tương đương A của nó, phương pháp phân cụm phân cấp gồm các bước như sau: 1. Gán cho mỗi đỉnh trong N đỉnh nằm trong một nhóm khác nhau, tức là chúng ta sẽ có N nhóm. 2. Tìm hai nhóm gần nhau nhất và trộn chúng lại thành một nhóm. 3. Tính toán lại các độ tương tự giữa các cụm mới và cụm cũ. 4. Lặp lại bước thứ hai và thứ ba cho tới khi tất cả các đỉnh được đặt vào trong cùng một nhóm. 5. Một lát cắt ngang của cây phân cấp kết quả được biểu diễn dưới dạng biểu đồ dendrogram sẽ cho ta kết quả phân cụm cuối cùng. Hình 1.7: Cây phân cấp (dendrogram cho mô hình câu lạc bộ karate của Zachary [9] Đối với một đồ thị các mạng xã hội, phân cụm phân cấp của một đồ thị mạng xã hội bắt đầu bằng việc kết hợp hai nút có cạnh nối giữa chúng với nhau. Sau khi hoàn thành bước này, các cạnh không kết nối hai nút trong cùng một cụm sẽ được lựa chọn ngẫu nhiên để kết hợp các cụm mà mỗi nút của cạnh thuộc về các cụm khác nhau. Việc lựa chọn này là ngẫu nhiên bởi tất cả các khoảng cách được biểu diễn bởi các cạnh là như nhau (không có trọng số cạnh . Điểm bất lợi của phương pháp phân cụm phân cấp cho một đồ thị được chỉ ra như ở hình 1.8 dưới đây đó là sau một vài bước chúng ta bắt buộc phải kết nối hai điểm B và D, mặc dù chúng hoàn toàn nằm trong các nhóm khác nhau.