CHƯƠNG 1: GIỚI THIỆU ĐỀ TÀI 1.1 Lý do chọn đề tài Mạng xã hội, hay gọi là mạng xã hội ảo (tiếng Anh: Social Network) là dịch vụ nối kết các thành viên cùng sở thích trên Internet lại với nhiều mục đích khác nhau không phân biệt không gian và thời gian. Mạng xã hội xuất hiện lần đầu tiên vào năm 1995 với sự ra đời của mạng Classmate có mục đích kết nối các bạn học. Sau đó, có khá nhiều mạng xã hội xuất hiện và trở thành một trào lưu mới như Friendster, MySpace, Facebook,…[22], [28]. Ngoài việc chia sẻ cảm nghĩ, sở thích,các mạng xã hội còn hướng tới lưu trữ, xử lý dữ liệu hình ảnh, âm thanh, video và nhiều loại dữ liệu khác ngày càng phong phú, đa dạng.
Các mạng xã hội đều thu hút một lượng rất lớn người dùng, có thể lên tới hang trăm triệu thành viên. Từ đó đặt ra nhu cầu rất lớn về cơ sở hạ tầng mạng, sức mạnh tính toán và dung lượng lưu trữ dữ liệu. Ngoài ra, do người sử dụng ở khắp nơi trên thế giới nên mạng xã hội cũng mang tính phân bố rộng khắp để đáp ứng nhu cầu ngày một gia tăng của người dùng. Khi lượng người tham gia mạng xã hội tăng cao, lượng dữ liệu lưu trữ cũng tăng, băng thông, bộ nhớ,.
đều đòi hỏi nhiều hơn dẫn tới việc quá tải các trung tâm dữ liệu và làm gia tăng độ trễ trong quá trình truyền nhận dữ liệu. Điều nghiêm trọng hơn là sẽ làm tăng thời gian đáp ứng của hệ thống khi nhận tương tác từ người dùng. Ngày nay, với tiến bộ vượt bậc của công nghệ lưu trữ, việc chế tạo các bảng mạch nhớ (RAM) và các thiết bị lưu trữ phát triển rất nhanh nhưng giá thành vẫn còn rất cao, và quan trọng hơn là không có khả năng lưu trữ hết toàn bộ người dung trên đó. Vì vậy, nhu cầu giảm số lượng lưu trữ mà cụ thể là giảm số lượng bản sao khi phân hoạch mạng xã hội là mục tiêu quan trọng được hướng đến.
Xu hướng phát triển ngày càng mạnh của mạng xã hội và nhu cầu đặt ra cho việc lưu trữ, truy xuất, xửlý lượng lớn dữ liệu ngày càng cấp thiết. Đề tài: “Sử dụng thuật toán meta-heuristic trong phân hoạch mạng xã hội hướng lưu trữ” là cần thiết đểhướng đến việc cung cấp dịch vụ tốt hơn cho cộng đồng, mang lại trải nghiệm tốt hơn cho người dùng; đồng thời cũng tiết kiệm chi phí cho các nhà cung cấp dich vụ mạng xã hội.2 Tình hình nghiên cứu trong và ngoài nước Hiện tại đã có nhiều công trình nghiên cứu liên quan đến việc phân hoạch dữ liệu mạng xã hội. Một số hướng nghiên cứu phổ biến như: phân hoạch dữ liệu theo nhận thức xã hội để phân phối việc lưu trữ dữ liệu xã hội (Socially aware data partitioning for distributed storage of social data) [7]; nhân bản (replication) dữ liệu trong mạng xã hội [3]; chiến lược phân vùng cơ sở dữ liệu cho dữ liệu mạng xã hội [8]; nhân rộng các mạng xã hội trực tuyến [4]… Với hướng nghiên cứu phân hoạch dữ liệu theo nhận thức xã hội [7], tác giả Duc A.Tran dùng giải pháp triển khai thêm nhiều server để đối phó với sự tăng trưởng nhanh chóng của số lượng user và các hoạt động. Tác giả nhấn manh tầm quan trọng của việc phân vùng dữ liệu trên các server sao cho hiệu quả và tối đa hóa cân bằng tải giữa chúng.
Đồng thời bài báo cũng nêu ra một trở ngại trong việc lưu trữ xã hội vì đa số các truy cập mang tính cục bộ. Tác giả đã tìm ra cách phân vùng dữ liệu hiệu quả theo mối quan tâm của user (sở thích đọc ghi dữ liệu trên mạng, thường xuyên đọc dữ liệu của ai). Thuật toán mới có hiệu xuất cao và cân bằng phân vùng tốt. Tiếp theo nghiên cứu trên, tác giả Duc A.Tran tiếp tục với hướng nghiên cứu nhân bản dữ liệu trong mạng xã hội [3] vào năm 2013.
Tác giả quan tâm tới việc xác định nơi tốt nhất để lưu dữ liệu. Nhu cầu nhân bản dữ liệu để đặt ở nhiều server xuất hiện. Toàn bộ bài báo chú trọng vào việc nhân bản: khi nào, ở đâu, cách thực hiện. Phương pháp S-CLONE [3] được đề xuất để giải quyết vấn đề.
Sự xuất hiện của các trở ngại trong việc thiết kế hệ thống có khối lượng lưu trữ và lưu thông cực lớn dẫn tới việc tốn nhiều chi phí để tái cấu trúc như Facebook, Twitter vẫn thường mắc phải.Với hướng nghiên cứu Scaling Online Social Networks [4], tác giả đề xuất phương pháp SPAR nhằm giảm chi phí khi tái kiến trúc dữ liệu. Việc tái kiến trúc phân vùng dữ liệu không ảnh hưởng tới ứng dụng bên trên. Một hướng nghiên cứu khác, tác giả Oscar Ricardo Moll Thomae [8] cung cấp một số chiến lược thiết kế database nhằm tối ưu hóa chi phí lưu trữ, truy vấn, cập nhật dữ liệu mạng xã hội. Với lượng dữ liệu lớn và các hoạt động phong phú của mạng xã hội, đề tài chỉ tập trung vào một hoạt động đơn lẻ là hoạt động kết bạn giữa các thành viên đã tham gia vào mạng xã hội.
Nội dung chính của đề tài liên quan đến bài toán phân hoạch đồ 2 thị mạng xã hội, hướng đến giảm số lượng bản sao khi mạng xã hội tăng trưởng nhanh. Đề tài không tập trung vào bản chất dữ liệu của người dùng và mặc định xem như dữ liệu của mọi người dùng là như nhau về độ phức tạp và lưu trữ. Ngoài ra, xét dưới khía cạnh đồ thị thuần túy thì bài toán phân hoạch đồ thị là rất kinh điển, và thuộc nhóm bài toán NP-Hard.3 Mục tiêu của đề tài 1.1 Về lý thuyết Hiểu rõ các giải thuật lưu trữ phân tán đang sử dụng cho mạng xã hội, đề xuất giải pháp tái phân hoạch mạng xã hội và tạo các bản sao dữ liệu người dùng sao cho các dữ liệu liên quan đều nằm trên cùng một phân hoạch và số lượng bản sao của mạng là ít nhất có thể.2 Về thực nghiệm Xây dựng một chương trình thử nghiệm có thể phân hoạch mạng xã hội giảlập (dựa trên tập dữ liệu thực tế) cho số lượng bản sao ít hơn so với các giải pháp phân tán đang được sử dụng. So sánh và đánh giá kết quả thực nghiệm của giải pháp với giải thuật SPAR.4 Nội dung nghiên cứu Các giải thuật lưu trữ phân tán: Phân hoạch dựa trên địa lý, Phân hoạch ngẫu nhiên, Phân hoạch theo đồ thị, Phân hoạch tối ưu theo khối.
Giải thuật tối ưu SPAR do Josep M.Pujol và các đồng sự phát triển. Đề xuất giải pháp cải tiến.5 Phương pháp nghiên cứu Nghiên cứu các giải thuật lưu trữ phân tán đã được trình bày trong các tài liệu như: luận văn thạc sĩ, các bài báo khoa học. Nghiên cứu các giải pháp đang thực hiện trên các mạng xã hội phổ biến. Sử dụng tập dữ liệu thực từ internet [40] để giả lập mạng xã hội theo giải thuật SPAR và giải thuật đề xuất.
3 Sử dụng các phần mềm, gói phần mềm, thư viện mã nguồn mở hỗ trợ tốt cho việc phân hoạch đồ thị dùng heuristic(Chaco, Metis. Cụ thể trong luận văn này tôi sẽ dùng Metis (gpmetis). Những thư viên này có thể giúp ta thực nghiệm các thuật toán đã có trước khi tổng hợp được phương pháp tốt cho phân hoạch đồ thị mạng xã hội. Đề xuất sử dụng mô hình quy hoạch nguyên, đưa bài toán về bài toán quy hoạch nguyên thuần túy và lập trình bằng ngôn ngữ C# kết hợp với công cụ lpsolve để giải quyết bài toán.
So sánh và đánh giá kết quả thu được từ thực nghiệm của chương trình với kết quả thu được từ phương pháp random, phần mềm gpmetis, giải thuật SPAR. 4 CHƯƠNG 2: TỔNG QUAN VỀ MẠNG XÃ HỘI 2.1 Mạng phức hợp (Complex network) Trong những năm gần đây người ta đã bắt đầu nhận thấy được tầm quan trọng của mạng phức hợp (Complex Networks) trong nhiều lĩnh vực trong khoa học cũng như trong đời sống của xã hội hiện đại. Việc nghiên cứu về mạng phức hợp cũng được khuyến khích và đã có rất nhiều nhà khoa học, nhà nghiên cứu trên thế giới quan tâm và tìm hiểu về mạng phức hợp. Mạng phức hợp là một tập các hệ thống được tạo bởi các yếu tố đồng nhất hoặc không đồng nhất kết nối với nhau thông qua sự tương tác khác nhau giữa các yếu tố này và được trải ra trên diện rộng.
Chúng có mặt ở khắp nơi trong tự nhiên và trong xã hội. Trong thực tế, có rất nhiều hệ thống trong tự nhiên có thể miêu tả thông qua các mô hình của mạng phức hợp. Đó là những hệ thống có cấu trúc gồm các nút (node) gắn với nhau thành một mạng bởi các liên kết (tie) [3], [13], [17], [20], [21]. Thí dụ như: mạng Internet là mạng của các router hoặc các domain [18]; mạng World Wide Web (WWW) là mạng của những trang web [14]; một tổ chức là mạng của những thành viên trong tổ chức; nền kinh tế toàn cầu là mạng kinh tế của các nước thành phần, nền kinh tế mỗi nước lại là một mạng các thị trường, mỗi thị trường lại là một mạng tương tác giữa những sản phẩm hàng hóa và người tiêu thụ; mạng của các chất hóa học (liên kết với nhau bởi các phản ứng hóa học); mạng ngôn ngữ (thí dụ như mạng đồng âm khác nghĩa, mạng đồng nghĩa); các mạng lưới điện cao thế (Electrical Power Grid); các chủ đề của một buổi nói chuyện và thậm chí việc vạch kế hoạch cho xử lý một vấn đề toán học nào đó cũng có thể mô hình bằng một mạng 2.2 Mạng xã hội Mạng xã hội là một trường hợp cụ thể của mạng phức hợp.
Mạng xã hội, hay còn gọi là mạng xã hội ảo (tiếng Anh: social network) là một cấu trúc mang tính xã hội tạo thành từ các nút (tiếng Anh: node) và các liên kết (tiếng Anh: tie), mỗi nút có thể là 5 một cá nhân hay một tổ chức, các liên kết thể hiện mối quan hệ giữa các nút (bạn bè, sự trao đổi thông tin,…) [22]. Trường hợp đơn giản nhất, mạng bao gồm 2 node và một liên kết giữa chúng. Bối cảnh có thể là hai người cùng học cứu tại một trường đại học. Ví dụ, A và B có một mối quan hệ bởi vì cả hai cùng học tập tại lớp Cao học khoa Khoa học và ky thuật máy tính, đại học Bách Khoa, ta biểu diễn một liên kết giữa hai nút A và B.
học cùng lớp A B Hình 2.1: Mối quan hệ đối xứng Mạng ở Hình 2.