NGHIÊN CỨU VÀ PHÁT TRIỂN THUẬT
TOÁN TÌM PHẦN TỬ CHÍNH YẾU
TRONG MẠNG XÃ HỘI VÀ ỨNG DỤNG
Học viên : ĐỖ VĂN MẠNH
Giảng viên hướng dẫn : PGS.TS. ĐỖ PHÚC

TRƯỜNG ĐẠI HỌC LẠC HỒNG
KHOA CÔNG NGHỆ THÔNG TIN
ĐỀ TÀI:
1
NỘI DUNG
ỨNG DỤNG CÁC ĐỘ ĐO CENTRALITY TÌM KEY PLAYER
5
GIỚI THIỆU ĐỀ TÀI

1
TỔ CHỨC CỦA MẠNG XÃ HỘI
2
PHÂN TÍCH MẠNG XÃ HỘI
3
CÁC ĐỘ ĐO CENTRALITY TRONG MẠNG XÃ HỘI
4
CHƯƠNG TRÌNH DEMO
6
2
 Phân tích mạng xã hội (Social Network Analysis –
SNA) hiện đang là một trong các chủ đề được
quan tâm nghiên cứu. Phân tích mạng xã hội bao
gồm việc nghiên cứu các quan hệ, kết nối, mẫu
truyền thông và hành vi giữa các nhóm xã hội khác
nhau…

1.
4
 Dựa vào bài toán tìm đường đi ngắn nhất qua các
đỉnh của một đồ thị. Có thể xem mạng xã hội như
một đồ thị, các thực thể trong mạng là các đỉnh
(node) của đồ thị, mối quan hệ giữa các thực thể
trong mạng là các cạnh (link) của đồ thị.
 Bài toán đặt ra là xây dựng thuật toán dựa vào các
độ đo Centrality và đường đi ngắn nhất đi qua các
đỉnh của đồ thị, từ đó xác định thực thể nào là
quan trọng nhất, có tầm ảnh hưởng lớn nhất tới
các thực thể khác trong mạng xã hội.

GIỚI THIỆU ĐỀ TÀI 1.
5
 Trong phân tích mạng xã hội, ta xem xét mạng xã hội
như là đồ thị mạng bao gồm các đỉnh (nodes), các cạnh
(links). Node biểu diễn tập các tác nhân, thực thể, còn
link biểu diễn mối quan hệ (relation) giữa các tác nhân,
thực thể đó:

2
TỔ CHỨC CỦA MẠNG XÃ HỘI
2.
Một đỉnh trong mạng XH
A
B

 Trong Phạm vi của lý thuyết đồ thị và phân tích mạng, có
nhiều biện pháp để nghiên cứu mô hình thông tin liên lạc
cũng như cấu trúc của một mạng xã hội. Trong đó biện pháp
Centrality là một trong các biện pháp được nghiên cứu nhiều
nhất nhằm xác định tầm quan trọng tương đối của một đỉnh
trong đồ thị
 Centrality mô tả vị trí tương đối của một tác nhân trong bối cảnh
của mạng xã hội của mình:
CÁC ĐỘ ĐO TRUNG TÂM TRONG MẠNG
4.
8
1. Độ đo trung tâm theo bậc (Degree
Centrality).
2. Độ đo trung tâm dựa trên trung
gian (Betweenness Centrality).
3. Đo đo trung tâm theo sự lân cận
(Closeness Centrality)
CÁC ĐỘ ĐO TRUNG TÂM TRONG MẠNG
4.
9
 Cho đồ thị G = (V, E) có n đỉnh.
- Degree centrality của một đỉnh chính là tng số
cc liên kết tới đỉnh đó trong đồ thị (tng số cạnh kề
của một đỉnh).
- Trường hợp đồ thị có hướng, degree centrality
được tnh bởi 2 gi trị: in-degree v out-degree.
* In-degree: tng số liên kết từ cc node
khc đến node đang xét.
* Out-degree: tng số liên kết từ node
đang xét đến cc node khc.

vC
D
)deg(
)(
11
VD1: Cho đồ thị gồm 7 đỉnh sau:
Dựa vo công thức 2.1 và 2.2 ta tính
được cc độ đo trung tâm theo bậc
của từng đỉnh như sau

CÁC ĐỘ ĐO TRUNG TÂM TRONG MẠNG
4.
1. Độ đo trung tâm theo bậc (Degree Centrality).
12
 Nhận xt:
 Degree centrality được dng để xc định node no có thể
lan truyền thông tin nhanh, có khả năng gây ảnh hưởng trực
tiếp đến cc node xung quanh.
 Một thực thể có gi trị degree centrality cao:
 Là người hoạt động tch cực hoặc ni tiếng nhất.
 L một đầu nối quan trọng.
 Có một vị tr thuận lợi.
 Có tầm ảnh hưởng quan trọng trong mạng.
CÁC ĐỘ ĐO TRUNG TÂM TRONG MẠNG
4.
1. Độ đo trung tâm theo bậc (Degree Centrality).
13
 Betweenness centrality của một đỉnh được tnh bằng tng số cc đường đi
ngn nhất ngang qua đỉnh đang xt chia cho tng số cc đường đi ngn nhất
của ton mạng. Nói cách khác thì Betweenness Centrality là độ đo dng để xc

Tổng số các đường đi ngn nht t đnh s đến
t (s ≠ v ≠ t).
(2.3)
14
 Công thức tnh Betweenness Centrality theo dạng chun:  Miền giá trị của độ đo này nằm trong khoảng [0 1], node
có giá trị càng lớn thì node đó sẽ có sự ảnh hưởng càng
lớn đến việc phân b cấu trúc của các cụm hay nhóm
trong mạng càng lớn. Một tác nhân có vai trò trung tâm
càng lớn trong mạng thì sẽ có tầm ảnh hưởng lớn trong
việc kiểm soát mọi thông tin trao đi giữa các tác nhân
khác trong mạng. CÁC ĐỘ ĐO TRUNG TÂM TRONG MẠNG
4.
2. Độ đo trung tâm dựa trên trung gian (Betweenness Centrality).
221 /))((
)(
)(
'


nn
vC
vC
B
B

 Dựa vào bảng 1 ta cũng tính được =17.
 Việc tiếp theo ta tnh tng đường đi ngn nhất từ đỉnh s tới
đỉnh t có qua đỉnh v:
 Xt đỉnh v1:không có bất kỳ đường đi từ đỉnh s bất kỳ tới đỉnh t m
đi qua v1. Như vậy
 Xt đỉnh v2: có 3 đường đi có đi qua đỉnh v2, vậy
 Xt đỉnh v3: có 3 đường đi có đi qua đỉnh v3, vậy
 Xt đỉnh v4: có 8 đường đi có đi qua đỉnh v4, vậy
 Xt đỉnh v5 và v6: ta không thấy có bất kỳ đường đi no đi qua 2
đỉnh ny, như vậy v

CÁC ĐỘ ĐO TRUNG TÂM TRONG MẠNG
4.
2. Độ đo trung tâm dựa trên trung gian (Betweenness Centrality).
st
haytsSP


),(
01 )(v
st

33 )(v
st

32 )(v
st

84 )(v
st

 Công thức I:
Closeness centrality được tnh bằng trị nghịch đảo của
tng số khoảng cch ngn nhất từ một đỉnh đến tất cả
cc đỉnh cn lại của đồ thị

CÁC ĐỘ ĐO TRUNG TÂM TRONG MẠNG
4.
3. Độ đo trung tâm theo sự lân cận (Closeness Centrality).
(2.5)
21
 Công thức II:

Với d
G
(v,t) là khoảng cch ngn nhất từ đỉnh v đến t của đồ
thị.

Closeness centrality được tnh bằng bình quân của tng số
khoảng cch ngn nhất từ một đỉnh đến tất cả cc đỉnh còn
lại.

CÁC ĐỘ ĐO TRUNG TÂM TRONG MẠNG
4.
3. Độ đo trung tâm theo sự lân cận (Closeness Centrality).

C
tvd
vC
20
5
1
2
1
2
2
.
),(
)(
\


 vVt
G
C
tvd
vC
170
6
1
3
1
3
3
.
),(

 Như vậy, đỉnh v4 có giá trị Closenness Centrality cao
nhất sẽ là đỉnh có thể truyền đạt, tiếp nhận thông tin từ
cc node khc trong mạng một cch nhanh nhất, ít tốn
thời gian nhất.
 Một thực thể có gi trị closeness centrality tốt nhất :
 Có thể truy xuất nhanh chóng đến cc thực thể khc
trong mạng.
 Có một đường đi ngn nhất đến nhiều thực thể
khc.

CÁC ĐỘ ĐO TRUNG TÂM TRONG MẠNG
4.
3. Độ đo trung tâm theo sự lân cận (Closeness Centrality).
24
 Việc xác định được các giá trị độ đo Centrality đã làm
nền tảng để tiếp cận giải quyết bài toán tìm phần tử
chính yếu (key player) trong mạng xã hội của đề tài.
 Quy trình tìm phần tử chnh yếu được thực hiện thông
qua cc bước cơ bản sau:
 Bước 1: Tính toán tìm tất cả các đường đi ngn nhất từ 1 đỉnh
đến tất cả các đỉnh còn lại trong đồ thị cho tất cả các đỉnh.
 Bước 2: Tính toán độ đo trung tâm theo bậc của tất cả các đỉnh
trong đồ thị.
 Bước 3: Tính toán tìm độ đo trung tâm theo trung gian của tất cả
các đỉnh trong đồ thị.
 Bước 4: Tính toán độ đo trung tâm theo sự lân cận của mỗi đỉnh
trong đồ thị.
 Bước 5: Dựa vào các độ đo trung tâm -> Đưa ra kết quả.