Đề xuất mô hình sử dụng cơ chế biểu quyết kết hợp với độ đo trung tâm cho bài toán xác định các nút ảnh hưởng trên mạng xã hội

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (2.58 MB, 84 trang )

TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

LUẬN VĂN THẠC SĨ
Mang l■i tr■ nghi■m m■i m■ cho ng■■i dùng, công ngh■ hi■n th■ hi■n ■■i, b■n online khơng khác gì so v■i b■n g■c. B■n có th■ phóng to, thu nh■ tùy ý.

Đề xuất mơ hình sử dụng cơ chế biểu quyết
kết hợp với độ đo trung tâm cho bài toán
xác định các nút ảnh hưởng trên mạng xã
hội
PHẠM VĂN DƯƠNG

Ngành Khoa học máy tính

Giảng viên hướng dẫn:

PGS.TS. Phạm Văn Hải

Trường:

Cơng nghệ Thông tin và Truyền thông

Chữ ký của GVHD

HÀ NỘI, 10/2022
123doc
Xu■t
Sau
Nhi■u
h■n
phát

event
s■
m■t
t■
h■u
thú
ýn■m
t■■ng
m■t
v■,raevent
kho
■■i,
t■oth■
c■ng
ki■m
123doc
vi■n
■■ng
ti■n
kh■ng
■ãthi■t
t■ng
ki■m
l■
th■c.
b■■c
v■i
ti■nh■n
123doc
online

kh■ng
2.000.000
b■ng
ln
■■nh
ln
tàitài
v■
li■u
t■o
li■u
tríhi■u
c■
c■a
■ t■t
h■i
qu■
mình
c■
gianh■t,
trong
l■nh
t■nguy
v■c:
l■nh
thu
tínnh■p
tài
v■c
cao

chính
nh■t.
tài
online
li■u
tínMong
cho
d■ng,
và kinh
t■t
mu■n
cơng
c■
doanh
các
mang
ngh■
online.
thành
l■i
thơng
cho
viên
Tính
tin,
c■ng
c■a
■■n
ngo■i
website.

■■ng
th■i
ng■,...Khách
■i■m
xã h■itháng
m■thàng
ngu■n
5/2014;
có th■
tài
123doc
ngun
d■ dàng
v■■t
tri tra
th■c
m■c
c■u
q
100.000
tàibáu,
li■uphong
m■t
l■■t cách
truy
phú,c■p
chính
■am■i
d■ng,
xác,

ngày,
nhanh
giàus■
giá
chóng.
h■u
tr■ 2.000.000
■■ng th■ithành
mongviên
mu■n
■■ng
t■oký,
■i■u
l■t ki■n
vào top
cho200
chocác
cácwebsite
users cóph■
thêm
bi■n
thunh■t
nh■p.
t■iChính
Vi■t Nam,
vì v■yt■123doc.net
l■ tìm ki■m
ra thu■c
■■i nh■m
top 3■áp

Google.
■ng Nh■n
nhu c■u
■■■c
chiadanh
s■ tài
hi■u
li■udo
ch■t
c■ng
l■■ng
■■ng
vàbình
ki■mch■n
ti■n là
online.
website ki■m ti■n online hi■u qu■ và uy tín nh■t.
Nhi■u
123doc
Sau
Th■a
khi
thu■n
event
s■
cam
nh■n
h■u
k■t
s■

thú
xác
m■t
d■ng
v■,
s■
nh■n
mang
event
kho
1. t■
th■
l■i
ki■m
■■ng
CH■P
vi■n
nh■ng
ti■n
h■
kh■ng
NH■N
quy■n
th■ng
thi■tl■
CÁC
th■c.
s■
l■i
v■ichuy■n

■I■U
t■t
h■n
123doc
nh■t
2.000.000
KHO■N
sang
ln
cho ng■■i
ph■n
ln
TH■A
tàit■o
li■u
thơng
dùng.
THU■N
c■
■ tin
t■t
h■i
Khixác
c■
khách
giaminh
l■nh
t■ng
Chào
hàng

tài
v■c:
thu
m■ng
kho■n
tr■
nh■p
tài thành
b■n
chính
email
online
■■n
thành
tínb■n
cho
d■ng,
v■i
viên
■ã
t■t
123doc.
123doc.net!
cơng
■■ng
c■a
c■ các
ngh■
123doc
kýthành

v■i
Chúng
thơng
và
123doc.netLink
viên
n■p
tơi
tin,
c■a
cung
ti■n
ngo■i
website.
vào
c■p
ng■,...Khách
xác
tài
D■ch
kho■n
th■c
V■
s■
c■a
(nh■
hàng
■■■c
123doc,
■■■c

cóg■i
th■v■
mơ
b■n
d■■■a
t■
dàng
s■
d■■i
■■■c
ch■
tra■ây)
email
c■u
h■■ng
cho
tài
b■n
li■u
b■n,
nh■ng
■ã
m■t
tùy
■■ng
quy■n
cách
thu■c
ky,
chính

l■i
b■n
vàosau
xác,
các
vuin■p
lịng
“■i■u
nhanh
ti■n
■■ng
Kho■n
chóng.
trên
nh■p
website
Th■a
email
Thu■n
c■a v■
mình
S■vàD■ng
click D■ch
vào link
V■”
123doc
sau ■ây
■ã (sau
g■i ■ây ■■■c g■i t■t T■i t■ng th■i ■i■m, chúng tơi có th■ c■p nh■t ■KTTSDDV theo quy■t ...
Nhi■u

Mang
Ln
123doc
Th■a
Xu■t
Sau
khi
h■n
h■■ng
phát
thu■n
l■i
event
s■
cam
nh■n
m■t
tr■
t■
h■u
k■t
s■
thú
nghi■m
t■i
ýxác
n■m
t■■ng
m■t
d■ng

v■,
là
s■
nh■n
website
ra
mang
event
kho
m■i
■■i,
1.
t■o
t■
th■
m■
l■i
c■ng
ki■m
■■ng
d■n
123doc
CH■P
vi■n
nh■ng
cho
■■u
■■ng
ti■n
h■

kh■ng
ng■■i
NH■N
■ã
quy■n
th■ng
thi■t
chia
t■ng
ki■m
dùng,
l■
CÁC
s■
th■c.
s■
l■i
b■■c
v■i
ti■n
vàchuy■n
■I■U
t■t
cơng
h■n
mua
123doc
online
kh■ng
nh■t

2.000.000
ngh■
bán
KHO■N
sang
b■ng
ln
cho
tài
■■nh
hi■n
ng■■i
li■u
ph■n
ln
tài
TH■A
tài
v■
th■
li■u
hàng
t■o
li■u
thơng
dùng.
tríhi■n
THU■N
hi■u
c■

c■a
■■u
■ tin
t■t
h■i
Khi
■■i,
qu■
mình
Vi■t
xác
c■
khách
gia
b■n
nh■t,
minh
trong
l■nh
Nam.
t■ng
Chào
online
hàng
uy
tài
v■c:
l■nh
thu
Tác

m■ng
tín
kho■n
tr■
nh■p
khơng
tài
phong
v■c
cao
thành
b■n
chính
email
nh■t.
tài
online
khác
chun
■■n
li■u
thành
tínb■n
Mong
gì
cho
d■ng,
và
v■i
so

nghi■p,
viên
kinh
■ã
t■t
123doc.
123doc.net!
v■i
mu■n
cơng
■■ng
c■a
c■
doanh
b■n
các
hồn
mang
ngh■
123doc
ký
g■c.
online.
thành
v■i
h■o,
Chúng
l■i
thơng
B■n

và
123doc.netLink
cho
viên
Tính
■■
n■p
có
tơi
tin,
c■ng
c■a
cao
th■
■■n
cung
ti■n
ngo■i
tính
website.
phóng
■■ng
th■i
vào
c■p
ng■,...Khách
trách
xác
tài
■i■m

D■ch
xã
to,kho■n
th■c
nhi■m
h■i
thutháng
V■
nh■
m■t
s■
c■a
(nh■
■■i
hàng
■■■c
tùy
ngu■n
5/2014;
123doc,
v■i
■■■c
ý.
cóg■i
t■ng
th■
tài
123doc
v■
mơ

ngun
b■n
d■
ng■■i
■■a
t■
dàng
s■
v■■t
d■■i
tri
dùng.
■■■c
ch■
tra
th■c
m■c
■ây)
email
c■u
M■c
h■■ng
q
100.000
cho
tài
b■n
tiêu
báu,
li■u

b■n,
nh■ng
■ã
hàng
phong
m■t
l■■t
tùy
■■ng
■■u
quy■n
cách
truy
thu■c
phú,
ky,
c■a
c■p
chính
■a
l■i
b■n
vào
123doc.net
m■i
d■ng,
sau
xác,
các
vuingày,

n■p
lịng
“■i■u
nhanh
giàu
ti■n
s■
■■ng
tr■
giá
Kho■n
chóng.
h■u
trên
thành
tr■
nh■p
2.000.000
website
■■ng
Th■a
th■
email
vi■n
th■i
Thu■n
c■a
thành
mong
tài v■

li■u
mình
viên
mu■n
S■
online
và
■■ng
D■ng
click
t■o
l■n
ký,
D■ch
■i■u
vào
nh■t
l■t
link
ki■n
V■”
vào
Vi■t
123doc
top
sau
cho
Nam,
200
■ây

cho
■ã
cung
các
các
(sau
g■iwebsite
c■p
users
■âynh■ng
■■■c
cóph■
thêm
tài
bi■n
g■i
thu
li■u
t■t
nh■t
nh■p.
■■c
T■it■i
khơng
t■ng
Chính
Vi■tth■i
th■
Nam,
vì v■y

■i■m,
tìm
t■123doc.net
th■y
l■chúng
tìm
trên
ki■m
tơi
th■
racóthu■c
■■i
tr■■ng
th■nh■m
c■p
top
ngo■i
3nh■t
■áp
Google.
tr■
■KTTSDDV
■ng
123doc.net.
Nh■n
nhu c■u
■■■c
theo
chiaquy■t
danh

s■ tài
hi■u
...li■udo
ch■t
c■ng
l■■ng
■■ng
vàbình
ki■mch■n
ti■n là
online.
website ki■m ti■n online hi■u qu■ và uy tín nh■t.
Mangh■n
Ln
123doc
Th■a
Xu■t
Sau
Nhi■u
khi
h■■ng
phát
thu■n
l■i
event
s■
cam
nh■n
m■t
tr■

t■
h■u
k■t
s■
thú
nghi■m
t■i
ýxác
n■m
t■■ng
m■t
d■ng
v■,
là
s■
nh■n
website
ra
mang
event
kho
m■i
■■i,
1.
t■o
t■
th■
m■
l■i
c■ng

ki■m
■■ng
d■n
123doc
CH■P
vi■n
nh■ng
cho
■■u
■■ng
ti■n
h■
kh■ng
ng■■i
NH■N
■ã
quy■n
th■ng
thi■t
chia
t■ng
ki■m
dùng,
l■
CÁC
s■
th■c.
s■
l■i
b■■c

v■i
ti■n
vàchuy■n
■I■U
t■t
cơng
h■n
mua
123doc
online
kh■ng
nh■t
2.000.000
ngh■
bán
KHO■N
sang
b■ng
ln
cho
tài
■■nh
hi■n
ng■■i
li■u
ph■n
ln
tài
TH■A
tài

v■
th■
li■u
hàng
t■o
li■u
thơng
dùng.
tríhi■n
THU■N
hi■u
c■
c■a
■■u
■ tin
t■t
h■i
Khi
■■i,
qu■
mình
Vi■t
xác
c■
khách
gia
b■n
nh■t,
minh
trong

l■nh
Nam.
t■ng
Chào
online
hàng
uy
tài
v■c:
l■nh
thu
Tác
m■ng
tín
kho■n
tr■
nh■p
khơng
tài
phong
v■c
cao
thành
b■n
chính
email
nh■t.
tài
online
khác

chun
■■n
li■u
thành
tínb■n
Mong
gì
cho
d■ng,
và
v■i
so
nghi■p,
viên
kinh
■ã
t■t
123doc.
123doc.net!
v■i
mu■n
cơng
■■ng
c■a
c■
doanh
b■n
các
hồn
mang

ngh■
123doc
ký
g■c.
online.
thành
v■i
h■o,
Chúng
l■i
thơng
B■n
và
123doc.netLink
cho
viên
Tính
■■
n■p
có
tơi
tin,
c■ng
c■a
cao
th■
■■n
cung
ti■n
ngo■i

tính
website.
phóng
■■ng
th■i
vào
c■p
ng■,...Khách
trách
xác
tài
■i■m
D■ch
xã
to,kho■n
th■c
nhi■m
h■i
thutháng
V■
nh■
m■t
s■
c■a
(nh■
■■i
hàng
■■■c
tùy
ngu■n

5/2014;
123doc,
v■i
■■■c
ý.
cóg■i
t■ng
th■
tài
123doc
v■
mơ
ngun
b■n
d■
ng■■i
■■a
t■
dàng
s■
v■■t
d■■i
tri
dùng.
■■■c
ch■
tra
th■c
m■c
■ây)

email
c■u
M■c
h■■ng
q
100.000
cho
tài
b■n
tiêu
báu,
li■u
b■n,
nh■ng
■ã
hàng
phong
m■t
l■■t
tùy
■■ng
■■u
quy■n
cách
truy
thu■c
phú,
ky,
c■a
c■p

chính
■a
l■i
b■n
vào
123doc.net
m■i
d■ng,
sau
xác,
các
vuingày,
n■p
lịng
“■i■u
nhanh
giàu
ti■n
s■
■■ng
tr■
giá
Kho■n
chóng.
h■u
trên
thành
tr■
nh■p
2.000.000

website
■■ng
Th■a
th■
email
vi■n
th■i
Thu■n
c■a
thành
mong
tài v■
li■u
mình
viên
mu■n
S■
online
và
■■ng
D■ng
click
t■o
l■n
ký,
D■ch
■i■u
vào
nh■t
l■t

link
ki■n
V■”
vào
Vi■t
123doc
top
sau
cho
Nam,
200
■ây
cho
■ã
cung
các
các
(sau
g■iwebsite
c■p
users
■âynh■ng
■■■c
cóph■
thêm
tài
bi■n
g■i
thu
li■u

t■t
nh■t
nh■p.
■■c
T■it■i
khơng
t■ng
Chính
Vi■tth■i
th■
Nam,
vì v■y
■i■m,
tìm
t■123doc.net
th■y
l■chúng
tìm
trên
ki■m
tơi
th■
racóthu■c
■■i
tr■■ng
th■nh■m
c■p
top
ngo■i
3nh■t

■áp
Google.
tr■
■KTTSDDV
■ng
123doc.net.
Nh■n
nhu c■u
■■■c
theo
chiaquy■t
danh
s■ tài
hi■u
...li■udo
ch■t
c■ng
l■■ng
■■ng
vàbình
ki■mch■n
ti■n là
online.
website ki■m ti■n online hi■u qu■ và uy tín nh■t.
Lnh■n
123doc
Th■a
Xu■t
Sau
khi

h■■ng
phát
thu■n
cam
nh■n
m■t
t■k■t
s■
t■i
ýxác
n■m
t■■ng
d■ng
là
s■
nh■n
website
ra
mang
■■i,
1.
t■o
t■l■i
c■ng
■■ng
d■n
123doc
CH■P
nh■ng
■■u

■■ng
h■
NH■N
■ã
quy■n
th■ng
chia
t■ng
ki■m
CÁC
s■s■
l■i
b■■c
ti■n
vàchuy■n
■I■U
t■t
mua
online
kh■ng
nh■t
bán
KHO■N
sang
b■ng
cho
tài
■■nh
ng■■i
li■u

ph■n
tài
TH■A
v■
li■u
hàng
thơng
dùng.
tríTHU■N
hi■u
c■a
■■u
tin
Khi
qu■
mình
Vi■t
xác
khách
nh■t,
minh
trong
Nam.
Chào
hàng
uy
tài
l■nh
Tác
m■ng

tín
kho■n
tr■
phong
v■c
cao
thành
b■n
email
nh■t.
tàichun
■■n
li■u
thành
b■n
Mong
và
v■i
nghi■p,
viên
kinh
■ã
123doc.
123doc.net!
mu■n
■■ng
c■a
doanh
hồn
mang

123doc
kýonline.
v■i
h■o,
Chúng
l■ivà
123doc.netLink
cho
Tính
■■
n■p
tơi
c■ng
cao
■■n
cung
ti■n
tính
■■ng
th■i
vào
c■p
trách
xác
tài
■i■m
D■ch
xãkho■n
th■c
nhi■m

h■itháng
V■
m■t
s■
c■a
(nh■
■■i
■■■c
ngu■n
5/2014;
123doc,
v■i
■■■c
g■i
t■ng
tài
123doc
v■
mơ
ngun
b■n
ng■■i
■■a
t■s■
v■■t
d■■i
tri
dùng.
■■■c
ch■

th■c
m■c
■ây)
email
M■c
h■■ng
q
100.000
cho
b■n
tiêu
báu,
b■n,
nh■ng
■ã
hàng
phong
l■■t
tùy
■■ng
■■u
quy■n
truy
thu■c
phú,
ky,
c■a
c■p
■a
l■i

b■n
vào
123doc.net
m■i
d■ng,
sau
các
vuingày,
n■p
lịng
“■i■u
giàu
ti■n
s■
■■ng
tr■
giá
Kho■n
h■u
trên
thành
tr■
nh■p
2.000.000
website
■■ng
Th■a
th■
email
vi■n

th■i
Thu■n
c■a
thành
mong
tài v■
li■u
mình
viên
mu■n
S■
online
và
■■ng
D■ng
click
t■o
l■n
ký,
D■ch
■i■u
vào
nh■t
l■t
link
ki■n
V■”
vào
Vi■t
123doc

top
sau
cho
Nam,
200
■ây
cho
■ã
cung
các
các
(sau
g■iwebsite
c■p
users
■âynh■ng
■■■c
cóph■
thêm
tài
bi■n
g■i
thu
li■u
t■t
nh■t
nh■p.
■■c
T■it■i
khơng

t■ng
Chính
Vi■tth■i
th■
Nam,
vì v■y
■i■m,
tìm
t■123doc.net
th■y
l■chúng
tìm
trên
ki■m
tơi
th■
racóthu■c
■■i
tr■■ng
th■nh■m
c■p
top
ngo■i
3nh■t
■áp
Google.
tr■
■KTTSDDV
■ng
123doc.net.

Nh■n
nhu c■u
■■■c
theo
chiaquy■t
danh
s■ tài
hi■u
...li■udo
ch■t
c■ng
l■■ng
■■ng
vàbình
ki■mch■n
ti■n là
online.
website ki■m ti■n online hi■u qu■ và uy tín nh■t.
Lnh■n
Th■a
Xu■t
Sau
Nhi■u
123doc
Mang
khi
h■■ng
phát
thu■n
l■i

event
cam
s■
nh■n
m■t
tr■
t■
h■u
k■t
s■
thú
nghi■m
t■i
ýxác
n■m
t■■ng
m■t
d■ng
v■,
là
s■
nh■n
website
ra
mang
event
kho
m■i
■■i,
1.

t■o
t■
th■
m■
l■i
c■ng
ki■m
■■ng
d■n
123doc
CH■P
vi■n
nh■ng
cho
■■u
■■ng
ti■n
h■
kh■ng
ng■■i
NH■N
■ã
quy■n
th■ng
thi■t
chia
t■ng
ki■m
dùng,
l■

CÁC
s■
th■c.
s■
l■i
b■■c
v■i
ti■n
vàchuy■n
■I■U
t■t
cơng
h■n
mua
123doc
online
kh■ng
nh■t
2.000.000
ngh■
bán
KHO■N
sang
b■ng
ln
cho
tài
■■nh
hi■n
ng■■i

li■u
ph■n
ln
tài
TH■A
tài
v■
th■
li■u
hàng
t■o
li■u
thơng
dùng.
tríhi■n
THU■N
hi■u
c■
c■a
■■u
■ tin
t■t
h■i
Khi
■■i,
qu■
mình
Vi■t
xác
c■

khách
gia
b■n
nh■t,
minh
trong
l■nh
Nam.
t■ng
Chào
online
hàng
uy
tài
v■c:
l■nh
thu
Tác
m■ng
tín
kho■n
tr■
nh■p
khơng
tài
phong
v■c
cao
thành
b■n

chính
email
nh■t.
tài
online
khác
chun
■■n
li■u
thành
tínb■n
Mong
gì
cho
d■ng,
và
v■i
so
nghi■p,
viên
kinh
■ã
t■t
123doc.
123doc.net!
v■i
mu■n
cơng
■■ng
c■a

c■
doanh
b■n
các
hồn
mang
ngh■
123doc
ký
g■c.
online.
thành
v■i
h■o,
Chúng
l■i
thơng
B■n
và
123doc.netLink
cho
viên
Tính
■■
n■p
có
tơi
tin,
c■ng
c■a

cao
th■
■■n
cung
ti■n
ngo■i
tính
website.
phóng
■■ng
th■i
vào
c■p
ng■,...Khách
trách
xác
tài
■i■m
D■ch
xã
to,kho■n
th■c
nhi■m
h■i
thutháng
V■
nh■
m■t
s■
c■a

(nh■
■■i
hàng
■■■c
tùy
ngu■n
5/2014;
123doc,
v■i
■■■c
ý.
cóg■i
t■ng
th■
tài
123doc
v■
mơ
ngun
b■n
d■
ng■■i
■■a
t■
dàng
s■
v■■t
d■■i
tri
dùng.

■■■c
ch■
tra
th■c
m■c
■ây)
email
c■u
M■c
h■■ng
q
100.000
cho
tài
b■n
tiêu
báu,
li■u
b■n,
nh■ng
■ã
hàng
phong
m■t
l■■t
tùy
■■ng
■■u
quy■n
cách

truy
thu■c
phú,
ky,
c■a
c■p
chính
■a
l■i
b■n
vào
123doc.net
m■i
d■ng,
sau
xác,
các
vuingày,
n■p
lịng
“■i■u
nhanh
giàu
ti■n
s■
■■ng
tr■
giá
Kho■n
chóng.

h■u
trên
thành
tr■
nh■p
2.000.000
website
■■ng
Th■a
th■
email
vi■n
th■i
Thu■n
c■a
thành
mong
tài v■
li■u
mình
viên
mu■n
S■
online
và
■■ng
D■ng
click
t■o
l■n

ký,
D■ch
■i■u
vào
nh■t
l■t
link
ki■n
V■”
vào
Vi■t
123doc
top
sau
cho
Nam,
200
■ây
cho
■ã
cung
các
các
(sau
g■iwebsite
c■p
users
■âynh■ng
■■■c
cóph■

thêm
tài
bi■n
g■i
thu
li■u
t■t
nh■t
nh■p.
■■c
T■it■i
khơng
t■ng
Chính
Vi■tth■i
th■
Nam,
vì v■y
■i■m,
tìm
t■123doc.net
th■y
l■chúng
tìm
trên
ki■m
tơi
th■
racóthu■c
■■i

tr■■ng
th■nh■m
c■p
top
ngo■i
3nh■t
■áp
Google.
tr■
■KTTSDDV
■ng
123doc.net.
Nh■n
nhu c■u
■■■c
theo
chiaquy■t
danh
s■ tài
hi■u
...li■udo
ch■t
c■ng
l■■ng
■■ng
vàbình
ki■mch■n
ti■n là
online.
website ki■m ti■n online hi■u qu■ và uy tín nh■t.

Vi■c
■■ng
Thành
s■
u■t
Nhi■u
Mang
Ln
123doc
Th■a
Xu■t
Sau
h■u
phát
khi
h■n
b■n
h■■ng
phát
thu■n
l■i
ýevent
viên
s■
cam
nh■n
r■ng
m■t
t■
m■t

tr■
s■
t■
h■u
s■
ýk■t
s■
thú
kho
nghi■m
t■i
ýd■ng
n■u
t■■ng
xác
n■m
ph■i
t■■ng
m■t
d■ng
v■,
là
s■
th■
nh■n
Thành
website
ra
ho■c
mang

th■c
event
t■o
kho
vi■n
m■i
■■i,
1.
t■o
t■
c■ng
th■
viên
■■ng
hi■n
m■
l■i
kh■ng
c■ng
ki■m
■■ng
d■n
123doc
CH■P
vi■n
nh■ng
ti■p
cho
theo
■■ng

■■u
ký
■■ng
ti■n
h■
l■
kh■ng
ng■■i
t■c
NH■N
s■
■ã
■úng
v■i
quy■n
th■ng
thi■t
chia
ki■m
d■ng
t■ng
s■
ki■m
h■n
dùng,
l■
các
CÁC
s■
d■ng

th■c.
ti■n
s■
l■i
b■■c
các
v■i
ti■n
2.000.000
và
ch■
chuy■n
■I■U
t■t
cơng
online
h■n
D■ch
mua
123doc
d■ch
online
kh■ng
d■n
nh■t
2.000.000
ngh■
bán
KHO■N
v■

b■ng
V■
■■■c
sang
tài
b■ng
ln
cho
tài
■■nh
c■a123doc.net
sau
li■u
hi■n
tài
ng■■i
li■u
ph■n
ln
tài
niêm
TH■A
khi
■
li■u
tài
v■
th■
li■u
hàng

t■t
t■o
■KTTSDDV
li■u
thơng
dùng.
trí
y■t
hi■u
hi■n
THU■N
c■
hi■u
c■
c■a
■■u
■
ho■c
l■nh
tin
qu■
■■ng
t■t
h■i
Khi
■■i,
qu■
mình
Vi■t
xác

c■
khách
gia
các
v■c:
nh■t,
■■■c
b■n
nh■t,
ngh■a
minh
trong
l■nh
Nam.
t■ng
Chào
quy
tài
online
uy
hàng
uy
c■p
tài
v■c:
■■nh
chính
l■nh
thu
Tác

tín
v■i
m■ng
tín
kho■n
tr■
cao
nh■t,
nh■p
khơng
tài
vi■c
phong
v■c
cao
tín
áp
thành
b■n
chính
nh■t.
d■ng,
d■ng
email
nh■t.
tài
b■n
vi■c
online
khác

chun
■■n
li■u
thành
tín
Mong
■ã
■ó
cho
b■n
cơng
Mong
gì
cho
d■ng,
và
v■i
■■ng
có
so
các
nghi■p,
viên
ki
kinh
■ã
mu■n
t■t
ngh■
123doc.

123doc.net!
ngh■a
v■i
mu■n
123doc
cơng
d■ch
■■n■
■■ng
c■a
c■
cwebsite.
ýdoanh
b■n
v■i
thơng
mang
các
hồn
mang
là
ngh■
123doc
v■
ký
v■■t
g■c.
các
■■a
Thàn

online.
thành
■ó
v■i■ng
v■i
l■i
tin,
h■o,
Chúng
Chún
■i■u
l■i
thơng
B■n
ch■
m■c
có
cho
ngo■i
và
là
123doc.netLink
chogun
cho
viên
Tính
■■
website
th■
mơ

n■p
kho■n
email
có
c■ng
tơi
tin,
ky,
100.000
c■ng
c■a
cao
ng■,...Khách
t■
■■■c
th■
■■n
cung
ti■n
b■n
ngo■i
d■■i
b■n
■■ng
tính
c■a
ki■m
website.
phóng
■■ng

trith■i
vào
c■p
vui
l■■t
niêm
th■c
ng■,...Khách
■ã
trách
n■ây)
xác
lịng
xã
ti■n
tài
■i■m
khơng
D■ch
xã
to,
■■ng
truy
y■t
q
h■i
kho■n
th■c
hànnh
nhi■m

h■i
cho
thu
■■ng
online
c■p
theo
m■t
báu,
tháng
V■
■■ng
ky,
nh■
m■t
b■n,
s■
c■a
xác,
m■i
(nh■
■■i
nh■p
hi■u
hàng
t■ng
ngu■n
b■n
phong
■■■c

tùy
ngu■n
5/2014;
ýtùy
123doc,
nhanh
v■i
Mong
ngày,
vui
■■■c
qu■
ý.
email
th■i
có
thu■c
phú,
tài
g■i
t■ng
lịng
th■
tài
123doc
và
s■
■i■m.
mu■n
ngun

chóng.
c■a
v■
mơ
ngun
b■n
■a
vào
uy
d■
■■ng
ng■■i
h■u
■■a
t■
tín
d■ng,
mình
dàng
các
s■
man
T■t
v■■t
tri
2.000.000
d■■i
nh■t.
nh■p
tri

dùng.
■■■c
ch■
th■c
“■i■u
c■
và
ngun
tra
th■c
giàu
m■c
■ây)
click
các
email
c■u
email
q
M■c
h■■ng
giá
Kho■n
q
100.000
thành
ocho
vào
tri
tài

báu,
tr■
b■nn
b■n
c■a
tiêu
báu,
th■c
li■u
b■n,
link
■■ng
nh■ng
Th■a
viên
phong
■ã
hàng
mình
phong
viên
m■t
l■■t
q
123doc
tùy
■■ng
■■ng
th■i
Thu■n

■■u
c■a
báo
và
phú,
quy■n
cách
truy
thu■c
phú,
click
mong
■ã
ky,
các
ký,
website.
c■a
c■p
■a
chính
v■
■a
l■i
b■n
g■i
vào
l■t
vào
users

d■ng,
123doc.net
m■i
S■
mu■n
d■ng,
sau
vào
xác,
các
link
vui
D■ng
ngày,
có
n■p
giàu
top
lịng
“■i■u
123doc
nhanh
t■o
giàu
thêm
200
ti■n
D■ch
giá
s■

■■ng
■i■u
tr■
giá
Kho■n
thu
chóng.
các
h■u
tr■
■ã
trên
thành
tr■
V■”
ki■n
nh■p.
nh■p
■■ng
g■i
website
2.000.000
website
■■ng
Th■a
sau
th■
cho
email
Chính

th■i
■ây
vi■n
th■i
ph■
Thu■n
chomong
c■a
thành
vì
(sau
mong
các
tài
bi■n
v■y
v■
li■u
mình
users
mu■n
■ây
viên
nh■t
mu■n
S■
123doc.net
online
và
■■■c

■■ng
có
D■ng
t■i
t■o
click
t■o
thêm
l■n
Vi■t
■i■u
g■i
ký,
D■ch
■i■u
vào
ra
nh■t
thu
Nam,
l■t
t■t
■■i
link
ki■n
nh■p.
ki■n
V■”
vào
T■i

Vi■t
123doc
nh■m
t■
cho
top
sau
cho
t■ng
l■
Nam,
Chính
cho
200
tìm
■ây
■áp
cho
■ã
th■i
cung
các
ki■m
các
vìcác
(sau
g■i
■ng
v■y
■i■m,

users
website
c■p
users
thu■c
■ây
nhu
123doc.net
nh■ng
có
chúng
c■u
■■■c
có
top
ph■
thêm
thêm
chia
3tơi
tài
bi■n
Google.
g■i
thu
ra
có
thu
li■u
s■

■■i
t■t
nh■p.
th■
nh■t
nh■p.
tài
■■c
T■i
Nh■n
nh■m
li■u
c■p
t■i
Chính
khơng
t■ng
Chính
ch■t
nh■t
Vi■t
■■■c
■áp
th■i
vìth■
l■■ng
Nam,
■KTTSDDV
vì■ng
v■y

v■y
danh
■i■m,
tìm
123doc.net
nhu
t■
và
123doc.net
th■y
hi■u
l■
ki■m
chúng
c■u
tìm
trên
theo
do
chia
ki■m
ti■n
c■ng
tơi
ra
th■
quy■t
ra
s■
có

■■i
online.
thu■c
■■i
tr■■ng
■■ng
th■
tài...
nh■m
nh■m
li■u
c■p
top
bình
ngo■i
ch■t
■áp
3nh■t
■áp
Google.
ch■n
l■■ng
■ng
tr■
■KTTSDDV
■ng
123doc.net.
lànhu
Nh■n
nhu

website
vàc■u
ki■m
c■u
■■■c
chia
theo
ki■m
chia
ti■n
s■
quy■t
danh
s■
online.
ti■n
tàitài
hi■u
li■u
online
...li■uch■t
do
ch■t
hi■u
c■ng
l■■ng
l■■ng
qu■
■■ng
vàvàki■m

uy
bình
ki■m
tín ch■n
ti■n
nh■t.
ti■nonline.
là
online.
website ki■m ti■n online hi■u qu■ và uy tín nh■t.

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc

BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn: Phạm Văn Dương
Đề tài luận văn: Đề xuất mơ hình sử dụng cơ chế biểu quyết kết hợp với
độ đo trung tâm cho bài toán xác định các nút ảnh hưởng trên mạng xã hội
Chuyên ngành: Khoa học máy tính
Mã số SV: 20202652M

Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác
nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày
29/10/2022 với các nội dung sau:
1. Bỏ tên đầu mục Chương 1: Giới thiệu và Chương 5: Kết luận thành Giới
thiệu và Kết luận
2. Bổ sung và chỉnh sửa nội dung Phần Giới thiệu của luận văn:
− Chỉnh sửa nội dung Phần Giới thiệu ngắn gọn và đầy đủ ý
− Phân chia các đoạn dài thành nhiều đoạn con, mỗi đoạn diễn tả một ý
trình bày
− Định nghĩa bài tốn trong Phần Giới thiệu với việc giải thích rõ đầu
vào và đầu ra của bài tốn cũng như các kí hiệu đi kèm
3. Bổ sung và chỉnh sửa nội dung Chương 2: Mơ hình đề xuất của luận văn:
− Phát biểu và mơ tả ngắn gọn về bài tốn trước khi đưa ra mơ hình tốn
học trong phần đầu Chương 2: Mơ hình đề xuất
− Mơ tả rõ nút và mối quan hệ trong bộ dữ liệu mạng xã hội
− Bổ sung ý nghĩa và vấn đề logic trong việc tính tốn và kết hợp 3 độ đo
của thuật tốn đề xuất EAVoteRank++
4. Bổ sung và chỉnh sửa nội dung Chương 3: Thực nghiệm, đánh giá của luận
văn:
− Bổ sung lí do lựa chọn so sánh thuật tốn đề xuất EAVoteRank++ với

các thuật tốn lựa khác trong Luận văn
− Mơ tả rõ cấu trúc các trường dữ liệu của bộ dữ liệu thực nghiệm
− Bổ sung ý nghĩa từng đường màu trên đồ thị tương ứng với từng thuật
toán nào trong các kết quả của thực nghiệm với các chỉ số quy mô lan
truyền.

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

− Bổ sung phần so sánh tính hiệu quả của các thực nghiệm với thuật toán
đề xuất EAVoteRank++ so với các thuật toán khác
− Bổ sung nội dung kết quả thực nghiệm đánh giá hiệu quả về mặt thời
gian khi áp dụng thuật toán đề xuất
Ngày 29 tháng 11 năm 2022

Giáo viên hướng dẫn

Tác giả luận văn

PGS.TS. Phạm Văn Hải

Phạm Văn Dương
CHỦ TỊCH HỘI ĐỒNG

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

ĐỀ TÀI LUẬN VĂN
Biểu mẫu của Đề tài/Luận văn tốt nghiệp theo qui định của Viện, tuy nhiên cần

đảm bảo giáo viên giao đề tài ký và ghi rõ họ và tên.
Trường hợp có 2 giáo viên hướng dẫn thì sẽ cùng ký tên.

Giáo viên hướng dẫn
Ký và ghi rõ họ tên

PGS.TS. Phạm Văn Hải

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

LỜI CAM ĐOAN
Tôi – Phạm Văn Dương - cam kết luận văn này là cơng trình nghiên cứu của bản
thân tôi, dưới sự hướng dẫn của PGS.TS. Phạm Văn Hải. Các kết quả công bố

trong báo cáo này là trung thực, không phải là sao chép của bất kỳ một cá nhân,
hoặc tổ chức đã được công bố nào khác. Tất cả các trích dẫn được tham chiếu rõ
ràng.
Ngày 12 tháng 10 năm 2022
Tác giả luận văn

Phạm Văn Dương
Xác nhận của người hướng dẫn
Giáo viên hướng dẫn
Ký và ghi rõ họ tên

PGS.TS. Phạm Văn Hải

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

LỜI CẢM ƠN
Lời đầu tiên em xin được gửi lời cảm ơn chân thành, sâu sắc đến các quý Thầy, Cô
giáo tại Trường CNTT – TT, Đại Học Bách Khoa Hà Nội đã tận tình chỉ dạy và
quan tâm em trong suốt quá trình học tập và rèn luyện tại trường.
Em trân trọng biết ơn PGS.TS Phạm Văn Hải đã tận tình hướng dẫn, chỉ bảo, góp
ý cho em trong suốt q trình thực hiện luận văn để em có thể hoàn thiện luận văn
đúng tiến độ.
Con xin gửi lời cảm ơn đến gia đình bố, mẹ, anh, chị, bà ngoại đã luôn ở bên động
viên con bất kể lúc nào và ln mong con có được thành cơng.
Cảm ơn đến người yêu, những người bạn đã luôn ở bên, chia sẻ những lúc mình
khó khăn.
Bốn năm học Đại học cùng hai năm học Thạc sĩ tại Trường CNTT - TT, Đại học
Bách Khoa Hà Nội là những năm thanh xuân rực rỡ của bản thân. Ở đây, có những
niềm vui cũng có những nỗi buồn nhưng tất cả là những khoảnh khắc vô cùng đáng
nhớ mà em mãi không bao giờ quên. Cảm ơn Bách khoa đã cho em cơ hội là một
phần trong đó, cảm ơn Trường CNTT & TT đã cho em một hành trang vô cùng
quý báu trong chặng đường phía trước. Em sẽ nhớ mãi ngày đầu nhập học với
những cơn mưa lác đác, nhớ mãi lúc bất ngờ phải lên phòng đào tạo xếp hồ sơ,
nhớ cả lúc tưởng chừng phải học lại mà vẫn qua, nhớ cảm giác khi mình được bằng
Giỏi, nhớ những học bổng mà mình được nhận. Sẽ nhớ mãi!
Xin chân thành cảm ơn!

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

TÓM TẮT NỘI DUNG LUẬN VĂN
Trong thời đại bùng nổ thông tin, đặc biệt thông tin trên mạng xã hội như hiện nay,
nhiều bài toán được đặt ra nhằm giải quyết các vấn đề thực tiễn trong cuộc sống
dựa vào tập dữ liệu trên như tìm mối quan hệ giữa những người dùng hay gợi ý
các sản phẩm người dùng quan tâm, … Những bài toán này được gọi chung là các
bài tốn phân tích mạng xã hội. Một trong số các bài tốn phân tích mạng xã hội
được nhiều nhà khoa học quan tâm và nghiên cứu là bài toán xác định các nút ảnh
hưởng trên mạng xã hội. Từ những giá trị thực tiễn mà bài toán mang lại trong các
chiến dịch quảng cáo, truyền thông hay kiểm sốt tin đồn, dịch bệnh, luận văn đề
xuất mơ hình xác định các nút ảnh hưởng trong mạng xã hội bao gồm: mơ hình
hóa dữ liệu thu thập từ mạng xã hội Facebook thành đồ thị đồng nhất bằng phương
pháp xây dựng đồ thị tri thức dựa trên tương tác người dùng; đề xuất thuật toán
xác định nút ảnh hưởng theo cơ chế biểu quyết kết hợp với độ đo trung tâm. Thuật
tốn đề xuất xây dựng cơng thức tính điểm khả năng biểu quyết dựa trên việc kết
hợp 3 thơng tin bao gồm hệ số bậc, vị trí trong mạng của nút và hệ số phân cụm
cục bộ. Xây dựng trọng số cho mỗi độ đo dựa theo thuật tốn thơng tin entropy.
Ngồi ra, luận văn xây dựng cơng thức tính điểm ảnh hưởng của mỗi nút dựa trên

các lân cận cấp 1 và cấp 2. Bên cạnh đó, thuật toán đề xuất lựa chọn tập hợp nút
ảnh hưởng phân phối rộng rãi trên toàn mạng bằng cách áp dụng cơ chế giảm nhiễu
với các lân cận theo hệ số. Để chứng minh tính hiệu quả của thuật tốn, luận văn
lựa chọn mơ hình mơ phỏng thơng tin lan truyền thơng tin SIR mơ phỏng lại q
trình lan truyền thông tin và áp dụng các chỉ số đánh giá như quy mô lan truyền,
quy mô lan truyền cuối và trung bình khoảng cách giữa các nút hạt giống. Kết quả
được thực nghiệm trên 8 bộ dữ liệu bao gồm 7 bộ dữ liệu mạng phức hợp thường
được sử dụng trong bài toán xác định nút ảnh hưởng và 1 bộ dữ liệu xây dựng từ
việc thu thập trên Facebook, đạt hiệu quả tốt hơn hơn các phương pháp và thuật
toán xác định nút ảnh hưởng khác.

HỌC VIÊN
Ký và ghi rõ họ tên

Phạm Văn Dương

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

MỤC LỤC
GIỚI THIỆU ............................................................................................................................... 1

Đặt vấn đề............................................................................................................... 1
Mục đích của luận văn ........................................................................................... 8
Phạm vi nghiên cứu ................................................................................................ 9
Nội dung luận văn .................................................................................................. 9
CHƯƠNG 1. CƠ SỞ LÝ THUYẾT......................................................................................... 11

1.1

Lý thuyết về đồ thị ................................................................................... 11
Định nghĩa ................................................................................. 11
Một số loại đồ thị ...................................................................... 11
Biểu diễn đồ thị ......................................................................... 12
Một số khái niệm khác .............................................................. 15

1.2

Tổng quan về các bài tốn phân tích mạng xã hội ................................... 16
Tổng quan ................................................................................. 16
Các bài tốn nghiên cứu trong phân tích mạng xã hội .............. 16

1.3

Một số phương pháp xác định nút ảnh hưởng ......................................... 18
Độ đo trung tâm dựa trên bậc.................................................... 19
Độ đo trung tâm dựa trên sự lân cận ......................................... 19
Phân rã k-shell và cải tiến k-shell ............................................. 20
Hệ số phân cụm ......................................................................... 22
Cải tiến mơ hình lực hấp dẫn .................................................... 23
Độ đo trung tâm kết hợp nhiều thông tin cục bộ có trọng số dựa
trên thơng tin entropy (LWC) ...................................................................... 23
Độ đo kết hợp vị trí, hệ số bậc và Entropy (MCDE) ................ 25
Thuật toán EnRenew ................................................................. 26
Thuật toán VoteRank ................................................................ 28
Thuật toán WVoteRank ............................................................ 28
Thuật toán cải tiến WVoteRank ................................................ 29
Thuật toán VoteRank++ ............................................................ 30

1.4

Một số lý thuyết liên quan........................................................................ 30
Đồ thị tri thức ............................................................................ 30
Thông tin Entropy ..................................................................... 31

1.5

Phương pháp đánh giá thuật tốn ............................................................. 31
Mơ hình Nhạy cảm – Bị nhiễm – Phục hồi ............................... 32
Trung bình đường đi ngắn nhất giữa các nút ............................ 35

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

Tính tốn lại điểm ảnh hưởng và điểm khả năng biểu quyết và lựa
chọn nút hạt giống ........................................................................................ 44

2.3

Mơ tả thuật tốn ....................................................................................... 46

CHƯƠNG 3. THỰC NGHIỆM, ĐÁNH GIÁ ......................................................................... 51

3.1

Bộ dữ liệu ................................................................................................. 51
Mơ hình hóa dữ liệu mạng xã hội ............................................. 51
Mô tả bộ dữ liệu ........................................................................ 52

3.2

Thực nghiệm thuật toán ........................................................................... 53

3.3

Kết quả thực nghiệm ................................................................................ 54

KẾT LUẬN ................................................................................................................................ 64

Kết quả đạt được .................................................................................................. 64
Hướng phát triển .................................................................................................. 64

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

DANH MỤC HÌNH VẼ
Hình 0.1: Thống kê người dùng Facebook tại Việt Nam năm 2021 ...................... 1
Hình 1.1: Đồ thị có hướng và biểu diễn đồ thị bằng ma trận kề .......................... 12
Hình 1.2: Đồ thị có hướng và biểu diễn ma trận liên thuộc đỉnh cạnh ................ 13
Hình 1.3: Danh sách cạnh (cung) của đồ thị ........................................................ 14
Hình 1.4: Danh sách kề của đồ thị vô hướng G ................................................... 14
Hình 1.5: Danh sách kề của đồ thị có hướng 𝐺𝐺1 ................................................. 15

Hình 1.6: Ví dụ về đồ thị vơ hướng ..................................................................... 16
Hình 1.7: Bài tốn dự đốn liên kết trong mạng .................................................. 17
Hình 1.8: Bài tốn phân loại nút .......................................................................... 17
Hình 1.9: Bài tốn phân loại trong lĩnh vực hóa dược [28] ................................. 18
Hình 1.10: Ví dụ về đồ thị vơ hướng ................................................................... 19

Hình 1.11: Ví dụ đồ thị cho thuật tốn phân rã k-shell ........................................ 20
Hình 1.12: Ví dụ đồ thị cho thuật tốn MCDE .................................................... 25
Hình 1.13: Ví dụ về tính điểm ảnh hưởng theo thuật tốn Enrenew ................... 27
Hình 1.14: Sơ đồ minh họa các tham số trong mơ hình SIR ............................... 32
Hình 1.15: Minh họa q trình mơ phỏng lan truyền bằng mơ hình SIR trên mạng
Krackhardt’s Kite ................................................................................................. 33
Hình 2.1: Mơ hình đề xuất ................................................................................... 36
Hình 2.2: Ví dụ về phương pháp xây dựng đồ thị tri thức dựa trên tương tác người
dùng ...................................................................................................................... 39
Hình 2.3: Ví dụ về mạng phức hợp ...................................................................... 47
Hình 3.1: Mô tả các nút và mối quan hệ trong dữ liệu thu thập được từ mạng xã
hội Facebook ........................................................................................................ 51
Hình 3.2: Chỉ số quy mơ lan truyền 𝐹𝐹(𝑡𝑡) thực nghiệm trên 8 bộ dữ liệu ............ 55

Hình 3.3: Chỉ số quy mô lan truyền cuối 𝐹𝐹(𝑡𝑡𝑡𝑡) thực nghiệm trên 8 bộ dữ liệu với
số lượng 𝜌𝜌 nút hạt giống khác nhau ..................................................................... 57
Hình 3.4: Chỉ số quy mơ lan truyền cuối 𝐹𝐹𝐹𝐹𝐹𝐹 với xác suất lây nhiễm 𝛽𝛽 khác nhau
.............................................................................................................................. 59

Hình 3.5: Chỉ số trung bình đường đi ngắn nhất giữa các nút hạt giống thực nghiệm
trên 8 mạng ........................................................................................................... 61

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

DANH MỤC BẢNG
Bảng 1.1: Độ đo trung tâm dựa trên bậc của đồ thị Hình 1.10 ............................ 19
Bảng 1.2: Độ đo trung tâm dựa trên lân cận của đồ thị Hình 1.10 ...................... 20
Bảng 1.3: Độ đo k-shell và cải tiến k-shell của các nút trong mạng Hình 1.11... 21
Bảng 1.4: Hệ số phân cụm cục bộ của các nút trong mạng Hình 1.11 ................ 22
Bảng 1.5: Độ đo DK_CLC của các nút trong đồ thị Hình 1.11 ........................... 23
Bảng 1.6: Kết quả tính tốn độ đo MCDE cho các nút trong đồ thị Hình 1.12 ... 26
Bảng 2.1: Độ đo của các nút trong mạng ............................................................. 48
Bảng 2.2: Bảng kết quả sau vịng lặp đầu tiên theo thuật tốn EAVoteRank++ . 49
Bảng 2.3: Bảng kết quả sau vòng lặp thứ 2 theo thuật tốn EAVoteRank++...... 50
Bảng 3.1: Các thơng số cơ bản của các mạng thực nghiệm ................................. 53
Bảng 3.2: Kết quả thời gian thực hiện thuật toán đề xuất EAVoteRank++ trên 8 bộ
dữ liệu thực nghiệm.............................................................................................. 62

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

truyền thơng tin Nhạy cảm – Bị nhiễm – Phục hồi

LT

Linear Threshold – Mơ hình

GSM

Global Structure Model – Mơ hình cấu trúc tồn cục

MCDE

Mixed core, degree and entropy - Độ đô kết hợp vị trí, hệ số
bậc và Entropy

LWC

Multiple local attributes-weighted centrality - Độ đo trung
tâm kết hợp nhiều thông tin cục bộ có trọng số dựa trên
thơng tin entropy

TOPSIS

Technique for Order of Preference by Similarity to Ideal
Solution – Kĩ thuật cho thứ tự ưu tiên theo sự tương đồng
với giải pháp lí tưởng

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

Tập hợp các đỉnh của đồ thị

|𝑉𝑉|

Số lượng nút trong đồ thị

𝑒𝑒𝑖𝑖𝑖𝑖

Cạnh nối từ nút 𝑖𝑖 đến nút 𝑗𝑗

𝛤𝛤𝑢𝑢

Tập hợp các lân cận của nút 𝑢𝑢

|𝐸𝐸|
𝑤𝑤(𝑖𝑖, 𝑗𝑗)
𝑓𝑓

Số lượng cạnh trong đồ thị

Trọng số cạnh nút 𝑖𝑖 đến nút 𝑗𝑗
Hàm xác định nút ảnh hưởng

〈𝑑𝑑 〉

Trung bình đường đi giữa các nút trong đồ thị

𝑘𝑘𝑣𝑣

Hệ số bậc của nút 𝑣𝑣

𝑤𝑤𝑖𝑖

Trọng số của các độ đo

𝜆𝜆, 𝛿𝛿

Hệ số giảm nhiễu thông tin với các lân cận

𝑣𝑣𝑎𝑎𝑖𝑖

Điểm khả năng biểu quyết của nút 𝑖𝑖

〈𝑘𝑘 〉

𝑘𝑘𝑚𝑚𝑚𝑚𝑚𝑚

Trung bình hệ số bậc của nút trong đồ thị

Hệ số bậc lớn nhất trong đồ thị

𝑁𝑁, 𝑛𝑛

Số lượng các nút trong đồ thị

𝑣𝑣𝑠𝑠𝑖𝑖

Điểm ảnh hưởng (điểm biểu quyết) của nút 𝑖𝑖

𝛽𝛽
𝛾𝛾

𝑑𝑑𝐺𝐺 (𝑣𝑣, 𝑡𝑡)

φ(r, c, s)
𝑛𝑛𝐼𝐼(𝑡𝑡)

Xác suất lây nhiễm lan truyền thông tin trong mơ hình
SIR
Xác suất phục hồi trong mơ hình SIR
Khoảng cách ngắn nhất từ nút 𝑣𝑣 đến nút 𝑣𝑣 trong đồ thị 𝐺𝐺

Hàm tính trọng số cho cạnh trong đồ thị tri thức dựa trên
tương tác người dùng
Số lượng các nút trạng thái 𝐼𝐼 ở thời điểm 𝑡𝑡

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

𝑛𝑛𝑆𝑆(𝑡𝑡)

𝑛𝑛𝑅𝑅(𝑡𝑡)
𝑅𝑅𝑑𝑑

Số lượng các nút trạng thái 𝑆𝑆 ở thời điểm 𝑡𝑡

Số lượng các nút trạng thái 𝑅𝑅 ở thời điểm 𝑡𝑡
Không gian 𝑑𝑑 chiều

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

GIỚI THIỆU
Đặt vấn đề
Bùng nổ thông tin trong thời đại cơng nghệ 4.0 là một vấn đề khơng cịn xa lạ trong
những năm gần đây. Nguồn thông tin đa dạng cũng đang và sẽ là cơ hội và thách
thức cho các nhà nghiên cứu trong việc phân tích và xử lý dữ liệu. Một trong số đó
là nguồn thơng tin đền từ nền tảng Internet. Sự phát triển nhanh chóng của internet
dẫn đến các tiện ích và cụ thể là mạng xã hội ngày càng phong phú. Ta có thể kể
đến các trang mạng xã hội trực tuyến như Facebook, Twitter, Instagram. …. Chúng
đã và đang trở nên vô cùng phổ biến với hầu hết mọi lứa tuổi [1]. Theo đó, mạng
xã hội trở thành một nền tảng quan trọng, hữu ích cho các chiến dịch truyền thơng
và quảng cáo [2]. Ở trên khơng gian mạng xã hội hiện có rất nhiều thông tin được
trao đổi và tiếp cận mỗi ngày. Riêng đối với việc sử dụng mạng xã hội Facebook,
theo số liệu thống kê tính tới tháng 6/2021 của NapoleonCat 1 (công cụ đo lường
các chỉ số mạng xã hội), tổng số người dùng Facebook tại Việt Nam là gần 76 triệu
người, chiếm hơn 70% dân số toàn quốc, tăng 31 triệu người dùng so với năm 2019
và vẫn dẫn đầu danh sách các mạng xã hội phổ biến tại Việt Nam. Mô tả chi tiết
về các thông tin người dùng mạng xã hội Facebook được mô tả ở biểu đồ Hình 0.1.

Hình 0.1: Thống kê người dùng Facebook tại Việt Nam năm 2021 2

Đây là những điều kiện mang đến cơ hội to lớn cho các nhà bán hàng gia tăng việc
tìm kiếm và tiếp cận hiệu quả với đối tượng khách hàng tiềm năng tại Việt Nam
1

/> />2

1
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

trên nền tảng mạng xã hội. Do đó, có thể khẳng định rằng mạng xã hội đã, đang và
sẽ là một nền tảng quan trọng cho các chiến dịch truyền thông và quảng cáo. Tuy
nhiên, việc phổ biến các thông tin đến mọi người dùng trên mạng xã hội hiện khơng
hiệu quả và tốn kém chi phí rất nhiều. Một giải pháp hợp lý là nhắm mục tiêu vào
một số lượng người dùng nhất định với mong muốn truyền bá thông điệp quảng
cáo càng rộng rãi càng tốt, nghĩa là tìm một nhóm người nhất định trên mạng xã
hội (hay cịn gọi là người có sức ảnh hưởng trên mạng xã hội - KoLs) để thực hiện
các chiến dịch quảng bá sản phẩm, lan tỏa thông điệp giúp tiếp cận đến càng nhiều
người dùng càng tốt. Giả sử rằng một cơng ty có một sản phẩm mới và có kế hoạch

bắt đầu một chiến dịch quảng cáo, tiếp thị đến với người dùng trên mạng xã hội.
Công ty này muốn chọn một nhóm người nhất định có khả năng truyền bá sản
phẩm của họ đến với những người dùng khác trên mạng lưới của những người này.
Việc lựa chọn nhóm người này là rất quan trọng vì nếu lựa chọn khơng hợp lý có
thể khiến tồn bộ chiến dịch quảng cáo này thất bại. Do đó, cơng ty nên chọn một
nhóm người có ảnh hưởng lớn để đảm bảo rằng sản phẩm của họ sẽ tiếp tục được
tiếp thị đến những người dùng khác. Việc xếp hạng theo mức độ ảnh hưởng của
những nhóm người này sẽ giúp doanh nghiệp linh hoạt hơn trong việc lựa chọn
những người có ảnh hưởng cho chiến dịch tiếp thị của mình. Cụ thể như, nếu thuật
tốn chỉ tìm thấy 𝑘𝑘 người có tầm ảnh hưởng hàng đầu và hầu hết trong số họ từ
chối hợp tác hoặc yêu cầu một mức giá rất cao khơng thể chi trả được, thì chiến
dịch tiếp thị của cơng ty có thể bị dừng hồn tồn. Do đó, thuật tốn đề xuất cho
phép có nhiều cơ hội hơn để tìm những người dùng có ảnh hưởng khác vì nó sắp
xếp các nút của mạng xã hội theo mức độ ảnh hưởng của họ. Bằng cách này, doanh
nghiệp có thể lựa chọn những người ảnh hưởng phù hợp hơn, ví dụ, lựa chọn nhiều
người dùng có tầm ảnh hưởng ở mức trung bình để dẫn đầu chiến dịch quảng cáo
thay vì chỉ lựa chọn một người có tầm ảnh hưởng nhất, nếu điều này phù hợp hơn
với yêu cầu của họ.
Không chỉ với các thông tin trên mạng xã hội mà nhiều dữ liệu trong thực tế cũng
được biểu diễn dưới các mạng đồ thị được gọi chung là các mạng phức hợp. Có
thể kể đến như mạng bao hàm sự hợp tác nghiên cứu khoa học giữa các tác giả [3],
mạng email biểu thị thông tin liên lạc email giữa người dùng [4], mạng proteinDNA giúp chúng ta có cái nhìn đa chiều về các phản ứng sinh hóa [5] hay mạng
đường sắt biểu diễn cấu trúc của đường sắt qua các trạm đỗ [6]. Những dữ liệu này
được mơ hình hóa thành các mạng phức hợp, tạo điều kiện thuận lợi cho việc
nghiên cứu các hệ thống.
Sự hiểu biết sâu sắc về các mạng phức hợp nói chung và mạng xã hội nói riêng
trong việc xác định các nút ảnh hưởng có ý nghĩa vơ cùng to lớn trong việc truyền
bá thơng tin và kiểm sốt các kết nối giữa các thành phần trong mạng. Một mặt,
bằng cách xác định các nút có ảnh hưởng trong mạng, chúng ta có thể thực hiện
các chiến dịch quảng bá truyền thông cho các sản phẩm đưa ra thị trường, hỗ trợ

truyền bá thông tin đến các người dùng trên nền tảng mạng xã hội như đã trình bày
ở phần trên hay trong lĩnh vực sinh học, bài toán cịn có thể giúp phát hiện các
protein thiết yếu trong đời sống [7]. Mặt khác, bằng cách loại bỏ một số nút ảnh
2
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

hưởng quan trọng trong mạng, nó có thể hạn chế tốc độ lan truyền thông tin nhanh
gây ảnh hưởng trên quy mơ lớn của tin giả ví dụ như thơng tin giả từ các tài khoản
mạng xã hội về tin trong việc phòng, chống dịch bệnh Covid-19 ở Việt Nam. Hay
trong quá trình lây lan dịch bệnh, việc xác định vị trí và tạo miễn dịch cho những
cá nhân có ảnh hưởng nhất có thể ngăn chặn sự lây lan thêm của vi rút. Điều này
là vô cùng cấp thiết vì những mối nguy thường bắt đầu với một số lượng nhỏ các
nút và có thể nhanh chóng lan rộng ra toàn bộ mạng [6]. Hoặc trong một hệ thống

mạng máy tính quy mơ lớn, việc phải thiết kế một kiến trúc mạnh mẽ và an toàn
là một điều bắt buộc vì hệ thống thực tế sẽ khơng được xảy việc gián đoạn đột
ngột, vậy nên việc tạo ra các máy chủ dự phòng và các liên kết dự phòng với các
máy chủ trong hệ thống chính tùy theo mức độ quan trọng là một giải pháp khá
hiệu quả [8]. Từ những ý nghĩa thực tiễn và lợi ích đã trình bày ở trên, việc xác
định các nút có ảnh hưởng trong mạng là một bài tốn hữu ích, có ý nghĩa to lớn
và đang được nhiều nhà khoa học quan tâm và nghiên cứu.
Việc xác định các nút ảnh hưởng thực chất là bài tốn tối đa hóa ảnh hưởng
(Influence Maximization - IM) trong mạng xã hội [9, 10]. Về mặt hình thức, vấn
đề tối đa hóa ảnh hưởng được định nghĩa là việc tối đa hóa phạm vi tiếp cận của
thông tin bằng cách ban đầu gửi thông tin đến một nhóm các nút có ảnh hưởng. Ở
đây, bài toán xác định nút ảnh hưởng với yêu cầu đầu vào là một mạng đồ thị đồng
nhất, thông qua các thuật tốn và mơ hình khác nhau sẽ đưa ra được một danh sách
các nút trong mạng có tầm ảnh hưởng nhất. Bài tốn có thể được mơ tả bằng cơng
thức tốn học như sau:
𝑓𝑓
PT 0.1
𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) → 𝑆𝑆
với 𝐺𝐺 là đồ thị đồng nhất, 𝑉𝑉 là tập hợp các nút và 𝐸𝐸 là tập hợp các cạnh có trong
đồ thị. 𝑓𝑓 ở đây biểu thị thuật toán xác định được tập hợp 𝑙𝑙 nút ảnh hưởng 𝑆𝑆.

Trong thực tế, như ta đã biết, mạng xã hội là một nền tảng chia sẻ thông tin vô
cùng hữu ích, nó mơ tả các hoạt động của người dùng trên đây như chính các hoạt
động trong thế giới thực. Người dùng có thể dễ dàng thể hiện các cảm xúc hay
những quan điểm của mình trên đây, tuy nhiên việc thu thập thơng tin này lại vơ
cùng khó khăn do các chính sách bảo mật, riêng tư của mỗi người dùng. Hơn nữa,
mối quan hệ phức tạp, chồng chéo của mỗi người dùng cũng khiến cho việc mơ
hình hóa dữ liệu này gặp rất nhiều khó khăn. Một trong những phương pháp gần
đây được nhiều nhà khoa học áp dụng để giải quyết khó khăn này là việc xây dựng
đồ thị tri thức. Đây là một trong những mô hình quan hệ hữu ích có thể được áp

dụng trong thế giới thực. Đặc biệt đối với mạng xã hội, đồ thị tri thức cơ bản được
xây dựng bởi các thực thể và các cạnh là mối quan hệ giữa chúng. Mối quan hệ
này chúng ta sẽ định nghĩa bởi các yếu tố khác nhau, tuy nhiên bên trong chúng sẽ
ẩn chứa các mối quan hệ trong thế giới thực. Từ các nhận định trên, ta có thể thấy
mạng xã hội là nền tảng dữ liệu mới, nơi mà dữ liệu thay đổi và cập nhật liên tục
từ người dùng. Do vậy, việc thu thập dữ liệu vơ cùng khó khăn do việc cá nhân
hóa của mỗi người dùng và các cơ chế phát hiện bất thường trên Facebook từ các
3
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

tài khoản được sử dụng để thu thập dữ liệu rất gắt gao, dễ dàng bị chặn hoặc khóa
các tài khoản này. Ngồi ra, việc bảo mật thơng tin với các tài khoản trên Facebook
để biết được mối liên hệ giữa những người dùng cũng là một vấn đề đáng lưu tâm

do các tài khoản thường để dưới dạng riêng tư, không công khai các thông tin cá
nhân.
Đối với bài toán xác định các nút ảnh hưởng trên mạng xã hội, các nhà khoa học
đã nghiên cứu và đề xuất nhiều thuật toán với các hướng tiếp cận khác nhau để
giải quyết [11]. Một trong số những hướng tiếp cận được nhiều nhà nghiên cứu áp
dụng đó là việc xác định tập hợp các nút ảnh hưởng trong mạng dựa trên việc xếp
hạng các nút trong mạng theo điểm được xác định bằng độ đo trung tâm của mỗi
nút. Dựa trên các nghiên cứu từ các thực nghiệm khác nhau, có rất nhiều độ đo
trung tâm được đề xuất. Các độ đo theo hướng tiếp cận này được chia thành 4 loại
bao gồm: độ đo trung tâm dựa trên thông tin cục bộ, độ đo trung tâm dựa trên thông
tin bán cục bộ, độ đo trung tâm dựa trên thông tin tồn cục và độ đo kết hợp.
Ví dụ, độ đo trung tâm dựa trên hệ số bậc (Degree Centrality - DC) [12] xác định
số lân cận của nút để đánh giá tầm ảnh hưởng. Độ đo DC cho rằng một nút có
nhiều lân cận sẽ có độ ảnh hưởng nhiều hơn. Cịn với, thuật tốn PageRank (PC)
[13] khơng chỉ xem xét số lượng lân cận mà cịn tính đến độ ảnh hưởng của các
lân cận như thế nào nữa. Thuật toán PageRank xác định rằng tầm ảnh hưởng của
một nút có thể được ảnh hưởng đến các nút khác có kết nối với nó, vì các nút có
kết nối với các nút có ảnh hưởng cũng có thể khiến các nút đó có ảnh hưởng nhiều
hơn. Đây là những độ đo trung tâm dựa trên thông tin cục bộ, nó chỉ tận dụng thơng
tin của các lân cận gần nhất và bỏ qua thơng tin tồn cục, dẫn đến độ chính xác
thấp, nhưng chúng phù hợp với các mạng quy mô lớn do độ phức tạp đơn giản,
dẫn đến chi phí tính tốn thấp.
Để giải quyết hạn chế việc tập trung vào thông tin cục bộ của mạng, một số thuật
toán khác đo lường mức ảnh hưởng của các nút dựa trên thơng tin tồn cục của
mạng được đề xuất có thể kể đến độ đo trung tâm dựa trên trung gian (Betweeness
Centrality - BC) hay độ đo trung tâm dựa trên sự lân cận (Closeness Centrality CC) [14]. Độ đo trung tâm dựa trên sự lân cận xác định rằng khoảng cách trung
bình giữa một nút và các nút khác trong mạng càng ngắn thì ảnh hưởng của nút
càng lớn. Các độ đo này giúp độ chính xác cao hơn, nhưng lại không phù hợp với
các mạng quy mơ lớn do sự phức tạp trong việc tính tốn.
Các độ đo trung tâm dựa trên thông tin cục bộ và độ đo trung tâm dựa trên thơng

tin tồn cục có những ưu điểm và hạn chế khác nhau. Vậy nên, các độ đo trung
tâm dựa trên thông tin bán cục bộ, được coi khắc phục được các hạn chế của 2 loại
độ đo trên, đã được nghiên cứu và đề xuất trong những năm gần đây. Chúng có độ
chính xác cao và thời gian tính tốn thấp khi xem xét thêm thông tin của nhiều hơn
của các lân cận của nút. Ví dụ như độ đo LC [15], nó xem xét đến thông tin của cả
lân cận cấp 1 và lân cận cấp 2 của mỗi nút để tính điểm số. Tuy nhiên, độ đo này
có hạn chế khi bỏ qua các kết nối giữa các lân cận, do đó độ đo LSC [16] đề xuất
kết hợp hệ số phân cụm cục bộ để giải quyết hạn chế trên.
4
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Hiện nay, để tránh sự mất cân bằng khi chỉ tập trung vào thơng tin cục bộ hay
thơng tin tồn cục, ta cần phải tính đến cả hai yếu tố này của mạng. Tuy nhiên, các

phương pháp xác định nút ảnh hưởng truyền thống trước đây thường khơng tính
đến đồng thời thơng tin tồn cục và cục bộ của mạng, dẫn đến mất mát thơng tin
do đó kết quả cuối cùng thường bị ảnh hưởng rất nhiều. Một số nhà nghiên cứu
khác đã phát hiện ra rằng việc kết hợp nhiều độ đo có thể đạt được kết quả đánh
giá mức độ ảnh hưởng của nút tốt hơn so với việc chỉ xem xét một độ đo duy nhất.
Nghiên cứu [17] đã áp dụng TOPSIS để xác định các nút có ảnh hưởng và kết hợp
nó với phân tích quan hệ xám để xếp hạng tầm quan trọng của các nút trong mạng
phức hợp. Một số các độ đo khác có thể kể đến như độ đo GSM [18], độ đo dựa
trên mơ hình lực hấp dẫn (Gravity Model) [19]. Độ đo dựa trên mơ hình lực hấp
dẫn dựa vào công thức lực hấp dẫn Newton, xem xét đến tầm ảnh hưởng của các
lân cận cũng như là thông tin về đường đi giữa các nút, tuy vậy, việc tính tốn này
lại gây khó khăn trong trường hợp mạng trở nên phức tạp hơn. Để giải quyết vấn
đề khó khăn trong việc dữ liệu lớn và mạng phức tạp, một thuật tốn khác được đề
xuất có tên là thuật tốn GSM. Nó khơng chỉ xem xét ảnh hưởng của chính nút
trong mạng mà cịn tập trung vào ảnh hưởng tồn cục của các nút nhằm tính tốn
điểm ảnh hưởng của các nút trong mạng. Các phương pháp sử dụng kết hợp nhiều
độ đo này đã được chứng minh là hướng nghiên cứu đầy hứa hẹn để đánh giá ảnh
hưởng của các nút. Tuy nhiên, vẫn còn một số hạn chế trong các phương pháp này,
chẳng hạn như một số phương pháp dựa trên các thơng tin tồn cục trong q trình
đánh giá, dẫn đến độ phức tạp tính tốn cao, không phù hợp với các mạng xã hội
phát triển nhanh hiện nay. Hay trong một số phương pháp, đóng góp của mỗi độ
đo được xem là bằng nhau hoặc trọng số của các độ đo khác nhau được đặt theo
cách thủ công, điều này dẫn đến việc cải thiện hiệu suất của thuật tốn vẫn cịn có
nhiều hạn chế.
Ngồi ra đối với biểu diễn các nút trong mạng thì nhúng mạng (network
embedding) là một trong số các kĩ thuật thường được sử dụng. Nhúng mạng bản
chất là tìm các đặc trưng của nút, sau đó ánh xạ để chuyển đổi mỗi nút trong mạng
thành một biểu diễn dựa trên vectơ. Biểu diễn dựa trên vectơ này có thể được sử
dụng như một đặc trưng của các bài toán khác nhau trên đồ thị, chẳng hạn như
phân loại, phân cụm, dự đốn liên kết và trực quan hóa. Một trong những lợi ích

chính của kĩ thuật nhúng mạng là biểu diễn vectơ và kết quả này có thể được đưa
trực tiếp vào hầu hết các mơ hình học máy để giải quyết các bài toán cụ thể. Các
phương pháp ban đầu để học các biểu diễn nút tập trung chủ yếu vào phân rã ma
trận, lấy cảm hứng trực tiếp từ các kỹ thuật cổ điển để giảm kích thước. Tuy nhiên,
các phương pháp này lại tốn rất nhiều chi phí tính tốn. Các cách tiếp cận gần đây
nhằm mục đích tìm hiểu cách nhúng các nút dựa trên các bước đi ngẫu nhiên.
DeepWalk là thuật toán tiên phong trong các thuật toán nhúng mạng [20], áp dụng
Word2vec [21] cho các chuỗi đi bộ ngẫu nhiên, do đó tạo ra các vectơ biểu diễn
với số chiều nhỏ của các nút. Một nghiên cứu khác đề xuất một thuật toán lấy mẫu
cạnh để tối ưu hóa hàm mục tiêu cho độ tương tự bậc nhất và độ tương tự bậc hai,
sau đó thu được biểu diễn vectơ của các nút. Node2vec [22] mở rộng thuật toán
5
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

DeepWalk bằng cách thay đổi cách tạo chuỗi đi bộ ngẫu nhiên, đưa tìm kiếm đầu
tiên theo chiều rộng và tìm kiếm đầu tiên theo chiều sâu vào quá trình tạo chuỗi đi
bộ ngẫu nhiên và xem xét thông tin cục bộ và thơng tin tồn cục của mạng để đại
diện cho các nút.
Khác với cách tiếp cận truyền thống chỉ xác định ảnh hưởng của nút bằng độ đo
trung tâm, một hướng tiếp cận khác dựa trên cơ chế biểu quyết cũng đang được
nhiều nhà nghiên cứu phát triển. Ý tưởng cơ bản là xác định một nhóm các nút có
ảnh hưởng, được gọi là các nút hạt giống, chúng phân phối trong các khu vực khác
nhau, rải rác trong tồn mạng. Nghiên cứu [23] đề xuất thuật tốn VoteRank dựa
trên cơ chế biểu quyết để xác định các nút có ảnh hưởng trong mạng. Dựa trên
thuật tốn VoteRank, nghiên cứu [6] đã đề xuất thuật toán EnRenew, thuật tốn
này tính đến thơng tin entropy của các nút để chọn các nút hạt giống và thu được
một hiệu quả tốt hơn so với thuật toán ban đầu. Nghiên cứu [24] đã trình bày thuật
tốn LAPSOIM tối ưu hóa vấn đề tối đa hóa ảnh hưởng bằng cách sử dụng tối ưu
hóa tập hợp các nút hạt giống phân phối trên toàn mạng dựa trên cơ sở dữ liệu học
tự động. Giữa các phương pháp theo hướng tiếp cận biểu quyết, VoteRank vẫn thu
hút được một số sự quan tâm của nhiều nhà nghiên cứu vì nó cung cấp một giải
pháp nhanh chóng và thuận tiện cho vấn đề tối đa hóa ảnh hưởng [6, 25]. Sau đó,
nghiên cứu [26] đã đề xuất cải tiến thuật toán VoteRank gọi là VoteRank++. Thuật
toán này cải thiện ở 2 vấn đề (1) khả năng biểu quyết của một nút có liên quan đến
tầm quan trọng của nó trong q trình khởi tạo và (2) mỗi nút có thể biểu quyết
cho các lân cận của nó với mỗi điểm số khác nhau trong q trình biểu quyết.
Ngồi ra, để giảm thời gian tính toán, thuật toán chỉ cập nhật một phần của các nút
trong mỗi lần lặp thay vì tất cả các nút. Sau đó lặp đi lặp lại để có thể tìm ra được
tập hợp các nút ảnh hưởng trong mạng.
Từ những nghiên cứu trên, ta có thể thấy rằng độ đo trung tâm là một thước đo
quan trọng để xác định các nút ảnh hưởng cũng như mức ảnh hưởng của các nút
lân cận cũng là những yếu tố khiến nút đó trở nên có ảnh hưởng hơn. Hơn nữa, các
liên kết giữa các lân cận cũng có tác động đến khả năng lan truyền của nút, càng

có nhiều kết nối giữa những nút lân cận, thì tầm ảnh hưởng của nút đó sẽ càng cao.
Bên cạnh đó, việc kết hợp các độ khác nhau và xây dựng trọng số cho mỗi độ đo
cũng là hướng nghiên cứu giúp cho việc xác định được tập hợp nút ảnh hưởng trở
nên chính xác hơn.
Có thể thấy việc xác định các nút ảnh hưởng trong mạng là một bài tốn có ý nghĩa
thực tiễn rất lớn nhưng mặt khác nó cũng chứa đựng nhiều khó khăn và thách thức.
Một số khó khăn gặp phải để giải quyết bài tốn như:
• Các phương pháp đánh giá tầm ảnh hưởng hiện tại chưa khai thác hết được
các khía cạnh ảnh hưởng của các nút.
• Dữ liệu trên mạng xã hội sẽ cập nhật thường xuyên, thay đổi liên tục và
khơng có theo một cấu trúc cụ thể, do đó việc áp dụng các thuật tốn sẽ
phức tạp hơn rất nhiều.

6
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep

Từ những khó khăn trong việc mơ hình hóa dữ liệu trên mạng xã hội cũng như
những ưu điểm và hạn chế của từng nghiên cứu liên quan trong việc giải quyết bài
toán xác định các nút ảnh hưởng trong mạng xã hội, luận văn lựa chọn “Đề xuất
mơ hình sử dụng cơ chế biểu quyết kết hợp với độ đo trung tâm cho bài toán xác
định các nút ảnh hưởng trên mạng xã hội” bao gồm 2 phần:
• Đề xuất thuật toán giải quyết bài toán xác định nút ảnh hưởng trên mạng xã
hội.
• Thu thập, xử lý và mơ hình hóa dữ liệu thu thập từ mạng xã hội Facebook
Với thuật toán đề xuất, dựa trên các khảo sát và những đánh giá ở trên, luận văn
nghiên cứu và đề xuất thuật toán mới gọi tên là EAVoterank++ theo cơ chế biểu
quyết và kết hợp các độ đo trung tâm có trọng số. Ta có thể thấy thơng tin cục bộ
bao gồm hệ số bậc, hệ số phân cụm và thơng tin về vị trí của nút là những thơng
tin đóng vai trị quan trọng trong việc xác định các nút có ảnh hưởng, nhưng các
phương pháp truyền thống hầu như lại không xem xét đến thông tin lân cận một
cách tồn diện. Trong thuật tốn này, luận văn xem xét kết hợp 3 độ đo trên cũng
như thông tin lân cận của chúng trong việc xây dựng cơng thức tính điểm khả năng
biểu quyết. Đối với hệ số bậc và độ đo phân rã k-shell, ta sẽ xem xét đến các chỉ
số này đối với cả các lân cận cấp 1 của nó, bởi một nút có tầm ảnh hưởng hơn khi
có liên kết với các nút có tầm ảnh hưởng khác. Hệ số phân cụm phản ánh mật độ
kết nối giữa các lân cận và nút cần xét. Nó là một chỉ số quan trọng để phản ánh
khả năng lan truyền của nút. Thuật toán đề xuất xem xét hai khía cạnh của hệ số
phân cụm: hệ số phân cụm của nút và các lân cận cấp 2. Hệ số phân cụm của nút
có ảnh hưởng tiêu cực đến khả năng lan truyền (hệ số phân cụm càng lớn thì nút
càng ít ảnh hưởng), trong khi hệ số phân cụm của các lân cận cấp hai có ảnh hưởng
tích cực đến khả năng lan truyền (hệ số phân cụm của các nút lân cận cấp 2 càng
lớn thì nút càng ảnh hưởng). Tóm lại, các cải tiến của thuật toán đề xuất
EAVoteRank++ giải quyết bài toán xác định nút ảnh hưởng bao gồm:

• Xây dựng cơng thức tính điểm khả năng biểu quyết bằng việc kết hợp thơng
tin bao gồm hệ số bậc, vị trí trong mạng của nút và hệ số phân cụm cục bộ.
Ngoài ra, cơng thức xây dựng cịn xem xét đến các lân cận của nút, làm tăng
thêm tính chặt chẽ của việc xác định điểm khả năng biểu quyết. Bên cạnh
đó, thuật tốn cịn đề xuất đánh trọng số của mỗi độ đo trên bằng mơ hình
lý thuyết entropy để việc xác định điểm khả năng biểu quyết của mỗi nút
đạt hiệu quả tối ưu nhất.
• Áp dụng cách tính điểm ảnh hưởng (điểm biểu quyết) bằng việc kết hợp
điểm ảnh hưởng trực tiếp với điểm ảnh hưởng gián tiếp của nút. Cùng với
đó, xây dựng cơng thức tính hệ số tỉ lệ lân cận giữa hai nút trong việc xác
định điểm ảnh hưởng.
• Thuật tốn đề xuất lựa chọn các nút ảnh hưởng phân phối trong toàn mạng
bằng cơ chế giảm điểm khả năng biểu quyết của các lân cận cấp 1 và cấp 2
của các nút hạt giống (nút được chọn là nút ảnh hưởng) trong mỗi vòng lặp
để giảm sự chồng chéo của các vùng có ảnh hưởng của tập hợp nút này.
7
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Với phần mơ hình hóa dữ liệu thu thập từ mạng xã hội, luận văn lựa chọn mạng xã
hội Facebook – đây là nền tảng mạng xã hội đang được sử dụng rộng rãi nhất trong
nhiều năm gần đây để thu thập, xử lí và tổ chức dữ liệu này dưới dạng đồ thị - thể
hiện các hoạt động của người dùng trên nền tảng này. Tiếp đó, để chuyển đổi đồ
thị này thành đồ thị đồng nhất, luận văn đề xuất phương pháp mơ hình hóa dữ liệu
thu thập thành đồ thị đồng nhất bằng phương pháp xây dựng đồ thị tri thức dựa
trên tương tác người dùng. Đồ thị sau khi được mơ hình hóa sẽ biểu diễn các mối
quan hệ chi tiết giữa người dùng trong mạng cùng với đó sẽ thuận lợi trong việc
áp dụng các thuật toán xác định nút ảnh hưởng khác nhau.
Để chứng minh tính hiệu quả của thuật tốn được đề xuất, luận văn sử dụng mơ
hình mơ phỏng lan truyền dịch bệnh SIR và các chỉ số đánh giá bao gồm quy mô
lan truyền, quy mô lan truyền cuối và trung bình khoảng cách giữa các nút hạt
giống. Kết quả thử nghiệm trên 7 bộ dữ liệu chứng minh hiệu quả của phương pháp
đề xuất về khả năng tìm kiếm các nút ảnh hưởng trong mạng. Ngồi ra, để đảm
bảo tính thực tiễn cũng như khả năng triển khai thực tế của thuật tốn đề xuất, luận
văn cịn thử nghiệm thuật toán trên tập dữ liệu thu thập từ mạng xã hội Facebook.
Dữ liệu thu thập trên được xử lý và xây dựng thành đồ thị đồng nhất, sau đó áp
dụng thuật tốn đề xuất để tìm ra tập hợp các nút có tầm ảnh hưởng. Kết quả thực
nghiệm cho thấy, thuật tốn đề xuất có hiệu quả và đạt độ chính xác cao hơn so
với các thuật tốn khác.
Mục đích của luận văn
Mục đích chính của luận văn “Đề xuất mơ hình sử dụng cơ chế biểu quyết kết hợp
với độ đo trung tâm cho bài toán xác định các nút ảnh hưởng trên mạng xã hội” là
tìm hiểu, nghiên cứu và xây dựng thuật toán xác định tập hợp các nút ảnh hưởng
cũng như đề xuất xuất phương pháp mơ hình hóa dữ liệu từ mạng xã hội để giải

quyết bài tốn tối đa hóa ảnh hưởng. Các vấn đề mà luận văn giải quyết bao gồm:
• Xác định ý nghĩa và giá trị thực tiễn mà bài toán xác định nút ảnh hưởng
mang lại.
• Tìm hiểu, khảo sát các hướng nghiên cứu liên quan trong việc giải quyết
bài tốn xác định nút ảnh hưởng trên mạng xã hội.
• Xây dựng bộ dữ liệu thu thập từ mạng xã hội Facebook bằng công nghệ thu
thập dữ liệu trên tập danh sách người dùng có sẵn, sau đó đề xuất phương
pháp mơ hình hóa chuyển đổi dữ liệu thu thập được thành đồ thị đồng nhất.
• Nghiên cứu và đề xuất thuật toán cải tiến cho bài toán các nút ảnh hưởng
trong mạng xã hội đạt hiệu quả chính xác cao, tốt hơn so với các nghiên cứu
khác.
• Áp dụng thuật toán đề xuất trên bộ dữ liệu mạng xã hội đã xây dựng, ngồi
ra thực nghiệm độ chính xác của thuật toán đề xuất trên các bộ dữ liệu mạng
phức hợp đảm bảo tính khách quan và đa dạng của bộ dữ liệu. Tính tốn độ
8
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

chính xác bằng các mơ hình mơ phỏng tầm ảnh hưởng, chỉ số đánh giá hiệu
quả cho bài toán xác định nút ảnh hưởng và so sánh kết quả với các thuật
toán, phương pháp xác định các nút ảnh hưởng khác để chứng minh tính
hiệu quả của thuật tốn đề xuất.
Phạm vi nghiên cứu
Từ các ứng dụng thực tiễn của bài tốn xác định các nút có tầm ảnh hưởng trong
mạng, luận văn sẽ thu thập dữ liệu các bài viết từ trang cá nhân của những cá nhân
trong tập dữ liệu có sẵn (danh sách người ảnh hưởng và danh sách cá nhân thông
thường) và tổ chức lại dữ liệu dưới dạng đồ thị thể hiện các hoạt động của người
dùng trên nền tảng này. Sau đó, luận văn đề xuất phương pháp mơ hình hóa dữ liệu
thu thập thành đồ thị đồng nhất bằng phương pháp xây dựng đồ thị tri thức dựa
trên tương tác người dùng và áp dụng thuật toán đề xuất EAVoteRank++ để xác
định tập hợp các nút hưởng có trong mạng. Ngồi ra, luận văn bổ sung thêm các
thực nghiệm trên các bộ dữ liệu mạng phức hợp thường được sử dụng trong các
bài toán xác định nút ảnh hưởng như bộ dữ liệu về hệ thống mạng máy bay ở US
năm 2010, mạng lưới những nhạc sĩ Jazz, … Chi tiết các bộ dữ liệu này được trình
bày ở phần sau. Để tính tốn độ chính xác và hiệu quả của thuật tốn, luận văn áp
dụng các mơ hình mơ phỏng lan truyền và các chỉ số đánh giá thường được sử
dụng trong bài tốn này, sau đó so sánh với các thuật toán, phương pháp xác định
các nút ảnh hưởng liên quan để chứng minh tính chính xác và hiệu quả của thuật
tốn đề xuất.
Nội dung luận văn
Nơi dung của luận văn “Đề xuất mơ hình sử dụng cơ chế biểu quyết kết hợp với
độ đo trung tâm cho bài toán xác định các nút ảnh hưởng trên mạng xã hội” chia
làm 5 phần:
Phần 1. Giới thiệu: Giới thiệu bài toán xác định nút ảnh hưởng, các nghiên

cứu khoa học liên quan trong việc giải quyết bài tốn cũng như mục đích, phạm
vi, đóng góp nghiên cứu của luận văn.
Phần 2. Cơ sở lý thuyết: Trình bày lý thuyết liên quan đến đồ thị, các thuật
toán, phương pháp xác định nút ảnh hưởng cũng như các phương pháp đánh giá
các thuật toán này.
Phần 3. Mơ hình đề xuất: Đề xuất mơ hình xác định nút ảnh hưởng trên
mạng xã hội bao gồm việc mơ hình hóa dữ liệu thành đồ thị đồng nhất bằng phương
pháp xây dựng đồ thị tri thức dựa trên tương tác người dùng từ dữ liệu thu thập từ
mạng xã hội Facebook và diễn giải chi tiết các bước tính tốn ở thuật tốn đề xuất
sử dụng cơ chế biểu quyết kết hợp với độ đo trung tâm.
Phần 4. Thực nghiệm, đánh giá: Trình bày các thơng tin về bộ dữ liệu sử
dụng, cấu hình thực nghiệm thuật toán cũng như các kết quả thực nghiệm của thuật
toán đề xuất và tính tốn độ chính xác và hiệu quả của thuật toán đề xuất so sánh
với các thuật toán khác.

9
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

Phần 5. Kết luận: Các kết quả đạt được và hướng phát triển tương lai của
luận văn với bài toán xác định nút ảnh hưởng.

10
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep

CHƯƠNG 1. CƠ SỞ LÝ THUYẾT
1.1 Lý thuyết về đồ thị

Định nghĩa
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này. Với
cách biểu diễn cơ sở, đồ thị được vẽ bởi tập hợp các nút và các mối liên kết giữa
các nút được mô tả bởi công thức 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸) với:
•
•
•
•

•

𝐺𝐺 gọi là đồ thị.

𝑉𝑉 là tập hợp các nút có trong đồ thị.

𝐸𝐸 là tập hợp các cạnh kết nối các nút của đồ thị.

𝑒𝑒ij = �𝑣𝑣𝑖𝑖 , 𝑣𝑣𝑗𝑗 � ∈ 𝐸𝐸 là biểu diễn các cạnh 𝑒𝑒 ∈ 𝐸𝐸 có trong đồ thị nối từ nút 𝑣𝑣𝑖𝑖
tới nút 𝑣𝑣𝑗𝑗 .

𝑁𝑁(𝑣𝑣) = {𝑢𝑢 ∈ 𝑉𝑉|(𝑣𝑣, 𝑢𝑢) ∈ 𝐸𝐸 là các nút kề u hay còn gọi là các nút lân cận
có chung cạnh với nút v.

Một số loại đồ thị
Đồ thị không đồng nhất và Đồ thị đồng nhất
Đồ thị đồng nhất: là các đồ thị đơn, khi các nút và cạnh của đồ thị chỉ biểu diễn
duy nhất 1 đối tượng, ví dụ nút biểu diễn con người và cạnh biểu diễn những người
là bạn bè với nhau.
Đồ thị khơng đồng nhất: là các đồ thị có nút và cạnh thể hiện nhiều mối liên kết
giữa các đối tượng với nhau, liên quan mật thiết tới 1 khái niệm rộng hơn là đồ thị

tri thức.
Đồ thị vô hướng: có các cạnh khơng có hướng. Đồ thị 𝐺𝐺 là tập hợp nút và các cặp
cạnh khơng có thứ tự được mô tả bởi 𝐺𝐺 = (𝑉𝑉, 𝐸𝐸), trong đó:

• 𝑉𝑉: tập các đỉnh hoặc nút.
• 𝐸𝐸: tập các cặp không thứ tự chứa các đỉnh phân biệt, được gọi là cạnh. Hai
đỉnh thuộc một cạnh liên kết được gọi là các đỉnh đầu và đỉnh cuối của cạnh
đó.

Với đồ thị vô hướng, một liên kết từ 𝑣𝑣𝑖𝑖 tới 𝑣𝑣𝑗𝑗 cũng giống như một liên kết từ 𝑣𝑣𝑗𝑗 tới
𝑣𝑣𝑖𝑖 . Do đó 𝑒𝑒𝑖𝑖𝑖𝑖 = 𝑒𝑒𝑗𝑗𝑗𝑗

Đồ thị có hướng: có các cạnh có hướng. Đồ thị có hướng 𝐺𝐺 được định nghĩa là
tập hợp nút và cặp cạnh có hướng được cho bởi 𝐺𝐺 = (𝑉𝑉, 𝐴𝐴) trong đó:
• 𝑉𝑉: là tập các đỉnh hoặc nút có trong đồ thị
• 𝐴𝐴: tập các cặp có thứ tự chứa các đỉnh. Những cặp này được gọi là các cạnh
có hướng hoặc cung. Một cạnh 𝑒𝑒 = (𝑥𝑥, 𝑦𝑦) được coi là có hướng từ 𝑥𝑥 tới 𝑦𝑦,
𝑥𝑥 được gọi là điểm đầu/gốc và 𝑦𝑦 được gọi là điểm cuối/ngọn của cạnh.

Với đồ thị có hướng, khi có một chiều xác định từ nút 𝑣𝑣𝑖𝑖 tới 𝑣𝑣𝑗𝑗 thì sẽ chỉ tồn tại
liên kết cạnh 𝑒𝑒𝑖𝑖𝑖𝑖 , không giống như trong đồ thị vô hướng.

11
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz
luan van hay luan van tot nghiep do an to nghiep docx 123docz

Đề xuất mô hình sử dụng cơ chế biểu quyết kết hợp với độ đo trung tâm cho bài toán xác định các nút ảnh hưởng trên mạng xã hội

Tài liệu liên quan

Tài liệu bạn tìm kiếm đã sẵn sàng tải về