Đề tài Phân tích mạng xã hội bằng công nghệ wave - phân tích quan hệ

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Phạm Minh Ngọc PHÂN TÍCH MẠNG Xà HỘI BẰNG CÔNG NGHỆ WAVE - PHÂN TÍCH QUAN HỆ KHÓA LUẬN TỐT NGHIỆP ĐẠI HỌC CHÍNH QUY Ngành: Công nghệ thông tin HÀ NỘI - 2009  LỜI CẢM ƠN  Lời đầu tiên, em xin gửi lời cảm ơn chân thành tới thầy giáo, Thạc sĩ Hồ Đắc Phương, Thạc sĩ Đào Minh Thư, những người đã hướng dẫn và chỉ bảo tận tình cho em trong suốt quá trình học tập cũng như thực hiện khóa luận tốt nghiệp này. Em cũng xin cảm ơn các thầy cô giáo đã chỉ bảo trong suốt quá trình học tập tại trường Đại học Công nghệ. Cùng với đó em cũng gửi lời cảm ơn tới Bùi Hiếu, Tuệ, Trương Hiếu, Thái, Tiệp và Chuẩn, những người bạn đã cùng giúp đỡ nghiên cứu các ứng dụng được trình bày trong khóa luận tốt nghiệp này. Ngoài ra, những kết quả nghiên cứu được trình bày trong khóa luận tốt nghiệp này cũng phải nhờ tới cha mẹ, bạn bè, những người đã rất ủng hộ, giúp đỡ và động viên em. Sinh viên Phạm Minh Ngọc  TÓM TẮT  Khóa luận tốt nghiệp này trình bày những hiểu biết về công nghệ WAVE như sự hình thành, các tính chất, đặc điểm, các điểm mạnh của công nghệ WAVE so với các công nghệ hiện thời và ứng dụng của nó vào việc giải quyết các bài toán cụ thể. Phần chính của khóa luận này là đưa ra các bài toán tổng quan về vấn đề phân tích thông tin trên mạng xã hội Yahoo!360, từ đó sẽ áp dụng nền tảng WAVE, kết hợp với ngôn ngữ lập trình Java, cơ sở dữ liệu MySQL để thực hiện một chương trình nhỏ thu thập và phân tích thông tin trên mạng xã hội Yahoo!360 hiện thời.  Mục lục LỜI CẢM ƠN..................................................................................................................1 TÓM TẮT........................................................................................................................2 MỞ ĐẦU .........................................................................................................................1 CHƯƠNG 1: MẠNG Xà HỘI VÀ CÁC BÀI TOÁN LIÊN QUAN.............................3 1.1 Lịch sử Mạng xã hội ..............................................................................................3 1.2 Đặc điểm Mạng xã hội (ảo) [30] ..............................................................................6 1.3 Một số bài toán đối với Mạng xã hội .....................................................................8 CHƯƠNG 2: NGÔN NGỮ WAVE ..............................................................................12 2.1 Giới thiệu về ngôn ngữ Wave ..............................................................................12 2.2 Node, Link và Không gian phân tán : Knowledge Network (KN) ......................12 2.3 Tổ chức chung của ngôn ngữ Wave.....................................................................13 2.4 Cấu trúc dữ liệu cơ bản của Wave .......................................................................15 2.5 Biến Spatial và kiểu .............................................................................................15 2.5.1 Task variables ................................................................................................15 2.5.2 Environment variables ...................................................................................15 2.6 Các hành động - ACTS ........................................................................................16 2.6.1 Control acts ....................................................................................................16 2.6.2 Fusion acts: Các phép toán hợp nhất .............................................................18 2.7 Rules – Các luật trong Wave................................................................................19 2.7.1 Các Luật Rẽ Nhánh........................................................................................19 2.7.2 Repetition.......................................................................................................20 2.7.3 Create .............................................................................................................20 2.7.4 Release ...........................................................................................................20 2.8 Wave và mô hình lập trình truyền thống..............................................................21 2.8.1 Sơ đồ luồng (SD) ...........................................................................................21 2.8.2 Wave và mô hình lập trình song song ...........................................................22 2.8.3 Wave và mô hình lập trình tuần tự ................................................................24 CHƯƠNG 3: XÂY DỰNG MẠNG TRI THỨC CHO MẠNG Xà HỘI.....................30  3.1 Mạng xã hội Yahoo!360 [9] ..................................................................................30 3.2 Xây dựng mạng tri thức cho mạng xã hội Yahoo!360.........................................33 3.2.1 Thu thập thông tin cho mạng tri thức ............................................................33 3.2.2 Tạo dựng mạng tri thức .................................................................................35 3.2.3 Lưu trữ ...........................................................................................................36 3.2.4 Filter...............................................................................................................38 3.3 Sơ đồ hoạt động các thành phần trong chương trình ...........................................40 3.3.1 Thành phần thu thập thông tin blog...............................................................40 3.3.2 Thành phần tạo dựng Mạng tri thức ..............................................................42 CHƯƠNG 4: BÀI TOÁN PHÂN TÍCH QUAN HỆ ....................................................43 4.1 Tạo lập mạng tri thức từ cơ sở dữ liệu không đồng nhất .....................................43 4.2 Các bài toán quan hệ ............................................................................................49 4.3 Mở rộng hệ thống.................................................................................................52 CHƯƠNG 5: BÀI TOÁN PHÂN TÍCH ĐẶC ĐIỂM...................................................53 5.1 Bài toán tìm kiếm theo mẫu .................................................................................53 5.2 Bài toán Tìm Đường đi ngắn nhất........................................................................54 5.2.1 Thuật toán ......................................................................................................54 5.2.2 Cài đặt ............................................................................................................58 5.3 Bài toán tìm Đường kính......................................................................................61 5.4 Bài toán tìm Tâm và Bán kính .............................................................................66 CHƯƠNG 6: KẾT QUẢ ...............................................................................................67 6.1 Kết quả thực nghiệm ............................................................................................67 6.2 Kết luận ................................................................................................................67 TÀI LIỆU THAM KHẢO.............................................................................................69   DANH MỤC CÁC HÌNH ẢNH Hình 1 1: Đồ thị biểu diễn cấu trúc đơn giản mạng xã hội .............................................3 Hình 1 2: Ma trận kề biểu diễn đồ thị gồm 4 đỉnh A, B, C, D ......................................10 Hình 2 1: Knowledge Network.....................................................................................13 Hình 2 2 Thành phần của Spread Diagrams..................................................................21 Hình 2 3: Tự động tách trong chuỗi Wave ....................................................................22 Hình 2 4: Một số trường hợp xử lý song song ..............................................................23 Hình 2 5: Wave xử lý song song có kèm theo Rule ......................................................23 Hình 2 6: Xử lý tuần tự không Rule và có Rule............................................................24 Hình 2 7: Wave xử lý tuần tự có Rule...........................................................................25 Hình 2 8: Một số trường hợp với mệnh đề if-else .........................................................25 Hình 2 9: Một số trường hợp với mệnh đề if-else .........................................................26 Hình 2 10: else-if với filter ............................................................................................26 Hình 2 11: else-if parallel ..............................................................................................27 Hình 2 12: else-if với Rule ............................................................................................27 Hình 2 13: Switch..........................................................................................................28 Hình 2 14: Câu lệnh lặp sử dụng Repetition .................................................................29 Hình 2 15: Câu lệnh lặp sử dụng Recursion..................................................................29 Hình 3 1: Các thành phần trong một trang cá nhân Yahoo!360....................................32 Hình 3 2: Cấu trúc của đường liên kết tới dịch vụ Yahoo!360 .....................................34 Hình 3 3: Cấu trúc Cơ sở dữ liệu MySQL.....................................................................37 Hình 3 4: Sơ đồ hoạt động thành phần thu thập thông tin blog.....................................40 Hình 3 5: Sơ đồ hoạt động thành phần tạo dựng mạng tri thức ....................................42 Hình 4 1: Cấu trúc cơ bản của một cơ sở dữ liệu không đồng nhất ..............................43  Hình 4 2: WORLD database..........................................................................................44 Hình 4 3: TOPICS database ..........................................................................................45 Hình 4 4: OCCUPATION database ..............................................................................46 Hình 4 5: BLOGGER database .....................................................................................47 Hình 4 6: Cơ sở dữ liệu tổng hợp ..................................................................................48 Hình 5 1 .........................................................................................................................53 Hình 5 2 .........................................................................................................................54 Hình 5 3 .........................................................................................................................55 Hình 5 4 .........................................................................................................................56 Hình 5 5 .........................................................................................................................56 Hình 5 6 .........................................................................................................................57 Hình 5 7 .........................................................................................................................59 Hình 5 8 .........................................................................................................................60 Hình 5 9 .........................................................................................................................61 Hình 5 10 .......................................................................................................................63 Hình 5 11 .......................................................................................................................64 Hình 5 12 .......................................................................................................................66 DANH MỤC CÁC BẢNG BIỂU Bảng 1 1: Thông tin về các dịch vụ mạng xã hội phổ biến .............................................5 Bảng 1 2: Tiềm năng đối với mạng xã hội thông qua vài con số [37] ............................8  BẢNG KÝ HIỆU VIẾT TẮT Ký hiệu Viết đầy đủ ADSL Asymmetric Digital Subscriber Line CSDL Cơ sở dữ liệu CSV Comma-Separated Values CSS Cascading Style Sheets HTML Hyper Text Markup Language KN Knowledge Network LAN Local Area Network Mbps Mega bit per second MD5 Message Digest 5 SMS Short Message Service SNR Set of Node Reached URL Uniform Resource Locator WI Wave Interpreter XML eXtensible Markup language 1  MỞ ĐẦU Ngày nay, sự phát triển của công nghệ thông tin nói chung và kiến trúc mạng nói riêng đã và đang đạt được những bước tiến nhất định. Công nghệ thông tin đang dần được đưa vào ứng dụng trong mọi lĩnh vực của cuộc sống, từ việc điều khiển các thiết bị một cách tự động, hỗ trợ hoạt động kinh doanh, sản xuất của con người, cho đến việc giả lập chính xã hội loài người – mạng xã hội. Mạng xã hội ra đời đã trở thành một trào lưu mới trong mọi tầng lớp sử dụng máy tính và Internet làm công cụ giao lưu, tìm kiếm kiến thức. Mạng xã hội giúp thu hẹp khoảng cách giữa người với người, góp phần biến thế giới mà chúng ta đang sinh sống trở thành một “thế giới phẳng”. Với khả năng kết nối, chia sẻ thông tin một cách dễ dàng, mạng xã hội dần trở thành một kho kiến thức khổng lồ. Và từ đây, nhu cầu tìm kiếm, phân tích lượng thông tin khổng lồ trong rất nhiều mạng xã hội đang tồn tại và phát triển trở nên cần thiết hơn bao giờ hết. Tuy thế, các công nghệ tìm kiếm hiện tại đứng đầu là Google đều chưa thể tận dụng hết khả năng của mạng xã hội. Bởi lẽ mạng xã hội có cấu trúc rất mở, các thành phần được gắn kết với nhau theo dạng quan hệ (một chiều, hai chiều) nên việc tìm kiếm thông tin trên mạng xã hội phải làm việc ở mức phân tích quan hệ, tìm kiếm các đặc điểm. Trong khi các cỗ máy tìm kiếm hiện thời vẫn chỉ tập trung vào tìm kiếm nội dung thì có một công nghệ mới đang có những bước phát triển rất lớn lại có khả năng phân tích, tìm kiếm dựa trên quan hệ, đó là công nghệ WAVE. Công nghệ WAVE bao gồm bộ ngôn ngữ WAVE và bộ thông dịch chính ngôn ngữ đó. Chúng tập hợp lại thành một nền tảng mạnh mẽ trong việc hỗ trợ tính toán và xử lý song song dựa trên các hệ thống phân tán. Với những bộ luật thông minh, WAVE cho phép tận dụng được gần như tối đa khả năng của một hệ thống mạng ngang hàng với các máy tham gia phân tán để thực hiện những bài toán đòi hỏi độ phức tạp tính toán cao. Trên cơ sở đó, khóa luận tốt nghiệp này tập trung tìm hiểu và làm rõ hơn khả năng tận dụng công nghệ WAVE vào việc xử lý các bài toán dựa trên quan hệ trên các mạng xã hội, để từ đó tạo tiền đề cho việc ứng dụng WAVE vào trong các bài toán lớn hơn, giải quyết vấn đề thu thập, tìm kiếm và phân tích thông tin trên diện rộng. Do giới hạn của một khóa luận tốt nghiệp, tất cả những ứng dụng của WAVE cũng như việc ứng dụng WAVE vào các bài toán phân tích trong mạng xã hội sẽ không thể được trình bày một cách đầy đủ và chi tiết, cho nên khóa luận tốt nghiệp này sẽ bao 2  gồm ba phần chính. Phần đầu nhằm giới thiệu về mạng xã hội, trình bày các đặc điểm của mạng xã hội đồng thời lý giải vì sao muốn tìm hiểu thông tin trong một mạng xã hội phải cần đến công nghệ WAVE. Phần thứ hai cung cấp cái nhìn chi tiết hơn về mạng xã hội hiện vẫn đang dần đầu về quy mô, số lượng người dùng tại Việt Nam, đó là Yahoo!360. Phần này cũng trình bày việc đưa các dữ liệu “ảo” của mạng xã hội Yahoo!360 vào thành các thành phần quan hệ trong WAVE, từ đó tạo ra mạng tri thức nhằm giải quyết các bài toán phân tích quan hệ trong mạng xã hội được trình bày đầy đủ hơn trong phần thứ 3. Khóa luận cũng sẽ dành hai chương cho việc giới thiệu về ngôn ngữ WAVE và việc ứng dụng WAVE trong giải quyết các bài toán phân tích đặc điểm của mạng xã hội. Hai phần này sẽ được nghiên cứu sâu hơn trong hai khóa luận tốt nghiệp: “Xây dựng trình biên dịch cho ngôn ngữ WAVE” của Trương Văn Hiếu và “Phân tích mạng xã hội bằng công nghệ WAVE – Phân tích đặc điểm mạng xã hội” của Phí Hồng Thái (khóa 50 – Công nghệ thông tin – Trường đại học Công nghệ - Đại học Quốc gia Hà Nội). 3  CHƯƠNG 1: MẠNG XàHỘI VÀ CÁC BÀI TOÁN LIÊN QUAN  Theo Wikipedia [17] và Whatissocialnetworking.com [39], 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), mỗi nút đó có thể là một cá nhân, hay một tổ chức. Mạng xã hội làm nhiệm vụ kết nối các thành viên, người dùng trên Internet lại với nhau dựa theo những tiêu chí nào đó, với nhiều mục đích khác nhau, không phân biệt thời gian và không gian. Hình 1 1: Đồ thị biểu diễn cấu trúc đơn giản mạng xã hội Cấu trúc xã hội của mạng xã hội được thể hiện ở cách thức mạng xã hội “giả lập” xã hội loài người. Mạng xã hội nhìn nhận những mối quan hệ xã hội thông qua các nút và ràng buộc giữa các nút. Trong một mạng xã hội, các nút là các cá thể, và ràng buộc giữa chúng là các mối quan hệ giữa các cá thể đó. Với một cấu trúc đơn giản nhất như thế, một mạng xã hội có thể được biểu diễn như một “đồ thị” như Hình 1 1 trong đó mỗi cá thể, mỗi nút là một điểm trên đồ thị, và quan hệ giữa chúng được thể hiện là một đoạn nối điểm này với điểm khác. 1.1 Lịch sử Mạng xã hội Mạng máy tính (tiếng Anh: computer network) ra đời làm nền tảng cho sự xuất hiện của mạng xã hội. 4  Có một vài cách tiếp cận khác nhau về mạng xã hội. Cách tiếp cận đầu tiên cho rằng mạng xã hội là một nơi để mọi người có thể tương tác với nhau thông qua các phòng trò chuyện (tiếng Anh: chat room), chia sẻ thông tin cá nhân, ý tưởng qua các chủ đề được tạo lập trên những trang cá nhân, mà về sau này được gọi là “blogging”. Những mạng xã hội dạng này thì đã xuất hiện từ năm 1985 với THE WELL, Theglobe.com (1994), Geocities (1995) và Tripod (1995). Còn với một cách tiếp cận khác, đơn giản hơn thì mạng xã hội là nơi mà mọi người có thể kết nối với nhau thông qua địa chỉ thư điện tử của họ. Mạng xã hội đầu tiên của dạng này – Classmates [29] – ra đời vào năm 1995 với mục đích kết nối bạn học, tiếp đó SixDegrees được tạo ra vào năm 1997 là với mục đích giao lưu kết bạn dựa theo sở thích. Năm 2002, Friendster [32] ra đời và mau chóng trở thành trào lưu tại Mỹ. Tuy vậy do phát triển quá nhanh mà thiếu đi sự tính toán đối với phân tải đã khiến các server của dịch vụ này hay bị xảy ra hiện tượng quá tải. Công ty này sau đó có được Google đề nghị mua lại với trị giá khoảng 30 triệu đô la Mỹ tuy nhiên thương vụ không thành công. Năm 2004, MySpace [34] đi vào hoạt động, nhanh chóng nổi bật với các tính năng mới hấp dẫn, trong đó phải kể đến tính năng chia sẻ nhạc. Dịch vụ này đã thu hút được rất nhiều các ban nhạc tham gia vào mạng xã hội MySpace, từ đó giúp cho mạng xã hội này có thêm được rất nhiều những thành viên quan tâm, để rồi trở thành mạng xã hội lớn nhất thế giới cho tới tận thời điểm hiện nay. Năm 2006 đánh dấu sự có mặt của Facebook [31] (thực ra là việc mở rộng phạm vi của mạng xã hội này ra toàn cầu thay vì cho cộng đồng các trường đại học tại Mỹ vốn đã tồn tại từ năm 2004), một mạng xã hội “mở”. Facebook cung cấp một nền tảng lập trình gọi là Facebook Platform cho phép những thành viên chuyên sâu có thể tạo ra các ứng dụng (tiếng anh: Applications). Nhờ vậy Facebook có được rất nhiều các ứng dụng vừa được cập nhật một cách nhanh chóng, lại vừa phù hợp với nhiều đối tượng với các sở thích cá nhân khác nhau. Ngoài ra hiện nay còn có một trào l