Đại Học Quốc Gia Thành Phố Hồ Chí Minh Trƣờng Đại Học Bách Khoa MAI PHÚC TIẾN PHÂN TÍCH MẠNG XÃ HỘI ZINGME Chuyên ngành: Khoa học Máy tính LUẬN VĂN THẠC SĨ TP. HỒ CHÍ MINH, tháng 8 năm 2011 ĐẠI HỌC QUỐC GIA TP. HCM CỘNG HOÀ XÃ HỘI CHỦ NGHIÃ VIỆT NAM TRƢỜNG ĐẠI HỌC BÁCH KHOA Độc Lập - Tự Do - Hạnh Phúc ---------------- ---oOo--- Tp. NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ và tên học viên: Mai Phúc Tiến.
Giới tính : Nam / Nữ Ngày, tháng, năm sinh : 26/03/1982. Nơi sinh : Phú Yên. Chuyên ngành : Khoa Học Máy Tính .PHÂN TÍCH MẠNG XÃ HỘI ZINGME. 2- NHIỆM VỤ LUẬN VĂN:.
Phân tích mạng xã hội ZingMe: cấu trúc đồ thị mạng xã hội ZingMe dựa trên liên kết bạn bè và hành vi ngƣời dùng. Nhận dạng các mẫu hành vi ngƣời dùng, quy luật phân bố hành vi dựa theo bậc ngƣời dùng, mức độ năng động. 3- NGÀY GIAO NHIỆM VỤ :. 4- NGÀY HOÀN THÀNH NHIỆM VỤ :.
5- HỌ VÀ TÊN CÁN BỘ HƢỚNG DẪN: PGS.TS Cao Hoàng Trụ. Nội dung và đề cƣơng Luận văn thạc sĩ đã đƣợc Hội Đồng Chuyên Ngành thông qua. CÁN BỘ HƢỚNG DẪN CHỦ NHIỆM BỘ MÔN (Họ tên và chữ ký) QUẢN LÝ CHUYÊN NGÀNH (Họ tên và chữ ký) PGS.TS CAO HOÀNG TRỤ LỜI CAM ĐOAN Tôi cam đoan rằng ngoại trừ các kết quả tham khảo từ các công trình khác nhƣ đã ghi rõ trong luận văn, các công việc trình bày trong luận văn này là do chính tôi thực hiện và chƣa có phần nội dung nào của luận văn này đƣợc nộp để lấy một bằng cấp ở trƣờng này hoặc trƣờng khác. Ngày 30 tháng 08 năm 2011 Mai Phúc Tiến LỜI CẢM ƠN Tôi xin gởi lời cảm ơn chân thành nhất đến PGS, TS.
Cao Hoàng Trụ đã tận tình hƣớng dẫn, giúp đỡ trong suốt quá trình thực hiện luận văn. Xin cảm ơn gia đình và những ngƣời bạn đã dành cho tôi tình thƣơng yêu và sự hỗ trợ tốt nhất. TÓM TẮT LUẬN VĂN Mạng xã hội (MXN) phát triển ngày càng mạnh mẽ, phổ biến và là thành phần không thể thiếu trong cuộc sống hằng ngày của các công dân điện tử. Ngƣời tham gia mạng xã hội ngoài việc tìm kiếm, thực hiện liên kết bạn bè, trao đổi thông tin còn có thể thực hiện các giao dịch mua bán trực tuyến, chơi điện tử,….
Đây là mảnh đất màu mỡ để các nhà cung cấp dịch vụ thƣơng mại điện tử phát triển nhƣ quảng cáo trực tuyến, phát triển trò chơi điện tử, dịch vụ văn phòng trực tuyến ảo. Tuy nhiên để phát triển các ứng dụng một cách hiệu quả cần hiểu rõ cấu trúc mạng xã hội hiện tại và hành vi ngƣời dùng trên các mạng xã hội đó. Đã có nhiều công trình nghiên cứu phân tích các đặc điểm này trên các mạng xã hội nhƣ Facebook, Orkut, Renren, LiveJournal,… và nhận thấy các mạng xã hội đều có tính chất Small-world, phân bố bậc theo luật power-law, những ngƣời dùng bậc cao có xu hƣớng kết nối với nhau hoặc hầu hết các tƣơng tác, thông tin công bố chỉ do một nhóm nhỏ ngƣời dùng tạo ra (quy luật Pareto). Đề tài này trình bày một cách có hệ thống về phân tích mạng xã hội ZingMe, mạng xã hội lớn nhất tại Việt Nam hiện nay, ở khía cạnh cấu trúc đồ thị mạng xã hội, cấu trúc đồ thị tƣơng tác, các mẫu phân bố hành vi của ngƣời dùng theo phân loại tổng số lƣợng bạn bè mà ngƣời dùng có hoặc theo mức độ năng động của ngƣời dùng.
Trong đề tài này cũng tiến hành tích hợp thƣ viện SNAP [30] vào chƣơng trình SocNetV [31] nhằm tạo công cụ mạnh để phân tích, hiển thị cấu trúc mạng xã hội có hàng triệu đỉnh và cạnh. Từ khóa: Small-world, Scale-free, Power-law, Social network, Interaction graph, Clustering coefficient, Assortativity coefficient, Joint degree distribution, Diamter, Radius, Average path lengh. DANH MỤC HÌNH. viii DANH MỤC BẢNG.
ix Chƣơng 1. Kết cấu của luận văn .2 Hàm phân bố xác xuất .3 Hàm phân bố xác xuất tích lũy .4 Hàm bù phân bố xác xuất tích lũy .5 Phân tích phân bố Power-law theo phƣơng pháp MLE. Phân tích cấu trúc đồ thị mạng xã hội .1 Các định nghĩa cơ bản .2 Phân bố bậc .3 Phân bố bậc kết hợp .4 Bậc liên kết trung bình .5 Hệ số kết hợp .6 Hệ số cụm .7 Bán kính, đƣờng kính và đƣờng đi trung bình .8 Độ quan trọng cạnh. PHÂN TÍCH VÀ SO SÁNH CẤU TRÚC MẠNG XÃ HỘI ZINGME VỚI CÁC MẠNG XÃ HỘI KHÁC.
Giới thiệu về ZingMe và các mạng xã hội khác. Tập dữ liệu ngƣời dùng của các mạng xã hội. Đồ thị xã hội và đồ thị tƣơng tác ZingMe. Phân tích bậc.
Bậc kết hợp. Bậc liên kết trung bình. Hệ số kết hợp r. Hệ số cụm.
Đƣờng đi trung bình, bán kính và đƣờng kính. PHÂN TÍCH HÀNH VI NGƢỜI DÙNG. Tập dữ liệu phân tích hành vi ngƣời dùng. Sự tƣơng quan giữa bậc ngƣời dùng với mức năng động.
Phân bố tƣơng tác theo mức năng động nhóm ngƣời dùng. Phân bố tỉ lệ ngƣời dùng theo tƣơng tác nhóm bạn bè. Phân bố số lƣợng tƣơng tác theo các nhóm bạn tƣơng tác. Phân bố tƣơng tác theo nhóm bậc xã hội.
Phân bố số lƣợng tƣơng tác trên cặp ngƣời dùng. Bậc xã hội và hành vi ngƣời dùng. Sự khác biệt hành vi ngƣời dùng trong từng nhóm bậc xã hội. Tƣơng quan bậc xã hội ngƣời dùng với thời điểm online.
Phân bố số lƣợng hành vi theo các thời điểm trong ngày. HIỆN THỰC CHƢƠNG TRÌNH. Cơ sở dữ liệu. Thƣ viện SNAP và các hàm phân tích cấu trúc đồ thị.
Chƣơng trình Social Networks Visualizer. Bảng thống kê thời gian thực thi các chƣơng trình phân tích. 58 TÀI LIỆU THAM KHẢO. 62 Bảng đối chiếu thuật ngữ Anh-Việt.
62 Bảng tham khảo các từ viết tắt. 63 DANH MỤC HÌNH Hình 3.1 So sánh tỉ lệ phân bổ nhóm ngƣời dùng theo bậc .2 Log-log bậc ngƣời dùng với tần xuất số lƣợng ngƣời dùng .3 Log-log hàm bù phân phối tích lũy bậc ZingMe (CCDF) .4 Hàm CCDF của Flickr, LiveJournal, Orkut, Youtube .5 Đƣờng phân bố xác xuất tích lũy bậc của ZingMe và các MXH .1 Bậc kết hợp đồ thị xã hội .2 Bậc kết hợp đồ thị tƣơng tác .1 Bậc liên kết trung bình knn của đồ thị ZingMe .2 Bậc liên kết trung bình knn của MXH khác .1 Đƣờng phân bố hệ số cụm C theo bậc ngƣời dùng của ZingMe .2 Đƣờng phân bố hệ số cụm C theo bậc ngƣời dùng của Facebook .1 Hàm phân bố tích lũy tỉ lệ số lƣợng comments theo bậc ngƣời dùng .2 Đƣờng tần xuất tỉ lệ comments theo bậc ngƣời dùng .1 Phân bố tích lũy tỉ lệ comments theo mức năng động ngƣời dùng .1 Phân bố tích lũy tỉ lệ ngƣời dùng theo tƣơng tác nhóm bạn bè .2 Tỉ lệ phân bổ ngƣời dùng theo số lƣợng bạn bè .1 Phân bố tích lũy tƣơng tác theo các nhóm bạn bè .2 Tỉ lệ phân bố tƣơng tác theo số bạn bè liên quan .1 Biểu diễn số tƣơng tác theo cặp bậc xã hội .1 Phân bố tích lũy tỉ lệ cặp ngƣời dùng theo số lƣợng comments .1 Tƣơng quan giữa bậc xã hội và hành vi ngƣời dùng .1 Sự khác biệt hành vi ngƣời dùng trong từng nhóm bậc xã hội.1 Tỉ lệ ngƣời dùng online tại các thời điểm trong ngày .1 Phân bố số lƣợng comments các thời điểm trong ngày .1 Hiển thị Social graph theo giải thuật Girvan-Newman .2 Hiển thị Social graph theo bậc xã hội. 56 DANH MỤC BẢNG Bảng 2.1 Ý nghĩa hệ số r .1 Các tập dữ liệu của các MXH .1 Số lƣợng đỉnh và cạnh trong WCC ZingMe .1 Số bạn bè trung bình của mỗi ngƣời dùng trên MXH .2 Số lƣợng ngƣời dùng phân bổ trong các nhóm bậc .3 Hệ số α, goodness-of-fit metrics D và cận dƣới xmin của các MXH .4 Hệ số α và D của Web, Flickr, LiveJournal, Orkut, YouTube .1 Hệ số kết hợp r của các MXH .1 Hệ số cụm trung bình của các MXH .1 Đƣờng đi trung bình, bán kinh, đƣờng kính và 90% đƣờng kính .1 Tập dữ liệu phân tích hành vi .2 Dữ liệu ngƣời dùng theo tháng.1 Thống kê thời gian thực thi các chƣơng trình phân tích. 57 Phân tích mạng xã hội ZingMe Chƣơng 1.
Giới thiệu Mỗi ngày có hàng triệu ngƣời dùng từ khắp nơi trên thế giới truy cập vào các trang điện tử (website) nhƣ Facebook [10], ZingMe [26], MySpace [11], LinkedIn [12], Youtube [13] để cập nhật tin tức, bình luận về các vấn đề đang quan tâm, chia sẻ nội dung các tập tin đa phƣơng tiện nhƣ hình ảnh, phim, sách điện tử, hoặc tán gẫu. Các trang điện tử này chính là các mạng xã hội ( online social network,OSN ). Các website truyền thống đƣợc tổ chức xoay quanh khái niệm nội dung. Ngƣời chủ sở hữu website công bố nội dung và chịu trách nhiệm quản lý các nội dung đã đƣợc công bố.
Ngƣời dùng truy cập website để tìm hiểu các nội dung quan tâm, thực hiện phản hồi về nội dung thông qua các công cụ đƣợc cung cấp, tuy nhiên các công cụ phản hồi này thƣờng rất hạn chế. Hoặc khi ngƣời dùng muốn trao đổi với những ngƣời dùng khác thì càng trở nên khó khăn hơn. Ngƣợc lại, các mạng xã hội đƣợc tổ chức xoay quanh khái niệm ngƣời dùng. Ngƣời dùng tham gia vào mạng xã hội có thể công bố các nội dung đang sở hữu và tự quản lý, chịu trách nhiệm về nội dung công bố, đồng thời có khả năng tạo các liên kết “bạn bè” với những ngƣời dùng khác.
Cấu trúc liên kết “ ngƣời với ngƣời ” là nền tảng cơ bản của một mạng xã hội. Nhƣ vậy mạng xã hội có thể xem là hình ảnh phản chiếu của thế giới thực biểu diễn các mối quan hệ, hoạt động con ngƣời trong xã hội thực. Hiện nay mạng xã hội Facebook có trên 500 triệu ngƣời dùng, ZingMe trên 12 triệu ngƣời dùng, MySpace trên 266 triệu ngƣời dùng, LinkedIn có trên 80 triệu ngƣời dùng. Sự phát triển nhanh chóng và rộng rãi trên khắp thế giới của mạng xã hội đã tạo điều kiện thuận lợi trong việc nghiên cứu và khám phá hành vi con ngƣời.
Những kết quả nghiên cứu đó có thể quay lại áp dụng cho nhiều lĩnh vực nhân chủng học, thống kê hoặc kinh tế. Phân tích cấu trúc mạng xã hội, hành vi ngƣời dùng là để giúp cải tiến các mạng xã hội hiện tại và phát triển các ứng dụng Mai Phúc Tiến Trang 1 Phân tích mạng xã hội ZingMe dựa trên nền tảng mảng xã hội một cách có hiệu quả.
