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 Đồ thị là công cụ phổ biến và quan trọng để biểu diễn mạng xã hội. Chương này giới thiệu một cách tổng quan những vấn đề lý thuyết liên quan đến đồ thị, đồ thị mạng xã hội, đến cấu trúc cộng đồng của mạng xã hội, các phương pháp phát hiện cấu trúc cộng đồng, các độ đo thường sử dụng trong quá trình phân tích, các tiêu chuẩn thường được áp dụng để đánh giá chất lượng cấu trúc cộng đồng, làm cơ sở cho việc đánh giá hiệu quả của các thuật toán đề xuất ở các chương sau.1 Giới thiệu chung Dữ liệu lớn tạo ra một sự bùng nổ các phương pháp, các kỹ thuật, các công nghệ khai phá dữ liệu và phát hiện tri thức, một phần bởi kích thước thông tin rất lớn, một phần bởi thông tin đa dạng, mở rộng hơn về các chủng loại phi cấu trúc và nội dung của dữ liệu. Đồ 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ấu trúc dữ liệu đồ thị là một tập hợp 9 các nút có dữ liệu và được kết nối với các nút khác. Đồ thị chứa đỉnh (đại diện cho các đối tượng) và các cạnh nối các đỉnh (đại diện cho mối quan hệ giữa các đối tượng). Đồ thị được sử dụng trong vô vàn lĩnh vực nghiên cứu, từ khai phá dữ liệu, xử lý ngôn ngữ tự nhiên, mô phỏng thế giới thực, đến phân tích mạng xã hội và khai thác thông tin,. Về mặt lý thuyết, người ta thường đồng nhất mô hình dữ liệu đồ thị với khái niệm hệ thống mạng và mạng xã hội.1 Cấu trúc dữ liệu đồ thị có mặt ở khắp nơi: Mạng đồng biểu hiện; mạng xã hội; các luồng chương trình; trong hợp chất hóa học và cấu trúc protein,.
Bản thân mỗi đồ thị còn có thể hàm chứa rất nhiều thông tin giá trị cho các ứng dụng thực tiễn, vì vậy khai phá dữ liệu thực hiện 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, đặc biệt 10 trong những thập kỷ gần đây. Khai phá đồ thị là một nhánh nghiên cứu trong khai phá dữ liệu. Đó là một trong những cách tiếp cận mới để khai thác tập dữ liệu được biểu thị bằng cấu trúc đồ thị. Khai phá đồ thị xuất hiện trong nhiều ứng dụng của các lĩnh vực xã hội, tự nhiên, bao gồm: tin sinh học, phản ứng hóa học, cấu trúc dòng chương trình, mạng máy tính, mạng xã hội,.
Trong khai phá dữ liệu đồ thị, việc phát hiện cấu trúc cộng đồng là một nhiệm vụ phổ biến và quan trọng bậc nhất, song cũng đầy thách thức, đặc biệt khi quy mô của đồ thị mạng xã hội ngày càng trở nên to lớn. Đã có 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, nhưng hầu hết chưa thực sự mang lại hiệu quả đối với các đồ thị mạng xã hội quy mô lớn. Luận án thực hiện đề xuất một số thuật toán mới phát hiện cấu trúc cộng đồng, 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ạng xã hội và đồ thị mạng xã hội 1.1 Mạng xã hội Theo Fortunato và các cộng sự [21] 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 hợp các mối quan hệ, liên kết, như quan hệ bạn bè, gia đình, cộng sự hay trao đổi thông tin,. 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ụ,.
Khi nghiên cứu về mạng xã hội, người ta còn gọi các thực thể này là các tác nhân (agent), bởi tính tương tác và ảnh hưởng của chúng đối với môi trường xung quanh (ít nhất là với các láng giềng của chúng). Các tác nhân luôn có xu hướng liên kết với nhau (có thể dựa trên tính tương đồng trong sự lựa chọn nào đó, hoặc mối quan hệ khăng khít về một lĩnh vực nào đó, hoặc sự đồng cảm theo sở thích/không thích, .) trong một nền tảng được chia sẻ và tạo thành các cụm ảo hoặc cộng đồng.2 Một số đặc tính của mạng xã hội Mạng xã hội có những đặc tính cơ bản [9, 10, 104] sau: • Dựa vào người dùng (User-based): Các mạng xã hội trực tuyến (Face- book, Twitter, Youtube,. ) được xây dựng và định hướng bởi chính người dùng. Người dùng thực hiện mở rộng các nội dung trao đổi, thảo luận với nhau trên mạng.
Nội dung đó được xác định bởi bất kỳ ai có tham gia vào tổ chức. • Tương tác (Interactive): Mạng xã hội hiện đại gồm các tác nhân thường xuyên tương tác thông qua các mối liên kết với nhau. Nghĩa là một mạng xã hội không chỉ là một bộ sưu tập các phòng chat, diễn đàn,. mà còn chứa các dịch vụ, chơi trò chơi, quảng cáo, tiếp thị, bán hàng online, quảng bá thông tin,.
Vì vậy, mạng xã hội càng ngày càng trở nên chuẩn mực, phổ biến, hấp dẫn và thu hút người dùng nhiều hơn bởi tính năng tương tác vượt trội so với sử dụng Internet thông thường. • Hướng đến cộng đồng (Community-driven): Mạng xã hội thể hiện hiệu ứng cộng đồng mạnh mẽ. Đó là, một nhóm những người có xu hướng tương tác với nhau nhiều hơn những người bên ngoài nhóm. Phát hiện các nhóm gắn kết trong một mạng xã hội (được gọi là phát hiện cấu trúc cộng đồng, gọi tắt là cộng đồng) là một vấn đề quan trọng và cốt lõi trong phân tích mạng xã hội.
• Các mối quan hệ (Relationships): Các mạng xã hội phát triển mạnh mẽ về các mối quan hệ. Càng có nhiều mối quan hệ trong mạng, các tác nhân càng thiết lập được vai trò trung tâm của mạng đó. Mạng xã hội cung cấp tiềm năng rất lớn về tương tác và giao tiếp giữa rất nhiều các thành viên trong mạng ở khắp mọi nơi, không phụ thuộc vào không gian địa lý, tạo môi trường cho việc tương tác và chia sẻ thông tin giữa các thành viên trong mạng. • Cảm xúc về nội dung (Emotion over content): Đặc điểm độc đáo của mạng xã hội là yếu tố cảm xúc và nhạy cảm.
Ngày nay, các trang web 12 thực sự mang đến cho người dùng về mặt cảm xúc và cảm giác rằng mối quan hệ, như bạn bè của họ luôn ở trong phạm vi kiểm soát. Khi mạng xã hội ngày càng trở nên phổ biến và nổi bật, câu hỏi rõ ràng đầu tiên đặt ra là: làm thế nào để trích xuất được những thông tin, tri thức có ý nghĩa từ những dữ liệu này? Để tìm kiếm câu trả lời, đòi hỏi phải có những phương pháp nghiên cứu và kỹ thuật phân tích phù hợp, hiệu quả nhất.3 Đồ thị mạng xã hội và cấu trúc cộng đồng của mạng xã hội 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) [34, 55, 82, 83]. Đồ thị mạng xã hội là đồ thị G = (V, E) [55], trong đó V là tập các nút (đỉnh) và E là tập các cạnh (cung). Tập V biểu diễn cho các thành viên (tác nhân) của mạng xã hội, tập E thể hiện mối quan hệ xã hội giữa các thành viên với nhau.
Đồ thị G = (V, E) là vô hướng nếu các cạnh (u, v) ∈ E không phân biệt thứ tự, ngược lại là đồ thị có hướng. Hai nút u và v trong đồ thị G được gọi là liền kề (lân cận) nếu (u, v) ∈ E , hoặc (v, u) ∈ E. Nếu e = (u, v) thì e gọi là cạnh liên thuộc với các nút u và v. Thông thường, đồ thị mạng xã hội là đồ thị đơn vô hướng và liên thông, ví dụ đồ thị mạng bạn bè trên Facebook.
Nhưng chúng cũng có thể là đồ thị có hướng, như đồ thị mạng xã hội những người theo dõi trên Twitter hoặc Google+. Việc phân tích đặc điểm tính chất của mỗi đồ thị mạng xã hội dựa nhiều vào lý thuyết đồ thị, bao gồm việc phân tích, xác định vai trò các nút và các cạnh trong đồ thị. Trong luận án có sử dụng một số định nghĩa và khái niệm cơ bản của lý thuyết đồ thị, cũng như hệ thống ký hiệu và cách biểu diễn thông thường cho một mạng xã hội theo các tài liệu tham khảo [55, 56, 57, 58]. Theo lý thuyết đồ thị, cho mạng xã hội G = (V, E), cấu trúc cộng đồng (community structure) [58] là một đồ thị con của G, có tập đỉnh 13 C là tập con các đỉnh của V, sao cho với mỗi đỉnh v ∈ C , có nhiều cạnh kết nối v với những đỉnh khác trong C (liên thông mạnh) và ít cạnh kết nối v với những đỉnh w khác thuộc V-C (liên thông yếu).
Nói cách khác một cấu trúc cộng đồng (gọi tắt là cộng đồng) được tạo ra bởi một tập hợp các tác nhân có tương tác thường xuyên với nhau hơn so với những tác nhân khác ngoài cộng đồng. Thực tế, cộng đồng có thể là một tập hợp các tác nhân như: bạn bè, đồng nghiệp, nhóm những người có cùng sở thích, cùng chuyên môn, cùng mối quan tâm,. trên mạng xã hội. 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. 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ị. Có thể kể ra rất nhiều ứng dụng sinh động ngay trong cuộc sống quanh ta.
Chẳng hạn, với các mối quan hệ hình thành từ các thông tin như sở thích của khách hàng, quan hệ bạn bè, hoặc lịch sử mua hàng, trình độ chuyên môn,. được mô tả bằng đồ thị; các cộng đồng trên đó có thể được hình thành và được phát hiện.