Phát hiện cộng đồng trong mạng xã hội khả năng ứng dụng cho mạng Go.vn.

- Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 1 LỜI MỞ ĐẦU 1.
- Tính cấp thiết của đề tài Trên thế giới hiện nay có hàng trăm mạng xã hội đang hoạt động như Facebook, MySpace…tại Châu âu và Bắc Mỹ, CyWorld, Mixi…tại Châu Á.
- Việt Nam cũng xây dựng các mạng xã hội riêng như Zing Me, YuMe, Tamtay,GoVN.
- Mạng xã hội ngày nay không chỉ là vấn đề trong lĩnh vực công nghệ thông tin đơn thuần mà đ ã trở nên rất gần gũi trong kinh doanh và đời sống.
- Nói tới nguồn gốc của mạng xã hội phải nói tới lý thuyết đồ thị lần đầu tiên được đưa ra bởi Euler vào năm 1736.
- Từ đó đến nay người ta thực hiện rất nhiều nghiên cứu về đồ thị và các tính chất của nó.
- Vào thế kỷ XX, đồ thị trở nên rất phổ biến vì ứng dụ ng rộng rãi của nó trong rất nhiều khía cạnh của đời sống như sinh học, xã hội học, công nghệ thông tin, mạng thông tin…Vào năm 1930, bài toán phân tích mạng xã hội ra đời và trở thành chủ đề quan trọng nhất trong xã hội học.
- Ngày nay, việc phân tích và phát hiện cộng đồng trong mạng xã hội là một nhu cầu bức thiết vì ứng dụng quan trọng của cộng đồng trong các 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ị.
- Tại Việt Nam, với mong muốn xây dựng một mạng xã hội thuần Việt cho giới trẻ, đủ sức cạnh tranh với mạng Facebook đang chiếm thị phần đa số, Bộ thông tin và truyền thông đã yêu cầu Tổng công ty truyền thông đa phương tiện (VTC) xây dựng ý tưởng và triển khai dự án về một mạng xã hội như thế.
- Mặc dù có sự hỗ trợ của Chính phủ, của Bộ chủ quản, Go.vn vẫn là một mạng non trẻ, đứng trước không ít thách thức để xây dựng hình ảnh và đuổi kịp các mạng xã hội khác đã tồn tại và phát triển từ nhiều năm nay.
- Bởi vậy, bài toán phát hiện cộng đồng đối với Go.vn càng trở nên cần thiết hơn bao giờ hết.
- Là một thành viên tham gia xây dựng mạng Go.vn từ những ngày đầu, tác giả mong muốn từ những lý thuyết tiếp cận được về mạng xã hội có thể tìm ra một giải pháp hiệu quả để khai phá cộng đồng cho mạng Go.vn, ngày càng đưa mạng Go.vn trở nên gần gũi hơn với người dùng Việt Nam.
- Đó là lý do tôi đã lựa chọn đề Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 2 tài “ Phát hiện cộng đồng trong mạng xã hội và khả năng ứng dụng cho mạng Go.vn” cho luận văn thạc sỹ công nghệ thông tin của mình.
- Mục đích nghiên cứu Đề tài được nghiên cứu nhằm mục đích nâng cao khả năng phát hiện cộng đồng trong mạng Go.vn với bài toán cụ thế là phát hiện cộng đồng cùng click vào một quảng cáo trên hệ thống quản trị quảng cáo goZone.
- Phương pháp nghiên cứu Để giải quyết được bài toán về phát hiện cộng đồng cho mạng xã hội nói chung và mạng Go.vn nói riêng, tác giả đã sử dụng phương pháp phân tích, tổng hợp, so sánh để khái quát các lý thuyết về mạng xã hội từ các nghiên cứu trước đây.
- Bên cạnh đó, tác giả đặc biệt chú trọng đến phương pháp mô hình hóa, phương pháp định lượng để giải quyết các thuật toán về phát hiện cộng đồng trong mạng xã hội.
- Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu của đề tài là mạng xã hội và các thuật toán phát hiện cộng đồng trong mạng xã hội.
- Cụ thể về mạng xã hội, tác giả nghiên cứu các vấn đề lý thuyế t liên quan tới mạng xã hội và thực tiễn mạng Go.vn.
- Về các thuật toán, ngoài những vấn đề lý thuyết chung về các thuật toán phát hiện cộng đồng, tác giả đi sâu nghiên cứu họ thuật toán Girvan-Newman, tập trung vào thuật toán CONGA (Cluster Overlapping Newman Girvan Algorithm) được Steve Gregory đề xuất năm 2007.
- Từ đó, tác giả xây dựng một mô hình áp dụng thuật toán CONGA phát hiện cộng đồng trong mạng xã hội Go.vn.
- Bố cục luận văn Luận văn được bố cục thành 3 chương chính như sau : Chương 1 : Tổng quan về mạng xã hội và phát hiện cộng đồng trong mạng xã hội Chương 2 : Tổng quan về các thuật toán phát hiện cộng đồng trong mạng xã hội Chương 3 : Mô hình phát hiện cộng đồng trong mạng Go.vn Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 3 CHƯƠNG 1: TỔNG QUAN VỀ MẠNG XÃ HỘI VÀ PHÁT HIỆN CỘNG ĐỒNG TRONG MẠNG XÃ HỘI 1.1.
- Tổng quan về mạng xã hội 1.1.1.
- Các nghiên cứu về mạng xã hội Jiyang Chen (2010) cho một giới thiệu khái quát về sự phát triển của quá trình nghiên cứu về mạng xã hội (social network).
- Nhu cầu phân tích mạng xã hội được bắt đầu từ những năm 1930 và nhanh chóng trở thành chủ đề quan trọng nhất trong xã hội học.
- Sáng tạo của Moreno là ông đã tạo ra được một “sociogram”, một cách để biểu diễn các tính chất của một cấu hình mang tính xã hội.
- Khái niệm “sociogram” sau này cũng được dùng để chỉ biểu diễn đồ thị của các mạng xã hội.
- Freeman, Visualizing social networks, Journal of Social Structure Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 4 Trong khi đó K.Lewin, trong một nghiên cứu về hành vi của các nhóm, cho rằng các tính chất về mặt cấu trúc của một đơn vị xã hội có thể biểu diễn một cách toán học bằng lý thuyết đồ thị và cấu trúc liên kết.
- Những ý tưởng này của Lewin và Heider sớm được phát triển bởi Frank Harary và Dorwin Cartwright, trong đó nhóm tác giả sử dụng lý thuyết đồ thị để xây dựng một công cụ khá hữu hiệu trong nghiên cứu mạng xã hội.
- Trong những năm 1950, các nhà nghiên cứu từ khoa Xã hội và Nhân chủng học của trường đại học Manchester, được dẫn đầu bởi John Barnes, đã bắt đầu đặt trọng tâm nghiên cứu của họ vào các mối quan hệ giữa các đối tượng trong xã hội, thay vì thiết lập các chuẩn mực và định mức cho toàn bộ cấu trúc xã hội như trước và tìm hiểu xem cấu trúc của các mối quan hệ giữa các cá thể trong xã hội có ảnh hưởng như thế nào đến toàn bộ xã hội.
- Từ đó, thuật ngữ “mạng xã hội”, lần đầu tiên được nhắc đến bởi Barnes năm 1954, đã đánh dấu sự phát triển chính thức của việc phân tích cấu trúc mạng xã hội.
- Dựa vào các nghiên cứu của Barnes và các cộ ng sự, vào những năm 1969 và 1970, các nhà nghiên cứu ở đại học Harvard dẫn đầu bởi Harrison C.White tiếp tục nghiên cứu và phát triển các khía cạnh toán học của mạng xã hội và biểu diễn rất nhiều khái niệm quan trọng trong xã hội học, ví dụ như khái niệm “vai trò xã hội”, sang công thức toán học và tìm cách mô hình hóa và tính toán chúng.
- Ý tưởng chính của nghiên cứu là việc phát hiện cấu trúc của các mạng xã hội không nên dựa vào các hạng mục nổi tiếng và đã được định nghĩa trước đó, mà phải dựa vào mối quan hệ giữa các cá thể trong mạng và cách thức mà các mối quan hệ này cấu tạo thành mạng như thế nào.
- Trong một nghiên cứu sau đó, Mark Granovetter đề ra giả thiết liên kết yếu, với nội dung chính là “nếu A có liên kết mạnh tới B và C thì rất có khả Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 5 năng giữa B và C tồn tại một liên kết”.
- Trên thực tế, người ta đã tìm hiểu được nhiều mạng xã hội thỏa mãn giả thuyết của Milgram, bao gồm các mạng cộng tác khoa học và đồ thị các cuộc gọi điện thoại.
- Tóm lại phân tích mạng xã hội được sinh ra từ các nhu cầu chung của xã hội học, nhân chủng học, toán học, sinh học và kinh tế học.
- Ngày nay phân tích mạng xã hội còn được áp dụng trong nhiều lĩnh vực như kinh tế, tài chính…Tuy nhiên trong thời đại bùng nổ thông tin hiện nay với số lượng và kích thước các mạng xã hội tăng lên không ngừng, các vấn đề về quản lý thông tin xã hội trở nên khó khăn hơn.
- Do đó, cần thiết phải áp dụng các kỹ thuật khoa học máy tính để phân tích chính xác và hiệu quả hơn các cấu trúc xã hội trên các mạng xã hội.
- Khái niệm mạng xã hội Thuật ngữ “mạng xã hội”, lần đầu tiên được Barnes nhắc đến vào năm 1954, đã đánh dấu sự phát triển chính thức của việc phân tích cấu trúc mạng xã hội.
- Mô Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 6 hình mạng xã hội thực tế xuất hiện lần đầu tiên năm 1995 với sự ra đời của trang Classmate với mục đích kết nối bạn học.
- Theo Garton và cộng sự (1997) mạng xã hội là “một tập hợp những người được kết nối với nhau bằng một tập hợp các mối quan hệ, ví dụ như tình bạn, cộng sự hay trao đổi thông tin”.
- Mạng xã hội là một cấu trúc mang tính xã hội được cấu tạo từ các nút và các cung, trong đó các nút được liên kết với nhau bởi một hoặc nhiều cung, thể hiện mối quan hệ cụ thể [1].
- Biểu diễn mạng xã hội Để biểu diễn mạng xã hội, các nhà phân tích mạng xã hội sử dụng 2 cấu trúc, đó là đồ thị và ma trận kề.
- Thật vậy, đồ thị là một trong những công cụ rất hữu hiệu để thể hiện các thông tin về mạng xã hội.
- Trong biểu diễn đồ thị của mạng xã hội, các đỉnh được dùng để biểu diễn các nút và các cạnh dùng để biểu diễn liên kết giữa các nút.
- Các cạnh trong đồ thị có thể vô hướng hay có hướng, cũng có thể được đánh trọng số tùy thuộc vào nhu cầu biểu diễn liên kết là vô hướng hay có hướng, trọng số như thế nào.
- Trong mạng xã hội thực tế, sự phân bố của các cạnh là không đều, với mức độ tập trung cao của các cạnh trong một số nhóm các đỉnh đặc biệt, và giữa các nhóm đó số lượng cạnh tập trung là thấp.
- Một số nhóm các đỉnh có liên kết chặt chẽ Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 7 với nhau thành các cụm, và giữa các cụm đó được nối với nhau chỉ bằng một vài cạnh khác.
- Tính chất đó của các mạng trên thực tế được gọi là tính cộng đồng (community) hay còn gọi là sự phân cụm [3].
- Đây là một tính chất quan trọng của mạng xã hội và đang ngày càng được nhiều nhà khoa học quan tâm nghiên cứu.
- Một số ví dụ về tính cộng đồng như các trang web về một chủ đề có thể được kết nối tới các trang web khác cùng với chủ đề tương tự, hay các nhà khoa học cùng viết chung một bài báo hoặc cuốn sách, các nhân viên cùng thuộc một phòng ban trong một công ty,… Tính cộng đồng được coi là một tính chất quan trọng nhất của mạng xã hội [3].
- Sự phát hiện các cộng đồng trong mạng xã hội này là mục tiêu cơ bản của nhiều nghiên cứu về mạng xã hội, ví dụ như xếp hạng thực thể, phân lớp,…Người ta đặt ra khái niệm “cộng đồng” trong mạng xã hội để chỉ ra các nhóm như vậy.
- Từ đó người ta định nghĩa khái niệm “khai phá cộng đồng”, là quá trình nghiên cứu và phân tích các mối quan hệ trong một mạng xã hội, nhằm mục tiêu tìm ra các cộng đồng trong mạng xã hội, và trích xuất được các thành phần ẩn trong các cộng đồng đó.
- Khai phá cộng đồng đã dành được sự chú ý của nhiều nhà khoa học trong nhiều lĩnh vực, đặc biệt gần đây là trong lĩnh vực Khai phá dữ liệu.
- Cộng đồng trong mạng xã hội và bài toán khai phá cộng đồng 1.2.1.
- Cộng đồng trong mạng xã hội Khái niệm cộng đồng, được định nghĩa là tập các thực thể có những tính chất tương tự nhau và/hoặc cùng đóng một vai trò trong một mạng xã hội.
- Hình 1.2 dưới đây chỉ ra một ví dụ về đồ thị với cấu trúc cộng đồng trong đó.
- Hình 1.2: Đồ thị đơn giản với 3 cộng đồng được giới hạn bằng nét gạch nối Nguồn: Fortunato và Castellano, 2009 Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 8 Theo [6], một tập hợp các đỉnh trên đồ thị được coi là một cộng đồng nếu mật độ cạnh bên trong nó cao hơn so với mật độ của các cạnh giữa đỉnh của nó và những cạnh bên ngoài.
- Dưới đây là một vài ví dụ khá điển hình về mạng xã hội và cộng đồng trong mạng xã hội.
- Hình 1.3: Mạng lư ới của các thành viên trong câu lạc bộ Karate (Zachary,1977) Nguồn: Donetti and Mun~oz, 2004 Đây làm một đồ thị nổi tiếng thường xuyên được sử dụng như là một tiêu chuẩn để kiểm tra phát hiện cộng đồng.
- Người ta đã quát sát mạng xã hội này trong khoảng ba năm, các cạnh kết nối cá nhân được quan sát thông qua các tương tác bên ngoài và các hoạt động củ a Câu lạc bộ.
- Câu hỏi đặt ra ở đây Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 9 là liệu từ bản gốc cấ u trúc mạng, có thể suy được ra các thành phần của hai nhóm này hay không? Hình 1.4: Mô hình mạng lưới cộng tác của các nhà khoa học làm việc tại SFI Nguồn: Girvan and Newman, 2002 Hình 1.4 hiển thị các thành phần kết nối lớn nhất trong mạng lưới các cộng tác của các nhà khoa học làm việc tại Viện Santa Fe (SFI).
- Đồ thị bao gồm 118 đỉnh đại diện cho các nhà khoa học cư trú tại SFI và các cộng tác viên của họ.
- Ở mạng này ta quan sát được rất nhiều cộng đồng, mỗi cộng đồng biểu hiện cho tất cả cá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 cộng đồng 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 cộng đồng 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.
- Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 10 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 (Hình 1.5) Mạng có tất cả 62 đỉnh và mỗi 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.
- Mỗi nhóm trong đồ thị là tương đối gắn kết, với một vài đồ thị con đầy đủ 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 cộng đồng trong mạng xã hội.
- Từ đó, việc xác định cộng đồng có thể được xem như là việc tìm kiếm các cụm nút phân nhóm.
- Trong xã hội hiện nay xuất hiện nhiều nhóm hoặc tổ chức với kích cỡ khác nhau, ví dụ như gia đình, nhóm các bạn bè hoặc đồng nghiệp, thành phố, quốc gia… Sự khuếch tán của Internet ngày nay cũng sinh ra nhiều nhóm ảo trên Web, hay còn được gọi là các cộng đồng trực tuyến.
- Các cộng đồng xã hội đã được nghiên cứu trong một thời gian rất dài và thường xuyên xuất hiện trong nhiề u các hệ thống mạng trong sinh học, khoa học máy tính, công nghệ, chính trị, kinh tế, …ví dụ như : các nhóm protein với các chức năng tương tự nhau trong tế bào trong mạng tương tác protein, các nhóm trang web thảo luậ n về cùng một chủ đề hoặc các chủ đ ề tương tự nhau trên World Wide Web,… Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 11 Hình 1.5: Mạng biểu diễn loài cá heo sống ở Doubtful Sound, New Zealand Nguồn: Arenas et al., 2008b Với sự phát triển nhanh chóng của các cộng đồng trong thời điểm hiện tại và nhu cầu cần thiết về tìm hiểu tính cộng đồng trong các mạng xã hội, bài toán phát hiện cộng đồng 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 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 Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 12 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.
- Ứng dụng phát hiện cộng đồng trong mạng xã hội Việc phát hiện cộng đồng có rất nhiều ứng dụng cụ thể.
- 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 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.
- Xác đinh cộng đồng trong đồ thị cũng là một chủ đề phổ biến trong khoa học máy tính, trong đó có hai lĩnh vực điển hình là học máy và khai phá quan điểm.
- 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 1970.
- Khai phá cộng đồng ứ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 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.
- Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 13 Tóm lại, cộng đồng 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 cộng đồng trong mạng xã hội vì các lý do đã được nêu ở trên.
- Phát hiện cộng đồng trong mạng xã hội Phát hiện cộng đồng trong mạng xã hội có ý nghĩa rất quan trọng .
- 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 cấu trúc cộng đồng 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 cộng đồng mà trong đó mỗi cộng đồng lại được cấu tạo từ một tập các cộng đồng khác, các cộng đồng con đó lại đ ư ợc cấ u tạo bằ ng một tập các cộng đồng 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.
- 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 Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 14 được xây dựng.
- Phát hiện cộng đồng là một lĩnh vực nghiên cứu mới, trong đó tập trung vào việc phát hiện và tìm ra đặc tính của cấu trúc mạng đã nhận được sự chú ý đáng kể trong những năm vừa qua.
- Một cộng đồng có thể được định nghĩa như một nhóm của các thực thể cùng chia sẻ những tài sản tương tự nhau, hoặc kết nối với nhau thông qua mối quan hệ được lựa chọn, xác định các kết nối và định vị các thực thể trong cộng đồng khác nhau là mục tiêu chính của nghiên cứu khai phá cộng đồng.
- Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 15 CHƯƠNG 2: TỔNG QUAN VỀ CÁC THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG TRONG MẠNG XÃ HỘI 2.1.
- Khái quát về các thuật toán phát hiện cộng đồng Santo Fortunato [3] đã tổng hợp các phương pháp/thuật toán phát hiện cộng đồng trong mạng xã hội.
- Theo tác giả, các nhóm phương pháp điển hình là: (1) Các phương pháp truyền thống (2) Các thuật toán chia (3) Các phương pháp dựa trên mô đun hóa (4) Các thuật toán dựa trên phổ (5) Các thuật toán động (6) Các phương pháp dựa trên suy luận thống kê (7) Các phương pháp phát hiện chồng chéo cộng đồng (8) Các phương pháp nhiều lời giải và hệ thống phân cụm phân cấp (9) Các phương pháp phát hiện cộng đồng động Các phương pháp truyền thống bao gồm 4 phương pháp, đó là phân vùng đồ thị, phân cụm phân cấp, phân cụm theo vùng và phân cụm theo phổ.
- Phương pháp phân vùng đồ thị được áp dụng chủ yếu trong tính toán song song, phân vùng mạch và một số các giải thuật nối tiếp .
- Phương pháp phân cụm phân cấp thường được sử dụng khi mạng xã hội có cấu trúc phân cấp ( tức một mạng chia làm nhiều cộng đồng con, mỗi cộng đồng con chia ra làm nhiều cộng đồng con khác, cứ như vậy.
- Ý tưởng cơ bản của thuật toán phân cụm phân cấp là xác định đ ư ợc sự tương tự của các đỉnh trong đồ thị mạng bằng một độ đo tương tự, sau đó các đỉnh có độ tương tự cao được xếp vào Phát hiện cộng đồng trong mạng xã hội – khả năng ứng dụng cho mạng go.vn Nguyễn Thanh Tuấn 16 cùng một nhóm.
- Phương pháp phân cụm phân cấp được áp dụng phổ biến trong phân tích mạng xã hội, sinh học, kỹ thuật, tiếp thị,… Phương pháp phân cụm theo vùng dựa trên ý tưởng như sau: định nghĩa trước một số k là số lượng các cụm, ta biểu diễn đồ thị trong một không gian metric sao cho mỗi đỉnh của đồ thị được biểu diễn bằng một điểm trong không gian đó.
- Sau đó người ta tính toán khoảng cách giữa các điểm trong không gian và lấy đó làm độ đo sự khác nhau giữa các đỉnh trong đồ thị.
- Phương pháp phân cụm bao gồm việc chuyển hóa các tập đối tượng thành các điểm trong một không gian, mà các điểm này là các thành phần của vector đặc trưng, sau đó các điểm được phân cụm dựa trên các phương pháp chuẩn, ví dụ phương pháp phân cụm k-mean Các phương pháp áp dụng thuật toán phân chia đều dựa trên mục đích cơ bản là tìm ra được các cạnh nối giữa các đỉnh của các cộng đồng khác nhau, sau đó loại bỏ chúng khỏi đồ thị.
- Như vậy các cụm trong đồ thị sẽ bị ngắt kết nối với nhau, từ đó ta có thể phân đồ thị thành các cộ ng đồ ng.
- Điểm mấu chốt của phương pháp này là xác định được tính chất nào đó của các cạnh nối các cộng đồng trong đồ thị, từ đ ó có thế phát hiện và loại bỏ chúng ra khỏi đồ thị.
- Phương pháp áp dụng thuật toán chia có thể coi là một kiểu thuật toán phân cụ m phân cấp, chỉ khác là thay vì tìm các cạnh có độ tươ ng đồng cao để ghép các đỉnh của các cạnh đó thành cộng đồng, thì ở đây người ta tìm cách loại bỏ các cạnh nối giữa các cộng đồng để thu được từng cộng đồng riêng biệt

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt