BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC LẠC HỒNG ĐỖ VĂN MẠNH NGHIÊN CỨU VÀ PHÁT TRIỂN THUẬT TOÁN TÌM PHẦN TỬ CHÍNH YẾU TRONG MẠNG XÃ HỘI VÀ ỨNG DỤNG LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN Đồng Nai, năm 2013 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC LẠC HỒNG ĐỖ VĂN MẠNH NGHIÊN CỨU VÀ PHÁT TRIỂN THUẬT TOÁN TÌM PHẦN TỬ CHÍNH YẾU TRONG MẠNG XÃ HỘI VÀ ỨNG DỤNG Chuyên ngành: Công nghệ thông tin Mã số : 60.01 LUẬN VĂN THẠC SĨ CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. ĐỖ PHÚC Đồng Nai, năm 2013 LỜI CAM ĐOAN Tôi cam đoan rằng, ngoại trừ các kết quả tham khảo từ các công trình khác và một số lý thuyết trên internet đã ghi rõ nguồn tham khảo trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chưa có phần nội dung nào của luận văn này được nộp để lấy bằng cấp ở trường này hoặc trường khác. Ngày tháng năm 2013 Đỗ Văn Mạnh LỜI CẢM ƠN Tôi xin gửi lời tri ân đến Thầy Cô, bạn bè và gia đình, những người đã hỗ trợ tôi rất nhiều về kiến thức chuyên môn cũng như tinh thần trong quá trình tôi thực hiện luận văn này. Xin đặc biệt cảm ơn Thầy PGS.
Đỗ Phúc, người đã cung cấp và truyền dạy cho tôi những kiến thức rất hữu dụng, giúp tôi hoàn thiện hơn về cách suy nghĩ cũng như tư duy về phương pháp nghiên cứu khoa học đến những công việc cụ thể trong luận văn này. TÓM TẮT ĐỀ TÀI Luận văn này tập trung nghiên cứu một vấn đề mà cộng đồng khoa học đang rất quan tâm đó là bài toán tìm phần tử chính yếu (Key Player) trong mạng xã hội. Bài toán tìm phần tử chính yếu là bài toán xác định một hoặc một nhóm các phần tử trong đồ thị mà nếu mất chúng đi thì sẽ làm gãy các liên kết trong đồ thị. Dựa vào bài toán tìm đường đi ngắn nhất qua các đỉnh của một đồ thị có hướng và các độ đo Centrality của nó.
Mạng xã hội được xem là đồ thị có hướng, các thực thể trong mạng là các đỉnh của đồ thị, mối quan hệ giữa các thực thể trong mạng là các cạnh của đồ thị. Bài toán đặt ra là xây dựng thuật toán tìm đường đi ngắn nhất đi qua các đỉnh của đồ thị, kết hợp với các độ đo Centrality từ đó xác định thực thể nào là quan trọng và có tầm ảnh hưởng lớn nhất tới các thực thể khác trong mạng xã hội. Luận văn tóm tắt lý thuyết các khái niệm liên quan đến mạng xã hội, kỹ thuật phân tích mạng, phần tử chính yếu, độ đo Centrality trong mạng xã hội. Trên cơ sở đó, tác giả luận văn thiết kế và xây dựng hệ thống để thực nghiệm thuật giải tìm tập Key player trên các tập dự liệu thực tế.
DANH MỤC NHỮNG TỪ VIẾT TẮT TRONG LUẬN VĂN BFS : Breadth First Search CNTT : Công Nghệ Thông Tin JUNG : Java Universal Network / Graph Framework MXH : Mạng Xã Hội SNA : Social Network Analysis DANH MỤC HÌNH Hình 1.1: Mô tả mạng xã hội. 1: Mô hình mạng Xã hội (Social Network).2: Mô hình mạng xã hội Facebook.3: Mô hình các thành viên của mạng Twitter.4: Mô hình phân biệt Follower và Friend trong mạng Twitter. 5: Giao diện chính của mạng Facebook .6: Lượng người truy cập Facebook trong 1 tuần từ 29/07/2012 đến 04/08/2012 (nguồn socialbakers.7: Biểu diễn tập đỉnh trong mô hình mạng.8: Diễn tả đồ thị có hướng và đồ thị vô hướng .9: Ví dụ đường đi trong mạng .10: Mô tả các thành viên trong mạng xã hội .11: Ví dụ một đồ thị gồm 7 đỉnh .12: Một đồ thị gồm 5 đỉnh để tìm Degree Centrality .13: Một đồ thị gồm 10 đỉnh để tìm Degree Centrality .14: Mô tả vị trí Betweenness Centrality.15: Một mạng xã hội dùng để tính Betweenness Centrality .16: Tầm ảnh hưởng của độ đo trung tâm dựa trên trung gian .17: Hình minh họa ví dụ tìm Closeness centrality .18: Mô tả mức độ Closeness Centrality của mạng.19: Độ đo trung tâm dựa trên trung gian, sự lân cận và trị vectơ đặc trưng 32 Hình 2.20: Hệ số gom cụm của các đỉnh trong đồ thị .21: Ví dụ một Mạng xã hội .22: Mô tả vị trí của Key player trong mạng .1: Cấu trúc mạng xã hội .2: Cách thức Duyệt đỉnh trong đô thị.1: Các bước thực hiện chương trình .2: Tập dữ liệu Karate.xml chưa được xử lý .3: Tập dữ liệu dolphins.xml chưa được xử lý .4: Danh sách Tập đỉnh Karate .5: Danh sách Tập cạnh Karate .6: Danh sách Tập đinh Dolphins .7: Danh Sách Tập Cạnh Dolphins .8: Đồ thị biểu diễn tập dữ liệu Karate .9: Đồ thị biểu diễn tập dữ liệu Dolphins .10: Màn hình báo cáo kết quả. 11 Lưu trữ đồ thị thành ma trận kề.
12: Lưu trữ đồ thị thành danh sách liên thuộc. 13: Lưu trữ đồ thị thành danh sách liền kề.14: Giao diện nạp dữ liệu.15: Giao diện Vẽ đồ thị trực quan .16: Tính Degree Centrality.17: Tính Betweenness Centrlity .18 Tính Closeness Centrality .19: Hiển thị kết quả của chương trình .20: Mô tả tập dữ liệu thực nghiệm .21: Giao diện kết quả cuối cùng của chương trình. 67 DANH MỤC BẢNG Bảng 2.1: Độ đo Degree Centrality của các đỉnh sau khi tính toán .2: Độ đo Degree Centrality cho đồ thị gồm 10 đỉnh .3: Độ đo Betweenness của đồ thị .4: Các đường đi ngắn nhất của tất cả các đỉnh trong đồ thị .5: Độ đo Closeness Centrality của Đồ thị .6: Mức độ Closeness Centrality của mạng .1: Cách thức duyệt đường đi của đồ thị bằng Thuật toán BFS .1: Cách thức lưu trữ dữ liệu đồ thị bằng Danh sách liên thuộc.2: Cách thức lưu trữ dữ liệu đồ thị bằng Danh sách liên kề. 62 MỤC LỤC * CHƢƠNG 1: TỔNG QUAN.
Giới thiệu đề tài. Lý do chọn đề tài. Mục tiêu của đề tài. Phạm vi nghiên cứu của đề tài.4 CHƢƠNG 2: CƠ SỞ LÝ THUYẾT.
Tổng quan về mạng xã hội. Các Mạng Xã hội thông dụng hiện nay. Mạng xã hội Twitter. Mạng xã hội Facebook.
Các khái niệm cơ bản trong việc tổ chức mạng xã hội. Đường đi và đường đi ngắn nhất trong mạng. Kỹ thuật phân tích mạng xã hội (Social Network Analysis – SNA). Ứng dụng thực tế.
Các độ đo trung tâm trong mạng. Độ đo trung tâm theo bậc - Degree Centrality. Độ đo trung tâm dựa trên trung gian. Độ đo trung tâm theo sự lận cận - Closeness Centrality.
Độ đo trung tâm dựa trên trị vectơ đặc trưng. Hệ số gom cụm trong mạng – Clustering Coefficient. Phần tử chính yếu .35 CHƢƠNG 3: BÀI TOÁN TÌM PHẨN TỬ CHÍNH YẾU TRONG MXH. Bài toán tìm phần tử chính yếu trong mạng xã hội.
Phát biểu bài toán. Ứng dụng của bài toán tìm phần tử chính yếu. Thuật giải tìm phần tử chính yếu. Thuật giải tìm Degree Centrality.
Thuật giải tìm Betweenness Centrality. Thuật giải tìm Closeness Centrality. Thuật giải tìm đường đi ngắn nhất từ một đỉnh đến tất cả các đỉnh còn lại trong đồ thị.48 CHƢƠNG 4: THIẾT KẾ XÂY DỰNG CHƢƠNG TRÌNH VÀ THỰC NGHIỆM. Giai đoạn 1: Thu thập và rút trích dữ liệu.
Giai đoạn 2: Xử lý dữ liệu. Tổ chức cơ sở dữ liệu. Các phương pháp lưu trữ dữ liệu. Cấu trúc ma trận kề.
Danh sách liên kết. Xây dựng hệ thống giải quyết bài toán tìm phần tử chính yếu. Kết quả thực nghiệm.66 CHƢƠNG 5: KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN. Những đóng góp của đề tài.
Hạn chế của đề tài, cách khắc phục. Hướng phát triển.70 TÀI LIỆU THAM KHẢO -1- CHƢƠNG 1: TỔNG QUAN Xu hướng giao tiếp của thế kỷ 21 gắn liền với cụm từ “Mạng xã hội” – nơi tìm kiếm và chia sẻ thông tin vô cùng hiệu quả. Với một cái tên hoặc địa chỉ email, mọi người có thể nhanh chóng tìm thấy nhau. Một hoạt động của một cá nhân hay một doanh nghiệp có thể được hưởng ứng với số đông nhiều người.
Mọi thông tin trên mạng xã hội có thể được nhanh chóng lan tỏa dựa vào mối quan hệ kết nối của mọi thành viên trên mạng xã hội. - Ví dụ, trong công nghệ thông tin, mạng xã hội trực tuyến (Online Social Network) là nơi kết nối các thành viên có cùng sở thích trên internet không phân biệt không gian và thời gian, thông qua các dịch vụ mạng xã hội (Social Network Service). Có thể nói, sự ra đời của các site Facebook, Twitter, Myspace, Youtube, Google+, ZingMe… đã khiến cho các mạng xã hội ngày càng trở nên phổ biến hơn.1: Mô tả mạng xã hội. Nguồn: [16] Phân tích mạng xã hội có nguồn gốc từ ngành Xã hội học và các ngành phân tích mạng, lý thuyết đồ thị.
Các nhà khoa học máy tính đã sử dụng phương pháp phân tích mạng xã hội – SNA để nghiên cứu các trang Web, lưu lượng truyền thông trên internet, mức độ phổ biến thông tin,… -2- 1. Giới thiệu đề tài Phân tích mạng xã hội (Social Network Analysis – SNA) hiện đang là một trong các chủ đề được quan tâm nghiên cứu. Phân tích mạng xã hội bao gồm việc nghiên cứu các quan hệ, kết nối, mẫu truyền thông và hành vi giữa các nhóm xã hội khác nhau… Các phương pháp "phân tích mạng xã hội" (Social Network Analysis - SNA) đã được nghiên cứu và ứng dụng ngày càng nhiều hơn trong các nghiên cứu xã hội học nói riêng và khoa học xã hội nói chung. Tại Việt Nam, phương pháp phân tích mạng xã hội còn khá mới mẻ, do đó việc ứng dụng phương pháp phân tích này còn khá hạn chế.
Đi kèm với phân tích nói trên là bài toán xác định phần tử chính yếu (Key player) hay còn gọi là những tác nhân quan trọng trong mạng xã hội. Phần tử chính yếu là các phần tử trong mạng được xem là quan trọng xét theo một điều kiện nào đó. Có thể nói rằng, key player là những node có khả năng điều khiển luồng thông tin, là những node nổi bật nhất và có tầm ảnh hưởng đến các node khác trong mạng xã hội. Độ đo Centrality là đơn vị đo lường xác định các mối liên kết của một đỉnh trong đồ thị.
Thông qua Centrality, ta có thể phát hiện được thực thể nào trong mạng là quan trọng và có tầm ảnh hưởng đến những thực thể khác. Dựa vào bài toán tìm đường đi ngắn nhất qua các đỉnh của một đồ thị có hướng. Có thể xem mạng xã hội như một đồ thị có hướng, các thực thể trong mạng là các đỉnh (node) của đồ thị, mối quan hệ giữa các thực thể trong mạng là các cạnh (link) của đồ thị.
