
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Trần Thị Sim
TỐI ƯU HÓA ẢNH HƯỞNG CỦA ĐỐI TƯỢNG
TRÊN MẠNG XÃ HỘI
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
HÀ NỘI - 2013

ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Trần Thị Sim
TỐI ƯU HÓA ẢNH HƯỞNG CỦA ĐỐI TƯỢNG
TRÊN MẠNG XÃ HỘI
KHOÁ LUẬN TỐT NGHIỆP ĐẠI HỌC HỆ CHÍNH QUY
Ngành: Công nghệ thông tin
Cán bộ hướng dẫn: PGS.TS Hà Quang Thụy
Cán bộ đồng hướng dẫn: ThS.NCS Vũ Ngọc Trình
HÀ NỘI - 2013
Ộ

i
LỜI CẢM ƠN
Trước tiên, tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc nhất tời Thầy giáo,
PGS-TS Hà Quang Thụy và ThS. Vũ Ngọc Trình đã tận tình hướng dẫn, động viên và
giúp đỡ tôi trong suốt quá trình thực hiện khóa luận này.
Tôi xin bày tỏ lời cảm ơn sâu sắc dến các thầy cô giáo đã giảng dạy tôi trong suốt
bốn năm học qua, đã cho tôi những kiến thức quý báu để tôi có thể vững bước trên con
đường đi của mình.
Tôi xin gửi lời cảm ơn đến các anh chị và các bạn trong phòng nghiên cứu
KTLab đã nhiệt tình chỉ bảo trong quá trình tham gia nghiên cứu khoa học và làm
khóa luận.
Tôi xin gửi lời cảm ơn tới các bạn trong lớp K54CD đã ủng hộ, khuyến khích
trong suốt quá trình học tập tại trường.
Và lời cuối cùng, tôi xin bày tỏ lòng chân thành và biết ơn vô hạn tới cha mẹ, và
các anh chị tôi, những người luôn bên cạnh tôi những lúc tôi khó khăn nhất, giúp tôi
vượt qua khó khăn trong học tập cũng như trong cuộc sống.
Hà Nội, ngày 15 tháng 05 năm 2013
Sinh viên
Trần Thị Sim

ii
TÓM TẮT
Bài toán tối đa hiệu quả ảnh hưởng của đối tượng trên mạng xã hội là việc tìm
kiếm một tập con nhỏ các nút (các nút nhân) trong mạng xã hội để lan truyền thông tin
hiệu quả nhất. Khóa luận này nghiên cứu về phương pháp tối đa hiệu quả ảnh hưởng
của đối tượng trên mạng xã hội dựa trên phương pháp giảm bậc dựa trên kinh nghiệm-
DegreeDiscount được Wei Chen và cộng sự đề xuất vào năm 2009 [1] và được tiếp tục
phát triển như Manuel Gomez-Rodriguez và Bernhard Scholkopf, 2012 [2], Bo Liu và
cộng sự, 2012 [12].
Trên cơ sở tìm hiểu và phân tích một số hướng tiếp cận bài toán tối đa hiệu quả
ảnh hưởng của đối tượng trên mạng xã hội [1, 2, 12], khóa luận áp dụng phương pháp
tối đa hiệu quả ảnh hưởng dựa trên việc giảm bậc theo kinh nghiệm. Theo tiếp cận đó,
khóa luận đưa ra mô hình để tìm được các nút “nhân” với các thành phần mô hình
được trình bày tường minh. Khóa luận tiến hành thực nghiệm mô hình trên dữ liệu lấy
từ arXiv.org. Phân tích kết quả thực nghiệm, khóa luận chứng tỏ được mô hình là khả
quan và có thể tiếp tục phát triển tiếp.

iii
LỜI CAM ĐOAN
Em xin cam đoan đây là phần nghiên cứu và thực hiện khóa luận của riêng em,
dưới sự hướng dẫn của PTS.TS Hà Quang Thụy và ThS. Vũ Ngọc Trình, không sao
chép từ các công trình nghiên cứu khác.
Em đã trích dẫn đầy đủ các tài liệu tham khảo, các công trình nghiên cứu liên
quan ở trong nước và quốc tế.Nếu sai em xin chịu hoàn toàn trách nhiệm và chịu mọi
kỷ luật của ĐHQH Hà Nội và Nhà trường.
Hà Nội, ngày 15 tháng 5 năm 2013
Sinh viên
Trần Thị Sim

