Upload
others
View
5
Download
0
Embed Size (px)
Citation preview
ĐẠ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
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
iv
MỤC LỤC
LỜI CẢM ƠN ...................................................................................................................i
TÓM TẮT ....................................................................................................................... ii
LỜI CAM ĐOAN .......................................................................................................... iii
MỤC LỤC ......................................................................................................................iv
Danh sách các bảng ........................................................................................................vi
Danh sách các hình vẽ .................................................................................................. vii
Danh sách các từ viết tắt .............................................................................................. viii
Mở đầu ............................................................................................................................. 1
Chương 1. Giới thiệu về bài toán tối ưu ảnh hưởng của đối tượng trên mạng xã hội. .... 3
1.1. Phân tích mối quan hệ trên mạng xã hội. ........................................................... 3
1.2. Tối ưu ảnh hưởng của đối tượng trong mạng xã hội. ........................................ 4
1.2.1. Động lực và mục đích. 4
1.2.2. Phát biểu bài toán tối ưu hóa ảnh hưởng của đối tượng trong mạng xã hội.
7
Chương 2.Một số hướng tiếp cận bài toán tối ưu hóa ảnh hưởng của đối tượng trong
mạng xã hội. .................................................................................................................... 9
2.1. Tối ưu hóa ảnh hưởng theo thời gian liên tục trên mạng khuếch tán. ............... 9
2.2. Tối ưu ảnh hưởng của đối tượng dựa trên cải tiến các thuật toán tham ăn -
Greedy và giảm bậc - DeegreeDiscount. ................................................................... 13
2.2.1. Cải tiến thuật toán Greedy 14
2.2.2. Thuật toán DegreeDiscountIC. 18
Chương 3. Phương pháp tối ưu hóa ảnh hưởng của đối tượng - DegreeDiscountIC. ... 22
3.1. Mô tả bài toán giảm bậc dựa trên kinh nghiệm DegreeDiscount. ................... 22
3.2. Mô hình đề xuất. .............................................................................................. 22
Chương 4.Thực nghiệm và đánh giá kết quả. ................................................................ 26
v
4.1. Mô tả thực nghiệm. .......................................................................................... 26
4.2. Dữ liệu thực nghiệm. ....................................................................................... 26
4.2.1. Đặc trưng của cơ sở dữ liệu trên trang arXiv.org 26
4.2.2. Xây dựng tập dữ liệu. 28
4.3. Thực nghiệm .................................................................................................... 30
4.3.1. Môi trường thực nghiệm 30
4.3.2. Mô tả cài đặt chương trình 30
4.4. Đánh giá kết quả .............................................................................................. 35
4.5. Nhận xét ........................................................................................................... 38
Kết luận .......................................................................................................................... 39
vi
Danh sách các bảng
Bảng 2-1: Một số biến quan trọng khi sử dụng đồ thị G ...................................... 14
Bảng 2-2 : Thuật toán Greedy………………………………………………… 15
Bảng 2-3: Thuật toán NewGreedyIC .................................................................... 16
Bảng 2-4: Thuật toán NewGreedyWC ................................................................. 18
Bảng 2-5: Thuật toán DegreeDiscountIC ............................................................. 20
Bảng 4-1 Cấu hình phần cứng .............................................................................. 30
Bảng 4-2: Công cụ phần mềm .............................................................................. 30
Bảng 4-3: Bản phân tách bản ghi trong file arXiv.html ....................................... 31
Bảng 4-4: Bảng ghi tên tác giả sau ghi gán ID .................................................... 32
vii
Danh sách các hình vẽ
Hình 1: Một mô hình đồ thị mạng xã hội ............................................................... 3
Hình 2: Thông tin lan truyền trên mạng xã hội ..................................................... 6
Hình 3: Mô tả bài toán ............................................................................................ 7
Hình 4: Tập các nút ảnh hưởng, các nút vô ích, nút không tác dụng ..................... 9
Hình 5: Điều tra hàm ảnh hưởng 𝜎(𝐴; 𝑇) ............................................................. 11
Hình 6: Biểu diễn hàm ảnh hưởng 𝜎(𝐴; 𝑇) .......................................................... 12
Hình 7: Hàm ảnh hưởng 𝜎(𝐴; 𝑇) đối với các mạng lớn nhỏ ................................ 13
Hình 8: Thông tin trên trang arXiv.org ................................................................. 23
Hình 9 : Quá trình xây dựng tập dữ liệu ............................................................... 27
Hình 10: Cấu trúc một bản ghi arXiv.html ........................................................... 28
Hình 11:Mô hình đề xuất ...................................................................................... 29
Hình 12: Phân tích cú pháp arXiv.org .................................................................. 32
Hình 13: Dữ liệu đầu vào của thuật toán .............................................................. 33
Hình 14:ID của tập nút “nhân” ảnh hưởng nhất và bậc của chúng ...................... 35
Hình 15: Lan truyền ảnh hưởng của các thuật toán khác nhau với mô hình IC...36
Hình 16 :Thời gian chạy của các thuật toán khác nhau ........................................ 37
viii
Danh sách các từ viết tắt
Viết tắt Từ hoặc cụm từ
IC Independent Case
WC Weight Case
CELF Cost Effective Lazy Forward
1
Mở đầu
Sự phát triển mạnh mẽ của các mạng xã hội dẫn đến nguồn thông tin phong phú
về mối quan hệ giữa người hoặc các thực thể với nhau.Tuy nhiên, nhiều tri thức trong
đó lại thường được ẩn giấu bên trong, trong đó có thông tin về những đối tượng “có
ảnh hưởng lớn” trong mạng xã hội. Biết được các đối tượng có ảnh hưởng lớn trong
mạng xã hội sẽ giúp ích rất nhiều cho việc tiếp thị, quảng bá sản phẩm, cho phép thông
tin và ý tưởng có thể đến với một số lượng lớn người sử dụng trong một thời gian
ngắn. Tuy nhiên, bài toán tìm kiếm đối tượng có ảnh hưởng lớn một cách hiệu quả
đem tới nhiều thách thức cần được giải quyết.
Tối ưu hóa ảnh hưởng của đối tượng trong mạng xã hội là bài toán thời sự, có ý
nghĩa. Có nhiều dự án nghiên cứu được hình thành để duy trì và phát triển hướng
nghiên cứu này như thông tin lan truyền (Leskovec, 2007[6]), tối ưu hóa ảnh hưởng
rời rạc (Kempe, 2003 [5]), lan truyền trong tiếp thị (Richardson & Domingos[3,4]) và
lan truyền ảnh hưởng trong dịch tễ học (Wallinga & Teunis,2004[7]). Gần đây, Wei
Chen và các cộng sự (2009) [1] đề xuất thuật toán cải tiến dựa trên thuật toán Greedy
ban đầu – thuật toán DegreeDiscountIC, giảm bậc dựa trên kinh nghiệm và sau đó
Manuel Gomez-Rodriguez và Bernhard Scholkopf, 2012 [2], Bo Liu và cộng sự, 2012
[12] tiến hành các nghiên cứu phát triển giải pháp nói trên..
Khóa luận “Tối ưu hóa ảnh hưởng của đối tượng trong mạng xã hội” đề cập tới
các phương pháp giải bài toán tối ưu hóa ảnh hưởng của đối tượng trong mạng xã hội,
tập trung vào lớp giải pháp giảm bậc dựa trên kinh nghiệm.
Nội dung của khóa luận được bố cục gồm có 4 chương :
Chương 1: Giới thiệu khái quát về bài toán tối đa ảnh hưởng đối tượng trên
mạng xã hội.
Chương 2 : Giới thiệu về các hướng tiếp cận giải quyết bài toán tối ưu ảnh
hưởng của đối tượng trên mạng xã hội. Chương này tập trung vào việc giới thiệu các
thuật toán cơ sở ban đầu mà Wei Chen và các cộng sự (2009) đề xuất. Đây là cơ sở
phương pháp luận quan trọng để khóa luận đưa ra mô hình thực nghiệm một phần mô
hình hệ thống được các tác giả xây dựng.
Chương 3 : Khóa luận xây dựng mô hình thực nghiệm, tối ưu ảnh hưởng của đối
tượng trên mạng xã hội của Wei Chen và cộng sự (2009) [1], dùng thuật toán
2
DegreeDiscountIC để giải quyết bài toán này. Chúng tôi sẽ tiến hành xây dựng mô
hình thực nghiệm dựa trên phương pháp DegreeDiscountIC.
Chương 4: Tiến hành thực nghiệm với mô hình đề xuất, đánh giá kết quả của mô
hình.
Phần kết luận và định hướng phát triển khóa luận : Tóm tắt nội dung chính
đạt được của khóa luận, đồng thời chỉ ra những điểm cần khắc phục và đưa ra những
định hướng nghiên cứu trong thời gian sắp tới.
3
Chương 1. Giới thiệu về bài toán tối ưu ảnh
hưởng của đối tượng trên mạng xã hội.
1.1. Phân tích mối quan hệ trên mạng xã hội.
Nghiên cứu về mối quan hệ trên mạng xã hội là một trong những hướng nghiên
cứu thu hút được sự chú ý của cộng đồng khai phá mạng xã hội hiện nay [ 2]. Mạng xã
hội là mạng của một nhóm người hoạt động và các mối quan hệ gắn kết họ với nhau.
Những người hoạt động trên mạng có thể là những cá nhân hoặc tập thể. Những người
này trao đổi tài nguyên với nhau và chính điều này gắn kết với nhau trong một mạng
xã hội. Mỗi tài nguyên đem trao đổi được xem như là mỗi liên kết trong mạng xã hội
và những cá nhân duy trì mối quan hệ này tương ứng với việc duy trì một cung trong
đồ thị mô phỏng mạng xã hội. Sức bền của cung này phụ thuộc vào mức độ trao đổi
thường xuyên của các cá nhân trong mạng xã hội. Gần đây có rất nhiều mạng xã hội
được phát triển với quy mô lớn trên các trang web mạng, chẳng hạn như Facebook,
Friendster, Twitter,… chúng trở nên thành công vì chúng đạt được hiệu quả trong việc
kết nối mọi người với nhau, tạo nên các cộng đồng ảo cùng chia sẻ với nhau về những
sở thích chung.
Hình 1 : Một mô hình đồ thị mạng xã hội [8].
4
Thông tin tiềm ẩn từ các cộng đồng này rất đa dạng, tuy nhiên để khám phá được
nó không hề đơn giản, bởi mạng xã hội có sự phối hợp và góp sức của hàng ngàn,
thậm chí hàng triệu thành viên, vì thế có thể trích chọn được những thông tin cần thiết
từ một cộng đồng rất lớn là vấn đề rất khó khăn.
Vấn đề phát hiện các mối quan hệ trên mạng xã hội, từ đó đưa ra giải pháp tối ưu
ả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 hợp con nhỏ các
nút ( các nút nhân ) trong mạng xã hội có ảnh hưởng lớn nhất . Một phần của mạng xã
hội được mô hình hóa thành một đồ thị trong đó các nút mô hình hóa các cá nhân trong
mạng và các cạnh mô hình hóa các mối quan hệ giữa các cá nhân. Những nhà phân
tích trong lĩnh vực mạng dựa vào quan hệ giữa các thành viên của cộng đồng, các hàng
xóm, một nhóm hoặc một lớp để hiểu cách thức các mạng xác định tổng số người hay
các nhóm nhỏ bên trong một mạng lớn. Cách thức mà một người kết nối với một
người khác thể hiện cấu trúc nền tảng của mạng, các nhà nghiên cứu dựa vào những
mối quan hệ này để phân tích và đưa ra được những kết luận về mối quan hệ giữa
người này với người kia, giữa một người với cả cộng đồng hay ảnh hưởng của họ đối
với cả cộng đồng ra sao.
Sự nghiên cứu về mạng xã hội của các nhà khoa học đã thu nhận được nhiều phát
minh khoa học mới về mạng xã hội trong nhiều thập kỷ qua, được mô hình và phân
tích bằng các công cụ của lý thuyết đồ thị. Qua những nghiên cứu đó, người ta chứng
minh rằng đồ thị mạng của mạng xã hội đưa đến nhiều thông tin hữu ích tiềm ẩn, giúp
con người khai thác được thế mạnh mà mạng xã hội đem lại.
1.2. Tối ưu ảnh hưởng của đối tượng trong mạng xã hội.
1.2.1. Động lực và mục đích.
Ngày nay, với sự phát triển nhanh chóng của web mạng xã hội, các ứng dụng
online như Facebook, Youtube, Twitter,… mang lại nguồn thông tin phong phú, đồng
thời con người có thể dễ dàng kết nối với nhiều mối quan hệ khác. Những mạng này
có thể giúp cho việc tiếp thị trở nên dễ dàng, cho phép thông tin và ý tưởng có thể ảnh
hưởng đến một số lượng lớn trong một thời gian ngắn. Với sự hỗ trợ của các lý thuyết
đồ thị, con người có thể trích xuất được rất nhiều thông tin ngữ nghĩa quan trọng và
hữu ích từ các đồ thị mạng.
Khóa luận tập trung khai thác mối quan hệ giữa những cá nhân trong mạng xã
hội, từ đó tìm ra được cá nhân có ảnh hưởng lớn nhất trong mạng xã hội. Mạng xã hội
5
được mô hình thành đồ thị được tạo thành với các nút là những cá nhân tham gia
mạng, và các cạnh biểu diễn mối quan hệ giữa họ [1].
Xem xét một trường hợp để thấy được động lực thúc đẩy cho nghiên cứu này [1]:
Một công ty nhỏ muốn phát triển một ứng dụng trực tuyến rất triển vọng trong
một mạng xã hội trực tuyến và muốn tiếp thị thông qua chúng. Nhưng công ty đó lại
có một ngân sách hạn chế, vì vậy chỉ có thể lựa chọn số lượng nhỏ người sử dụng ban
đầu trong mạng để sử dụng nó ( bằng cách cho họ quà tặng hoặc các khoản thanh
toán). Công ty mong muốn rằng những người sử dụng ban đầu sẽ thích ứng dụng đó và
bắt đầu ảnh hưởng đến bạn bè của họ trong mạng xã hội để cùng sử dụng nó, và bạn bè
của họ cũng sẽ như vậy. Như vậy, nếu như trong xã hội thực ta có thể thực hiện điều
đó bằng cách lan truyền miệng, còn trong mạng xã hội thì cần thông qua các ứng dụng.
Vấn đề ở đây là chọn ai làm người sử dụng ban đầu để kết quả thu được có sự
ảnh hưởng đến số lượng người sử dụng lớn nhất trong mạng, tức là ta trở về vấn đề tìm
kiếm các cá nhân có ảnh hưởng nhất trong mạng xã hội.
Vấn đề này được gọi là tối ưu ảnh hưởng, sẽ là quan tâm của nhiều công ty cũng
như các cá nhân muốn quảng bá sản phẩm, dịch vụ của họ, và ý tưởng sáng tạo của họ
thông qua các cách thức tiếp thị lan truyền. Mạng xã hội trực tuyến cung cấp các giải
pháp để giải quyết vấn đề này, bởi vì chúng đang kết nối một số lượng lớn người với
nhau và chúng thu thập một lượng lớn thông tin về cấu trúc cũng như động lực truyền
thông trên mạng xã hội. Tuy nhiên, cũng có những thách thức đặt ra khi giải quyết vấn
đề này đó là : các mạng xã hội có quy mô lớn, có cấu trúc kết nối phức tạp và luôn
biến đổi theo thời gian, có nghĩa là giải pháp cho vấn đề này cần phải được rất hiệu
quả và có khả năng mở rộng.
Bài toán tối ưu ảnh hưởng của đối tượng trên mạng xã hội được Domingos và
Richardson [3, 4] là người đầu tiên nghiên cứu tối đa ảnh hưởng như là một vấn đề
thuật toán. Đây là bài toán thời sự có ý nghĩa, đặc biệt trong các mạng xã hội về lĩnh
vực khoa học. Có nhiều dự án và nghiên cứu đã được hình thành để duy trì và phát
triển hướng nghiên cứu này : Kempe, Kleinberg và Tardos [5] là người đầu tiên xây
dựng vấn đề tối ưu hóa ảnh hưởng theo cách tối ưu hóa rời rạc, Leskovec[6] trình bày
một giải pháp tối ưu hóa trong việc lựa chọn hạt nhân lan truyền mới, được gọi là
“Cost Effective Lazy Forward”, viết tắt là CELF, đề xuất thuật toán cải tiến dựa trên
thuật toán Greedy ban đầu – thuật toán DegreeDiscountIC, giảm bậc dựa trên kinh
6
nghiệm và sau đó Manuel Gomez-Rodriguez và Bernhard Scholkopf, 2012 [2], Bo Liu
và cộng sự, 2012 [12] tiếp tục phát triển nó,…
Hình 2 : Thông tin lan truyền trên mạng xã hội [11]
Tuy nhiên, các thuật toán trên cho thấy rằng chúng vẫn còn mất một vài giờ để có
thể hoàn thành việc duyệt một đồ thị với một vài chục ngàn nút [1] , vì vậy nó không
hiệu quả cho các mạng có quy mô lớn. Bởi vậy, cần nghiên cứu thuật toán có thể lựa
chọn được tập “ nhân” lan truyền đem lại hiệu quả nhất và có thể áp dụng trên quy mô
lớn , trong thời gian ngắn.
Bằng cách tiếp cận theo cách khai phá vào đồ thị mô phỏng mạng xã hội, với các
đăch trưng của nút và các cạnh đóng vai trò trung tâm. Chúng ta xem xét đến nút được
coi là đỉnh và các nút kề nó, gọi là các hàng xóm của nó.
Tối ưu hóa ảnh hưởng của đối tượng trong mạng xã hội có những đặc điểm khác
biệt so với những nghiên cứu mạng thông tin trước đó, và có nhiều thách thức :
Mạng xã hội có quy mô lớn, có cấu trúc và kết nối phức tạp, và cũng liên
tục thay đổi, vì vậy cần cần có một giải pháp hiệu quả và có khả năng mở
rộng.
Với một mạng xã hội lớn, thì khối lượng dữ liệu thu được cũng rất lớn và
yêu cầu cần đặt ra cần có một phương pháp tối ưu hóa ảnh hưởng vừa hiểu
quả và vừa đảm bảo về mặt thời gian chạy.
7
1.2.2. Phát biểu bài toán tối ưu hóa ảnh hưởng của đối tượng trong
mạng xã hội.
Bài toán tối ưu hóa ảnh hưởng của đối tượng trong mạng xã hội được Wei Chen
và cộng sự (2009) [1] phát biểu như sau :
Đầu vào : Một mạng xã hội được mô phỏng như một đồ thị vô hướng G
(V,E), với đỉnh V mô hình hóa các cá nhân trong mạng và cạnh E mô hình
hóa các mối quan hệ giữa các cá nhân, các cặp (đỉnh, hàng xóm của đỉnh)
= (ui,vi).
Đầu ra : Tất cả các cặp quan hệ (đỉnh, hàng xóm của đỉnh) có điểm ảnh
hưởng lớn nhất.
Hình 3. Mô tả bài toán
Ví dụ : Trong một mạng có 4 người sử dụng A, B, C, D. A là bạn bè của B, B là bạn
của C, C là bạn của D, A là bạn của C, A là bạn của D, B là bạn của D. Từ đó ta có thể
xét ra các cặp là (đỉnh, hàng xóm của đỉnh là) là (A,B), (B,C), (C,D), (A,C), (A,D),
(B,D). Những cặp đó trở thành đầu vào của thuật toán mà chúng ta lựa chọn, sau khi
cài đặt thuật toán, ta thu được đầu ra là tập “nhân” có ảnh hưởng lớn nhất trong mạng.
8
Tóm tắt chương 1
Trong chương này, khóa luận đã giới thiệu khái quát một số nội dung liên quan
và trình bày về động lực và mục đích của bài toán tối ưu hóa ảnh hưởng của đối tượng
trên mạng xã hội. Trong chương tiếp theo, khóa luận sẽ tập trung làm rõ một số hướng
nghiên cứu liên quan về bài toán tối ưu hiệu quả ảnh hưởng trên web.
9
Chương 2.Một số hướng tiếp cận bài toán tối
ưu hóa ảnh hưởng của đối tượng trong mạng xã
hội.
Tối ưu hóa ảnh hưởng của đối tượng là bài toán được quan tâm rất nhiều trên thế
giới. Có rất nhiều nghiên cứu tiếp cận vấn đề này, có những nghiên cứu đưa ra một
mạng lưới hoạt động, mô tả chuỗi thời gian liên tục Markov, từ đó tính toán số lượng
trung bình các nút đạt được bởi quá trình lan truyền từ nút nguồn [2], có những nghiên
cứu tập trung giải quyết vấn đề thời gian của các thuật toán tham ăn - Greedy, hay
giảm dựa trên kinh nghiệm DegreeDiscount [1,12],…
Trong chương này, chúng tôi giới thiệu một số hướng tiếp cận bài toán tối ưu ảnh
hưởng của đối tượng trong mạng xã hội.
2.1. Tối ưu hóa ảnh hưởng theo thời gian liên tục trên mạng khuếch
tán.
Nghiên cứu xây dựng mô hình khuếch tán liên tục theo thời gian được đề xuất
bởi Gomez và Rodriguez [2] . Xem xét quá trình xảy ra khuếch tán và lan truyền trên
các mạng tĩnh với kết nối được biết đến với tỉ lệ lan truyền. Một quá trình khuếch tán
bắt đầu khi một nút “nhân” lan truyền ảnh hưởng tại thời điểm t =0 bởi hành động của
một nguồn bên ngoài mạng. Sau đó nút nguồn cố gắng lan truyền cho hàng xóm của
chúng. Khi một hàng xóm i gây ảnh hưởng tại thời điểm ti, nó cố gắng gây ảnh hưởng
tiếp tục cho các hàng xóm của nó và cứ thế tiếp tục.
Quá trình lan truyền ảnh hưởng bắt đầu trong tập hợp các nút “nhân” A, Gomez
và Rodriguez [2] định nghĩa N(A;T) là số lượng các nút bị ảnh hưởng trong T thời
gian và sau đó xác định các hàm ảnh hưởng 𝜎(𝐴; 𝑇) là tổng trung bình các nút bị ảnh
hưởng trong thời gian T, nghĩa là 𝜎(𝐴; 𝑇) = EN(A;T).
Hình 4: Hình (a,b): tập các nút bị ảnh hưởng(I, màu đỏ), các nút vô ích(Un, màu da
cam) tại 2 thời điểm khác nhau cho một quá trình khuếch tán bắt đầu ở nút “nhân”
A3,5 so với một nút đặc biệt – gọi là nút chìm (n, màu đen). Bất kì đường dẫn từ một
10
nút vô ích đến nút chìm bị chặn lại bởi nút bị ảnh hưởng. Tập hợp các nút không tác
dụng(Xn) là sự kết hợp của bộ nút bị ảnh hưởng và nút vô ích. Hình (c) : tập các nút
không tác dụng X∈ Q*n , giống như A⊆ X.Chúng đại diện cho những trạng thái mà
chúng ta cần mô tả cho sự tiến triển theo thời gian của một quá trình khuếch tán về
phí n nút chìm mà bắt đầu trong tập hợp các nút “nhân” A.
Mục tiêu của nghiên cứu là tìm ra tập hợp các nút “nhân” A trong mạng khuếch
tán G nhằm tối ưu hóa hàm ảnh hưởng 𝜎(𝐴; 𝑇). Nói cách khác, việc tìm tập hợp các
nút “nhân” như vậy là một quá trình khuếch tán trong G, đạt đến trung bình số lượng
lớn nhất các nút trước khi cắt cửa sổ T. Vì vậy, hướng giải quyết của nghiên cứu là :
ở đây tập nguồn A là biến để tối ưu hóa, đường chân trời T và một tập k là hằng số.
Các tác giả sử dụng nghiên cứu của Kulkami (1986) [9] để đánh giá hàm ảnh
hưởng 𝜎(𝐴; 𝑇) cho tập nguồn A bất kì trong mạng G.
Hàm đánh giá ảnh hưởng :Các hàm ảnh hưởng phụ thuộc vào khả năng lan
truyền qua tất cả các nút mạng như sau :
1
( ; ) ( ; ) ( | ).
N
n
nA T EN A T P t T A
Trong đó tn là thời gian lan truyền của nút n, A là tập hợp các nút “nhân” và T là
đường chân trời hay cửa sổ cắt. Vì vậy, ta cần tính xác suất lan truyền P(tn≤T|A) cho
mỗi nút n trong mạng. Lưu ý rằng, bất cứ khi nào n n∈A thì xác suất lan truyền
P(tn≤T|A) là không đáng kể và bằng 1. Và những nút n như vậy được gọi là những nút
chìm. Với một mạng khuếch tán G = (V,E), một tập các nút B ⊂V, và một nút n ∈V,
[2] định nghĩa tập hợp các nút bị chặn hoặc bị chi phối bởi B như sau :
Sn(B) = u ∈V : bất kỳ một đường dẫn nào từ u đến n trong G sẽ đi qua ít nhất
một nút trong B .
Từ định nghĩa, B ⊆Sn và Sn(Sn(B))=Sn(B), [2] định nghĩa tập *
n như sau :
*
: ( ).n n
X V X S X
| |
* argmax ( ; )A k
A A T
11
Trong đó, tất cả các nút trong X ∈ *
n bị chặn duy nhất bởi các nút bị chìm n.
Phương pháp này có thể tìm thấy tất cả các tập trong *
n bị ảnh hưởng.
Với một quá trình khuếch tán được bắt đầu từ tập nút “nhân” A, một nút chìm n
và bất kì một khoảng thời gian t 0 nào, chúng ta biểu thị tập hợp các nút bị ảnh
hưởng như I(t|A), tập hợp các nút vô ích là Un(t|A) và tập hợp các nút khiếm khuyết (
tức là các nút bị ảnh hưởng hoặc sử dụng ít ) là (t|A). Lưu ý rằng tập các nút khiếm
khuyết (Xn) là bao gồm các tập bị ảnh hưởng (I) và nút vô ích(Un). Theo định nghĩa Sn-
(.),Un(t|A) = Sn(I(t|A))\I(t|A) và Xn(t|A)=Sn(I(t|A)). Bây giờ bằng cách nghiên cứu thời
gian quá trình tiến triển của Xn(t|A), chúng ta có thể tính toán P(tn ≤T|A).
Đầu tiên, cho một quá trình khuếch tán bắt đầu trong tập hợp các nút “nhân” A,
nó có thể được hiển thị bằng các tập hợp của các nút khiếm khuyết Xn(t|A) tại bất kì
thời điểm t≥ 0 thuộc Ωn* .
Hình 5 : Điều tra hàm ảnh hưởng 𝜎(𝐴; 𝑇) , thuật toán INFLUMAX và các thuật toán
cơ sở khác đạt được trong một mạng ngoại vi nhỏ với 35 nút và 39 cạnh trong thời
gian khác nhau, đường chân trời T và tập số nút của tập “nhân” |A|. INFLUMAX luôn
đạt được ảnh hưởng tối ưu.
Định lý 1 (Kullkarni – 1986 ) : Cho một tập nút nguồn A, một nút ẩn n và tại bất
cứ khoảng thời gian t 0 , Xn (t|A) *
n
12
Hình 1(c) liệt kê tất cả tập hợp các nút khiếm khuyết Xn∈ Ωn* mà A ⊆X cho một
mạng nhỏ mô tả trong hình 1(a) và 1(b). Chúng đại diện cho các trạng thái mà chúng
ta cần để mô tả sự phát triển của một quá trình khuếch tán bắt đầu từ tập hợp các nút
“nhân” so với n nút chìm. Bây giờ, giả định khả năng truyền theo cặp theo cấp số nhân
trong mạng khuếch tán. Định lý sau đây được áp dụng:
Định lý 2 : Cho một tập các nút “nhân” A, một nút ẩn n và khả năng lan truyền
độc lập của các nút theo cấp số nhân f(tj|ti;𝛼ij),Xn(t|A), t≥ 0 là một chuỗi Markov
liên tục theo thời gian(CTMC) với không gian trạng tháiX:X∈ Ωn*,A⊆X và một ma
trận vô cùng Q=[q[D,B](D,B∈X:X∈ Ωn*,A⊆X) thì :
,
,
( , ) ( ) : ( ),
( , ) ( , ) ( ) ,
0
i j
i j
v ni j C D v B S D v
q D B i j C D B D
ở đó C(D) là tối thiểu đơn nhất giữa D và D=V/D và Cv(D)=(u,v)∈C(D).
Tối ưu ảnh hưởng : Gomez và Rodriguez [2] chỉ ra cách đánh giá hàm mục tiêu
𝜎(𝐴; 𝑇) cho các tập nguồn A bất kỳ. Tuy nhiên tối ưu 𝜎(𝐴; 𝑇) đối với tập nguồn A là
một nhiệm vụ khó khăn bởi việc tìm các tập k nút ngay trên các mạng nhỏ đã là rất
khó.
Hình 6: Biểu diễn hàm ảnh hưởng 𝜎(𝐴; 𝑇) khi T =1 và tốc độ lan truyền α∼U(0,5) so
với tập “nhân” (a): 1.014 nút trong mạng Forest Fire (b): 512 nút ngẫu nhiên trong
mạng Kronecker (c): 1.024 nút mạng Kronecker được phân bậc. Thuật toán được đề
xuất INFLUMAX nhanh hơn so với các phương pháp khá ít nhất là 20%.
Định lý 3: Cho một đồ thị mạng G=(V,E), 1 tập nguồn A⊆V và một giới hạn
thời gian T, tối ưu ảnh hưởng trong mạng khuếch tán liên tục được định nghĩa bởi
phương trình là NP-hard.
13
Định lý 4: Cho một đồ thị mạng G(V,E), một tập “nhân” A⊆V và một giới hạn
thời gian T, hàm ảnh hưởng 𝜎(𝐴; 𝑇) là một hàm mô đun con trong tập hợp các nút
“nhân” A.
Định lý 5: Cho một tập “nhân” A ⊆V với k nút “nhân” và một nút a ∈ 𝑉 \ A ,
cho 𝛿a = 𝜎 ( A ∪ a;T-𝜎 A ;T) và a1,…,ak chuỗi k nít với 𝛿a theo thứ tự giảm dần.
Khi đó max|a|<k𝜎(𝐴; 𝑇) ≤ 𝜎 A ;T) + ∑ 𝛿𝑘𝑖=1 ai.
Có thể tăng tốc độ của thuật toán bằng cách sử dụng thuật toán INFLUMAX :
- Lazy evaluation [6] : Nó làm giảm đáng kể thời gian trong việc đánh giá ảnh
hưởng ở vùng cận biên.
- Localized source nodes(LSN): tăng tốc bằng cách tính toán P(tn≤T|A).
Hình 7 : Hàm ảnh hưởng σ (A, T) được tăng tốc bằng thuật toán INFLUMAX so với
trên trang trực tuyến bị ràng buộc từ Định Lý 5 khi T = 1 (a) 35 nút mạng Kronecker
(b) 1.024 nút mạng phân cấp Kronecker (c) 1000 nút mạng khuếch tán thực phân phối
từ các siêu liên kết khác.
2.2. Tối ưu ảnh hưởng của đối tượng dựa trên cải tiến các thuật toán tham
ăn - Greedy và giảm bậc - DeegreeDiscount.
Vấn đề cần giải quyết đó chính là tìm ra một thuật toán mà từ mô hình đồ thị
mạng ban đầu có thể lựa chọn được tập các nút có ảnh hưởng nhất trong mạng đó.
Kempe, Kleinberg và Tardos [5] là người đầu tiên xây dựng các vấn đề tối ưu hóa rời
rạc, theo [5] ảnh hưởng của một người trong mạng được lan truyền theo 3 mô hình : IC
( Independedt Case ), WC ( Weight Case) và mô hình ngưỡng tuyến tính. Dựa vào các
mô hình đó, Wei Chen và các cộng sự [1] đã đề xuất những cải tiến mới cho thuật toán
Greedy và Discount theo hai mô hình IC và WC.
14
2.2.1. Cải tiến thuật toán Greedy
a) Định nghĩa thuật toán Greedy
Một mạng xã hội được mô phỏng như một đồ thị vô hướng G (V,E), với nút V
trong đồ thị mô hình hóa các cá nhân trong mạng và cạnh E mô hình hóa mối quan hệ
giữa các cá nhân trong mạng đó. Ví dụ, trong một mạng về công bố và đăng tải các bài
báo khoa học, một nút là đại diện cho một tác giả, và giữa 2 nút có 1 cạnh nếu hai tác
giả đó là đồng tác giả cho một bài báo. Ta có bảng liệt kê các biến cần dùng trong bài
toán khi liên quan đến đồ thị G như sau :
Bảng 2-1 : Một số biến quan trọng khi sử dụng đồ thị G.
Biến Mô tả
N Số đỉnh của G
M Số của các cạnh trong G
K Số lượng nhân cần tìm cho tập S
R Số vòng lặp của thuật toán
T Số lần lặp trong thuật toán của Cohen trong thuật toán
P Lan truyền xác suất trong mô hình IC
dv Bậc của đỉnh v trong G
tv số các láng giềng của đỉnh v được chọn là nhân
Cho S là tập hợp con của điểm được chọn để bắt đầu lan truyền ảnh hưởng, và
được gọi là các nút nhân. RanCas(S) biểu thị các hàm ngẫu nhiên ảnh hưởng từ bộ
nguồn S, đầu ra là một tập hợp ngẫu nhiên của các đỉnh ảnh hưởng bởi tập nhân S. Ta
chọn đồ thị G và một số k là đầu vào và tạo ra một tập S có k nút nhân, lan truyền ảnh
hưởng, càng lớn càng tốt.
Thuật toán được cài đặt như sau :
15
Bảng 2-2 : Thuật toán Greedy
Thuật toán với một hàm ngẫu nhiên RanCas(). Trong mỗi vòng lặp i, thuật toán
thêm 1 đỉnh S vào tập S nếu đỉnh đó làm tăng độ lan truyền để làm được điều này. Để
làm được điều này, với mỗi đỉnh v không thuộc tập S, độ lan truyền của S , S∪v
được ước lượng với R được mô phỏng nhắc lại của hàm RanCas(S∪v). Mỗi lần tính
toán hàm RanCas(S) thì độ phức tạp của thuật toán là O(m), vì vậy độ phức tạp của
thuật toán tham ăn là O(knRm), tương đối lớn.
b) Kết hợp thuật toán Greedy với thuật toán CELF.
Thuật toán Greedy là thuật toán đơn giản nhất, dễ thực hiện cài đặt. Hiệu suất tối
ưu của thuật toán là 1-1/e ( 63%) [10] tương đối tốt nhưng nó có một số hạn chế là độ
phức tạp lớn, mất nhiều thời gian chạy. Vì vậy, để giải quyết vấn đề này Leskovec và
các cộng sự [6] đã đề xuất cách tối ưu thuật toán này bằng cách kết hợp thuật toán này
với thuật toán CELF (Cost Effective Lazy Forward ).
Thuật toán CELF khi kết hợp với thuật toán tham ăn cần thông qua 2 bước [1] :
- Tập S : sử dụng sự hỗ trợ của từ hiệu suất của thuật toán tham ăn
- Tập S∪v : sử dụng đơn vị hiệu suất của thuật toán tham ăn.
Giải pháp cuối cùng đó là : argmax(RanCas (S), RanCas(S∪v))
Đơn giản nó được hiểu là khi thêm một đỉnh v vào trong tập S, kết quả sẽ làm
tăng độ lan truyền khi thêm đỉnh v lớn hơn nếu S nhỏ. CELF giúp chúng ta trong việc
Khởi tạo tập S = ∅ và R = 2000
For i = 1 to k do
For mỗi đỉnh v ∈ V \ S do
Sv = 0.
For i = 1 to R do
Sv += |RanCas(S ∪ v ) |
End for
S = S ∪ \argmax v V S vS
End for
Đầu ra tập nguồn S.
16
không cần đánh giá lại độ lan truyền của các nút ở các vòng trước, giảm số nút cần
đánh giá ở vòng lặp tại.
c) Thuật toán NewGreedyIC.
Trong IC , hàm RanCas(S) hoạt động như sau. Ai là tập các cạnh đã được active
tại vòng thứ i, A0=S.Với mỗi cạnh uv∈ E, u ∈ Ai , v không thuộc Ai ,v được active bởi
u ở vòng thứ i+1 với p gọi là xác suất lan truyền. Nói cách khác, l tập hàng xóm của v
ở vòng Ai,v∈ Ai+1 với xác suất 1-(1-p)l, kết thúc khi Ai+1 rỗng.
Chú ý là hàm ngẫu nhiên RanCas(S), với mỗi cạnh uv được xác định, thì ảnh
hưởng từ u đến v, và từ v đến u là như nhau. Vì vậy, để xác định xem cạnh uv có dùng
để lan truyền ảnh hưởng hay không, chúng ta chỉ cần loại bỏ tất cả các cạnh không lan
truyền từ G để tạo ra một đồ thị mới G’. Với việc làm này, hàm RanCas(S) chỉ đơn
giản là tập hợp các tập từ S trong đồ thị G’.
Đánh giá độ phức tạp của thuật toán này là O(kRm) với R là số vòng lặp thuật
toán. Vì vậy để nâng cao thuật toán 2 này, người ta đã đề xuất một thuật toán mới là
NewGreedyIC. So sánh thuật toán NewGreedyIC với thuật toán tối ưu CELF, có một
sự cân bằng trong thời gian chạy.
Bảng 2-3 : Thuật toán NewGreedyIC
Khởi tạo tập S = và R = 20000
For i =1 to k do
Tập sv = 0 với tất cả v V\S
For i =1 to R do
Tính toán G’ bằng cách bỏ từng cạnh từ G với xác suất 1-p
Tính toán RG’(S)
Tính |RG’(v)| với tất cả v V
For từng đỉnh v V\S do
If v RG’ (S) then
End for
End for
Set sv = sv/R với tất cả v V\S
S argmaxvssv
End for
Kết quả đầu ra tập S
17
Vòng đầu tiên của CELF thì nó cũng chạy chậm như thuật toán gốc. Tuy nhiên
bắt đầu từ vòng thứ 2, nếu dùng CELF cúng ta chỉ cần tìm thêm một số lượng nhỏ các
đỉnh và các hàm RanCas(S) thường dừng ngay để tiếp tục với phần khác của đồ thị.
Ngược lại, trong mỗi vòng của thuật toán NewGreedyIc chúng ta cần phải đi qua toàn
bộ đồ thị R một lần để tạo ra các R ngẫu nhiên từ đồ thị G’. Để giải quyết vấn đề này,
Wei Chen và cộng sự [1] đề xuất thuật toán MixGreedyIC, đó là vòng đầu tiên sẽ sử
dụng thuật toán NewGreedyIC và các vòng tiếp theo sẽ sử dụng giải thuật tối ưu
CELE để lựa chọn các điểm làm hạt nhân còn lại.
d) Thuật toán NewGreedyWC.
Cho dv là bậc của v trong đồ thị G, và uv là môt cạnh trong G. Trong WC, nếu
đỉnh u active trong vòng i, khi đó với xác suất 1/dv, v active bởi u trong vòng i+1.
Giống như trong IC, mỗi hàng xóm active độc lập với v. Vì vậy nếu có l hàng xóm
quanh v, thì xác suất v active trong vòng i+1 là 1-(1-1/dv)l.
Điểm khác nhau chính của hàm RanCas(S) của WC so với IC là xác suất u active
v và v active u là khác nhau. Bởi vì điều này, chúng ta có thể xây dựng một đồ thị có
hướng G
= ( V, E
), trong đó mỗi cạnh uv E
được thay thế bằng 2 cạnh có hướng uv
và vu , vẫn sử dụng dv để biểu thị bậc của v trong đồ thị ban đầu.
Xem xét quá trình ngẫu nhiên như sau : Đỗi với mỗi cạnh uv E
, loại bỏ nó
khỏi G
với xác suất 1-1/dv . Hàm RanWC( G
) biểu thị quá trình ngẫu nhiên này và G’
= RanWC( G
) biểu thị kết quả của đồ thị có hướng. Vì vậy, đầu ra của tầng ngẫu nhiên
quá trình RanCas(S) trong mô hình WC giống như 'GR , tập các đỉnh có thể truy cập
trong G’ từ S.
Sử dụng ý tưởng giống như trong mô hình IC, mỗi vòng của thuật toán chúng ta
sẽ chọn một đỉnh để thêm vào tập S đã tồn tại, R phát sinh ngẫu nhiên bởi hàm ngẫu
nhiên G’ RanWC( G
). Với mỗi đỉnh v và đồ thị G’, cần tính toán '| ( ) |G
R S v và sau
đó tính trung bình tất cả G’ để có được ảnh hưởng lan truyền của S v và lựa chọn v
nhằm tối ưu hóa giá trị này.
Điểm khác nhau giữa IC và WC còn là độ phức tạp trong việc tính toán
'| ( ) |G
R S v cho tất cả đỉnh v , trong IC, có O(kRm) là tổng độ phức tạp trong đồ thị
không hướng G’. Trong WC, thì G’- là đồ thị có hướng nên độ phức tạp tạo là
O(kRTm), ở đó T là số lần lặp của thuật toán Cohen [13] – thuật toán này để ước
lượng số tất cả các đỉnh có thể truy cập từ mỗi đỉnh.Thuật toán này có thể giải thích
ngắn gọn thuật toán Cohen trong việc tính toán '| ( ) |G
R S v cho tất cả các đỉnh v
V\S. Cho một đồ thị có hướng G’, bước đầu tiên là duyệt qua đồ thị một lần, tính toán
tất cả các thành phần kết nối mạng của G’, và thu gọn mỗi thành phần liên thông mạnh
vào một đỉnh với trọng số là kích thước của các thành phần kết nối mạnh . Cho đồ th
18
'*G biểu thị kết quả đồ thị có hướng mạch thẳng (DAG), và tập đỉnh V* của '*G . Với
bất kì v V, cho v* tương ứng với đỉnh trong V*. Cho S* = v* V* | v S và cho
Bảng 2-4 : Thuật toán NewGreedyWC
2.2.2. Thuật toán DegreeDiscountIC.
Các thuật toán NewGreedyIC và NewGreedyWC đã được cải tiến, nhưng thời
gian chạy của chúng vẫn lớn và không khả dụng trong một mạng xã hội lớn.Một
phương pháp được đề xuất, dựa trên việc ước lượng ảnh hưởng của các nút trong mạng
xã hội.
Khởi tạo tập S = , R =20000, T = 5
For i = 0 to k do
Khởi tạo sv = 0 cho tất cả các đỉnh
For j to R do
Thu được G’ = RanWC(G)
Tính toán DAG G’* và trọng số w(v*) cho tất cả các đỉnh v* V*
For l = 1 to T do
For từng v* V*, tạo ra giá trị ngẫu nhiên *
t
vX từ phân phối mũ
với nghĩa 1/w(v*)
For từng v* V*, tính toán *
t
vY = * * * *'* ( )
minG
l
u R S v vX
For từng v* V*, s *
l
v+=Y *
l
v
End for
Set sv = sv/R for all v V\S
S = \argmax v V S vS S s
End for
Output S
19
Degree thường sử dụng việc chọn các hạt nhân để lan truyền tối đa. Kết quả thực
nghiệ cho thấy, viêc lựa chọn các đỉnh của Degree áp dụng được với các mạng lớn hơn
với các phương pháp khác.
Wei Chen và cộng sự [1] đã đề xuất DegreeDiscount, kết hợp với thuật toán
Greedy IC, trong khi vẫn cải tiến phương pháp Degree.
Ý tưởng của thuật toán như sau : v là một hàng xóm của đỉnh u. Nếu u được chọn
làm hạt nhân, khi đó quan tâm xem v là nhân hay không dựa vào bậc của nó. Vì vậy,
chúng ta giảm bậc của v đi 1 (tức là không tính cạnh vu). Cũng giảm bậc của v nếu
như hàng xóm nào đó của nó cũng là hạt nhân. Đây là dựa giảm bậc dựa trên kinh
nghiệm có thể áp dụng cho cả IC và WC, được gọi là SingleDiscount.
Với IC, với một xác suất lan truyền nhỏ p, các tác giả lấy được để phân tích để
việc giảm bậc chính xác hơn. Vì v là một hàng xóm của u được lựa chọn vào bộ
“nhân”, với xác suất p, v sẽ bị ảnh hưởng bởi u, trong trường hợp đó không cần phải
chọn v trong tập nhân nữa. Đó là lý do tại sao tiếp tục giảm bậc. Khi p nhỏ, có thể bỏ
qua việc ảnh hưởng gián tiếp của v tới các láng giềng khác, tập trung vào việc ảnh
hưởng trực tiếp của v đến các láng giềng. Đây chính là ý tưởng của thuật toán
DegreeDiscountIC.
Cho N (v) =v∪ w∈V| wv ∈ E, và gọi nó là hàng xóm trực tiếp của v. Cho
Star (v) là đồ thị con với N(v) là các đỉnh và cạnh gắn liền với v. Tính toán việc gia
tăng độ ảnh hưởng của v tới đồ thị con Star(v) từ sự giảm bậc. Cho tv là số hàng xóm
của đỉnh v thực sự được chọn làm nhân.
Định lý 6: Trong IC, với xác suất lan truyền p, giả sử dv=O(1/p) và tv=o(1/p) cho
một đỉnh v. Số đỉnh dự định thêm vào trong đồ thị con Star(v) bị ảnh hưởng bởi v
trong tập nhân là :
1 ( 2 ( ) ( )).v v v v v vd t d t t p o t p
Cài đặt thuật toán DegreeDiscountIC :
20
Bảng 2- 5 : Thuật toán DegreeDiscountIC
Thuật toán DegreeDiscount chính là phương pháp giảm bậc. Sử dụng Fibonaci,
thời gian chạy của thuậ toán là O(klogn + m). Vì vậy, về mặt lý thuyết chúng ta có thể
thấy, phương pháp giảm bậc là nhanh hơn nhiều so với các thuật toán Greedy ban đầu.
Khởi tạo S =
For từng đỉnh v do
Tính toán giảm bậc dv
ddv = dv
Khởi tạo tv to 0
End for
for i =1 to k do
select u = argmaxvddv| v V\S
S = Su
Cho từng hàng xóm v của u và v V\S do
tv = tv + 1
ddv= dv – 2tv – (dv – tv)tvp
end for
end for
Đầu ra là tập S
21
Tóm tắt chương hai
Giới thiệu nghiên các nghiên cứu và các hướng tiếp cận giải quyết bài toán tối ưu
hóa ảnh hưởng của đối tượng : tối ưu hóa ảnh hưởng theo thời gian liên tục trên mạng
khuếch tán, tối ưu hóa ảnh hưởng của đối tượng dựa trên việc cải tiến thuật toán tham
ăn Greedy và thuật toán giảm bậc dựa trên kinh nghiệm DegreeDisount : kết hợp
Greedy với CELF, kết hợp DegreeDiscount với Greedy IC…Chương này tập trung
vào việc giới thiệu tối ưu ảnh hưởng của đối tượng dựa trên phương giảm bậc dựa trên
kinh nghiệm DegreeDiscountIC do Wei Chen và cộng sự [1] đề xuất. Đây là cơ sở
phương pháp luận quan trọng để khóa luận đưa ra mô hình thực nghiệm được các tác
giả xây dựng.
22
Chương 3. Phương pháp tối ưu hóa ảnh hưởng của
đối tượng - DegreeDiscountIC.
Trên cơ sở phân tích các hướng tiếp cận giải quyết bài toán tối ưu ảnh hưởng đối
tượng trên mạng xã hội, khóa luận đã lựa chọn phương pháp tối ưu ảnh hưởng dựa trên
việc giảm bậc dựa trên kinh nghiệm – giải thuật DegreeDiscountIC [1] để giải quyết
bài toán.
3.1. Mô tả bài toán giảm bậc dựa trên kinh nghiệm DegreeDiscount.
Bài toán tối ưu ảnh hưởng của đối tượng trên mạng xã hội đã được Wei Chen [1]
phát biểu như ở chương 1, trong trường hợp này có thể được viết lại như sau:
Đầu vào :
Tập dữ liệu D : danh sách tác giả và đồng tác giả, mỗi cặp tác giả - đồng tác giả
tạo thành 1 cặp quan hệ (đỉnh và hàng xóm của đỉnh)
Đầu ra :
Một tập S có k nút nhân (có ảnh hưởng lan truyền lớn nhất).
Mô hình trích tối ưu ảnh hưởng gồm 2 giai đoạn chính đó là :
- Giai đoạn xây dựng tập dữ liệu
- Giai đoạn áp dụng thuật toán
3.2. Mô hình đề xuất.
Qua quá trình khảo sát một số hướng tiếp cận giải quyết và dựa vào các ưu nhược
điểm điều kiện thực tế về kỹ thuật xử lý ngôn ngữ tự nhiên, tài nguyên ngôn ngữ học,
cũng như các kỹ thuật học máy phục vụ cho quá trình xử lý, khóa luận trình bày mô
hình thực nghiệm phương pháp tối ưu ảnh hưởng của đối tượng dựa trên phương pháp
DegreeDiscountIC do Wei Chen và cộng sự đề xuất [1]. Dưới đây là mô hình đề xuất.
23
Hình 8 : Mô hình đề xuất.
- Bước 1 : Xử lý dữ liệu
Bước này sẽ thực hiện việc phân tích dữ liệu ở file khi crawler được về
từ mạng xã hội.
Sau đó lấy tên tác giả ( kể cả những người đồng tác giả )
- Bước 2 : Tạo ra các cạnh từ các đỉnh
Tạo ra các cạnh :
o Gán cho mỗi tên tác giả thu được ở bước 1, một số ID khác
nhau.
Mạng xã hội (file
html)
Xử lý dữ liệu
Parser file
html
Tách lấy tên
tác giả
Tạo ra các cạnh
từ các cặp đỉnh
Gán cho mỗi
tên tác giả
một ID
Tạo ra cạnh
(cặp số
nguyên ID)
Đồ thị G
Thuật toán
DegreeDiscountIC
Tập nguồn S
24
o Tạo ra tất cả các cạnh từ ID đó ( cặp số nguyên ID)
Xây dựng đồ thị G : Kết nối nhiều cạnh với nhau.
- Bước 3 : Cài đặt thuật toán DegreeDiscountIC
Từ đồ thị sinh ra được G, biết được các cặp ( đỉnh, hàng xóm của
đỉnh) tức là (tác giả, đồng tác giả).
Áp dụng thuật toán DegreeDiscountIC do Wei Chen và cộng sự đề
xuất [1]
o Ý tưởng chung :
Nếu v là hàng xóm của u
Nếu u là nhân, xem xét v là nhân hay không dựa vào bậc của
nó. Giảm bậc của v đi 1 ( tức là không tính cạnh vu)
Cũng giảm bậc của v nếu như hàng xóm nào đó của nó cung là
nhân.
o Nếu v là hàng xóm của u với xác suất nhỏ nhất là p,u S
v bị ảnh hưởng bởi u thì không chọn v là nhân.
Khi p nhỏ, bỏ qua những ảnh hưởng gián tiếp của v tới những
“hàng xóm xa” mà tập trung vào những hàng xóm trực tiếp →
quản lý được việc tính toán giảm bậc.
Tập nhân S bao gồm tập các nút có khả năng lan truyền ảnh hưởng
tốt nhất.
25
Tóm tắt chương 3
Trên cơ sở phân tích dựa vào miền dữ liệu, khóa luận đã lựa chọn thuật toán và
xây dựng mô hình thực , tối ưu ảnh hưởng của đối tượng dựa trên phương pháp giảm
bậc dựa trên kinh nghiệm DegreeDiscountIC để giải quyết bài toán này.
Do hạn chế về mặt thời gian và kiến thức, nên chúng tôi mới tiến hành thực
nghiệm được trên một thuật toán này mà chưa thể tiến hành trên các nghiên cứu liên
quan để đưa ra những so sánh thích hợp nhất.
Chúng tôi tiến hành thực nghiệm một mô hình đề xuất.Quá trình thực nghiệm và
kết quả thực nghiệm của mô hình chúng tôi sẽ trình bày ở chương tiếp sau đây.
26
Chương 4.Thực nghiệm và đánh giá kết quả.
4.1. Mô tả thực nghiệm.
Dựa trên mô hình đề xuất ở chương ba, khóa luận tiến hành thực nghiệm để tìm
ra tập nhân gồm 50 nút có ảnh hưởng nhất trong mạng, bên cạnh đó cũng tính thời
gian chạy thực nghiệm. Từ đó thực hiện so sánh kết quả với các phương pháp khác để
đưa ra đánh giá, cho thấy tính đúng đắn của mô hình, cũng như rút ra được những mặt
hạn chế , từ đó xây dựng định hướng nghiên cứu tiếp theo.
Khóa luận tiến hành thực nghiệm theo 3 phần như sau :
Phần 1 : Thực nghiệm tiến hành việc lấy dữ liệu từ trang arXiv.org, phân tích dữ
liệu và lấy được tên các tác giả.
Phần 2: Thực nghiệm tiến hành gán ID cho tên tác giả như hình , gắn cặp các ID
để tạo thành cặp ( đỉnh, hàng xóm của đỉnh).
Phần 3 : Tiến hành cài đặt thuật toán DegreeDiscountIC, với dữ liệu đầu vào là
kết quả đầu ra ở phần 2, và đầu ra là 50 nút “nhân” có ảnh hưởng nhất.
4.2. Dữ liệu thực nghiệm.
4.2.1. Đặc trưng của cơ sở dữ liệu trên trang arXiv.org
Trang arXiv được phát triển bởi Paul Ginsparg (1991) như là một cơ sở dữ liệu
lưu trữ điện tử dạng tiền in ấn (hoặc nháp) của các bài báo khoa học trong các lĩnh vực
toán học, vật lý, khoa học máy tính, sinh học, thống kê và mọi người có thể truy cập
miễn phí. Sự tồn tại của trang Web là một trong những yếu tố tác động dẫn đến sự
chuyển động hiện tại trong việc xuất bản khoa học.Các nhà khoa học thường xuyên tải
lên các bài viết của họ lên arXiv.org để có thể truy cập trên toàn thế giới và đôi khi để
đánh giá trước khi chúng được công bố trên các tạp chí phản biện ngang hàng.
Các thực thể trong arXiv :
Trang web lưu trữ nhiều bài báo báo khoa học, và được chia ra nhiều lĩnh vực
sắp xếp theo thứ tự từ trên xuống dưới gồm : Physics, Mathematics, Computer
Science, Quantitative Biology, Quantitative Finance, Statistics,…
Mỗi lĩnh vực lại được chia ra nhiều miền cụ thể của lĩnh vực đó, chẳng hạn như
trong Physics có High Energy Physic, Mathematical Physics,Nuclear Theory,…
Mức tiếp theo của trang web là người truy cập có thể tìm chính xác bài công bố
của mình theo năm, theo thời gian đăng tải gần nhất, hay theo ngày tháng cụ thể.
27
Tên của của các bài báo đăng tải, tên tác giả bài báo, cùng với số trang bình luận,
số người bình luận chính là mức độ tiếp theo của trang arXiv.
Trên arXiv, một thực thể được liên kết với một trang arXiv khác mô tả liên quan
đến các thực thể theo cách : mỗi thực thể xuất hiện trong trang arXiv này, liên kết tới
trang arXiv mô tả các thông tin liên quan đó. Ví dụ : khi click vào tên tác giả, chuyển
đến một trang trong đó liệt kê tất cả các bài báo khoa học của người này, và những
người đồng tác giả.
Hình 9 : Thông tin trên trang arXiv
Trong lĩnh vực nghiên cứu khoa học hiện nay, số lượng các bài báo được công bố
tăng với tốc độ nhanh chóng. Mặc dù arXiv không có quá trình phản biện ngang hàng,
nó có một nhóm giám khảo cho mỗi lĩnh vực để giám sát các bài viết được tải lên và
họ có thể sửa đổi thể loại các bài viết mà họ cho là lạc đề. Phần lớn bài viết được đưa
vào arXiv cũng đã được xuất bản trong các báo chí khoa học chuyên ngàng, tuy nhiên
có một số công trình, kể cả những công trình có ảnh hưởng lớn, chỉ xuất bản ở dạng
điện tử và chưa bao giờ được xuất bản trong các báo chí khoa học. Theo thống kê, đến
cuối năm 2008, arXiv.org vượt qua mốc lưu trữ nửa triệu bà báo, với gần 5000 bản
điện tử được thêm vào hàng tháng [11].
28
arXiv cung cấp các mục phân loại, sắp xếp dữ liệu cho phép liên kết từ các trang
tới các mục phân loại tương ứng. Một trang có thể liên kết với nhiều mục. Mỗi bài báo
được công bố trên arXiv, có một trang riêng, bao gồm tiêu đề, tên tác giả và đồng tác
giả, tóm tắt ngắn gọn về nội dung bài công bố, và cung cấp số trang, số hình ảnh, số
bảng biểu của bài. Một số từ chính được coi là từ khóa của bài công bố đó, arXiv cung
cấp tiện ích giúp người truy cập có thể tải về bài đăng hoàn chỉnh theo nhiều định dạng
khác nhau.
Với số lượng danh sách các nghiên cứu được đăng tải và danh sách tên các tác
giả, chúng tôi nhận thấy arXiv là cơ sở dữ liệu phục vụ tốt cho việc tối ưu ảnh hưởng
của đối tượng trên mạng. arXiv được phát triển từ một thực nghiệm nhỏ cho dịch vụ
Web Server cho cộng đồng nghiên cứu khoa học. Việc lấy dữ liệu từ trang arXiv được
lưu trữ trong các file html, vấn đề đặt ra là trích chọn được dữ liệu bao gồm tên tác giả,
và đồng tác giả của bài báo, từ đó tìm ra được quan hệ giữa họ qua những công bố
chung, để phục vụ cho dữ liệu bài toán.
4.2.2. Xây dựng tập dữ liệu.
Mô hình thu thập dữ liệu :
Hình 10 : Quá trình xây dựng tập dữ liệu
Parser
arXiv.html
Name
Author
29
Với mỗi bản ghi trong dữ liệu crawler được từ trang arXiv.org , có dạng file html
và có cấu trúc tương tự như bản dưới :
Hình 11 : Cấu trúc một bản ghi trong arXiv.html
Sau khi tiến hành parse arXiv.html ( phân tích cú pháp của file html), chúng tôi
thu được tập dữ liệu dùng làm đầu vào cho bài toán : danh sách các tác giả (author),
cung cấp cho mỗi tên tác giả một ID, sau đó tạo ra tất cả các cạnh dựa vào quan hệ
đồng tác giả ( cặp số nguyên ID).
30
4.3. Thực nghiệm
4.3.1. Môi trường thực nghiệm
a) Cấu hình phần cứng
Bảng 4-1: Cấu hình phần cứng
Thành phần Chỉ số
CPU Intel Core i3 2.27Ghz
RAM 2G
HDD 320G
OS Window 8 - 32 bit
b) Công cụ phần mềm
Bảng 4-2: Công cụ phần mềm
STT Tên phần mềm Tác giả Nguồn
1 Cygwin http://cygwin.com/install.html
4.3.2. Mô tả cài đặt chương trình
Xây dựng tập dữ liệu trên arXiv.html
Chúng tôi cài đặt chương trình Grab.cpp để tải các dữ liệu từ trang arXiv.org về
dưới dạng các file html. Grab.cpp sử dụng một lệnh hệ thống “-wget” để lấy các trang
từ internet. Trên windows, chúng ta có thể chạy chương trình này dưới Cygwin hoặc
cài đặ một cửa sổ phiên bản “wget”.
Trong dữ liệu, chúng tôi quan tâm tới tên của tác giả. Chúng tôi xem mỗi bài
nghiên được đăng đi kèm theo là một danh sách các tác giả. Các thông tin khác như :
số trang , tên tiêu đề, năm xuất bản,…có thể bỏ qua
31
Cấu trúc của mỗi bản ghi trong arXiv được miêu tả :
Bảng 4-3 : Phân tích bản ghi trong arXiv.html
Việc phân tích các bản ghi html để lấy được dữ liệu đầu vào cho thuật toán được
cài đặt trong project crawler, có nhiệm vụ lậy tên tác giả, gán ID và tạo ra các cạnh (
các cặp ID)
<span class="descriptor">Title:</span> Instantons, Euclidean
supersymmetry and Wick rotations
</div>
<div class="list-authors">
<span class="descriptor">Authors:</span>
<a href="/find/hep-th/1/au:+Belitsky_A/0/1/0/all/0/1">A.V.
Belitsky</a>,
<a href="/find/hep-th/1/au:+Vandoren_S/0/1/0/all/0/1">S.
Vandoren</a>,
<a href="/find/hep-th/1/au:+Nieuwenhuizen_P/0/1/0/all/0/1">P.
van Nieuwenhuizen</a>
</div>
<div class="list-comments">
<span class="descriptor">Comments:</span> 8 pages, LaTeX, typos
fixed
</div>
<div class="list-journal-ref">
<span class="descriptor">Journal-ref:</span> Phys.Lett. B477
(2000) 335-340
</div>
<div class="list-subjects">
<span class="descriptor">Subjects:</span><span class="primary-
subject">High Energy Physics - Theory (hep-th)</span>
32
Hình 12 : Bộ phân tích cú pháp arXiv.html
Chương trình Namelist.cpp có nhiệm vụ trích lấy tên của các tác giả trong file
html từ thẻ <span class=\"descriptor\">Authors:</span>, sau đó gán cho mỗi tên một
ID, cho đầu ra là file namelist.txt.
Bản ghi của namelist.txt có dạng như sau
Bảng 4-4 : Bản ghi tên tác giả sau khi gán ID
Sau đó bản ghi namelist.txt sẽ trở thành đầu vào edges. Chương trình này có
nhiệm vụ là tạo ra các cạnh bằng cách ghép cặp các ID, đầu ra chính là dữ liệu cuối
/find/hep-th/1/au:+Horne_J/0/1/0/all/0/1
/find/hep-th/1/au:+Horowitz_G/0/1/0/all/0/1
/find/hep-th/1/au:+Huitu_K/0/1/0/all/0/1
/find/hep-th/1/au:+Nemeschansky_D/0/1/0/all/0/1
/find/hep-th/1/au:+Ooguri_H/0/1/0/all/0/1
/find/hep-th/1/au:+Sasakura_N/0/1/0/all/0/1
/find/hep-th/1/au:+LeCLair_A/0/1/0/all/0/1
/find/hep-th/1/au:+Smirnov_F/0/1/0/all/0/1
/find/hep-th/1/au:+Sonnenschein_J/0/1/0/all/0/1
/find/hep-th/1/au:+Yankielowicz_S/0/1/0/all/0/1
/find/hep-th/1/au:+Lerche_W/0/1/0/all/0/1
33
cùng mà chương trình sử dụng . Dữ liệu đó được lưu tại file edges.txt, bản ghi có dạng
như sau :
Hình 13 : Dữ liệu đầu vào của thuật toán
File dữ liệu đầu vào có thể được mô tả như sau :
Dòng 1 :
Hai số nguyên n và m trong đó n là số nút trong đồ thị, tất cả các nút được đánh
số từ 0 đến n-1, và m là số cạnh, nhiều cạnh giữa cùng một cặp của các nút được tính
cho nhiều hơn một lần.
Dòng 2 đến m+1:
Có m dòng.Mỗi dòng chứa 2 số nguyên, đại diện cho hai đỉnh được kết nối thành
một cạnh.Như đã đề cập ở trên, nếu có hai hoặc nhiều cạnh giữa cùng một cặp nút, id
của chúng sẽ xuất hiện cùng nhau nhiều hơn một lần.
Như vậy, sau khi xử lý dữ liệu, chúng tôi xây dựng được đồ thị G với các đỉnh là
danh sách các tác giả, mỗi cạnh là đường liên kết giữa tác giả này với tác giả khác.
34
Tiếp đến, sẽ sử dụng dữ liệu của đồ thị G, tiến hành xử lý và tìm ra tập nút có ảnh
hưởng nhất.
Cài đặt thuật toán DegreeDiscountIC.
Thuật toán được cài đặt chính ở file degreediscount_ic.cpp và được cài đặt cùng
với thư viện degreediscount_ic.h. Ngoài ra còn sử dụng các thư viện limit.h, thư viện
này dùng để khai báo một số tham số như tổng số đỉnh, tổng số cạnh, tổng số nút tập
cần lấy cho tập nhân S,... và hàm graph.cpp, thư viện graph.h dùng để đọc dữ liệu đầu
vào từ đồ thị, khai báo các phương thức để kết nối các cạnh với nhau, tạo thành đồ thị
G, làm đầu vào cho thuật toán.
Ở file Degreediscount_ic.cpp có 3 hàm chính : hàm Build( double ratio), hàm
BuildFromFile() và GetNode(int i).
- Hàm Build (double ratio) : hàm này duyệt qua tất cả đồ thị G, và làm hàm
chính cài đặt thuật toán DegreeDiscountIC như đã nói ở phần 2.5
- Hàm BuildFromFile() : hàm này dùng để ghi kết quả từ file
- Hàm GetNote(int i)
Các hàm liên quan được gọi bởi hàm main, ngoài ra còn có toSimulate() hàm
tính toán thời gian chạy của thuật toán để tính toán thời gian chạy của thuật toán, từ đó
có kết quả để so sánh ưu điểm của thuật toán so với các thuật toán khác.
Kết quả chạy hàm main cho ta được file kết quả IC_DiscountIC.txt, gồm 50 nút
có ảnh hưởng nhất trên mạng và file time_degreediscount_ic.txt cho ta biết được thời
gian chạy của thuật toán với đầu vào đã dùng.
Kết quả thực nghiệm cài đặt thuật toán DegreeDiscountIC.
Kết quả được cho ở file đầu ra degreediscount_ic.txt, với ID của các nút “nhân”,
theo thứ tự có khả năng lan truyền ảnh hưởng tốt nhất, bản ghi có dạng như sau :
35
Hình 14 : ID của tập các nút “nhân” có ảnh hưởng nhất và bậc của chúng.
Bên cạnh đó, thời gian chạy của thuật toán cũng được tính toán và cho kết quả ở
file đầu ra time_degreediscount_ic.txt, và thời gian chạy của thuật toán rất ngắn, chỉ là
0.182666 s .
4.4. Đánh giá kết quả
Trích xuất từ hai lĩnh vực khoa học khác nhau trên trang arXiv.org, mỗi nút trong
mạng biểu thị cho một tác giả, số cạnh giữa các cặp nút là số bài báo mà 2 tác giả cộng
tác. Dữ liệu được lấy từ “High Energy Physics-Theory” và chọn lựa từ các bài váo từ
năm 1991 đến năm 2003 với hơn 50 000 nút và gần 300 000 cạnh.
36
Thực hiện thực nghiệm của thuật toán và so sánh với kết quả thực nghiệm của
Wei Chen [1] và các cộng sự đã thực hiện, thấy có kết quả trùng khớp với thuật toán
DegreeDiscountIC và so sánh với các thuật toán khác mà các tác giả đã cài đặt thấy
rằng :
Thuật toán toán CELFGreedy cho kết quả tốt nhất, sau đó là thuật toán
Distance,Random cho kết quả tệ nhất( là phương pháp đơn giản chọn một các đỉnh có
bậc nhỏ nhất và đường đi từ nó đến các đỉnh khác là nhỏ nhất) . Tuy không cho kết
quả tốt nhất như CELFGreedy, nhưng thuật toán DegreeDiscount lại kết hợp được ưu
điểm đó là thời gian chạy rất thấp và kết quả cũng tốt hơn rất nhiều so với các thuật
toán Distance,Random. Dựa vào kết quả thực nghiệm đã thực hiện, so sánh với kết quả
thực nghiệm mà các tác giả đã làm, ta có thể vẽ đồ thị so sánh kết quả như sau :
Hình 15 : Lan truyền ảnh hưởng của các thuật toán khác nhau trên hợp tác mạng
arXiv.org với IC
0
20
40
60
80
100
120
140
160
1 6 11 16 21 26 31 36 41 46
infl
uen
ce s
pre
ad
seed set size
DegreeDiscountIC
Greedy
MixedGreedyIC
NewGreedyIC
SingleDiscount
Degree
Distance
Random
37
DegreeDiscount và SingleDiscount rất nhanh, chỉ mất vài phần nghìn giâu là kết
thúc, nhanh gấp khoảng 6 lần các thuật toán Greedy thông thường. Distance có thời
gian chạy rất tồi tệ, nó cho thấy nó không phải là giải thuật tốt để tính toán độ lan
truyền.
Thời gian chạy của NewGreedyIC và DegreeDiscountIC là không bị ảnh hưởng
nhiều vởi biến xác suất lan truyền p.
Hình 16 : Thời gian chạy của các thuật toán khác nhau
Nhìn trên đồ thi ta thấy, SingDiscount là thuật toán chạy nhanh nhất, nhanh gấp
khoảng 6 lần các thuật toán Greedy đơn thuần.
Giải thuật DegreeDiscountIC cho kết quả rất khả quan: không những thời gian
chạy ít mà dộ lan truyền cũng tốt. Single Discount cũng cho kết quả tốt, tốt hơn so với
Distance và Degree.
Dựa trên cơ sở đó, chúng ta có những ý tưởng để cài đặt các thuật toán tối đa ảnh
hưởng.Khi muốn thời gian chạy ngắn chúng ta có thể chọn SingleDiscount và
DegreeDiscountIC. DegreeDiscountIC luôn luôn biểu diện tốc độ lan truyền tốt, còn
SingleDiscount thì lại áp dụng cho phạm vi rộng cho tất cả các mô hình. Khi không lấy
2909.55 3031.13 2121.63
0.003944490.00129652
2092.87
0.001020910.00054689
0.0001
0.001
0.01
0.1
1
10
100
1000
10000
run
nin
g t
ime
(in
sec
)
38
yếu tố thời gian làm yếu tố chính, nhưng vẫn đảm bảo độ lan truyền là cốt yếu, chúng
ta có thể chọn thuật toán MixedGreedy và MixedGreedyWC.
4.5. Nhận xét
Bước đầu thực nghiệm phần xử lý dữ liệu để tìm được các đối tượng có lan
truyền ảnh hưởng tốt nhất trong số những tác giả bài nghiên cứu khoa học cho kết quả
tương đối khả quan. Tuy nhiên vẫn còn nhiều trường hợp nhập nhằng và do số lượng
dữ liệu rất lớn nên sử dụng kỹ thuật tìm kiếm, kết quả trả về là chưa tối ưu và chặt chẽ.
Nhưng chúng tôi nhận thấy, dữ liệu có thể được dùng để tiếp tục xử lý cho các thuật
toán khác, những thuật toán tốt cả cho kết quả tốt hơn, cũng như thời gian chạy ít hơn
thuật toán mà chúng tôi đã dùng.Tuy nhiên hiện tại chúng tôi chưa có điều kiện để
thực nghiệm được.
39
Kết luận
Thông qua nghiên cứu giải pháp tối ưu hóa ảnh hưởng dựa trên thuật toán
DegreeDiscountIC do Wei Chen và cộng sự đề xuất,2009 [1] và được Manuel Gomez
- Rodriguez và Bernhard Scholkopf, 2012 [2], Bo Liu và cộng sự, 2012 [12] phát triển,
khóa luận đưa ra một mô hình lựa chọn tập nhân có ảnh hưởng nhất trên mạng xã hội.
Khóa luận đã đạt được những kết quả sau:
Giới thiệu bài toán tối ưu hóa ảnh hưởng của đối tượng dựa trên mạng xã
hội, động lực, mục đích nghiên cứu của khóa luận.
Trình bày một số hướng tiếp cận của bài toán tối ưu ảnh hưởng của đối
tượng , tập trung vào phương pháp DegreeDiscount trên mô hình IC do
Wei Chen và cộng sự đề xuất [1], được Manuel Gomez – Rodriguez và
Bernhard Scholkopf [2], Bo Liu và cộng sự, 2012 [12] phát triển.
Dựa vào đặc trưng của dữ liệu trên arXiv.org , khóa luận đưa ra mô hình
thực nghiệm đầy đủ cho bài toán.
Khóa luận đã thực hiện cài đặt thực nghiệm theo các bước của mô hình và
thu được tập nhân có ảnh hưởng lớn nhất. Sau khi phân tích và so sánh kết
quả, những đánh giá thu được cho thấy mô hình là khả quan.
Do hạn chế về mặt thời gian và kiến thức, khóa luận còn một số khiếm
khuyết:
Mới chỉ tiến hành thực nghiệm được trên một thuật toán DegreeDiscontIC.
Vì số lượng dữ liệu rất lớn, cho nên việc xử lý và lọc dữ liệu tìm ra được
các nút nhân vẫn chưa thật tối ưu.
Hướng phát triển:
Dự định tiến hành thực nghiệm với những bước phát triển cao hơn mà
Manue Gomez – Rodriguez và Bernhard Scholkopf [2] , Bo Liu và cộng
sự [12] đề xuất.
40
Tài liệu tham khảo
[1] Wei Chen, Yajun Wang, Siyu Yang. Efficient Influence Maximization in
Social Networks.KDD, 2009
[2] Manuel Gomez-Rodriguez, Bernhard Scholkopf. Influence Maximization in
Continuous Time Diffusion Networks, ICML 2012.
[3] P. Domingos, M. Richardson. Mining the network value of customers. In
Proceedings of the 7th ACM SIGKDD Conference on Knowledge Discovery and
Data Mining, pages 57–66, 2001
[4] M. Richardson, P. Domingos. Mining knowledge-sharingsites for viral
marketing. In Proceedings of the 8th ACMSIGKDD Conference on Knowledge
Discovery and DataMining, pages 61–70, 2002
[5] D. Kempe, J. M. Kleinberg, É. Tardos. Maximizing the pread of influence
through a social network. In Proceedings of the 9th ACM SIGKDD Conference
on Knowledge Discovery and Data Mining, pages 137–146, 2003.
[6] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos,J. VanBriesen,N. S.
Glance. Cost effective outbreakdetection in networks. In Proceedings of the 13th
ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages
420–429, 2007
[7] Jacco Wallinga, Peter Teunis. Different Epidemic Curves for Severe Acute
Respiratory Syndrome Reveal Similar Impacts of Control Measures .Received
for publication October 27, 2003; accepted for publication March 29, 2004.
[8] Wei Chen, Chi Wang,Yajun Wang. Scalable Influence Maximization for
Prevalent Viral Marketing in Large Scale Social Networks. KDD'10, July 27,
2010.
[9] Kulkarni, V.G. Shortest paths in networks with exponen-tially distributed
arc lengths. Networks, 16(3):255–274, 1986.
[10] Carlos Castillo, Wei Chen, Laks V.S.Lakshmanan. Imformation and
Influence Spread in Social Networks. KDD’2012 Tutorial, August 12, 2012.
[11] Gwen Glazer. Online Scientific Repository Hits Milestone.ITHACA, N.Y.
October 3, 2008.
[12] Bo Liu, Gao Cong, Dong Xu, Yifeng Zeng. Time Constrained Influence
Maximization in Social Networks.ICDM 2012: 439-448.
[13] E. Cohen. Size-estimation framework with applications to transitive closure
and reachability. J. Comput. Syst. Sci., 55(3):441–453, 1997.