Khóa luận 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ưu mới xuất hiện nhưng cũng đã phát triển hết sức nhanh chóng, đó là Twitter [25]. Nếu như các mạng xã hội trước kia thường được gọi là blogging thì Twitter còn được gọi là micro-blogging [12]. Được gọi như vậy bởi Twitter chỉ cung cấp cho người dùng khả năng tạo ra những dòng tin nhắn nhanh và 5  ngắn gọn cỡ 140 ký tự (gần giống với số ký tự cho phép trong một tin nhắn SMS [14] trên điện thoại di động). Bảng 1 1 đưa ra một vài con số thống kê nhỏ về mạng xã hội và sự phát triển của chúng trong thời gian gần đây dựa vào hai tiêu chí cơ bản là số lượng người dùng (thống kê vào thời điểm đầu năm 2009) và xếp hạng lưu lượng truy cập tại trang thống kê nổi tiếng Alexa (thống kê được ghi lại vào thời điểm tháng 5 năm 2009) Bảng 1 1: Thông tin về các dịch vụ mạng xã hội phổ biến Tên dịch vụ Thời gian ra đời Số lượng người dùng [11] - 2009 Global Alexa page Ranking [28] – 5/2009 Bebo bebo Tháng 1/2005 40 triệu 143 Classmates 1995 50 triệu 510 Facebook Tháng 2/2004 200 triệu 4 Flixster Tháng 6/2005 63 triệu 584 Friendster 2002 90 triệu 54 Habbo 2000 (Phần Lan) 117 triệu 3812 hi5 27/6/2003 80 triệu 24 LinkedIn Tháng 5/2003 40 triệu 101 MySpace Tháng 8/2003 Khoảng 253 triệu 9 Netlog 2004 42 triệu 99 Orkut 22/1/2004 67 triệu 107 Reunion (MyLife.com) 2002 51 triệu 2555 (1086) Tagged Tháng 10/2004 70 triệu 72 Twitter 2006 25 triệu 49 6  Windows live spaces Đầu năm 2004 120 triệu 5 1.2 Đặc điểm Mạng xã hội (ảo)  [30]  Có thể nói Mạng xã hội có thể phát triển mạnh mẽ được như hiện nay là do những ưu thế đáng kể mà chúng mang lại so với các cách tiếp cận cộng đồng truyền thống. Đầu tiên là vấn đề chi phí. Có thể thấy rằng việc tham gia vào một mạng xã hội, dù là đối với một cá nhân hay một tổ chức đều chiếm một chi phí tương đối thấp, bởi trên thực tế, các mạng xã hội hiện nay hầu hết cho phép đăng ký và sử dụng miễn phí. Trong khi đó, khi đã trở thành một thành viên của một mạng xã hội, các cá nhân hay tổ chức đó có thể có được rất nhiều thông tin hữu ích cho mối quan tâm, sự phát triển của mình. Ví dụ như một công ty sau khi tham gia một mạng xã hội nào đó, có thể chỉ cần vài cú nhấp chuột là đã có thể tìm hiểu về các sở thích của người dùng, xu hướng của những sở thích đó. Qua đó, công ty có thể phát hiện ra được những khách hàng tiềm năng, vạch ra một chiến lược kinh doanh mới cho thời kỳ khó khăn … Những việc làm này có thể giúp ích rất nhiều cho hoạt động kinh doanh hiện tại của công ty đó. Thứ hai là khả năng xây dựng các mối quan hệ tin cậy. Nhờ vào việc quan sát được các bài viết, đánh giá của các thành viên trong mạng xã hội, một tổ chức có thể nắm bắt được nhu cầu và đánh giá của khách hàng về các sản phẩm hay dịch vụ mà họ cung cấp. Hơn thế là khi họ có những phản hồi tích cực đối với khách hàng, từ đó xây dựng một mối quan hệ “ảo” với khách hàng trong khi có thể mang lại một niềm tin “thực”. Không quá tốn kém như những hệ thống chăm sóc khách hàng lớn mà mang lại hiệu quả cũng không hề nhỏ, đó chính là lợi thế của mạng xã hội. Hay đối với những cá nhân, nhờ việc đọc được những bài viết phần nào mang tính chất riêng tư, tâm sự của bạn bè, hay con cái, họ có thể có được những hiểu biết rõ ràng hơn về bạn bè, con cái của mình, thấy được vấn đề mà người kia đang gặp phải, từ đó giúp họ giải quyết vấn đề dễ dàng hơn. Bởi nghiên cứu cho thấy, giới trẻ đang có xu hướng kể ra những phức tạp cá nhân trên blog, mạng xã hội dễ dàng hơn là nói chuyện trực tiếp với các bậc phụ huynh, hay cả với bạn bè. Khi ấy niềm tin trong mối quan hệ cũng được nâng lên đáng kể. Thứ ba, việc tạo lập các mối quan hệ trong mạng xã hội trở nên dễ dàng hơn bao giờ hết. Thử tưởng tượng trong mạng xã hội nào đó, người dùng có một vài người bạn, 7  những người ấy lại có nhiều bạn bè khác, cứ như vậy. Nhờ vào mạng xã hội, người dùng ban đầu có thể thiết lập một mối quan hệ với bất cứ ai, đơn giản chỉ khởi đầu bằng việc gửi đi một lời nhắn đề nghị được kết bạn. Sau khi được chấp nhận bởi phía bên kia, việc cần làm để gìn giữ mối quan hệ đó đó là cố gắng cân bằng giữa việc cho đi và nhận lại. Việc này ở trên một mạng xã hội tỏ ra đơn giản hơn so với việc duy trì mối quan hệ trong xã hội bình thường, bởi cho đi và nhận về trong mạng xã hội nhiều khi chỉ nằm ở mức có những bình luận trong những bài viết của bạn bè. Những ưu điểm mà mạng xã hội mang lại như đã kể trên là rất to lớn, tuy vậy cũng cần phải chỉ ra một số mặt hạn chế của mạng xã hội. Vấn đề đầu tiên mà mạng xã hội gặp phải là vấn đề về thông tin cá nhân của người dùng [20]. Khi đã kết nối vào mạng xã hội, có bạn bè trên đó đồng nghĩa với việc người dùng cũng phải đối mặt với nguy cơ bị lợi dụng các thông tin (cá nhân) đăng tải lên đó. Với những thông tin như vậy, những kẻ có ý đồ không tốt có thể tìm hiểu nhiều thứ khác hơn về người dùng đó. Điều đó có thể làm ảnh hưởng tới lợi ích cá nhân của người dùng đó ngay trong thời điểm hiện tại cũng như tương lai. Biết đâu một bức ảnh xưa cũ có thể được lôi ra để làm hại tới thanh danh của người dùng đó về sau này??? Vấn đề thứ hai nằm ở chính cơ chế vận hành của các mạng xã hội. Mạng xã hội cũng như mọi trang web khác, đều phải giải quyết các vấn đề liên quan tới bảo mật thông tin. Thêm vào đó, các trang mạng xã hội còn gặp phải một số vấn đề riêng ví dụ như tình trạng nhắn tin rác làm phiền những thành viên tham gia, sử dụng những công cụ tự viết. Vấn đề này xuất hiện khá nhiều trên các phương tiện thông tin đại chúng gần đây, có thể lấy ví dụ về vài sự cố các tài khoản mạng xã hội của những người nổi tiếng bị hacker kiểm soát, những thông tin nhạy cảm được tung ra … Một điểm nữa cần nói tới trong mặt hạn chế của mạng xã hội là việc tiêu tốn thời gian sử dụng. Việc tham gia một mạng xã hội, kiểm tra các thay đổi gần đây từ bạn bè, cập nhật những thay đổi, thông tin cho chính mình nhiều khi làm mất thời gian của người tham gia. Tất nhiên điều này còn tùy thuộc vào cách từng người phân phối thời gian của mình cho việc “online” trên các mạng xã hội mà họ tham gia. Tuy vậy theo những phân tích gần đây thì có tình trạng khá nhiều người trẻ bị hội chứng “nghiện” khi tham gia mạng xã hội. Nếu tình trạng này xảy ra ở diện rộng thì sẽ có rất nhiều hiệu ứng không tốt kèm theo. Như vậy, cũng như những dịch vụ khác triển khai và khai thác trên nền Internet, mạng xã hội cũng thể hiện được những ưu và nhược điểm nhất định. Nhược điểm của mạng 8  xã hội phần lớn kế thừa từ những nhược điểm vốn có của các dịch vụ nền web, nhưng những ưu điểm của dịch vụ này lại mang tính chất đột phá so với các cách thức truyền thông cộng tác truyền thống. Như trong một cuốn sách với tựa đề Groundswell của nhà xuất bản Forrester Research ra đời năm 2008, mạng xã hội và tác động của nó đã được mô tả với thuật ngữ “groundswell”, tạm hiểu là: “một bước tiến tự nhiên của loài người khi sử dụng các công cụ trên mạng để kết nối, tích lũy kiến thức, lấy những gì họ cần – thông tin, hỗ trợ, các ý tưởng, các sản phẩm hay khả năng thương lượng với cộng đồng”1 .Và với những tiềm năng hiện tại mà mạng xã hội mang lại (xem Bảng 1 2), việc tham gia, phân tích và tận dụng những điểm mạnh mà mạng xã hội mang lại là cần thiết. Bảng 1 2: Tiềm năng đối với mạng xã hội thông qua vài con số [37] Thống kê nhỏ về mạng xã hội - 80% số người sử dụng Internet đã từng dùng các tiện ích của các mạng xã hội khác nhau - Hiện tồn tại khoảng 500 mạng xã hội trên thế giới và hàng nghìn trang web có chức năng như một mạng xã hội - Dịch vụ mạng xã hội có tốc độ tăng trưởng trung bình 47% mỗi năm, cao hơn hầu hết các dịch vụ trên nền Internet khác (Facebook là 150% trong năm khủng hoảng 2008 [38]) - Cứ 11 phút online trên mạng thì người sử dụng lại dành 1 phút cho blog và các mạng xã hội - Người sử dụng ngày càng đa dạng về lứa tuổi - Di động ngày càng đóng vai trò quan trọng. 23% người sử dụng mạng xã hội ở Anh truy cập web thông qua điện thoại cầm tay 1.3 Một số bài toán đối với Mạng xã hội  Tiềm năng phát triển rất mạnh hiện nay đồng thời cũng đặt ra những bài toán xử lý thông tin trên mạng xã hội. Các công nghệ tìm kiếm hiện tại nói chung vẫn chỉ dừng lại ở mức tìm kiếm nội dung trong các bài viết, tin nhắn được đăng tải trên các mạng 1 Nguyên văn: “a spontaneous movement of people using online tools to connect, take charge of their own  experience, and get what they need‐information, support, ideas, products, and bargaining power‐from each  other.”  9  xã hội. Trong khi nhu cầu tìm hiểu và phân tích thông tin còn cao và không chỉ ở khả năng tìm kiếm nội dung thông thường, mà còn ở phương diện thu thập và phân tích các mối quan hệ, các đặc điểm. Như vậy các lĩnh vực nghiên cứu dựa trên các mạng xã hội hiện nay cần hơn một công cụ nào đó giúp cho phép thiết lập một sơ đồ quan hệ và phân tích sơ đồ đó. Hiện tại cũng có một số phần mềm cho phép phân tích, xử lý các thông tin dựa trên quan hệ kiểu như trên [16]. Tuy nhiên có thể nhận thấy rằng, hầu hết những công cụ đó cần phải có một cơ sở dữ liệu đầu vào để tạo ra đồ thị quan hệ, thông thường là từ một kiểu file cơ sở dữ liệu như CSV, XML … từ đó mới bắt đầu thực thi các phân tích liên quan tới đồ thị quan hệ đó. Việc thu thập các nút, quan hệ giữa các nút hay các thuộc tính khác thường không được định nghĩa mà có thể nhờ một phần mềm khác, hay cũng có thể do người dùng trực tiếp đưa vào. Cách thức này hạn chế ở điểm sẽ khó nắm bắt được các thay đổi trên mạng xã hội mang tính chất “thời gian thực” (tiếng Anh: realtime). Công nghệ WAVE mà các bài toán trong khóa luận này khai thác sẽ có thể hỗ trợ toàn bộ các công việc trên, từ bước thu thập (theo thời gian thực) và tạo lập đồ thị quan hệ (mà trong WAVE được gọi là một mạng tri thức – Knowledge Network) tới bước thực hiện phân tích quan hệ dựa trên một cấu trúc ngôn ngữ mới cũng mang tên WAVE. Công nghệ WAVE cho phép việc xử lý thông tin ở mức đồ thị, tức là xử lý thông tin ở dạng quan hệ. WAVE tự nó sẽ tạo ra một đồ thị biểu diễn các mối quan hệ, các thuộc tính để rồi từ đồ thị đó thực hiện các bài toán phân tích quan hệ. Ngoài việc có thể xử lý các bài toán liên quan tới quan hệ mà hiện tại các cỗ máy tìm kiếm dạng Google chưa thể làm được thì về sau này, còn có thể ứng dụng WAVE vào các bài toán xây dựng các Ontology [13] [40], từ đó tiếp tục xử lý thông tin ở mức độ Ontology. Ngoài ra việc xử lý thông tin dạng nội dung cũng có thể được thực hiện khá dễ dàng thông qua việc gửi các truy vấn tìm kiếm dạng Full-Text Search [10] vào trong WAVE. Tóm lại, WAVE giúp xử lý dễ dàng hơn các bài toàn cả ở mức tìm kiếm nội dung lẫn tìm kiếm trong quan hệ cộng đồng. Về tìm kiếm dựa trên quan hệ, hiện có khá nhiều bài toán liên quan có khả năng tận dụng để lấy ra kết quả phục vụ các mục đích khác nhau, thường là ứng dụng trong lĩnh vực xã hội học. Có thể chia các bài toán này ra làm hai dạng chính ¾ Tìm các quan hệ ¾ Phân tích các đặc điểm 10  Một bài toán tìm quan hệ có thể có rất nhiều dạng, tựu chung lại, những bài toán dạng này làm nhiệm vụ tìm ra trong một tập hợp cá thể có mối quan hệ với nhau, một, hoặc một vài, hoặc một tập hợp con thỏa mãn một dạng quan hệ nào đó. Lấy ví dụ, có thể kể ra như tìm bạn chung (tiếng Anh: mutual friend) của hai hay ba người bất kỳ trong mạng xã hội. Kết quả của bài toán này có thể phần nào giúp chúng ta tìm hiểu điểm gặp nhau trong quan hệ giữa những người được chỉ ra, tức là phân tích tại sao giữa họ lại có mối quan hệ. Bài toán phân tích đặc điểm cũng là dạng bài toán được dùng khá nhiều trong nghiên cứu xã hội học. Ví dụ như bài toán tìm đường kính, là bài toán giúp giải quyết vấn đề tìm khoảng cách ngắn nhất giữa hai người (hai nút) trong một mạng xã hội. Nó gần giống với thử nghiệm Small World [15] nhằm tìm ra khoảng cách đủ để kết nối giữa hai người bất kỳ trên toàn nước Mỹ, và kết quả khá bất ngờ rằng khoảng cách trung bình nằm trong khoảng 5.5-6, tức là khá nhỏ so với người ta tưởng tượng. Có một bài toán tìm đặc điểm khác trong quan hệ là tìm tâm của một tập hợp các cá thể (các nút). Kết quả của bài toán này sẽ cho thấy nút trong đồ thị mà khoảng cách từ nút đó tới mọi nút khác trong đồ thị của tập hợp các cá thể đó là ngắn nhất. Các bài toán trên đơn thuần là những bài toán dựa trên đồ thị, và nếu chỉ như vậy thì có lẽ rằng với một ma trận kề dạng như Hình 1 2 dưới, các bài toán trên cũng có thể được giải quyết tương đối dễ dàng với một số thao tác tính toán không phức tạp. (bởi lẽ một đồ thị có thể được biểu diễn dưới dạng ma trận [26]) Hình 1 2: Ma trận kề biểu diễn đồ thị gồm 4 đỉnh A, B, C, D 11  Tuy nhiên ma trận không thể giải quyết được tình huống mở rộng đồ thị sẵn có với những nút mới, những thuộc tính mới. Và WAVE có thể giải quyết trọn vẹn điều này, bởi WAVE xử lý trên một đồ thị thuần túy. Có thể lấy ví dụ về việc thêm một thuộc tính mở rộng cho quy trình phân tích trong đồ thị. Đó là khi muốn mở rộng thêm cho quá trình phân tích quan hệ đơn thuần một thuộc tính chỉ nghề nghiệp của người tham gia mạng xã hội. Giả sử xét nghề nghiệp SINH VIÊN, đối với việc tính toán dựa trên ma trận, việc này là hết sức khó khăn, có thể phải xây dựng lại toàn bộ ma trận. Nhưng với WAVE, việc cần làm chỉ là tạo ra một nút với tên gọi “SINH VIÊN”, và những nút có sẵn nếu có thuộc tính nghề nghiệp tương ứng thì sẽ có một liên kết với tên gọi dạng “LÀ” đến nút “SINH VIÊN” này. Rất dễ ràng, và lúc này việc tìm kiếm một cá nhân với thuộc tính nghề nghiệp là sinh viên lại trở lại với một bài toán đồ thị đơn giản: tìm kiếm các nút có liên kết “LÀ” đến nút “SINH VIÊN”. Ví dụ này cho thấy khả năng mở rộng rất lớn của đồ thị, mạng tri thức trong WAVE. Khi các cơ sở, thuộc tính tăng lên, WAVE chỉ cần thay đổi một phần nhỏ của đồ thị trong khi những truy vấn trước đó sẽ không bị ảnh hưởng hoặc bị ảnh hưởng rất ít bởi những sự thay đổi đó. 12  CHƯƠNG 2: NGÔN NGỮ WAVE  Chương 2 của khóa luận này xin trình bày về cú pháp và ngữ nghĩa của ngôn ngữ Wave. Đây là một ngôn ngữ đặc biệt cho phép tạo và xử lý thông tin trong không gian mạng theo hướng. Chương trình viết bằng ngôn ngữ này có thể được coi như một thành phần linh hoạt có khả năng di động và kết hợp với các thành phần riêng lẻ, phân tán khác. Trong quá trình “di chuyển”, chương trình có thể mang theo dữ liệu đồng thời cập nhật vào dữ liệu lưu tại mạng KN. Các chương trình mặc dù được xử lý song song nhưng vẫn có những cơ chế cho phép chúng phối hợp đồng bộ với nhau thông qua hệ thống các luật. Phần cuối chương còn đề cập tới một vấn đề mang tính tương quan: Wave và các phương pháp lập trình truyền thống (lập trình tuần tự và lập trình song song). 2.1 Giới thiệu về ngôn ngữ Wave  Wave là một ngôn ngữ đặc biệt cung cấp khả năng thực thi mềm dẻo, đa người dùng trên hệ thống phân tán. Quá trình thực thi của ngôn ngữ Wave giống như virus, tức là có khả năng nhân bản và lan tỏa qua mạng, thực thi phân tán mà không cần bất kỳ sự điều khiển tập trung nào. Kiến trúc Wave mô tả quá trình xử lý phân tán qua việc tự định hướng luồng chương trình qua không gian dữ liệu phân tán có cấu trúc như một đồ thị hay được gọi là Knowledge Network. Các node trên mạng phân tán thuộc về một Wave Interpreter nào đấy. WI là thành phần có trách nhiệm thực thi trên từng bộ phận riêng lẻ của mạng, thao tác lên dữ liệu được lưu trữ trong các node.Trong khi di chuyển, những thành phần của mã Wave có thể tự nhân bản, phân chia hay được chỉnh sửa trong khi vẫn duy trì sự trao đổi dữ liệu qua lại lẫn nhau. 2.2 Node, Link và Không gian phân tán : Knowledge Network (KN)  Định nghĩa: • Node: Có thể coi là một đối tượng – hay một điểm trong không gian, chứa các biến (biến là thuộc tính của node) • Link: Có thể coi là một quan hệ giữa các nút - hay một đoạn, đường thẳng trong không gian. Nó cũng có các thuộc tính Wave tạo và xử lý KN – là tập hợp các node và các link có hướng hoặc vô hướng. Cả node và link đều có nội dung riêng của mình (kiểu giá trị là string). KN có thể được 13  phân tán trong không gian mạng, tồn tại trên nhiều máy tính khác nhau. Mỗi máy tính có thể không chứa hoặc chứa nhiều node của KN và các link có thể kết nối tới các node trong cùng máy tính hoặc với các máy tính khác. Tất cả các node đều có địa chỉ duy nhất trong không gian phân tán bao gồm 2 thành phần: thành phần thứ nhất để phân biệt các node trong cùng một máy, và thứ hai là để phân biệt các node giữa các máy khác nhau trong không gian mạng. Node có thể được truy cập qua các node khác một cách trực tiếp bằng Content hay bằng Address của chúng hoặc qua quá trình mở rộng qua các link của KN, việc đặt tên cho link và node nhằm phục vụ điều này. Có 2 kiểu nhảy qua lại giữa các node đó là direct hop và surface hop để thực hiện việc nhảy tới 1 node hay có thể nhảy đến tất cả các node khác – được dùng cho việc gửi quảng bá. Không giống với node, link của KN không thể truy xuất trực tiếp qua tên. Dữ liệu lưu trữ trong link chỉ có thể nhận được hoặc thay đổi một cách cục bộ, trong quá trình di chuyển qua link hay khi đứng trực tiếp tại một node cụ thể nào đó. Từ một node, cả nội dung và hướng của link có thể truy xuất trực tiếp. Ví dụ: Hình 2 1: Knowledge Network 2.3 Tổ chức chung của ngôn ngữ Wave  Ngôn ngữ Wave đặc trưng cho quá trình lan tỏa song song trong không gian dữ liệu phân tán được biết là KN. Do vậy cú pháp của ngôn ngữ miêu tả rõ quá trình hoạt động này: 14  trong đó các phần nằm trong [] là tùy chọn Một chương trình Wave hay gọi đơn giản là Wave bao gồm sự kết hợp các tác động lên KN gọi là các move – thành phần có thể thực hiện xử lý dữ liệu cục bộ tại các Node của KN và mở rộng tới các Node khác. Quá trình thực thi song song hay thực thi không theo thứ tự được tách biệt bởi dấu phẩy (,) phát triển một cách độc lập từ cùng một Node trong KN. Tập các moves độc lập gọi là zone, được tách biệt nhau bởi dấu chấm (.), các thành phần này sẽ được thực thi một cách tuần tự. Ví dụ: Ft={Fa=1;2;3}. Fa+1. ^Ft.T=Fa Các Rule trong Wave cung cấp cho Wave khả năng mở rộng trong không gian mạng, kết hợp cùng với các Wave khác. Một ví dụ, các luật có thể tự động tách Wave ra thành nhiều nhánh riêng biệt rồi sau đó phát triển chúng song song hoặc tuần tự trong KN, chúng có thể tạo ra hoặc mở rộng KN trong khi di chuyển. Các Rule sẽ được làm rõ hơn trong phần sau. Một cách tổng quát, việc thực thi phần đầu của Wave (Wave’s Head) tại một vài Node có thể là nguyên nhân dẫn tới quá trình lan tỏa của Tail của chuỗi Wave (Wave’s Tail) tới 0 hay nhiều các Node khác– chúng ta sẽ gọi chúng là tập các Node tới được (SNR). Ví dụ: • w1.w2.w3.w4 : cấu trúc của một chương trình Wave - sự nối tiếp của các zones • w1,w2,w3: zone đơn lẻ với tập các move độc lập, tất cả đều được thực thi tại cùng một Node bắt đầu • w1,w2.w3,w4: sự kết hợp của 2 kiểu trên. wave  Æ  {{move , } . }  move Æ  {  data_unit act  }  |  [rule]  (Wave) }  rule   Æ  SQ | OS | AS | AP | RP | WT | ID | CR  unit   Æ  { stirng;  } | N{l_d} | F{l_d} | C | A | P | S | L  | T |  act    Æ  # | ~ | /~ | == | / = | < | <= | + | ‐ | * | / | ** |  |  | % | & | : | :: |  15  2.4 Cấu trúc dữ liệu cơ bản của Wave  Wave là ngôn ngữ được dùng cho quá trình xử lý trên mạng, nhưng không giống các ngôn ngữ khác, kiểu dữ liệu cơ sở không phản ánh việc đó. Wave sử dụng kiểu dữ liệu cơ sở là Vector: là tập các string được phân tách nhau bới dấu chấm phẩy (;). Tất cả các hoạt động của ngôn ngữ đều thực thi trên Vector. Truy cập tới thành phần của Vector có thể thông qua chỉ số hay chính nội dung của các thành phần trong Vector – indexing và contenting. Dữ liệu lưu trữ trong Vector là động, tức có thể thay đổi khi có sự thêm bớt dữ liệu một cách tự động. Ví dụ: • Vector chứa 1 phần tử: 3 • Chứa 6 phần tử: 1;2;3;4;5;6 • Chứa nhiều kiểu dữ liệu khác nhau: 34;NONE;25;;a;;;b 2.5 Biến Spatial và kiểu  Wave thao tác trên kiểu biến được gọi là spatial variable, chúng nằm phân tán và thường liên quan tới dữ liệu cục bộ tại các Node của KN hay có thể thuộc về một chuỗi Wave nào đó. Biến kiểu này được chia làm 2 loại: task variable và environment variable  2.5.1 Task variables   Task variable bao gồm: node variable và frontal variable. Các biến kiểu nodal được lưu cục bộ tại node của KN, các biến kiểu frontal có thể đi cùng Wave qua các node khác nhau trong mạng. Cả 2 loại biến này đều là tạm thời. 9 Biến Nodal: các biến loại này được khai báo bắt đầu bằng ký tự N 9 Biến Frontal: các biến loại này được khai báo bắt đầu bằng ký tự F  2.5.2 Environment variables  Biến môi trường có những định danh và ý nghĩa khác nhau: 9 CONTENT (C): chứa content của Node hiện thời. Giá trị của C luôn là string, việc thay đổi nội dung của C có thể được gán trực tiếp bằng giá trị nào đó hoặc NONE – xóa Node cùng với các Link liên kết với nó. 9 ADDRESS (A): địa chỉ của Node hiện thời. Luôn trả lại địa chỉ đầy đủ của Node nơi Wave đang đứng gồm định danh của Node trong máy và định danh của Node trong mạng. Đây là biến chỉ đọc. 16  9 PREDECESSOR (P): biến lưu địa chỉ của Node trước đó Wave đã đi qua. Nó chỉ thay đổi khi có sự di chuyển của Wave sang Node khác. 9 LINK (L): chứa content của Link vừa mới đi qua. 9 TERMINAL (T): một loại biến đặc biệt dùng để in ra giá trị tương ứng tại một đầu cuối nào đó. Ví dụ: • Biến Nodal: N, Nhieu, Ntue.. • Biến Frontal: Fpath, Ftemp… • Biến môi trường: TERMINAL, LINK, L… 2.6 Các hành động ‐ ACTS  2.6.1 Control acts  Các Act thực hiện các phép toán cơ bản bên trong move, dùng để thay đổi giá trị các biến, thay đổi trạng thái hoạt động của wave. Giá trị trả về gồm 3 loại chính sau: • TRUE (2): thành công và cho phép Wave tiếp sau đó thực thi tại Node hiện thời. • DONE (1): thành công nhưng không cho phép Wave thực thi tiếp tại Node hiện thời. • FALSE (0): thất bại, loại bỏ Wave tại Node hiện thời. Control acts được phân loại như hop, filters, assignment, state genertator và code injection. Hop. Được thực thi bằng toán hạng #. Ta sẽ hiểu rõ hơn cách thực thi của Hop qua các Ví dụ sau: • DIRECT # ALL, cách viết khác @#: nhảy tới tất cả các node khác trong KN trên cùng máy tính từ một node nào đó • -p#b: nhảy từ node hiện thời theo cung đi ra (-)p tới node b • ANY#ALL hay #: nhảy qua tất cả các link tới tất cả hàng xóm của một node • Và một số kiểu nhảy khác: x#ALL, ANY#x • Để nhảy sang 1 node ở máy khác ta có cấu trúc: a#b$$`IP, trong đó IP là địa chỉ IP của máy đích Filter. Các filter gồm các phép toán sau đây: ~ (thuộc về), /~ (không thuộc về), == (so sánh bằng), /= (so sánh không bằng), < (so sánh nhỏ hơn), <= (so sánh nhỏ hơn hoặc 17  bằng), > (so sánh lớn hơn), >= (so sánh lớn hơn hoặc bằng). Giá trị trả về sẽ là TRUE hoặc FALSE. Nếu giá trị trả về là TRUE, node hiện thời sẽ trở thành một SNR và Wave tail sẽ tiếp tục phát triển từ node này. • Filter ~: o Cú pháp: vector1 ~ vector2 o Chức năng: kiểm tra các phần tử của vector 1 có nằm trong vector 2 hay không • Ví dụ: a;b ~ p;q;b;a sẽ trả về TRUE • Filter /~: ngược lại toán tử ~ • Filter ==: o Cú pháp: v1 == v2 o Chức năng: kiểm tra 2 vector có bằng nhau hay không o Ví dụ: 2;3 == 2;3 sẽ trả lại TRUE • Filter /=: ngược lại với == • Các filter còn lại: >,>=,<,<= có ý nghĩa toán học thông thường nhưng được thực hiện trên vector Nếu 1 filter trả lại giá trị TRUE, node hiện tại sẽ trở thành SNR, ngược lại SNR sẽ rỗng và chuỗi Wave sẽ dừng quá trình thực thi. Assignment. Toán tử gán = sẽ gán giá trị của toán hạng bên phải vào toán hạng bên trái. Dữ liệu bên phải có thể là giá trị số, string, biến, vector. Phép gán luôn trả lại kết quả là TRUE. Ví dụ: Na=1, Na=1;2;3, Na=Nb;2;3;Fc State Generator. Các trạng thái trả về ở trên đều xảy ra sau một quá trình thực thi nào đó. Đôi khi ta muốn trực tiếp xác định trạng thái kết quả trả về để điều khiển luồng chương trình, có một cách khác để thực hiện đó là dùng State Generator gồm 4 trạng thái: TRUE, DONE, FALSE, ABORT. Cú pháp gồm tên trạng thái, theo sau là dấu ! Ví dụ: w1.TRUE!.w2 Trong Ví dụ này w2 sẽ tiếp tục thực hiện • w1.DONE.w2 hoặc w1.!.w2 sẽ dừng sau khi thực hiện xong w1 18  Code Injection. Cú pháp ^Func, trong đó Func là một chuỗi Wave. Phép chèn mã này sẽ bổ sung thêm vào chuỗi Wave một chuỗi nằm trong biến sau ^. Phép này hay được sử dụng khi gọi chương trình con Ví dụ: Ft={Fa=1;2;3}. Fa+1. ^Ft.T=Fa 2.6.2 Fusion acts: Các phép toán hợp nhất  Các phép toán số học. Bao gồm các phép toán +, -, *, /. Nếu thực hiện chia cho 0, kết quả trả về là FALSE Ví dụ: • `124.36’ + 100 có kết quả: `224.36’ • 66;4;24 – 1;1;1;1;1;1;1 có kết quả: 65;3;23;-1;-1;-1;-1 • 1;2;3;4;5 * 1;1;1 có kết quả: 1;2;3;0;0 • 2;3;4 / 1;2 có kết quả: FALSE • NONE * sẽ trả lại rỗng Các phép toán trên Vector đặc biệt. Gồm 1 số phép toán sau: • &: append, nối 1 Vector vào sau 1 Vector khác o Ví dụ: v1 & v2 – v1, v2 là 2 Vector • Toán tử hai chấm (:) : lấy giá trị tại 1 vị trí của Vector o Ví dụ: Fa=3;2;3. Fa:1 sẽ trả lại 3 • Toán tử (::): o Ví dụ: Fa=3;2;3. Fa::3 = 10. Kết quả Fa = 10;2;10 • |: splits, chia string ở toán hạng bên trái thành 1 Vector các string con bởi dấu phân cách ở toán hạng bên phải o Ví dụ: `a+b+c’ | `+’ sẽ trả lại a;b;c • %: join, ngược lại với | tức nó sẽ hợp các Vector con lại thành 1 string với phân cách là toán hạng bên phải o Ví dụ: a;b;c % `+’ sẽ trả lại a+b+c Gọi hàm bên ngoài (External calls). Thực hiện qua toán tử ?, gọi một hàm nào đó của hệ thống với đầu vào là các tham số từ Wave truyền vào Ví dụ: 50?`sleep’ sẽ dừng chương trình 50 giây 19  2.7 Rules – Các luật trong Wave  Wave có thể phát triển độc lập, dị bộ và được xử lý song song trong không gian phân tán. Tuy nhiên điểm mạnh của Wave là nó có hệ thống các RULE để quản lý và đồng bộ các các hành động. RULE thiết lập các ràng buộc trong việc lan tỏa chuỗi Wave. Thông qua RULE, hệ thống có thể thực thi nhiều lần một Wave, hay tiếp tục lan tỏa Wave nếu thỏa mãn một điều kiện nào đó, hoặc có thể chấm dứt toàn bộ wave. RULE thường “treo” phần còn lại của chuỗi Wave (remainder) và lan tỏa nó ra chỉ khi chuỗi Wave nằm trong luật thực thi xong và trả lại trạng thái TRUE. 2.7.1 Các Luật Rẽ Nhánh  • SEQUENCE(SQ): kích hoạt tất cả các nhánh một cách tuần tự mà không cần quan tâm tới trạng thái kết quả trả về. SNR trên SQ là tập các SNR từ các nhánh con. Ví dụ: SQ(Fa=1, Fa+1).T=Fa sẽ tạo ra 2 nhánh Fa=1 và Fa+1, thực hiện tuần tự 2 nhánh này. Kết quả cuối là 2 • OS_SEQUENCE: kích hoạt tất cả các nhánh tuần tự cho tới khi nó nhận được kết quả TRUE hoặc DONE trả về từ một nhánh nào đó Ví dụ: OS(Fa=5.Fa>1, T=Fa) tạo ra 2 nhánh Fa=5.Fa>1 và T=Fa và thực hiện tuần tự. Nhưng do nhánh thứ nhất trả về TRUE nên không thực hiện tiếp nhánh thứ 2 • AND_SEQUENCE(AS): tương tự SQ nếu tất cả các nhánh đều trả về TRUE hoặc DONE, nếu 1 nhánh FALSE, trạng thái toàn bộ AS sẽ là FALSE Ví dụ: AS(TRUE!, FALSE!) sẽ trả lại FALSE • OR_PARALLEL(OP): kích hoạt các nhánh và thực thi chúng song song, nếu 1 nhánh trả về TRUE hoặc DONE, OP sẽ nhận TRUE. Nếu không nhánh nào trả về TRUE hoặc DONE, OP sẽ FALSE Ví dụ: OP(FALSE!, FALSE!, TRUE!) sẽ trả lại TRUE • AND_PARALLEL(AP): như AS nhưng các nhánh thực thi song song Ví dụ: AP(TRUE!, TRUE!, FALSE!) sẽ trả lại FALSE • RANDOM(RN): chọn một nhánh ngẫu nhiên để phát triển tiếp 20  2.7.2 Repetition  Luật REPEAT với khả năng vòng lặp cho phép chia Wave thành các phần nhỏ hơn khi di chuyển trong KN. Nếu kết quả trạng thái trả về là TRUE hoặc FALSE (SNR không rỗng) thì mỗi thành phần này sẽ được ghép thêm Tail của Wave. Lúc này, ở tất cả SNR Node đều chứa biến Frontal (biến này được mang tới từ các Node). Nếu kết quả trạng thái trả về là DONE (SNR không rỗng) thì Tail của Wave sẽ bị loại bỏ. Ví dụ: F = 1; 9; 5; 6; 7; 8; 12. REPEAT ( Fi +1. F : Fi /= NONE. N + ( F: Fi)). TERMINAL =N. 2.7.3 Create  Luật CREATE(CR) cho phép Wave có khả năng mở rộng chính mạng KN trong khi lan tỏa trong không gian. Chuỗi Wave chứa luật này vẫn phát triển như thông thường, chỉ có các bước nhảy là bị ảnh hưởng - có thể thay đổi chế độ của chúng từ chế độ lan tỏa (navigation) sang chế độ tạo mới (creation). Khi đó các node và link nếu chưa có sẽ được tạo ra. Có rất nhiều chi tiết quan trọng trong ngữ nghĩa của luật CR. Nếu node của 1 bước nhảy tương ứng bằng địa chỉ của nó – điều này có nghĩa node đó đã tồn tại, tức các thành phần trong luật CR nếu chưa có sẽ được tạo ra, còn nếu đã tồn tại thì quá trình CR sẽ không tạo ra node hoặc link mới. Ví dụ: CR(@#a.+p#b.+q$$c`192.168.1.10’) Ý nghĩa: nhảy trực tiếp tới node a mặc dù node a chưa có nhưng do nằm trong luật CR nên node a sẽ được tạo ra, sau đó tạo ra link có hướng +p tới node b, tạo node c và link +q nối từ a đến c trên máy 192.168.1.10 2.7.4 Release  Luật RL sẽ khởi tạo một Wave mới độc lập với chuỗi Wave ban đầu, mã của Wave mới này là phần nằm trong dấu ngoặc của RL, WE của Wave mới chính là WE của 21  Wave ban đầu. Wave mới được tạo ra được đưa vào Wave Queue để chờ xử lý. Phần remainder của Wave ban đầu sẽ tiếp tục được thực hiện như bình thường. Ví dụ: w1.RL(w2).w3 Ý nghĩa: sau khi thực thi xong w1, gặp RL chương trình Wave sẽ tách w2 cùng với biến môi trường thành Wave mới cho vào hàng đợi xử lý, chuỗi Wave tiếp tục thực thi là w3 cùng với biến môi trường của nó. 2.8 Wave và mô hình lập trình truyền thống  2.8.1 Sơ đồ luồng (SD)  Wave là ngôn ngữ có khả năng xử lý cấu trúc dữ liệu không gian phân tán lớn. Một thuộc tính quan trọng của Wave là các chương trình điều khiển luôn được liên kết với vị trí nào đó trong không gian dữ liệu (trong khi dữ liệu giữa các Node lan tỏa, hay giữa các SNR lan tỏa). Dữ liệu của cùng một Node có thể xuất hiện ở những nơi khác nhau trong cùng một SNR ở cùng một không gian cục bộ. Hình 2 2 Thành phần của Spread Diagrams Các kiểu module của Spread Diagram là • SNR • Move • Rule • Halt 22  • Các thành phần liên quan o Link o Biến Spatial 2.8.2 Wave và mô hình lập trình song song  Wave biểu diễn theo SD trong mạng dữ liệu có thể được điều khiển hoàn toàn bởi Rule. Các thành phần của chuỗi Wave tự tách thành các nhánh trước và trong quá trình thực thi. Ví dụ: Tách chuỗi Wave m1, m2 , m3. m4, m5 Æ (m1. m4, m5), (m2. m4, m5 ), (m3. m4, m5) Hình 2 3: Tự động tách trong chuỗi Wave Ngoài ra, trong quá trình Wave thực thi, các thành phần của nó có thể được sao chép và thay thế mà dữ liệu không bị thay đổi (Như trong Hình 2 4: m2 được sao chép và thay thế mà dữ liệu vẫn được giữ nguyên) m1. m2. m3 Æ m1. m2, m2, m2. m3 Æ m1.(m2. (m3, m3, m3)), (m2. (m3, m3, m3)), 23  (m2. (m3, m3, m3)) Hình 2 4: Một số trường hợp xử lý song song Ở một ví dụ khác ta thấy rõ hơn Rule điều khiển chuỗi Wave như nào (Hình 2 5). Hình 2 5: Wave xử lý song song có kèm theo Rule m1. OR_PARALLEL (m2, m3. m4). m5 Æ m1. OR_PARALLEL((m2, m4), (m3. m4)) .m5 Æ 24  m1. OR_PARALLEL((m2. m4, m4, m4), ( m3. m4, m4, m4) ). m5 2.8.3 Wave và mô hình lập trình tuần tự  Việc cho phép phát triển không gian, xử lý song song và tự động trong môi trường phân tán, Wave có thể dễ dàng mô hình hóa một số chương trình xử lý tuần tự. Giống các chương trình bình thương, truyền thống ở cùng một máy tính, Wave phải ở cùng một điểm trong không gian và chỉ có duy nhất một luồng được xử lý. Chúng ta sẽ bàn về vấn đề này thông qua các ví dụ ở dưới đây. Ví dụ 1 s1. s2. s3. s4 Ví dụ 2 SEQUENCE (s1, s2, s3, s4) Hai ví dụ trên được thể hiện ở Hình 2 6 Hình 2 6: Xử lý tuần tự không Rule và có Rule Ngoài ra có thể ví dụ ở Hình 2 7 s1. SQ ((s2. s3), s4) và SQ (s1, (s2. SQ (s3, s4))) 25  Hình 2 7: Wave xử lý tuần tự có Rule • Biều thức If-else Biểu thức điều kiện “If- else” trong mô hình lập trình tuần tự có cú pháp như sau: If (e) s1 else s2 Mệnh đề s1 thực hiện và trả về kết quả đúng thì mệnh đề s2 sẽ được thực thi. Ở Hình 2 8: OR_SEQUENTIAL (( e. s1), s2) và OR_ SEQUENTIAL (AND_SEQUENTIAL ( (e. DONE ! ) , s1). s2) Hình 2 8: Một số trường hợp với mệnh đề if-else 26  Hình 2 9: Một số trường hợp với mệnh đề if-else • Lựa chọn nhiều nhánh o If – else với filter Hình 2 10: else-if với filter 27  o Else – if parallel Hình 2 11: else-if parallel o Else – if với Rule Hình 2 12: else-if với Rule 28  o Switch Hình 2 13: Switch • Vòng lặp o while ( e ) s o do s while ( e ) o For (e1 ; e2 ; e3) s 29  Hình 2 14: Câu lệnh lặp sử dụng Repetition Hình 2 15: Câu lệnh lặp sử dụng Recursion 30  CHƯƠNG 3: XÂY DỰNG MẠNG TRI THỨC CHO MẠNG XàHỘI  Về cơ bản, một mạng xã hội sẽ cho phép người dùng tạo ra cho mình một “profile” [19] (tạm hiểu là một trang thông tin cá nhân). Ở trang cá nhân đó, người dùng có khả năng tùy chỉnh về giao diện, các bài viết, các thành phần theo sở thích cá nhân. Họ cũng có thể đăng tải hình ảnh đại diện (tiếng Anh: avatar), hoặc tạo ra những album ảnh cá nhân để chia sẻ cùng mọi người. Một cơ chế quan trọng nữa của mỗi mạng xã hội là bạn bè – friends. Cơ chế kết bạn trong các mạng xã hội thường là khi muốn kết bạn với ai đó, người dùng phải được người kia chấp nhận lời mời. Một vài mạng xã hội có một cơ chế khác là Favorites (tạm hiểu: các thông tin ưa thích) giúp cho họ có thể theo dõi một số hoạt động của người khác mà không cần phải có quan hệ bạn bè với người kia. Do vậy các mạng xã hội cũng phải cung cấp thêm các tính năng cơ bản cho việc xác định quyền hạn đối với người xem, bạn bè. Cơ chế này đơn giản nhất là cho phép hay không cho phép những người chưa có kết nối bạn bè xem các thông tin có trên trang cá nhân, hay chặn một số người ác ý xuất hiện trên mạng xã hội. Đó là cấu trúc cơ bản của một mạng xã hội, ngoài ra các mạng xã hội có thể cung cấp thêm các tính năng khác giúp làm cho người dùng thấy thoải mái nhất khi tham gia. Phổ biến trong các tính năng kiểu như vậy là khả năng tham gia mạng xã hội sử dụng OpenID [23], hay chia sẻ các video clips từ các mạng xã hội khác (Youtube, Flickr …), và rất mới mẻ nhưng cũng không kém phần quan trọng là khả năng truy cập cho các thiết bị di động. Số lượng người sử dụng các thiết bị di động hỗ trợ khả năng duyệt web ngày càng tăng làm cho việc quan tâm tới khả năng tương thích với các thiết bị di động vốn hạn chế hơn về tính năng trở nên cần thiết hơn bao giờ hết. 3.1 Mạng xã hội Yahoo!360  [9] Các mạng xã hội ở Việt Nam cũng đang ở giai đoạn phát triển khá mạnh. Các nhà cung cấp dịch vụ đang đẩy mạnh việc tạo ra những mạng xã hội của riêng mình, mang phong cách thuần Việt hơn, hướng đến lớp người dùng trong nước. Tuy vậy có một dịch vụ đã phát triển được khá lâu và hiện vẫn đang là mạng xã hội có số lượng người dùng lớn nhất Việt Nam, đó là Yahoo!360. Ra đời vào năm 2005 và mau chóng trở thành một trào lưu trong cộng đồng sử dụng Internet Việt Nam, Yahoo!360 đã trở thành một ngôi nhà thứ hai, một ngôi nhà ảo cho cộng đồng mạng. Với các tính năng giúp chia sẻ thông tin khá thú vị, đồng thời rất dễ sử dụng, Yahoo!360 giúp cho mọi người đều có thể đến với thế giới mạng xã hội một cách dễ dàng, từ giới trẻ năng động, cho tới các bậc phụ huynh … Cùng với đó, cơ chế 31  liên lạc rất mở rộng của Yahoo!360 cũng giúp cho mạng xã hội này thu hút thêm được một số lượng đông đảo những nhà nghiên cứu lịch sử, chính trị, những ca sĩ, diễn viên nhằm mở rộng quan hệ với công chúng. Mạng xã hội này từ đó đã trở thành một sân chơi chung dành cho rất nhiều lớp người Việt đến từ nhiều ngành nghề khác nhau. Cũng như các mạng xã hội khác, Yahoo!360 được tạo thành từ một mạng các cá thể được liên kết với nhau như một đồ thị vô hướng. Như vậy, như đã đề cập ở trên, các công cụ tìm kiếm hiện nay chưa thể làm việc với quan hệ đồ thị dạng này của các mạng xã hội, cho nên đây sẽ là một lĩnh vực cần và còn được khai thác trong nay mai. Chương trình dựa trên nền WAVE trong khóa luận này sẽ nắm phần nào nhiệm vụ khai thác này. Từng trang cá nhân trong Yahoo!360 được phát triển như một trang thông tin cho một cá nhân (hay một nhóm người, tùy vào mục đích sử dụng). Trong đó có các thành phần cơ bản như blog (nhật ký ảo), friend list (danh sách bạn bè), blast, list (danh sách sở thích), comment (bình luận), tag … Blog là thành phần chính trong một trang cá nhân Yahoo!360. Đây là nơi cho người dùng viết lên những suy nghĩ, cảm xúc … về mọi thứ diễn ra xung quanh, nên nó còn được gọi là nhật ký ảo. Mỗi một bài viết như vậy còn được gọi là một entry. Bạn bè của người viết sẽ vào xem những bài viết như vậy, để lại những lời bình luận, đánh giá nếu muốn. Friend list chính là điểm cấu thành mạng xã hội Yahoo!360. Friend list chỉ ra mối quan hệ giữa các cá thể trong mạng xã hội Yahoo!360, ở đây là mối quan hệ bạn bè. Nhờ có danh sách bạn bè này mà ta có thể biết được tất cả bạn bè của một người. Việc thăm danh sách bạn bè của một người để tìm ra bạn bè của người đó, rồi cứ tiếp tục thăm dần dần tới những người bạn đó để lại tiếp tục tìm ra bạn bè của họ sẽ giúp ta lan tỏa dần trong đồ thị mạng xã hội Yahoo!360. Việc này không khác gì với việc làm sao để thăm tất cả các nút trong một đồ thị vô hướng, vấn đề chỉ còn là thuật toán và cách thức tiến hành việc thăm sao cho công sức bỏ ra là nhỏ nhất. Blast cũng là một thành phần khá thú vị trong Yahoo!360. Blast có thể là một lời giới thiệu, mẩu tin nhỏ, một đường siêu liên kết, hay đơn giản là suy nghĩ trong đầu người viết tại thời điểm đó. Blast được đặt ở vị trí đầu của trang cá nhân Yahoo!360, điều này giúp cho blast trở thành thứ được để ý đầu tiên khi ghé thăm một trang cá nhân. Nếu một trang cá nhân Yahoo!360 được ví như một cuốn nhật ký, một cuốn sách thì 32  có lẽ blast sẽ đóng vai trò như lời mở đầu, lời đề tựa cho cuốn nhật ký, cho cuốn sách đó. Một thành phần khác trong Yahoo!360 cũng rất thu hút đối với những người tham gia mạng xã hội này là hệ thống các comment hay còn gọi là bình luận. Với hệ thống này, những người tham gia có thể trao đổi những dòng tin ngắn với nhau, về một chủ để nào đó, về vấn đề trong bài viết của người viết … Với hệ thống này, những người bạn có thể thể hiện sự quan tâm đến nhau, nhờ đó duy trì mối quan hệ bạn bè. Ngoài ra Yahoo!360 còn có các thành phần khác nhằm giúp người dùng tìm ra những người có cùng sở thích với mình như Lists. Hay Tag cloud giúp tạo ra các từ khóa (tiếng Anh: keyword) nhằm hệ thống hóa các bài viết mà người dùng đã soạn. Những thành phần này có thể được minh họa ở ảnh chụp màn hình, Hình 3 1 dưới đây Hình 3 1: Các thành phần trong một trang cá nhân Yahoo!360 Với những đặc điểm như trên, Yahoo!360 đã và đang là dịch vụ mạng xã hội được sử dụng nhiều nhất, và có người dùng gắn bó nhất tại Việt Nam. Điều đó lý giải được tại sao người dùng Việt Nam quyết bám trụ lại mạng xã hội này, thậm chí có những động thái yêu cầu nhà cung cấp tiếp tục duy trì và phát triển dịch vụ này khi gần đây có nhiều thông tin cho rằng mạng xã hội Yahoo!360 chuẩn bị đóng cửa. Do vậy, trên thực tế, việc phân tích và tìm kiếm thông tin trên mạng xã hội này là rất đáng giá. 33  3.2 Xây dựng mạng tri thức cho mạng xã hội Yahoo!360 Để thực hiện được những bài toán đặt ra trên cơ sở quan hệ đồ thị của WAVE, cần phải tạo ra được một đồ thị quan hệ trong WAVE, hay còn gọi là một KN – Mạng tri thức. Đối với các bài toán phân tích mạng xã hội, cần phải thực thi việc tạo ra KN tương ứng với đồ thị quan hệ trong mạng xã hội đó. Tức là mỗi cá thể (mỗi cá nhân hiện diện trên mạng xã hội) sẽ tương ứng với một nút trong KN, quan hệ giữa các cá thể là đường liên kết giữa các nút trong KN. 3.2.1 Thu thập thông tin cho mạng tri thức Việc đầu tiên cần làm là phải lấy ra được một hệ thống các nút tương ứng với các cá thể trong mạng xã hội. Và để làm việc này sẽ có từng bộ Web Crawler – Parser tương ứng với từng dạng mạng xã hội khác nhau. Bộ Web Crawler – Parser đơn giản là một phương thức trong Java dùng để lấy về toàn bộ mã HTML của liên kết (URL [18]) được chỉ định, mà ở đây là đường dẫn tới danh sách bạn bè (tiếng Anh: Friend List) của một cá thể nào đó trên mạng xã hội. Sau khi lấy được nội dung dạng mã HTML lưu trữ như một xâu ký tự trong Java, bộ Phân tích cú pháp (tiếng Anh: Parser) làm việc và lấy ra các friend có xuất hiện trong mã HTML thu được. Thực ra bộ phân tích cú pháp ở đây không hoàn toàn đúng nghĩa là một bộ phân tích cú pháp, nó không có luật cú pháp, cũng không sinh ra tập từ tố … Bộ phân tích ở đây chỉ làm nhiệm vụ lợi dụng việc tồn tại những ký tự tạo nên một định danh cho mỗi cá nhân trên mạng xã hội trong mã HTML của danh sách bạn bè, cộng với việc có một số mã HTML với các thuộc tính nhất định nằm trước và sau định danh đó, từ đó tìm kiếm vị trí các định danh đó, lấy ra và lưu trữ tại Cơ sở dữ liệu. Như vậy, về mặt bản chất bộ Web crawler và Parser yêu cầu hai điều kiện: - Danh sách bạn bè của một cá thể trong mạng xã hội phải có thể được hiển thị và lấy về dưới dạng mã HTML. - Mã HTML thu về phải có những quy tắc nhất định để xác định vị trí của các định danh tương ứng với từng cá thể trong mạng xã hội. Đây là cách thức xử lý trong thời điểm hiện tại, rõ ràng vẫn bộc lộ nhiều điểm hạn chế nhất định: - Việc phải lấy toàn bộ mã HTML của trang web danh sách bạn bè của mạng xã hội là tương đối lãng phí đường truyền, bởi trong một trang web có thể còn có nhiều thành phần hơn là chỉ có mã HTML (vd: JavaScript, CSS …), 34  ngoài ra còn có ảnh … trong khi cái cần thu được chỉ là một vài đoạn mã HTML đơn giản. - Việc phân tích mã HTML dựa vào các đặc điểm nhất định để lấy ra vị trí xuất hiện các định danh có thể bị ảnh hưởng nếu trong mã HTML đó xuất hiện các đặc điểm nhưng do người dùng tạo ra. Việc này sẽ có thể làm sai lệch kết quả thu được. Cụ thể với mạng xã hội Yahoo!360, dựa vào một vài đặc điểm của mạng này giúp thỏa mãn các điều kiện kể trên, chương trình có thể xây dựng nên KN tương ứng với mạng. Đầu tiên đó là việc mỗi cá nhân, mỗi blog trong mạng xã hội Yahoo!360 đều được mang một giá trị duy nhất, như một “khóa” chỉ ra đích danh cá nhân đó trong toàn mạng xã hội. Đó là một chuỗi ký tự được sinh ngẫu nhiên bởi Yahoo, dạng “4CpxgpElc6f19oY.sVNubnV5cw”. Định danh này cũng được sử dụng luôn trong đường dẫn URL của mỗi blog, như một cách để giấu đi định danh thật (tên tài khoản Yahoo) thường ở dạng text thông thường. Với mỗi blog, trang đầu tiên được hiển thị sẽ có URL dạng: Hình 3 2: Cấu trúc của đường liên kết tới dịch vụ Yahoo!360 Theo Hình 3 2, định danh cho mỗi blog là không đổi với các đường dẫn tồn tại trong blog đó, còn có các thành phần có thể thay đổi tùy vào thành phần muốn được hiển thị, hay các tùy chọn hiển thị thêm vào. Ví dụ như trên hình minh họa, thành phần “profile” có thể được thay thế bằng “blog” nếu muốn xem danh sách các bài viết của blog này, hay thay bằng “friends” khi muốn xem danh sách bạn bè của chủ blog. 35  Ngoài ra có tùy chọn hiển thị như “cs=0” dùng khi muốn trình duyệt bỏ qua không hiển thị theme của blog, hay nếu đang ở thành phần xem blog bài viết thì có tùy chọn “list=1” để đặt chế độ xem các bài viết dạng danh sách (tiếng Anh: list) (tiết kiệm băng thông do chỉ phải nạp trang với danh sách tiêu đề các bài viết chứ không nạp toàn bộ nội dung của các bài viết). Nhờ vào tính chất như vậy, bộ Web Crawler – Parser đối với Yahoo!360 làm nhiệm vụ thu thập các định danh người dùng của từng blog để tạo ra KN bằng cách bắt đầu từ một định danh nào đó (coi như một giá trị khởi tạo). Tiếp đó tiến hành lấy mã HTML của danh sách bạn bè của blog với định danh đó bằng cách thay thế định danh có được vào chuỗi URL với thành phần hiển thị được chỉ định là “friends”. Có được mã HTML, bộ Parser hoạt động, lọc ra các định danh có trong mã HTML đó và tiếp tục quá trình lấy mã HTML của các định danh mới thu được. Với phương pháp như vậy, dần dần từ một blog, sử dụng phương thức lan tỏa theo chiều rộng, chương trình sẽ thu được hầu như toàn bộ các định danh của các blog tồn tại trên hệ thống Yahoo!360. Với thử nghiệm hiện tại là mạng xã hội Yahoo!360, cách thức crawl web và phân tích mã HTML như nêu trên vẫn có thể áp dụng mà không phát sinh lỗi. Tuy nhiên về phát triển sau này, chương trình sẽ có thể sử dụng những bộ Web Crawler – Parser, có thể tích hợp Cơ sở dữ liệu hỗ trợ tìm kiếm Full-text được phát triển riêng như Nutch [22]. Bởi còn cần có một cơ chế ở mức phát triển cao hơn của hệ thống này, thực hiện việc lấy và lưu trữ nội dung của mỗi trang web cá nhân (gọi tắt là blog) thu được như các bài viết, comment … 3.2.2 Tạo dựng mạng tri thức  Sau khi đã thu thập được một tập hợp các định danh của các blog trên mạng xã hội Yahoo!360 cùng với mối quan hệ bạn bè của từng định danh đó, cần tạo dựng mạng tri thức ứng với mạng xã hội này. Khi Wave Interpreter được khởi tạo, nó sẽ tạo ra một mạng tri thức (KN) “rỗng”, tức là chưa tồn tại một nút nào trên đó. Như vậy, để tạo ra mạng tri thức với các nút tương ứng với các định danh thu được ở trên, chương trình chỉ cần gửi truy vấn cho WI, đề nghị WI tạo ra những nút cũng như liên kết như đã xác định. Câu truy vấn có dạng: 36  CR(@#`blogID_1’ . `friend’#`blogID_2’ , `friend’#`blogID_3’ , `friend’#`blogID_4’) Với câu truy vấn này, WI sẽ hiểu rằng phải tạo ra trên KN một nút với định danh là “blogID_1”, sau đó tạo ra các nút với định danh lần lượt là “blogID_2”, “blogID_3” và “blogID_4”. Đồng thời WI cũng hiểu rằng sẽ phải tạo ra các liên kết mang tên “friend” từ nút “blogID_1” tới 3 nút còn lại. Như vậy, với câu truy vấn tương đối đơn giản, một mạng tri thức nhỏ đã được tạo ra với 4 nút có liên kết với nhau theo kiểu “friend”, hay nói cách khác, một phần nhỏ của mạng xã hội Yahoo!360 đã được tạo ra, quan hệ bạn bè cũng đã được xác định trong đó. Thêm một cơ chế nữa của WI đó là khi WI nhận được một truy vấn tạo nút với định danh giống với nút đã được tạo ra trước đó thì truy vấn đó được bỏ qua, không có sự thay đổi nào tới mạng tri thức đã được tạo. Do vậy, cứ tiếp tục với các nút khác thu thập được, chương trình chỉ cần gửi cho WI những câu truy vấn dạng trên thì dần dần mạng tri thức gần như hoàn chỉnh so với mạng xã hội Yahoo!360 sẽ được tạo ra với đầy đủ các mối quan hệ như trong mạng Yahoo!360. 3.2.3 Lưu trữ  Về cơ bản, quá trình thu thập thông tin hay tạo dựng mạng tri thức đều không nhất thiết phải cần đến một hệ cơ sở dữ liệu hoàn chỉnh bởi các thông tin hoàn toàn có thể lưu tạm thời ra file. Tuy nhiên khi lưu trữ thông tin theo cách này, có thể gặp một số vấn đề sau: • Phải tự xây dựng các bộ đọc dữ liệu từ file cũng như thống nhất quy cách ghi dữ liệu ra file • Có thể bị xung đột khi tiến trình đọc ghi cùng truy xuất file • Truy xuất file thường chậm Ngoài ra có một bài toán đặt ra cho quá trình thu thập thông tin blog đó là làm sao để sau khi tắt chương trình (vì một lý do nào đó như lỗi, cần khởi động lại máy, sự cố mất điện …) thì khi bật lên trở lại, chương trình có thể tiếp tục quá trình thu thập thông tin từ vị trí trước khi xảy ra sự cố. Đối với bài toán cho mạng Yahoo!360, cần quan tâm tới hai thông số thu thập về: “blogID” và “friends” của blogID đó. Một cách đơn giản đó là đọc ra những bản ghi nào trong cơ sở dữ liệu mà chưa có friend nào (có giá trị rỗng), những bản ghi đó sẽ là những bản ghi cần phải sử dụng để tiếp tục thu thập 37  thông tin về bạn bè. Tuy nhiên cách này cũng không hề đơn giản nếu cơ sở dữ liệu được đặt trên một file. Hơn thế nữa, về mở rộng sau này của hệ thống là thu thập, lưu trữ thông tin về toàn bộ các thành phần cần thiết trong một blog (bài viết, bình luận …), cho nên việc sử dụng một cơ sở dữ liệu khi ấy là việc bắt buộc. Có nhiều dạng cơ sở dữ liệu có thể sử dụng cho trường hợp này, nhưng tùy vào mục đích mở rộng mà cso thể lựa chọn loại phù hợp. Nếu cần lưu trữ phân tán, hiệu năng cao, tìm kiếm theo từ khóa có thể sử dụng BerkerlyDB [36]. Nếu cần lưu trữ phân tán, tìm kiếm dạng Full-text search thì lại có thể sử dụng Solr [21] (hiệu năng vừa phải), Tokyo Cabinet [24] (hiệu năng khá cao). Nhưng với khả năng của WAVE, việc tìm kiếm full-text có thể gửi thông qua WAVE tới các máy trong mạng, từ đó việc tìm kiếm không còn mang tính chất phân tán đối với cơ sở dữ liệu nữa thì có thể sử dụng một hệ cơ sở dữ liệu không phân tán nhưng cung cấp tìm kiếm full-text search. Với lý do đó cộng với lượng dữ liệu thử nghiệm ở mức trung bình, chưa lớn, hệ thống được mô tả trong khóa luận này sẽ sử dụng một hệ cơ sở dữ liệu quan hệ quen thuộc: MySQL [35]. Với bài toán đối với mạng xã hội Yahoo!360, cơ sở dữ liệu trong MySQL hiện được thiết kế với một bảng duy nhất gồm các trường và thông số như Hình 3 3 Hình 3 3: Cấu trúc Cơ sở dữ liệu MySQL Như vậy, bài toán khôi phục sau sự cố ở trên có thể được giải quyết bằng cách lấy ra từ cơ sở dữ liệu những bản ghi có trường “friends” là rỗng. Việc này hoàn toàn đơn giản trong cơ sở dữ liệu MySQL chỉ với một câu truy vấn: SELECT `blogID` FROM `blog_list` WHERE `friends`=’’; 38  3.2.4 Filter  Vì chương trình được thực hiện dựa trên nền tảng WAVE, và lợi dụng khả năng của mạng ngang hàng để xử lý nên đòi hỏi việc lấy và lưu trữ thông tin về mỗi blog cần phải có một cơ chế phân tải. Cơ chế này tạm gọi là Filter. Trong WAVE, các nút được hình thành dưới dạng một mạng tri thức, KN. Tuy nhiên các nút đó vẫn phải được quản lý hay nói cách khác phải thuộc về một máy tính nào đó tham gia vào mạng xử lý thông tin WAVE. Mạng thật ở đây là mạng giữa các máy tham gia WAVE, mạng ảo là mạng tri thức. Một nút trên mạng thật, hay một máy tính, có thể nắm giữ nhiều nút trên mạng tri thức. Như vậy, việc phân tán tải trên WAVE mang ý nghĩa phân tán các nút trên mạng tri thức lên các máy trên mạng thật. Về cơ chế phân tán, bộ thông dịch ngôn ngữ WAVE – Wave Interpreter (viết tắt: WI) tự nó đã hỗ trợ khả năng phân tán các nút trên mạng tri thức vào các máy trong mạng thật. WI có cơ chế truyền thông riêng để gửi các yêu cầu tạo nút tới các máy khác, WI ở các máy khác lúc đó sẽ có trách nhiệm phải hoàn tất yêu cầu được gửi. WI truyền thông giữa các máy tính thông qua một định danh xác định duy nhất máy tính đó trên toàn mạng, trong giới hạn của khóa luận này, định danh đó được lấy chính là địa chỉ IP của máy. Tuy nhiên đây là bước làm sau khi đã xác định được nút nào trên mạng tri thức sẽ được quản lý tại máy nào trên mạng thật. Điều này WI không làm, do vậy chương trình muốn thực hiện được những quyết định kiểu này phải sử dụng tới Filter. Filter phải làm một cách nào đó để thông báo cho WI biết định danh của máy tính sẽ quản lý nút của mạng tri thức. Filter trong bài toán xây dựng mạng xã hội Yahoo!360 sẽ làm nhiệm vụ quyết định xem một định danh của một blog thu thập được sẽ cần được thuộc về máy nào trong một tập hợp các máy đang tham gia vào mạng WAVE. Nói cách khác, Filter sẽ như một hàm của blogID, dạng: F(blogID) = IP_ADDRESS Tức là với đầu vào là một định danh blog, blogID nào đó, Filter sẽ phải trả lại một giá trị là địa chỉ IP của máy sẽ có trách nhiệm quản lý nút tương ứng với định danh blog đó cho chương trình, từ đó chương trình sẽ gửi yêu cầu tạo nút và địa chỉ IP máy tương ứng cho WI. Việc còn lại là tạo nút trên mạng tri thức lúc này do WI đảm trách. Như vậy Filter là một thành phần hoàn toàn độc lập với thành phần thu thập thông tin và thành phần tạo dựng mạng tri thức. Có nghĩa là Filter có thể được thiết kế riêng mà 39  không cần quan tâm đến hai thành phần kia, chỉ cần thỏa mãn đầu vào và đầu ra theo đúng yêu cầu. Cũng có thể thấy Filter với khả năng như vậy, sẽ không chỉ đóng vai trò phân tải cho hệ thống, mà còn có thể được lập trình để cung cấp khả năng cân bằng tải. Cân bằng tải trong một mô hình xử lý phân tán là rất quan trọng, bởi việc cung cấp tính năng xử lý phân tán là nhằm giảm bớt xử lý cho một máy tính, nếu phân tán không hiệu quả để cho một vài máy tính phải xử lý một số lượng công việc nhiều hơn hẳn so với các máy còn lại thì việc phân tán không còn ý nghĩa. Tuy nhiên cân bằng tải là một lĩnh vực tương đối khó, bao gồm nhiều tiêu chí khác nhau như cân bằng lưu trữ, cân bằng băng thông … Trong giới hạn của khóa luận này, Filter được lập trình sẽ cố gắng ở mức cân bằng lưu trữ cho các máy, có thể giải quyết phần nào việc phân tán băng thông cho phía máy khách. Filter được thiết kế cho khóa luận làm việc theo cơ chế gần giống một mạng Chord, nhưng ở mức rất đơn giản. Filter sẽ có một danh sách các máy tính có mặt trong mạng (do giới hạn của khóa luận, danh sách này sẽ được cố định mỗi lần khởi chạy hệ thống, và phải giống nhau ở mọi máy tham gia mạng WAVE), nó tạo ra các mã băm (tiếng Anh: hash) sử dụng thuật toán MD5 [33] cho các máy ấy và sắp xếp theo thứ tự từ nhỏ tới lớn (theo thuật toán so sánh xâu ký tự trong Java). Tiếp đó khi nhận được một định danh “blogID”, Filter cũng sẽ băm định danh này với cùng thuật toán MD5, tạo một vòng lặp để so sánh (xâu ký tự) với tất cả giá trị trong danh sách các máy tính. Khi kết quả so sánh trả về nhỏ hơn 0 (mã băm của “blogID” đưa vào nhỏ hơn mã băm của máy tính đang xét), theo cách làm việc của Chord, blog có định danh “blogID” sẽ được phân cho máy đang xét. Tức là Filter khi đó sẽ trả về cho hệ thống IP của máy đang xét. 40  3.3 Sơ đồ hoạt động các thành phần trong chương trình  3.3.1 Thành phần thu thập thông tin blog  Hình 3 4: Sơ đồ hoạt động thành phần thu thập thông tin blog Sơ đồ trên Hình 3 4 mô tả chi tiết hoạt động của thành phần thu thập thông tin blog được nói trong mục 3.2.1. Có một vài chi tiết cần lưu ý so với những mô tả ở mục 3.2.1. Đó là sự xuất hiện của “Configuration file”, “Wave Interpreter” và “Bộ tiếp nhận yêu cầu”. Như đã nói, hệ thống được thiết kế với khả năng có thể xử lý, lưu trữ phân tán, và 3 thành phần kể trên là những thành phần hỗ trợ cho khả năng đó. Bởi vì việc thu thập thông tin này sẽ do nhiều máy đảm trách, được phân chia công việc rõ ràng thông qua Filter nên là các máy cần phải biết được mình có thể bắt đầu 41  công việc từ đâu. File cấu hình (Configuration file) được dùng để chỉ ra những blogID khởi đầu cho quá trình thu thập thông tin về các blog trên mạng xã hội Yahoo!360. Trong một tập hợp các máy tham gia vào quá trình xử lý và thu thập thông tin, có thể chỉ cần có một máy có những điểm khởi đầu này, các máy còn lại có thể lặp đi lặp lại việc đọc ra từ cơ sở dữ liệu đặt tại máy đó xem có bản ghi nào chưa được thu thập thông tin (bạn bè) hay không. Nếu có thì máy đó làm việc như bình thường với các quy trình có thể nhìn thấy trên sơ đồ, còn không nó tiếp tục chờ cho tới khi nhận được yêu cầu từ máy khác. Yêu cầu từ máy khác xuất hiện khi có một máy nhận được một blogID, thông qua Filter nó nhận thấy blogID đó thuộc quyền “quản lý” (việc phân chia quyền hạn quản lý được dành cho Filter) của một máy khác, do vậy nó sẽ thông qua Wave Interpreter để gửi tới máy kia blogID vừa nhận được. Thực ra lúc đó Wave Interpreter sẽ gọi lệnh chạy hệ thống (System Call), gọi ra một class (được tạo dựng sẵn trên các máy, gọi là Bộ tiếp nhận yêu cầu) trên máy đầu xa, dùng để đưa bản ghi blogID vào cơ sở dữ liệu của máy đầu xa. Do vậy sau khi tiếp tục thực hiện vòng lặp đọc trong cơ sở dữ liệu, máy đầu xa nhận thấy nó có một blogID chưa được lấy danh sách bạn bè. Máy đầu xa lúc này tiến hành lấy bạn bè của blogID này, và nếu gặp một blogID không thuộc quyền quản lý của mình, nó lại gửi đến máy khác qua những quy trình vừa được trình bày. 42  3.3.2 Thành phần tạo dựng Mạng tri thức  Hình 3 5: Sơ đồ hoạt động thành phần tạo dựng mạng tri thức Trong sơ đồ trên Hình 3 5, cũng chỉ có một điểm lưu ý so với trình bày ở mục 3.2.2 là Wave Interpreter. Cũng giống như ở thành phần thu thập thông tin blog, ở đây Wave Interpreter đóng vai trò là người trung gian, luân chuyển thông tin để phân tán xử lý cho toàn bộ các máy tham gia trên mạng. Ở việc tạo dựng mạng tri thức, thông qua Filter, các đoạn mã wave sẽ được tạo ra, chứa các thông tin về tên nút cần được tạo, và nơi mà nút ấy sẽ được tạo, trong trường hợp này là địa chỉ IP (do Filter trả về) của máy nào đó trong mạng. Một mã wave có dạng CR(@#`blogID`$$`ip_add_1’. `friend’#`blogID_f1’$$`ip_add_2’) Câu lệnh này sẽ tạo ra một nút với tên “blogID” tại máy có địa chỉ ip là “ip_add_1”, sau đó tạo ra một nút khác với quan hệ là bạn bè của nút vừa tạo, tên là “blogID_f1”, tại máy có địa chỉ ip là “ip_add_2”. Những câu lệnh dạng này khi được gửi tới WI sẽ được WI tự động thực hiện giao tiếp với các WI tại máy đầu xa, gửi thông tin về nút cần tạo tới WI tại máy đầu xa. Khi ấy WI tại máy đầu xa sẽ tiến hành tạo nút được gửi. Tương tự như vậy, WI tại máy đầu xa cũng có thể gửi tới máy đang xét những nút cần thiết. Từ đó mạng tri thức được tạo thành sẽ là một mạng tri thức tổng hợp từ các máy nằm phân tán.  43  CHƯƠNG 4: BÀI TOÁN PHÂN TÍCH QUAN HỆ 4.1 Tạo lập mạng tri thức từ cơ sở dữ liệu không đồng nhất  Tạo lập và xử lý một mạng tri thức có thể được thực hiện phân tán trên nhiều máy tính trên mạng, do vậy WAVE được tạo ra để có thể sử dụng rất hiệu quả trong việc tạo lập, quản lý các cơ sở dữ liệu lớn nằm phân tán. Để chứng minh khả năng khả năng này của WAVE, có thể xét một hệ cơ sở dữ liệu không đồng nhất lưu trữ thông tin về một trung tâm nghiên cứu, thí nghiệm như sau: 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 Như Hình 4 1 ta có một cơ sở dữ liệu không đồng nhất, nhưng có mối quan hệ liên quan. Hệ cơ sở dữ liệ không đồng nhất này sẽ cho thấy thông tin về những blogger trong mạng xã hội, họ có thể đến từ nhiều quốc gia khác nhau, có những mối quan tâm tới các chủ đề khác nhau và làm những công việc khác nhau … Cấu trúc của hệ cơ sở dữ liệu này được biểu diễn dưới dạng mạng tri thức, trong đó mỗi đối tượng dữ liệu, hay một bản ghi được coi là một nút riêng lẻ, và mối quan hệ giữa những đối tượng dữ liệu đó được biểu diễn như những liên kết hai chiều hay một chiều, tùy thuộc vào loại quan hệ giữa chúng là hai hay một chiều. Hệ cơ sở dữ liệu không đồng nhất này được hình thành từ bốn hệ cơ sở dữ liệu nhỏ có thể nằm riêng rẽ tại các máy là WORLD database, TOPICS database, OCCUPATION database và BLOGGER database, mỗi cơ sở dữ liệu có một cấu trúc xác định riêng. - WORLD Database (WDB): Hệ cơ sở dữ liệu này biểu diễn hệ thống quốc gia, vùng lãnh thổ, thành phố nhằm xác định nơi cư trú của những thành viên trong mạng xã hội. 44  Hình 4 2: WORLD database WDB có bốn lớp, đầu tiên là “WORLD”, là gốc của CSDL. Lớp tiếp theo biểu diễn các lục địa (tiếng Anh: continents). Lớp tiếp theo là các quốc gia, và lớp cuối cùng là các thành phố, sẽ là những nơi sinh sống của các blogger. Các node ở các lớp liền kề sẽ được liên kết với node ở lớp trên bằng một liên kết “isa” (is a) một chiều như trong Hình 4 2. Đoạn mã WAVE để tạo lập cấu trúc cơ sở dữ liệu này trong mạng tri thức có thể được viết dạng “breadth-first” như sau: CREATE ( DIRECT # world. ( +isa # europe. ( +isa # germany. +isa # berlin, +isa # bonn), ( +isa # uk. +isa # guildford, +isa # london) ), ( +isa # asia. +isa # vietnam. +isa # hanoi, +isa # hcm ) ) - TOPICS Database (TDB): Cơ sở dữ liệu này mô tả các chủ để mà các blogger quan tâm 45  Hình 4 3: TOPICS database Nhìn vào Hình 4 3, cấu trúc của TOPICS database gần giống như của WORLD database với bốn lớp. Trong đó các lớp bên dưới thể hiện các topic như là topic con của các topic ở lớp trên. Và cũng như WORLD database, các nút lớp dưới có liên kết một chiều với các nút lớp trên với tên liên kết là “isa”. Đoạn mã WAVE xây dựng mạng tri thức dựa trên cơ sở dữ liệu trên có dạng: CREATE ( DIRECT # topics. ( +isa # it. +isa # software, ( +isa # network. +isa # cisco, +isa # microsoft ), ), ( +isa # politics. +isa # capitalism, +isa # socialism ) ) - OCCUPATION Database (ODB): Cơ sở dữ liệu này mô tả các công việc mà các blogger đang làm, sắp xếp theo từng lĩnh vực cụ thể 46  Hình 4 4: OCCUPATION database Như trong Hình 4 4, cơ sở dữ liệu này có ba lớp, lớp đầu tiên có nút “OCCUPATION” đóng vai trò là gốc, nút này có các nút con là các lĩnh vực nghề nghiệp như nghệ thuật (ART), công nghệ thông tin (IT – Information Technology). Lớp thứ ba là các công việc cụ thể trong từng lĩnh vực, ví dụ như trong công nghệ thông tin có các công việc dạng như thiết kế (DESIGNER), lập trình viên (CODER), quản trị viên (ADMINISTRATOR) … Để tạo lập mạng tri thức chứa các thành phần của cơ sở dữ liệu trên, có thể sử dụng đoạn mã WAVE như sau: CREATE ( DIRECT # occupation. ( +isa # art. +isa # singer, +isa # writer ), ( +isa # oit. +isa # designer, +isa # coder, +isa # administrator ) ) - BLOGGER Database (BDB): Mô tả các blogger trong mạng xã hội và mối quan hệ bạn bè giữa họ. Ở mạng xã hội, quan hệ bạn bè là quan hệ hai chiều, do đó các liên kết sẽ không có mũi tên chỉ hướng. 47  Hình 4 5: BLOGGER database Đoạn mã WAVE tạo lập mạng tri thức dựa trên cơ sở dữ liệu blogger này được thực thi dưới dạng “depth-first” như sau: CREATE ( DIRECT # james. friends # peter. friends # anna. friends # ngoc. friends # michael. friends # james, friends # anna, ( friends # thai. friends # james, ( friends # olga. friends # peter, friends # james ) ) ) Và đây là sự kết hợp của các Cơ sở dữ liệu phân tán trên thành một hệ cơ sở dữ liệu chung không đồng nhất 48  Hình 4 6: Cơ sở dữ liệu tổng hợp Cơ sở dữ liệu này sẽ đưa ra cái nhìn tổng quan về các nhân viên trong trung tâm. Ví dụ như ta sẽ thấy “JAMES” hay quan tâm tới chủ đề chính trị, cụ thể là về “Tư bản chủ nghĩa”, tuy thế anh này lại là một Lập trình viên (coder), và đến từ thành phố “BERLIN” của “GERMANY”. Và với các đoạn mã WAVE như ở các phần trên, trên lý thuyết các cơ sở dữ liệu hợp thành cơ sở dữ liệu tổng hợp này đã được tạo ra. Do vậy để cho ra một mạng tri thức tổng hợp của cơ sở dữ liệu tổng hợp này, cần phải thực hiện việc lập các liên kết giữa các cơ sở dữ liệu con. Đoạn mã WAVE thực hiện việc này được trình bày ở dưới: 49  CREATE ( ( DIRECT # james. works # coder, lives # london, concerns # capitalism ), ( DIRECT # thai. works # administrator, lives # hanoi, concerns # software ), ( DIRECT # olga. works # singer, lives # berlin, concerns # cisco ), ( DIRECT # peter. works # designer, lives # guildford, concerns # cisco ), ( DIRECT # anna. works # singer, lives # bonn, concerns # capitalism ), ( DIRECT # ngoc. works # administrator, lives # hcm, concerns # socialism ), ( DIRECT # michael. works # writer, lives # london, concerns # microsoft ) ) 4.2 Các bài toán quan hệ  Với mạng tri thức được tạo thành, có thể thực hiện các mẫu truy vấn để giải quyết rất nhiều các bài toán có thể kể ra sau đây • Tìm các chủ đề con, trực tiếp thuộc chủ đề IT. - Mã Wave: Freturn = CONTENT. DIRECT # it. +isa # ALL. Ftransit = CONTENT. DIRECT # Freturn. TERMINAL = Ftransit - Kết quả: SOFTWARE; NETWORK 50  • Vùng lãnh thổ nào gần nhất trong đó có hai thành phố Bonn và London - Mã Wave: Freturn = CONTENT. DIRECT # bonn, DIRECT # london. REPEAT ( OR_SEQUENTIAL ( ( SQ ( Ncounter + 1. Ncounter == 2 ) . Ftransit = CONTENT. DIRECT # Freturn. TERMINAL = Ftransit. DONE ! ), - isa # ALL ) ) - Kết quả: EUROPE • Liệt kê những blogger đến từ Việt Nam và quan tâm tới chủ đề “Xã hội chủ nghĩa” - Mã Wave: Freturn = CONTENT. DIRECT # vietnam, DIRECT # socialism. Fcolor = CONTENT. REPEAT ( +isa # ALL, ( lives; concerns # ALL. SQ ( Fcolor /~ Ncolors. Ncolors & Fcolor. Ncolors :: NONE > 2. Ftransit = CONTENT. DIRECT # Freturn. TERMINAL = Ftransit ) . DONE ! ) ) - Kết quả: NGOC 51  • Liệt kê những người bạn của Thái đến từ cùng một thành phố, tên thành phố là gì? - Mã Wave: Freturn = CONTENT. DIRECT # thai. friends # ALL. Fcollect = CONTENT. lives # ALL. Fcity = CONTENT. ##. Fcollect & CONTENT. lives # thai. Fcollect & Fcity. DIRECT # Freturn. TERMINAL = Fcollect - Kết quả: JAMES; MICHAEL – LONDON • Liệt kê những người dùng có mối quan tâm tới chủ đề “Network” - Mã Wave: DIRECT # network. AS( (#.Fcollect=C.#P.Ncollect&Fcollect), (T=Ncollect) ) - Kết quả: OLGA; PETER; MICHAEL • Có điểm chung nào về chủ đề quan tâm giữa những người làm nghệ thuật (OCCUPATION = ART) và những người làm IT (OCCUPATION = IT) không? - Mã Wave: Freturn = CONTENT. DIRECT # art. isa # ALL. ANY # ALL. concerns# ALL. Ftransit = CONTENT. ANY # ALL. works # ALL. isa # it. DIRECT # Freturn. T=Fc - Kết quả: CISCO; CAPITALISM 52  4.3 Mở rộng hệ thống  Như đã nói, việc sử dụng công nghệ Wave vào phân tích quan hệ có một đặc điểm nổi trội so với các cách thức phân tích quan hệ truyền thống (ma trận kề) đó là khả năng mở rộng đối tượng, thuộc tính, quan hệ rất cao. Giả sử mạng tri thức được trình bày tại mục 4.2 đã tồn tại, nhưng người dùng mới muốn tạo thêm một vài thuộc tính cho các bản ghi về blogger như giới tính, tuổi, tổng số bài viết … Việc này trong Wave có thể được thực hiện rất dễ dàng bằng cách thêm vào những cơ sở dữ liệu tương ứng với các thuộc tính đó, sau đó tạo thêm trên mạng tri thức những nút thể hiện các bản ghi cơ sở dữ liệu, thiết lập quan hệ (một chiều) từ các nút chủ thể blogger tới các nút thuộc tính này. Việc tạo ra trên mạng tri thức các nút tương ứng với các cơ sở dữ liệu mới được định nghĩa không có khác biệt so với việc tạo ra các cơ sở dữ liệu được nói tại mục 4.2 (WDB, TDB, ODB, BDB). Sau công đoạn này, việc thêm vào các liên kết quan hệ cho các nút thể hiện blogger có thể tiến hành với những đoạn mã Wave kiểu như sau: CR( ( DIRECT # THAI. Gender # male, age # 22, entries # 10 ), ( DIRECT # NGOC. Gender # male, age # 25, entries # 7 ), ( DIRECT # ANNA. Gender # female, age #20, entries #20 ) ) Sau bước này, các bài toán quan hệ có thể được mở rộng dưới dạng tìm kiếm thuộc tính. Ví dụ như tìm “blogger nữ trẻ nhất?”, “tìm blogger nam có tầm tuổi 20-30 có số lượng entry nhiều hơn 20?” … Như vậy chứng tỏ được khả năng mở rộng cao của hệ thống phân tích dựa trên nền tảng Wave, chỉ cần thêm vào một vài thay đổi là có thể thực hiện nhiều phân tích mở rộng cần thiết. 53  CHƯƠNG 5: BÀI TOÁN PHÂN TÍCH ĐẶC ĐIỂM  5.1 Bài toán tìm kiếm theo mẫu  Trong mạng xã hội, giữa các node, ngoài quan hệ là bạn bình thường, chúng ta có thể thiết lập những quan hệ phức tạp hơn và thực hiện tìm kiếm theo các mẫu cho trước. Một số ít các node sẽ có thuộc tính nghề nghiệp (job) nhận các giá trị như nhà báo (journalist) hay ca sĩ (singer). - Tìm tất cả các node có đường nối trực tiếp tới hai node cho trước (bạn chung của hai node bất kỳ cho trước) – Hình 5 1. - Cho trước hai node A và B, tìm tất cả các node có đường nối trực tiếp với node A và nối với node B qua một node trung gian (tìm tất cả các node có khoảng cách với A là 1, khoảng cách với B là 2) – Hình 5 2. Hình 5 1 Bạn chung của node D và E là hai node C và B 54  Hình 5 2 A và C là hai node có khoảng với D là và khoảng cách với G là 2 5.2 Bài toán Tìm Đường đi ngắn nhất  5.2.1 Thuật toán  - Từ node nguồn tìm một cây đường đi ngắn nhất (shortest-path tree) tới tất cả các node khác trong đồ thị. - Sau khi tìm được cây đường đi ngắn nhất, tới node đích, lần vết ngược trở về node bắt đầu để tìm ra dãy đường đi ngắn nhất giữa hai node. Chúng ta tìm cây đường đi ngắn nhất bằng cách loang theo chiều rộng. Ở mỗi node, có một biến cục bộ để đánh dấu tình trạng của node là đã được thăm hay chưa được thăm. Thuật toán bắt đầu bằng việc nhảy tới node nguồn, từ nút nguồn di chuyển tới tất cả các node có đường nối trực tiếp với node nguồn, kiểm tra nếu biến cục bộ lưu tình trạng của node đang ở trạng thái chưa được thăm thì gán giá trị của biến cục bộ đó bằng địa chỉ của node mà chuỗi wave vừa từ đó di chuyển tới node hiện tại. Lặp lại việc di chuyển tới tất cả các node có đường nối trực tiếp với node đang đứng. Trong WAVE có lệnh “##” di chuyển sang các nút lân cận trừ node mà từ đó đã tới nó. Do 55  vậy chuỗi WAVE sẽ di chuyển sang các node có đường nối trực tiếp với các node hàng xóm của node nguồn nhưng không di chuyển trở về node nguồn. Loang cho tới khi thăm xong toàn bộ đồ thị. Sau khi đã tạo được cây đường đi ngắn nhất. Nhảy tới node đích, di chuyển ngược về node khởi đầu dựa vào biến cục bộ lưu tình trạng tại mỗi node và lưu đường đi vào một biến toàn cục. Đồ thị minh họa thuật toán:Giả sử ta cần tìm đường đi ngắn nhất giữa node A và node H .   Hình 5 3 Phần 1: Tìm cây đường đi ngắn nhất (loang theo chiều rộng): Đặt chuỗi WAVE vào node A. Di chuyển tới các node hàng xóm của A là B, C, D – mũi tên màu da cam. Chuỗi WAVE tách thành ba nhánh tại ba node B, C, D. 56  Hình 5 4 Từ các node B, C, D di chuyển tới các node có đường nối trực tiếp với B, C, D – mũi tên màu xanh biển. Do có ba nhánh WAVE nên chuỗi WAVE sẽ di chuyển tới các node B, C, D, E, F, G. Ở các node B, C, D, biến Nback đã có giá trị. Nên chuỗi WAVE sẽ bị dừng. Còn ở ba node E, F, G biến Nback vẫn có giá trị NONE – node chưa được thăm nên chuỗi WAVE sẽ tiếp tục lan tỏa. Từ E, F, G chuỗi WAVE lại tiếp tục lan tỏa tới hai node chưa được thăm là H và I. Ở hai node H và I, chuỗi WAVE dừng do không tìm thấy node nào chưa thăm. Hình 5 5 57  Phần 2: Lần vết tìm chuỗi đường đi giữa hai node: Hình 5 6 Nhảy tới node đích là node H. Gán biến Fpath=C – với C là nội dung (tên) của node H. Di chuyển tới node G - chứa trong biến Nback của nod H. Gán Fpath:0=C (tức tên của node G). Di chuyển tiếp tới node B – chứa trong biến Nback của node G. Fpath giờ đang là [H,G] sẽ được gán Fpath:0=C và sẽ chứa các giá trị [H,G,B]. Tiếp tục di chuyển tới node A – chứa trong biến Nback của node B và gán Fpath:0=C. Fpath giờ sẽ chứa [H,G,B,A]. Di chuyển tiếp tới node chứa trong biến Nback của node A, nhưng 58  node `stop’ không tồn tại nên vòng lặp trong chuỗi WAVE sẽ dừng. Và ta có đường đi ngắn nhất giữa hai node A và H chứa trong biến Fpath=[H,G,B,A] 5.2.2 Cài đặt  Giả mã: B1: Nhảy tới node khởi đầu. Nback=`stop'. B2: Nhảy tới tất cả các bạn bè của node đang đứng. Nếu Nback==NONE, gán Nback=P. Nếu Nback /= NONE, không làm gì cả. B3: Nếu còn Nback==NONE, Lặp lại bước 2. Nếu không sang bước 4. B4: Nhảy tới node đích. Fpath=Tên node. B5: Nhảy tới nút trước nút hiện tại. Gán Fpath:0=Tên node. Lặp lại bước 5 tới khi nào không thể nhảy tới nút trước nó (khi Nback=`stop') B6: In ra đường đi ngắn nhất (nếu có). Lưu đồ thuật toán: Bước 1: Tìm cây đường đi ngắn nhất 59  Hình 5 7 Bước 2: Lần ngược tìm đường nối giữa node đích và node nguồn 60  Hình 5 8 61  Wave code: SQ( (@#`blogsource'.Nback=`stop'. RP(##.(Nback==NONE.Nback=P))), (@#`blogdesti'.Fpath=C.RP(#Nback.Fpath:0=C).T=Fpath) ) 5.3 Bài toán tìm Đường kính  Định nghĩa đường kính của một đồ thị: Đường đi ngắn nhất giữa hai node trong đồ thị được gọi là khoảng cách giữa hai node đó. Khoảng cách dài nhất giữa hai node trong đồ thị gọi là đường kính của đồ thị. Với đồ thị trong hình 9, khoảng cách giữa node D và node H chính là đường kính của đồ thị với độ dài đường kính là 3. Hình 5 9 Thuật toán tìm đường kính: Bài toán tìm đường kính của đồ thị có thể coi là một bài toán mở rộng của bài toán tìm cây đường đi ngắn nhất. Ta tìm đường đi ngắn nhất giữa tất cả các cặp node trong đồ thị, và đường kính tương ứng sẽ là đường dài nhất trong số những đường ngắn nhất. Để giải quyết bài toán một cách hiệu quả, ta đặt chuỗi 62  wave vào tất cả các node trong đồ thị và tìm kiếm cây đường đi ngắn nhất của tất cả các node một cách song song. Độ dài đường đi ngắn nhất từ tất cả các node khác trong đồ thị tới node hiện tại được lưu tại một biến cục bộ tại node hiện tại, biến này có dạng vector, với mỗi phần tử là một khoảng cách tới một node trong đồ thị. Để xác định chính xác khoảng cách nào ứng với node nào từ node hiện tại, ta sử dụng một biến cục bộ khác lưu địa chỉ của node đi kèm biến lưu khoảng cách. Biến này cũng có dạng vector với các phần tử là tên của các node trong đồ thị, các phần tử trong vector khoảng cách và vector tên node được xếp một cách tương ứng nhau. Ví dụ với node hiện tại là node A: Biến vector Ndistance lưu khoảng cách: 1 1 1 2 2 2 3 4 Biến vector Nsource lưu tên các phần tử ứng với khoảng cách lưu tại biến Ndistance: B C D E F G H I Sau khi thực một cách song song hiện thuật toán tìm cây đường đi ngắn nhất tại tất cả các node, chúng ta nhận được ở biến Ndistance ở mỗi node khoảng cách từ node đó tới tất cả các node còn lại trong đồ thị. Khoảng cách lớn nhất trong những khoảng cách này (tính ở tất cả các node) – gọi là đường kính – được tìm qua hay bước: Đầu tiên tìm khoảng cách lớn nhất cục bộ trong các phần tử của vector Ndistace tại mỗi node, sau đó tìm khoảng cách lớn nhất toàn cục là giá trị lớn nhất của các khoảng cách cục bộ. 63  Hình 5 10 Chương trình wave sử dụng để thực hiện việc tìm đường kính của đồ thị: Flocal_max= {REPEAT( Next=Ndistance:1. Next/=NONE. Ndistance:1=NONE. (Next>Nmax. Nmax=Next. DONE!), STAY ) }. SEQUENCE( (DIRECT#ALL.Fsource=CONTENT. Flength=0. REPEAT( ( Findex = Nsources:: Fsource. OR_SEQUENCE( (Findex==NONE. Nsources & Fsource. Ndistances & Flength ), (Flength<Ndistances:Findex. Ndistances:Findex=Flength ) ) 64  ).ANY#ALL. Flength+1 ) ), (DIRECT#ALL. ^Flocal_max. Ftransit=Nmax. DIRECT#PREDECESSOR. (Ftransit>Nmax. Nmax = Ftransit) ), TERMINAL=Nmax ) Việc lan tỏa để tìm cây đường đi ngắn nhất trên một phạm vi lớn (hàng trăm nghìn tới hàng triệu node) là tương đối lâu, hơn nữa với đồ thị có hàng trăm nghìn node thì số lượng phần tử trong hai vector Ndistances và Nsources cũng sẽ lên tới hàng trăm nghìn, và cũng như để tránh việc mỗi lần tìm đường kính ta lại phải tìm kiếm cây đường đi ngắn nhất của toàn bộ mạng. Chúng ta sẽ cải tiến thuật toán tìm đường kính, thay vì mỗi lần tìm đường kính lại thực hiện thuật toán tìm kiếm cây đường đi ngắn nhất trên toàn bộ node của đồ thị, ta làm việc này một lần duy nhất và lưu khoảng cách lớn nhất của mỗi node tới các node khác trong đồ thị vào cơ sở dữ liệu. Hình 5 11 65  Để đi tìm đường kính của một đồ thị có n node. Chúng ta phải đi tìm khoảng cách giữa tất cả các node với nhau. Gọi D(i,j) là khoảng cách giữa node i với node j (i khác j, i,j trong khoảng từ 1 tới n). Giá trị lớn nhất Max(D(i,j)) chính là đường kính cần tìm. Đồng thời, cần xác định hai node i, j và chuỗi các node nối hai node i và j. Chuẩn bị dữ liệu (phân tích dữ liệu thô): Ở mỗi node của đồ thị, thực hiện thuật toán tìm cây đường đi ngắn nhất. Thuật toán tìm cây đường đi ngắn nhất chính là thuật toán loang theo chiều rộng. Mỗi lần loang rộng, ta tăng biến Fd đếm khoảng cách từ node nguồn tới node hiện tại. Sau khi loang xong toàn bộ độ thị, biến Fd chứa giá trị là khoảnh cách từ node nguồn tới node xa nhất trong đồ thị. Ta đưa lưu Fd vào cơ sở dữ liệu. Việc tìm Fd và đưa vào cơ sở dữ liệu được thực hiện gần như song song trên các node. Đoạn mã wave thực hiện việc tìm khoảng cách lớn nhất từ một node tới các node còn lại trong đồ thị và đưa khoảng cách tìm được vào cơ sở dữ liệu: @#`blogID'.Nd=0.Fd=0. SQ( (RP(#.Nd==NONE.Fd+1.Nd=Fd.Nb=P).@#`"+blogID+"'.Nmax=Fd), T=Nmax.Fa=1;1;Ft=`blogID'.Ft&Nmax.Fa&Ft.Fa?getRequestedBlog ).@#.Nd=NONE Fa chứa hai tham số là blogID và giá trị của Nmax, lớp getRequestedBlog sẽ thực hiện việc đưa giá trị biến Nmax vào cơ sở dữ. Sau khi tìm được khoảng cách xa nhất cho tất cả các node của đồ thị và lưu vào cơ sở dữ liệu. Việc tìm kiếm và phân tích sẽ trở nên thuận tiện hơn rất nhiều. Tìm đường kính của đồ thị từ các dữ liệu đã lưu trong cơ sở dữ liệu: đường kính chính là giá trị lớn nhất của DMax được lưu trong cơ sở dữ liệu. Truy vấn cơ sơ dữ liệu lấy ra blogID và khoảng cách Dmax lớn nhất. Thực thi đoạn mã WAVE sau đây để tìm ra chuỗi các node tạo thành đường kính của đồ thị: @#`"+blogID+"'.Nd=0.Fd=0.Nb=`stop'. SQ( (RP(#.Nd==NONE.Fd+1.Nd=Fd.Nb=P.Fdes=C). @#`"+blogID+"'.Nd=Fd.Nde=Fdes), @#Ndes.Fpath=C.RP(#Nb.Fpath:0=C).@#`"+blogID+"'.Np=Fpath ) 66  5.4 Bài toán tìm Tâm và Bán kính  Một khái niệm quan trọng khác trong đồ thị là tâm của đồ thị. Tâm của đồ thị là một node mà khoảng cách lớn nhất từ node đó tới một node khác bất kì trong đồ thị là nhỏ nhất. Bán kính là độ dài khoảng cách từ tâm tới node xa nhất trong đồ thị. Hình 5 12 Ví dụ như với đồ thị Hình 5 12 tâm của đồ thị là B và bán kính của đồ thị là khoảng cách từ B tới node xa nhất là 2. A không thể là tâm vì khoảng cách từ A tới node xa nhất – node H - là 3, lớn hơn khoảng cách từ B tới H Thuật toán: Để tìm node có khoảng cách tới một node bất kì trong đồ thị là ngắn nhất so với các node khác, với tất cả các node trong đồ thị, ta tìm khoảng cách xa nhất từ node đó tới các node còn lại trong đồ thị. Trong các khoảng cách tìm được, node nào có khoảng cách ngắn nhất chính là tâm của đồ thị. Ta có thể sử dụng kết quả tìm cây đường đi ngắn nhất của bài toán tìm đường kính trong đồ ở phần 5.3, bán kính cần tìm chính là giá Dmax nhỏ nhất được lưu trong cơ sở dữ liệu. 67  CHƯƠNG 6: KẾT QUẢ  6.1 Kết quả thực nghiệm  Chương trình được chạy thử trên một vài điều kiện thử nghiệm khác nhau được trình bày trong các bảng sau. Thời gian cần thiết để thu thập thông tin về khoảng 20.000 blog khác nhau Số máy Số nút Thời gian vận hành Điều kiện thiết bị 1 20.503 27’45’’ ADSL 4Mbps Thời gian cần thiết để tạo lập Mạng tri (3 lần test) Số máy Số nút Filter Cách thức tạo chuỗi WAVE Thời gian vận hành 1 20.411 HashCode Short 44s 2 20.411 HashCode Short 55s 4 20.503 HashCode Long 26s 2 20.503 HashCode Long 29s 6.2 Kết luận  Khóa luận tốt nghiệp đã trình bày tổng quan về công nghệ WAVE và ứng dụng của công nghệ này vào các bài toán phân tích mạng xã hội Yahoo!360. Với việc phát triển thành công một ứng dụng nhỏ dựa trên nền tảng WAVE có chức năng thu thập thông tin về các blog Yahoo!360, sau đó tiến hành tạo dựng mạng tri thức trong WAVE tương ứng với các thông tin về đối tượng và quan hệ giữa các đối tượng thu thập được, cộng với những kết quả thực nghiệm tương đối khả quan về hiệu năng của hệ thống, tôi tin tưởng rằng đây sẽ là cơ sở cho việc phát triển các ứng dụng lớn hơn nhằm hỗ trợ tối đa cho việc phân tích, định hình thông tin đang tồn tại trên các mạng xã hội hiện nay. Từ đó giúp giải quyết rất nhiều các bài toán nghiên cứu ứng 68  dụng đang được đưa ra để phân tích về các hoạt động của con người dựa trên việc mô phỏng hoạt động ấy trên mạng xã hội. 69  TÀI LIỆU THAM KHẢO  TÀI LIỆU TIẾNG ANH [1] Borst, P.M., H.-T Goetz, P. S. Sapaty, and W. Xorn, “Paralled Knowledge Processing in Open Networks,” Proc. International Conference and Exhibition “High-Performance Computing in Networks” (HPCN Europe ‘94), Munich, Germany, April 1994. [2] Corbin M. J., and P. S. Sapaty, “Distributed Object-Based Simulation in Wave,” J. Simul. Pract. Theory, Vol. 3, No.3, pp. 157-181, 1995. [3] Livatharas, C., “Integration of Heterogeneous Databases Using WAVE,” M.Sc. Project Report, Department of Electrical Engineering, Un