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

LINK DOWNLOAD MIỄN PHÍ TÀI LIỆU "phân tích mạng xã hội bằng công nghệ wave - phân tích quan hệ": http://123doc.vn/document/1045081-phan-tich-mang-xa-hoi-bang-cong-nghe-wave-phan-tich-quan-he.htm


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,