LỜI CẢM ƠN
Luận Văn Thạc Sỹ này được thực hiện tại Trường Đại Học Công Nghệ Thông
Tin TP. Hồ Chí Minh. Để hoàn thành luận văn này, tôi xin tỏ lòng biết ơn sâu sắc
và gửi lời cảm ơn chân thành đến Thầy TS. Ngô Thanh Hùng, đã tận tình hướng
dẫn, giúp đỡ cho tôi trong suốt quá trình thực hiện luận văn tốt nghiệp.
Tôi xin chân thành cảm ơn quý Thầy, Cô trong khoa Khoa học máy tính và
phòng Sau đại học của Trường Đại Học Công Nghệ Thông Tin TP. Hồ Chí Minh đã
tận tình truyền đạt kiến thức, tạo điều kiện thuận lợi về mặt thủ tục cho hoạt động
học tập và thực hiện luận văn của tôi.
Tôi cũng xin gửi lời cảm ơn tới các anh chị và các bạn lớp cao học khóa 8 đã
giúp tôi rất nhiều trong quá trình học tập cũng như hoàn thành luận văn.
Cuối cùng, tôi xin được bày tỏ lòng biết ơn sâu sắc tới gia đình, bạn bè đã luôn
động viên, khích lệ tinh thần để tôi có đủ nghị lực hoàn thành luận văn thạc sỹ.

Huỳnh Thanh Việt


LỜI CAM ĐOAN
Tôi cam đoan các kết quả tìm hiểu đưa ra trong luận văn này dựa trên các kết
quả thu được trong quá trình tìm hiểu của riêng tôi.
Nội dung của luận văn có tham khảo và sử dụng một số thông tin, tài liệu từ
các nguồn sách, tạp chí, website được liệt kê trong danh mục các tài liệu tham khảo.
TP. Hồ Chí Minh, Tháng 06 năm 2016

Huỳnh Thanh Việt


MỤC LỤC
MỤC LỤC .............................................................................................................. 1
DANH MỤC CÁC KÝ TỰ, CHỮ VIẾT TẮT ......................................................... 5

DANH MỤC CÁC BẢNG ...................................................................................... 6
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .................................................................. 8
MỞ ĐẦU .............................................................................................................. 10
Chương 1: TỔNG QUAN ...................................................................................... 15
Chương 2: CƠ SỞ LÝ THUYẾT ........................................................................... 20
2.1 Lý thuyết về truyền thông ----------------------------------------------------------- 20
2.1.1 Truyền thông và quá trình truyền thông ................................................. 20
2.1.2 Các loại truyền thông ............................................................................. 25
2.1.3 Mô hình truyền thông hai giai đoạn ....................................................... 28
2.1.4 Truyền thông trong cộng đồng ảo .......................................................... 31
2.2 Lý thuyết về Opinion Leader ------------------------------------------------------- 32
2.2.1 Định nghĩa Opinion Leader ................................................................... 32
2.2.2 Xác định Opinion Leader ....................................................................... 34
2.2.3 Mô hình hóa mạng xã hội ...................................................................... 35
2.2.3.1 Mô hình đồ thị mạng xã hội ............................................................ 35
2.2.3.2 Mô hình lan truyền sức ảnh hưởng .................................................. 36
2.2.4 Các phương pháp xác định Key Player/Opinion leader .......................... 37
2.3. Lý thuyết về xử lý đa luồng và xử lý phân tán----------------------------------- 39
2.3.1 Xử lý đa luồng ....................................................................................... 39
2.3.2 Mô hình lập trình phân tán MapReduce ................................................. 40
Chương 3: XÂY DỰNG MÔ HÌNH VÀ GIẢI THUẬT XÁC ĐỊNH KEY
PLAYERS ............................................................................................................. 42

1


3.1 Mô tả bài toán ------------------------------------------------------------------------- 42
3.2 Những giả định của bài toán -------------------------------------------------------- 42
3.2.1 Mô hình đồ thị thông tin ........................................................................ 42
3.2.1.1 Hướng của cạnh .............................................................................. 42

3.2.1.2 Trọng số của cạnh ........................................................................... 42
3.2.2 Mô hình lan truyền độc lập .................................................................... 43
3.2.3 Lựa chọn mô hình cho bài toán .............................................................. 43
3.3 Áp dụng mô hình cho nhóm Facebook -------------------------------------------- 43
3.3.1 Giới thiệu nhóm Facebook, phân tích nhóm Facebook ........................... 43
3.3.2 Phương pháp thu thập dữ liệu từ nhóm Facebook .................................. 45
3.4 Sức ảnh hưởng giữa 2 đỉnh trong đồ thị ------------------------------------------- 48
3.4.1 Sức ảnh hưởng trực tiếp giữa 2 đỉnh ...................................................... 48
3.4.2 Sức ảnh hưởng gián tiếp giữa 2 đỉnh ...................................................... 48
3.4.2.1 Sức ảnh hưởng giữa 2 đỉnh khi chỉ có 1 đường đi nối 2 đỉnh đó ...... 49
3.4.2.2 Sức ảnh hưởng giữa 2 đỉnh khi có 2 đường đi nối 2 đỉnh đó ............ 49
3.4.2.3 Sức ảnh hưởng giữa 2 đỉnh trong trường hợp tổng quát ................... 50
3.4.3 Kiểm chứng công thức tìm sức ảnh hưởng của một đỉnh tới đỉnh khác .. 51
3.5 Phương pháp xác định Opinion leader/Key player ------------------------------ 51
3.5.1 Dựa vào tổng sức ảnh hưởng tới tất cả các đỉnh ..................................... 51
3.5.1.1 Mô tả bài toán ................................................................................. 51
3.5.1.2 Các bước thực hiện thuật toán ......................................................... 51
3.5.2 Dựa vào tổng số đỉnh bị ảnh hưởng của từng đỉnh theo một ngưỡng
(threshold) quan tâm  .................................................................................... 52
3.5.2.1 Mô tả bài toán ................................................................................. 52
3.5.2.2 Các bước thực hiện thuật toán ......................................................... 52
3.6 Xác định sức ảnh hưởng giữa hai đỉnh theo mô hình xử lý đa luồng --------- 53
2


3.6.1 Ý tưởng thực hiện .................................................................................. 53
3.6.2 Mô hình xử lý ........................................................................................ 53
Chương 4: CÀI ĐẶT VÀ THỬ NGHIỆM ............................................................. 55
4.1 Dữ liệu đồ thị thông tin dùng thử nghiệm ----------------------------------------- 55
4.1.1 Dữ liệu đồ thị thông tin tự tạo ................................................................ 55

4.1.1.1 Đồ thị thông tin dạng thẳng ............................................................. 55
4.1.1.2 Đồ thị thông tin chứa các đường đi gián tiếp giao nhau giữa hai đỉnh
................................................................................................................... 55
4.1.1.3 Đồ thị thông tin chứa hai đường đi gián tiếp không giao nhau giữa hai
đỉnh ............................................................................................................ 56
4.1.1.4 Đồ thị thông tin chứa đường đi trực tiếp và hai đường đi gián tiếp
giữa hai đỉnh ............................................................................................... 56
4.1.1.5 Đồ thị thông tin chứa đường đi trực tiếp và nhiều đường đi gián tiếp
giữa hai đỉnh ............................................................................................... 57
4.1.2 Dữ liệu đồ thị thông tin thu thập từ Facebook Group ............................. 57
4.1.2.1 Đồ thị thông tin một nhóm của các lập trình viên Windows Phone
trong chương trình DVLUP tại Việt Nam ................................................... 57
4.1.2.2 Đồ thị thông tin một nhóm chuyên về điện thoại Nokia Lumia ........ 58
4.2 Môi trường cài đặt -------------------------------------------------------------------- 59
4.3 Thử nghiệm --------------------------------------------------------------------------- 59
4.3.1 Kiểm nghiệm công thức tìm sức ảnh hưởng của từng đỉnh tới các đỉnh
khác trong đồ thị bằng mô hình lan truyền ý tưởng ......................................... 59
4.3.1.1 Đồ thị thông tin dạng thẳng ............................................................. 60
4.3.1.2 Đồ thị thông tin chứa các đường đi gián tiếp giao nhau giữa hai đỉnh
................................................................................................................... 67
4.3.1.3 Đồ thị thông tin chứa hai đường đi gián tiếp không giao nhau giữa hai
đỉnh ............................................................................................................ 68
3


4.3.1.4 Đồ thị thông tin chứa đường đi trực tiếp và hai đường đi gián tiếp
giữa hai đỉnh ............................................................................................... 69
4.3.1.5 Đồ thị thông tin chứa đường đi trực tiếp và nhiều đường đi gián tiếp
giữa hai đỉnh ............................................................................................... 70
4.3.2 Xác định Key players dựa theo phương pháp KPP-TI, KPP-NOA và

phương pháp sức ảnh hưởng thông tin ............................................................ 71
4.3.2.1 Dữ liệu đồ thị thông tin tự tạo ......................................................... 72
4.3.2.2 Dữ liệu đồ thị thông tin thu thập từ nhóm Facebook ........................ 75
4.3.4 So sánh các phương pháp xác định Key players/Opinion leaders ........... 78
4.3.4.1 Nhận xét, so sánh các kết quả 2 phương pháp tìm Key players KPPTI, KPP-NOA với phương pháp dựa vào sức ảnh hưởng thông tin ............. 78
4.3.4.2 Nhận xét, so sánh 2 cách tiếp cận xác định Key player trong đề tài . 78
Chương 5: KẾT LUẬN, ƯU ĐIỂM, HẠN CHẾ, HƯỚNG PHÁT TRIỂN ............ 80
5.1 Kết quả --------------------------------------------------------------------------------- 80
5.2 Đóng góp chính của đề tài----------------------------------------------------------- 80
5.3 Ưu điểm-------------------------------------------------------------------------------- 81
5.4 Hạn chế -------------------------------------------------------------------------------- 81
5.5 Hướng phát triển ---------------------------------------------------------------------- 81
TÀI LIỆU THAM KHẢO ..................................................................................... 82
PHỤ LỤC.............................................................................................................. 85

4


DANH MỤC CÁC KÝ TỰ, CHỮ VIẾT TẮT
KPP-TI: Key player Problem – Total Influence
KPP-NOA: Key player Problem – Number Of Affected

5


DANH MỤC CÁC BẢNG
Bảng 3.1 Bảng dữ liệu Available của module thu thập dữ liệu ............................... 45
Bảng 3.2 Bảng dữ liệu Feeds của module thu thập dữ liệu ..................................... 46
Bảng 3.3 Bảng dữ liệu Likes của module thu thập dữ liệu ..................................... 46
Bảng 3.4 Bảng dữ liệu Users của module thu thập dữ liệu ..................................... 46

Bảng 4.1: Kết quả kiểm nghiệm sức ảnh hưởng trực tiếp giữa 2 đỉnh của đồ thị
thông tin dạng thẳng .............................................................................................. 62
Bảng 4.2: Kết quả kiểm nghiệm sức ảnh hưởng giữa 2 đỉnh qua 1 đỉnh trung gian
của đồ thị thông tin dạng thẳng .............................................................................. 64
Bảng 4.3: Kết quả kiểm nghiệm sức ảnh hưởng giữa 2 đỉnh qua 2 đỉnh trung gian
của đồ thị thông tin dạng thẳng .............................................................................. 65
Bảng 4.4: Kết quả kiểm nghiệm sức ảnh hưởng giữa 2 đỉnh qua 3 đỉnh trung gian
của đồ thị thông tin dạng thẳng .............................................................................. 66
Bảng 4.5: Kết quả kiểm nghiệm sức ảnh hưởng giữa 2 đỉnh qua 4 đỉnh trung gian
của đồ thị thông tin dạng thẳng .............................................................................. 67
Bảng 4.6: Kết quả kiểm nghiệm sức ảnh hưởng với đồ thị thông tin chứa các đường
gián tiếp giao nhau ................................................................................................ 68
Bảng 4.7: Kết quả kiểm nghiệm sức ảnh hưởng với đồ thị thông tin chứa hai đường
gián tiếp không giao nhau ...................................................................................... 69
Bảng 4.8: Kết quả kiểm nghiệm sức ảnh hưởng với đồ thị thông tin chứa đường đi
trực tiếp và hai đường gián tiếp ............................................................................. 70
Bảng 4.9: Kết quả kiểm nghiệm sức ảnh hưởng với đồ thị thông tin chứa đường đi
trực tiếp và nhiều đường gián tiếp.......................................................................... 71
Bảng 4.10: Kết quả các đỉnh Key Players theo 3 phương pháp của đồ thị thông tin
dạng thẳng ............................................................................................................. 73
Bảng 4.11: Kết quả các đỉnh Key Players theo 3 phương pháp của đồ thị thông tin
chứa các đường đi gián tiếp giao nhau ................................................................... 73

6


Bảng 4.12: Kết quả các đỉnh Key Players theo 3 phương pháp của đồ thị thông tin
chứa hai đường đi gián tiếp không giao nhau ......................................................... 74
Bảng 4.13: Kết quả các đỉnh Key Players theo 3 phương pháp của đồ thị thông tin
chứa đường đi trực tiếp và hai đường đi gián tiếp .................................................. 74

Bảng 4.14: Kết quả các đỉnh Key Players theo 3 phương pháp của đồ thị thông tin
chứa đường đi trực tiếp và nhiều đường đi gián tiếp .............................................. 75
Bảng 4.15: Kết quả các đỉnh Key Players theo 3 phương pháp với ngưỡng KPPNOA bằng 0.4 của đồ thị thông một nhóm của các lập trình viên Windows Phone
trong chương trình DVLUP tại Việt Nam .............................................................. 76
Bảng 4.16: Kết quả các đỉnh Key Players theo 3 phương pháp với ngưỡng KPPNOA bằng 0.7 của đồ thị thông một nhóm của các lập trình viên Windows Phone
trong chương trình DVLUP tại Việt Nam .............................................................. 76
Bảng 4.17: Kết quả các đỉnh Key Players theo 3 phương pháp với ngưỡng của KPPNOA bằng 0.4 của đồ thị thông tin nhóm điện thoại Nokia Lumia ......................... 77
Bảng 4.18: Kết quả các đỉnh Key Players theo 3 phương pháp với ngưỡng của KPPNOA bằng 0.7 của đồ thị thông tin nhóm điện thoại Nokia Lumia ......................... 78

7


DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 2.1: Truyền thông trong đời sống hàng ngày ................................................. 21
Sơ đồ 2.1: Mô hình truyền thông tuyến tính ........................................................... 23
Sơ đồ 2.2: Mô hình truyền thông chu kỳ theo Jakobson [3] ................................... 23
Hình 2.2: Truyền thông liên cá nhân ...................................................................... 26
Hình 2.3: Truyền thông đại chúng ......................................................................... 27
Sơ đồ 2.3: Giả thuyết về quá trình truyền thông hai giai đoạn ................................ 30
Hình 2.4: Opinion Leader trong cộng đồng ............................................................ 33
Hình 2.5: Mô hình đa luồng[1] .............................................................................. 39
Hình 2.6: Minh họa một chương trình đa luồng ứng với các hàm[1] ...................... 39
Hình 2.7: Minh họa không đồng bộ giữa các luồng trên một dữ liệu[12] ............... 40
Hình 2.8: Mô hình lập trình Map-Reduce[2] .......................................................... 41
Hình 2.9: Ba vai trò chính trong thực hiện Map-Reduce[2].................................... 41
Sơ đồ 3.1: Liên kết giữa hai đỉnh (người) trên mạng xã hội ................................... 42
Sơ đồ 3.2: Quan hệ giữa hai người trên mạng xã hội với trọng số .......................... 43
Hình 3.1: Hình ảnh một nhóm Facebook ............................................................... 44
Sơ đồ 3.3 Sơ đồ thu thập dữ liệu từ nhóm Facebook .............................................. 47
Sơ đồ 3.4: Quan hệ ảnh hưởng của 2 đỉnh gián tiếp ............................................... 49

Sơ đồ 3.5: Quan hệ ảnh hưởng của 2 đỉnh có 2 đường đi ....................................... 49
Sơ đồ 3.6: Quan hệ ảnh hưởng của 2 đỉnh có nhiều đường đi ................................ 50
Sơ đồ 3.7: Mô hình xử lý đa luồng tìm sức ảnh hưởng từng đỉnh đến các đỉnh khác
.............................................................................................................................. 54
Hình 4.1: Đồ thị thông tin dạng thẳng .................................................................... 55
Hình 4.2: Đồ thị thông tin chứa các đường đi gián tiếp giao nhau .......................... 55
Hình 4.3: Đồ thị thông tin chứa hai đường đi gián tiếp không giao nhau ................ 56

8


Hình 4.4: Đồ thị thông tin chứa đường đi trực tiếp và hai đường đi gián tiếp ......... 56
Hình 4.5: Đồ thị thông tin chứa đường đi trực tiếp và nhiều đường đi gián tiếp ..... 57
Hình 4.6: Đồ thị thông tin một nhóm của các lập trình viên Windows Phone trong
chương trình DVLUP tại Việt Nam ....................................................................... 58
Hình 4.7: Đồ thị thông tin một nhóm chuyên về điện thoại Nokia Lumia .............. 58
Hình 4.8: Giao diện thực thi chương trình kiểm nghiệm mô hình lan truyền ý tưởng
.............................................................................................................................. 59
Hình 4.9: Giao diện thực thi chương trình tìm Key Players theo Phương pháp KPPTI và KPP-NOA .................................................................................................... 72

9


MỞ ĐẦU
Trong thời đại ngày nay, công nghệ thông tin có tác động vô cùng to lớn đối
với xã hội loài người, nó có mặt trong tất cả các lĩnh vực như kinh tế, giáo dục, y tế,
an ninh quốc phòng,…Tác động của công nghệ thông tin không chỉ góp phần tăng
trưởng kinh tế và còn phát triển tư duy con người. Ngày nay, con người đã sáng tạo
ra nhiều loại máy móc dần dần thay thế công việc của mình, không chỉ thay thế con
người lao động mà còn có thể thay thế con người tư duy. Mọi loại thông tin, số liệu

âm thanh, hình ảnh có thể được đưa về dạng kỹ thuật số để bất kỳ máy tính nào
cũng có thể lưu trữ, xử lý và chuyển tiếp cho nhiều người. Những công cụ và sự kết
nối của thời đại kỹ thuật số cho phép chúng ta dễ dàng thu thập, chia sẻ thông tin và
hành động trên cơ sở những thông tin này theo phương thức hoàn toàn mới, kéo
theo hàng loạt sự thay đổi về các quan niệm, các tập tục, các thói quen truyền thống,
và thậm chí cả cách nhìn các giá trị trong cuộc sống.
Hiện nay, có rất nhiều ứng dụng công nghệ thông tin giúp cho mọi người trên
toàn thế giới có thể trao đổi thông tin với nhau, trong số đó thì mạng xã hội là một
dịch vụ thu hút được số lượng lớn người dùng trên toàn cầu. Mạng xã hội là là dịch
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í, sở thích nào đó, với nhiều mục đích khác nhau, là nơi họ trao đổi thông tin với
nhau, chia sẻ suy nghĩ, ý tưởng mà không bị giới hạn về không gian và thời gian.
Một mạng xã hội có thể đề cập đến nhiều lĩnh vực, hoặc chỉ đề cập đến một lĩnh vực
nhất định nào đó.
Các thành viên trong mạng xã hội sẽ giao tiếp với các thành viên khác trong
mạng, mỗi thành viên sẽ là một thành phần (truyền hoặc nhận) trên luồng thông tin
đang hoạt động của mạng xã hội đó. Để khai thác được tối đa lợi ích từ luồng thông
tin này thì việc phân tích các trang mạng xã hội là cần thiết. Phân tích mạng xã hội
sẽ giúp ta có cái nhìn rõ hơn về mạng xã hội đó, hiểu rõ được luồng thông tin được
lan truyền trên nó cũng như những thành phần quan trọng, có ảnh hưởng lớn đến tất
cả các thành phần còn lại.

10


Phân tích mạng xã hội là dùng các kĩ thuật phân tích, tiến hành trên một mạng
các người dùng tham gia vào mạng xã hội. Phân tích mạng xã hội sẽ giúp ta có cái
nhìn rõ hơn về mạng xã hội đó, hiểu rõ được luồng thông tin được lan truyền trên
nó cũng như những thành phần quan trọng, có ảnh hưởng lớn đến tất cả các thành
phần còn lại, từ đó ta có thể tác động vào luồng thông tin đang hoạt động trên mạng

xã hội theo mục đích cụ thể.
Mục tiêu nghiên cứu
Đề tài “Đề xuất mô hình và thuật toán xác định những người hướng dẫn dư
luận trong các cộng đồng ảo chuyên biệt như Facebook Groups” thực hiện tìm
hiểu mạng xã hội Facebook, thu thập dữ liệu, nghiên cứu xây dựng mô hình dựa
trên mô hình đồ thị thông tin và mô hình lan truyền độc lập; xây dựng công thức
tính sức ảnh hưởng dựa trên mô hình lan truyền độc lập; đề xuất phương pháp xác
định người hướng dẫn dư luận; cài đặt giải thuật xác định người hướng dẫn dư luận
trong một cộng đồng ảo chuyên biệt như Facebook groups.
Đối tượng nghiên cứu
Đề tài nghiên cứu các thuộc tính, đặc trưng của trang mạng xã hội như bài viết
của người dùng đăng trên các trang mạng xã hội, các trạng thái của người dùng với
bài viết của người dùng khác như thích (like). Việc xác định sức ảnh hưởng một
người đến người khác trong mạng dựa vào những thuộc tính này, dựa trên xác suất
lan truyền ý tưởng thành công giữa các thành viên trong nhóm Facebook.
Phạm vi nghiên cứu
Đề tài chỉ tập trung vào việc xác định những người hướng dẫn dư luận trên
một nhóm người dùng trên các diễn đàn Facebook với lĩnh vực/chủ đề nhất định.
Việc xác định dựa vào số lượng bài viết, số lượng thích bài viết. Đề tài chưa xét đến
phản hồi (comments) từ phía người dùng, thành viên, vấn đề này thuộc về nghiên
cứu trong lĩnh vực xử lý ngôn ngữ tự nhiên, trong giới hạn đề tài không đề cập đến.
Đề tài mô hình hóa mạng xã hội, cụ thể là nhóm Facebook dưới dạng đồ thị thông
tin, tập trung vào xác định công thức tính sức ảnh hưởng giữa hai đỉnh dựa trên xác
11


suất lan truyền ý tưởng thành công và đề xuất công thức xác định Keyplayer/
Opinion Leader.
Ý nghĩa khoa học và thực tiễn
Hiện nay có rất nhiều công trình nghiên cứu về Key Player, cùng với một số

nghiên cứu về Opinion Leaders và Influential People. Tuy nhiên, với đề tài “Đề
xuất mô hình và thuật toán xác định những người hướng dẫn dư luận trong các
cộng đồng ảo chuyên biệt như Facebook Groups” thì cần phải xây dựng lại mô
hình mạng xã hội và công thức tìm Opinion Leader/ Key Player cho phù hợp, nên
đề tài sẽ xây dựng lại một mô hình dựa vào mô hình đồ thị thông tin và mô hình lan
truyền độc lập; xây dựng công thức tính sức ảnh hưởng dựa trên xác suất lan truyền
ý tưởng thành công; đề xuất phương pháp xác định Opinion Leader/ Key Player.
Đây là những đóng góp có ý nghĩa khoa học của đề tài.
Xác định được những người hướng dẫn dư luận trong mạng xã hội cũng có ý
nghĩa lớn trong nhiều ứng dụng của thực tiễn cuộc sống, hỗ trợ tích cực cho việc
hoàn thành các mục tiêu, yêu cầu của con người. Đối với mỗi ngành nghề kinh tế có
ý nghĩa quan trọng trong việc quảng cáo, tiếp thị, tư vấn người tiêu dùng… Trong
đời sống xã hội, góp phần giáo dục tư tưởng, tinh thần cho con người, hướng con
người tới những suy nghĩ và hành động đúng đắn.
Nội dung và phương pháp nghiên cứu
Nội dung 1
Tìm hiểu trang mạng xã hội Facebook Groups và thu thập dữ liệu.
Nội dung 2
Mô hình hóa mạng xã hội dựa trên mô hình đồ thị thông tin và mô hình lan
truyền độc lập phục vụ cho bài toán xác định Opinion Leaders/ Key players.

12


Phương pháp
Tìm hiểu và phân tích mô hình của các nghiên cứu có liên quan về việc xác
định Opinion leaders/ Key players, cải tiến/áp dụng hai mô hình đồ thị thông tin và
mô hình lan truyền độc lập phù hợp với bài toán của đề tài.
Nội dung 3
Nghiên cứu các thuật toán xác định những người hướng dẫn dư luận đề xuất

phương pháp xác định Keyplayers/ Opinion Leaders.
Phương pháp
Tìm hiểu các phương pháp xác định Key players. Xây dựng công thức tính
sức ảnh hưởng giữa hai thành viên trong mạng dựa vào xác suất lan truyền ý tưởng
thành công. Từ đó đề xuất hai phương pháp xác định Key players/Opinion Leaders.
Nội dung 4
Cài đặt mô hình, giải thuật. Kiểm nghiệm mô hình và thuật toán xác định
những người hướng dẫn dư luận.
Phương pháp
Cài đặt thuật toán tính sức ảnh hương giữa hai thành viên trong mạng, kiểm
nghiệm bằng mô hình lan truyền ý tưởng; Cài đặt thuật toán cho hai phương pháp
xác định người hướng dẫn dư luận, so sánh các kết quả.
Cấu trúc của báo cáo
-

Chương 1: Tổng quan, trình bày các nghiên cứu có liên quan mật thiết đến
đề tài.

-

Chương 2: Cơ sở lý thuyết, bao gồm các lý thuyết về truyền thông, lý
thuyết về opinion leader, các mô hình mạng xã hội và các phương pháp xác
định Opinion leader/Key player.

-

Chương 3: Xây dựng mô hình bài toán dựa trên mô hình đồ thị thông tin và
mô hình lan truyền độc lập; xây dựng công thức tính sức ảnh hưởng giữa
13



hai thành viên trong mạng; đề xuất hai phương pháp xác định Key players/
Opinion Leader; xây dựng giải thuật cho các công thức;
-

Chương 4: Những mô tả về quá trình cài đặt công thức tính sức ảnh hưởng,
kiểm chứng bằng mô hình lan truyền độc lập; Cài đặt, thử nghiệm hai
phương pháp xác định Key players.

-

Chương 5: Kết luận, những ưu điểm, hạn chế và hướng phát triển của đề
tài.

14


Tổng quan

Chương 1: TỔNG QUAN
Hiện nay, có rất nhiều trang mạng xã hội như Google Plus+, MySpace,
LinkedIn, Twitter, Facebook… Trong số các trang mạng xã hội trên thì Facebook là
trang mạng xã hội thu hút số lượng người dùng nhiều nhất. Tính đến tháng 10 năm
2015, trên toàn thế giới có hơn 1,49 tỷ hàng tháng người sử dụng Facebook đang
hoạt động, 968 triệu người đăng nhập Facebook hàng ngày, có 4,5 tỉ lượt thích được
tạo ra hàng ngày, 300 triệu ảnh được upload hàng ngày. Tại Việt Nam đã có 30 triệu
người dùng Facebook tính đến tháng 6 năm 2015.
Phân tích mạng xã hội là một lĩnh vực nghiên cứu tích cực, có ý nghĩa quan
trọng trong thực tiễn, giúp con người có thể nắm bắt và điều chỉnh được luồng
thông tin phức tạp đang hoạt động liên tục trên cộng đồng [10,11]. Phân tích mạng

xã hội để tìm ra thành phần có ảnh hưởng lớn đến các thành phần còn lại, những
thành phần này được gọi là Key Player [14].
Xác định được Key Player trên mạng xã hội là một nhân tố thuận lợi, giúp ta
có thể khai thác tốt mạng xã hội đó theo những mục đích nhất định[7]. Trong một
số trường hợp key player được hiểu như là những người hướng dẫn dư luận(opinion
leader). Những người này thông qua các phát biểu, bài viết của mình có thể tác
động đến hành vi (mua sắm, suy nghĩ, lựa chọn, bầu cử…) của những người khác.
Có nhiều phương pháp xác định Key players như phương pháp tiếp cận trung
tâm được đưa ra bởi Stephen Borgatti và một phương pháp khác là phương pháp
dựa vào sức ảnh hưởng thông tin.
Nghiên cứu của Stephen Borgatti [14] đã nêu lên hai vấn đề về key player là
KPP-1 (Key player problem-1) và KPP-2:
 KPP-1:với một mạng xã hội, tìm ra một tập k đỉnh, nếu loại bỏ sẽ làm gián
đoạn tối đa việc giao tiếp giữa các nút còn lại. KPP-1 thì thực hiện việc xác
định Key players cho mục đích tối ưu việc lan truyền thông tin qua mạng qua
các đỉnh được chọn làm Key player.
 KPP-2: với một mạng xã hội, tìm ra một tập k đỉnh, mà có kết nối lớn nhất
đến tất cả các nút khác, khi loại bỏ chúng sẽ gây ra sự phân mảnh (đổ vỡ)
15


Tổng quan

thông tin lớn nhất cho những đỉnh còn lại. KPP-2 thực hiện việc xác định
Key players cho mục đích phân mảnh mạng bằng cách loại bỏ các nút trọng
điểm trong mạng.
Phương pháp tiếp cận trung tâm của Borgatti xác định key player dựa vào độ
đo về tính trung tâm của mỗi đỉnh trên mạng, sau đó chọn ra một tập bao gồm k
đỉnh có tính trung tâm nhất. Những đỉnh này là Key players.
Borgatti sử dụng ba độ đo trung tâm của một đỉnh là Betweeness, Degree và

Closeness để giải quyết hai vấn đề về key player là KPP-1 và KPP-2. Trong đó,
Betweenness được dùng cho KPP-1, Degree và Closeness được dùng cho KPP-2.
Giả sử ta có đồ thị G=(V, E) với V là tập đỉnh, E là tập cạnh (liên kết giữa hai đỉnh)
thì độ đo Betweenness, Degree và Closeness của một đỉnh được tính theo công thức
1.1 [14]:
 Betweenness:

CB (v) 

 st (v)
s  v  tV  st



(1.1)

s t

Trong đó:
+ st : số đường đi ngắn nhất giữa đỉnh s và đỉnh t.
+ st(v): số đường đi ngắn nhất giữa đỉnh s và đỉnh t và có đi qua đỉnh v.
Freeman đã định nghĩa độ đo Betweenness là tổng tỷ lệ của đường đi ngắn
nhất từ một đỉnh đến các đỉnh khác qua một đỉnh cho trước[21]. Độ đo Betweenness
của một đỉnh cho thấy vai trò của đỉnh đó trong sự kết nối của những cặp đỉnh khác
với nhau thông qua đường đi tốt nhất. Nếu loại bỏ đỉnh này thì có thể làm cho
những cặp đỉnh còn lại không thể kết nối được với nhau, làm mất tính kết nối đầy
đủ giữa những cặp đỉnh còn lại.
 Mức độ trung tâm dựa trên bậc của đỉnh (Degree centrality). Công thức tính:

CD(v) =


deg(v)
n−1

(1.2)

Trong đó: deg(v) là bậc của đỉnh v.
 Mức độ trung tâm dựa trên độ gần (Closeness centrality) tỷ lệ với tổng
khoảng cách ngắn nhất giữa đỉnh đang xét với từng điểm khác trong mạng.
16


Tổng quan

Công thức tính:
n

CC (i )   dij , i  j

(1.3)

j 1

Với dij là khoảng cách ngắn nhất giữa đỉnh i với đỉnh j.
Closeness của một đỉnh là tổng đường đi ngắn nhất từ đỉnh đó đến tất cả các
đỉnh còn lại trên đồ thị.
Một nghiên cứu của tác giả người Ấn Độ là Mohamed Abdel-Ghany thực hiện
tại ngôi làng Elkordy ở Ai Cập[8]. Tác giả đã tiến hành thu thập dữ liệu từ tất cả
nông dân của làng, bao gồm 72 nông dân thông qua một bảng thăm dò ý kiến. Mỗi
người dân sẽ trả lời tên người mà họ nói với người đó hoặc họ nhận được lời

khuyên từ người đó về vấn đề nông nghiệp và vấn đề chăn nuôi [8]. Từ dữ liệu thu
thập được thông qua bảng thăm dò ý kiến, tác giã đã mô hình hóa thành một đồ thị
G = (V, E), với V là tập đỉnh, E là tập cạnh. Mỗi đỉnh trên đồ thị G sẽ đại diện cho
một người nông dân và mỗi cạnh sẽ biểu diễn sự tương tác giữa hai đỉnh [8]. Sau
khi đã mô hình hóa tập dữ liệu bảng thăm dò ý kiến những người dân trong làng
thành đồ thị G, tác giả đã dùng phương pháp dựa trên 2 vấn đề về Key Players của
Borgatti để tìm ra người có sức ảnh hưởng đến những người dân trong làng
Elkordy.
Phương pháp xác định key player dựa vào cách tiếp cận trung tâm của
Borgatti, đã được hai nhà nghiên cứu người Ấn Độ là Mohamed Sathik và Abdul
Rasheed vận dụng để xác định Key player trên trang blog trực tuyến[9].
Hai tác giả đã phân tích mạng xã hội kết hợp dùng phương pháp tiếp cận trung
tâm để tìm những cá nhân có vai trò quan trọng trên mạng các bài viết (Blog) trực
tuyến. Nhóm tác giả định nghĩa mạng xã hội như là một đồ thị biểu diễn sự tương
tác giữa các cá nhân, bao gồm tập hợp các đỉnh đại diện cho người tham gia, tổ
chức hoặc có thể là nhóm người, tập các cạnh đại diện cho sự liên kết giữa các
đỉnh[9].
Mohamed Sathik và Abdul Rasheed đã sử dụng bộ dữ liệu được thu thập từ
trang blog trực tuyến, bao gồm 146 bài viết được viết bởi 146 bệnh nhân AIDS, với
mỗi bài viết thu thập được còn kèm theo các phản ứng với nó. Từ bộ dữ liệu thu
17


Tổng quan

thập, nhóm tác giả đã xây dựng lên một đồ thị có hướng G=(V, E), với V là tập
đỉnh, mỗi đỉnh đại diện cho từng bài viết, E là tập cạnh biểu diễn cho sự tương tác
giữa hai đỉnh. Cạnh của đồ thị được xây dựng trên cơ sở: nếu có phản ứng j với bài
viết i thì sẽ có một cạnh xuất phát từ i tới j. Bài viết có sức ảnh hưởng là bài viết
được nhiều sự phản hồi ý kiến [9]. Bài viết có sức ảnh hưởng được xác định thông

qua ba độ đo Betweeness, Degree và Closeness.
Một nghiên cứu khác của Ala Berzinji là “Detecting Key Players in Terrorist
Networks” [4], phát hiện nhân tố quan trọng trong mạng lưới khủng bố. Nhóm tác
giả cũng định nghĩa cấu trúc của mạng lưới khủng bố là đồ thị gồm các đỉnh là
những tên khủng bố và cạnh là mối quan hệ của những tên này. Nhóm tác giả sử
dụng phương pháp tìm nhân tố quan trọng dựa vào vai trò trung tâm trong mạng
theo ba độ đo: Degree, Betweenness và Closeness.
Một phương pháp khác xác định key player là dựa vào sức ảnh hưởng thông
tin, được hai tác giả Vito Latora và Massimo Marchiori dùng để tìm ra các thành
phần có sức ảnh hưởng, có tính chất quyết định đến toàn bộ mạng thông tin[17].
Mục đích của nghiên cứu là chống lại bọn tội phạm khủng bố.
Dữ liệu được nhóm tác giả sử dụng là thông tin của những tên tội phạm thực hiện
vụ tấn công vào ngày 11 tháng 9 năm 2001 trên nước Mỹ và những kẻ có liên quan
trực tiếp hoặc gián tiếp đến những tên tội phạm này. Dữ liệu này được mô hình hóa
thành một đồ thị có hướng G = (V, E), với V là tập đỉnh, mỗi đỉnh đại diện cho một
tên tội phạm hoặc một người có liên quan tới tội phạm khủng bố; E là tập cạnh, biểu
diễn cho mối quan hệ giữa hai đỉnh [17].
Để tìm ra người có sức ảnh hưởng lớn, tác giả sử dụng công thức tính sức
ảnh hưởng thông tin của toàn mạng:

E (G) 



i  jG

 ij

N (N 1)




1
1

N (N 1) i  jG dij

(1.4)

Trong đó: N là số đỉnh, ɛij là sức ảnh hưởng thông tin của đỉnh i lên đỉnh j và được
xác định bằng nghịch đảo đường đi ngắn nhất từ i tới j dij.
Để xác định những người có sức ảnh hưởng nhất thì đầu tiên tác giả tính sức ảnh
hưởng thông tin của toàn mạng, sau đó tiến hành loại bỏ từng đỉnh (người) ra khỏi

18


Tổng quan

đồ thị và tính lại sức ảnh hưởng thông tin của mạng sau khi bỏ đỉnh (sức ảnh hưởng
thông tin của từng đỉnh).
Sức ảnh hưởng thông tin của từng đỉnh được xác định như độ lệch giữa sức
ảnh hưởng thông tin của đồ thị G và sức ảnh hưởng thông tin của đồ thị G’, với G’
là đồ thị G sau khi vô hiệu hóa đỉnh đang xét.
Công thức tính sức ảnh hưởng thông tin của đỉnh k:
P(G) – P(Gk)

(1.5)

Trong đó Gk là đồ thị G khi đã vô hiệu hóa đỉnh k.

Những đỉnh có sức ảnh hưởng thông tin cao sẽ được chọn làm key player/opinion
leader.
Trong một bài viết khác của tác giả Ortiz-Arroyo, Discovering Sets of Key
Players in Social Networks [10], nhóm tác giả cũng sử dụng công thức tính sức ảnh
hưởng thông tin để xác định nhân tố quan trọng trong mạng xã hội sử dụng phương
pháp dựa vào sức ảnh hưởng thông tin.


Kết chương
Có nhiều công trình nghiên cứu về key player/opinion leader. Đề tài “Đề xuất

mô hình và thuật toán xác định những người hướng dẫn dư luận trong các cộng
đồng ảo chuyên biệt như Facebook Groups” sẽ xây dựng lại mô hình mạng thông
tin thể hiện được sức ảnh hưởng giữa các đỉnh trong mạng với nhau và xây dựng
công thức tính sức ảnh hưởng giữa hai đỉnh trong mạng, đề xuất hai phương pháp
xác định Key players.

19


Xây dựng mô hình và giải thuật

Chương 2: CƠ SỞ LÝ THUYẾT
Key player được hiểu như là những người có vai trò quan trọng trong cộng
đồng, là những thành phần có vai trò như là trung tâm, liên kết chặt chẽ đến các
thành phần còn lại của toàn mạng. Nếu loại bỏ Key player ra khỏi mạng thì sẽ gây
ra sự phân mảnh mạng. Key player cũng có thể được hiểu như là người có sức ảnh
hưởng đến hành vi, quyết định của người khác thông qua quá trình trao đổi, truyền
đạt thông tin. Key player hiểu theo nghĩa này còn được gọi là những người có sức
ảnh hưởng (Opinion leader), và trong đề tài này sẽ tập trung nghiên cứu về Key

player theo nghĩa này.
Do đó, trong phần cơ sở lý thuyết sẽ không chỉ trình bày về các khái niệm, mô
hình, giải thuật xác định người có sức ảnh hưởng mà còn trình bày về lý thuyết
truyền thông và ảnh hưởng của truyền thông tới hành vi và quyết định của con
người.
2.1 Lý thuyết về truyền thông
2.1.1 Truyền thông và quá trình truyền thông
Truyền thông là quá trình truyền đạt thông tin thông qua trao đổi ý tưởng, cảm
xúc, ý định, thái độ, mong đợi, nhận thức hoặc các lệnh như ngôn ngữ, cử chỉ phi
ngôn ngữ, chữ viết, hành vi hoặc có thể bằng các phương tiện khác như thông qua
điện từ, hoá chất, hiện tượng vật lý và mùi vị [3]. Đó là sự trao đổi có ý nghĩa của
thông tin giữa hai hoặc nhiều thành viên. Truyền thông đòi hỏi phải có một người
gửi, một tin nhắn, một phương tiện truyển tải và người nhận, mặc dù người nhận
không cần phải có mặt hoặc nhận thức về ý định của người gửi để giao tiếp tại thời
điểm việc truyền thông này diễn ra. Do đó, thông tin liên lạc có thể xảy ra trên
những khoảng cách lớn trong thời gian và không gian. Truyền thông yêu cầu các
bên giao tiếp chia sẻ một khu vực dành riêng cho thông tin được truyền tải. Quá
trình giao tiếp được coi là hoàn thành khi người nhận hiểu thông điệp của người
gửi. Truyền thông(communication) có thể nói ngắn gọn là quá trình truyền đạt
thông tin, là một dạng hoạt động căn bản của bất cứ một tổ chức nào mang tính chất
xã hội [3].
Truyền thông đóng vai trò rất quan trọng trong sự phát triển của xã hội.
20


Xây dựng mô hình và giải thuật

Truyền thông được sử dụng rộng rãi trong mọi hoạt động diễn ra trong đời
sống hằng ngày. Hoạt động của con người hằng ngày sử dụng truyền thông rất
nhiều như trong giao tiếp, trong công việc và cả vui chơi giải trí. Truyền thông đóng

vai trò tiên quyết để có thể hình thành nên một xã hội hoặc cộng đồng con người.
Con người chúng ta giao tiếp, trao đổi với nhau thông qua truyền thông như lời nói,
chữ viết, cử chỉ, điệu bộ… Khi nghe hay xem một tin tức trên đài phát thanh hay
truyền hình, thì ta đã tiếp thu được thông tin, đây cũng là truyền thông.
Trong một cơ quan, tổ chức truyền thông được sử dụng trong các cuộc họp,
các sự kiện triển khai kế hoạch mới, hay đơn giản là trong một cuộc phỏng vấn việc
làm thông thường thì đều sử dụng truyền thông.

Hình 2.1: Truyền thông trong đời sống hàng ngày

Trong hình 2.1, mọi người đang trao đổi với nhau về thông tin mà họ quan
tâm. Thông tin được truyền giữa những người này với nhau thông qua lời nói, cử
chỉ, hành động và đôi khi có cả thái độ.
Truyền thông không chỉ được sử dụng trong hoạt động của con người mà còn
được sử dụng trong sự trao đổi thông tin giữa các loài động vật. Một số loài động
vật ăn thịt săn mồi theo đàn, làm tăng khả năng thành công của việc săn mồi, để
thực hiện hành động săn mồi theo tổ chức thì chúng cũng đã trao đổi thông tin với
nhau. Hay một loài vật bị tấn công thì nó sẽ phát ra thông tin kêu cứu đến đàn của
nó, để cầu mong sự cứu giúp từ tập thể của chúng [3].

21


Xây dựng mô hình và giải thuật

Một bầy ong hay một bầy kiến cũng có truyền thông. Đám ong thợ thường
truyền đạt cho nhau thông tin về các loài hoa mà chúng tìm được, cũng như về
khoảng cách hoặc phương hướng mà chúng rủ nhau bay tới để hút nhụy và đưa mật
về tổ.



Quá trình truyền thông
Khi nhắc đến truyền thông, người ta thường đề cặp đến công thức “5W” (Who

says what in which channel to whom with what effect?) [3], một công thức nổi tiếng
của Harold Lasswell. Công thức 5W có thể được diễn tả: “Ai nói cái gì, bằng kênh
nào, nói cho ai nghe và có hiệu quả gì”. Harold Dwight Lasswell sinh ngày 13 tháng
02 năm 1902, mất ngày 18 tháng 12 năm 1978, là một nhà khoa học chính trị và nhà
lý thuyết thông tin hàng đầu ở Hoa Kì. Ông là thành viên của trường xã hội học
Chicago và là một Giáo sư luật tại đại học Yale.
Mô hình truyền thông của Lasswell là một trong những mô hình truyền thông
sớm nhất và có ảnh hưởng nhất, được phát triển bởi các nhà khoa học chính trị Mỹ
và lý thuyết truyền thông của Harold Lasswell vào năm 1948, khi Harold Lasswell
là một Giáo sư ở trường luật Yale.
Trọng tâm mô hình truyền thông của Lasswell được chia nhỏ theo từng thành phần
của truyền thông:
 Who: liên quan đến người giao tiếp, là người công thức hoá thông điệp
được
truyền đi.
 What: nội dung của thông điệp.
 Channel: các phương tiện lan truyền.
 Whom: mô tả cho người nhận thông điệp.
 Effect: hiệu quả của thông điệp.
Tuy nhiên, giới hạn của mô hình truyền thông của Lasswell là chỉ hình dung
quá trình truyền thông như một đường thẳng (tuyến tính) giữa người phát và người
nhận. Điều này dễ làm sinh ra quan niệm người nhận thông điệp là một người nhận
tin thụ động và không có bất cứ phản ứng nào trở lại người phát tin.
Vấn đề này có thể được minh hoạ trong sơ đồ 2.1.

22