B GIÁO DO
I HC LC HNG
    NH 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 LU THÔNG TIN 
L ng, ngoi tr các kt qu tham kho t các
công trình khác và mt s lý thuyt trên internet   ngun
tham kho trong luc trình bày trong lu
này là do chính tôi thc hin ni dung nào ca lun
c n ly bng cp  ng này hong khác.

Ngày tháng 
 nh
LI C

Tôi xin gi ln Thy Cô, bng
n tr tôi rt nhiu v kin th
tinh thn trong quá trình tôi thc hin lu

tp d liu thc t.
DANH MC NHNG T VIT TT TRONG LU

BFS : Breadth First Search
CNTT : Công Ngh Thông Tin
JUNG : Java Universal Network / Graph Framework
MXH : Mng Xã Hi
SNA : Social Network Analysis

DANH MC HÌNH
Hình 1.1: Mô t mng xã hi. 1
Hình 2. 1: Mô hình mng Xã hi (Social Network) 6
Hình 2.2: Mô hình mng xã hi Facebook. 7
Hình 2.3: Mô hình các thành viên ca mng Twitter. 8
Hình 2.4: Mô hình phân bit Follower và Friend trong mng Twitter 10
Hình 2. 5: Giao din chính ca mng Facebook 11
i truy cp Facebook trong 1 tun t n
04/08/2012 (ngun socialbakers.com) 11
Hình 2.7: Biu din tnh trong mô hình mng. 13
Hình 2.8: Din t  th  th ng 14
Hình 2.9: Ví d ng 15
Hình 2.10: Mô t các thành viên trong mng xã hi 18
Hình 2.11: Ví d m th gnh 19
Hình 2.12: M th g tìm Degree Centrality 20

Hình 4.16: Tính Degree Centrality 64
Hình 4.17: Tính Betweenness Centrlity 65
Hình 4.18 Tính Closeness Centrality 65
Hình 4.19: Hin th kt qu c 65
Hình 4.20: Mô t tp d liu thc nghim 69
Hình 4.21: Giao din kt qu cui cùng c 67
DANH MC BNG
B nh sau khi tính toán 20
B  th gnh 21
Bng 2.3:   th 25
Bn nht ca tt c  th 26
B Closeness Centrality c th 29
Bng 2.6: M Closeness Centrality ca mng 36
Bng 3.1: Cách thc duy th bng Thut toán BFS 51
Bng 4.1: Cách th d li th bng Danh sách liên thuc. 61
Bng 4.2: Cách th d li th bng Danh sách liên k 62
MC LC
*
NG QUAN 1
1.1. Gii thi tài 2
1.2. Lý do ch tài 3

d. Thut gin nht t mn tt c nh còn
l th. 48
T K XÂY DC
NGHIM 53
4.1. Gii thiu. 53
4.1.1. n 1: Thu thp và rút trích d liu 53
4.1.2. n 2: X lý d liu 54
4.1.3. n 3: 58
4.2. T ch d liu. 58
4.2.1. Gii thiu 58
4.2.2.  d liu. 59
a. Cu trúc ma trn k 59
b. Danh sách liên kt 60
4.3. Xây dng h thng gii quyt bài toán tìm phn t chính yu. 63
4.4. Kt qu thc nghim. 66
T LUNG PHÁT TRIN 69
5.1. Nh tài 69
5.2. Hn ch c tài, cách khc phc 70
5.3. ng phát trin 70
TÀI LIU THAM KHO -1-
NG QUAN

các nhóm xã h
ng xã hi" (Social Network Analysis -
c nghiên cu và ng dng ngày càng nhi
cu xã hi hc nói riêng và khoa hc xã hi nói chung. Ti Vi
pháp phân tích mng xã hi còn khá mi mc ng d
pháp phân tích này còn khá hn ch.
     nh phn t chính yu
(Key player) hay còn gi là nhng tác nhân quan trng trong mng xã hi.
Phn t chính yu là các phn t trong mc xem là quan trng xét
theo mu ki nói rng, key player là nhng node có kh
u khin lung thông tin, là nhng node ni bt nht và có tm nh
n các node khác trong mng xã hi.
  nh các mi liên kt ca mt
 th. Thông qua Centrality, ta có th phát hic thc th nào
trong mng là quan trng và có tm n nhng thc th khác.
Dn nhnh ca m th có
ng. Có th xem mng xã h th ng, các thc th trong
mnh (node) c th, mi quan h gia các thc th trong mng
là các cnh (link) c th.
t ra là xây dng thun nh
nh c th, t nh thc th nào là quan trng nht, có tm nh
ng ln nht ti các thc th khác trong mng xã hi.
Các v t ra n
-3-
 Các khái nim v mng xã h
Link, Edge, Clique,
 Cu trúc d lia mng xã hc t ch

này là:
- Nghiên cu v mng xã hi (Social Network).
- Tìm hiu v Key player trong mng xã hi.
- Tìm hiu v các lo ng xã hi.
- Tìm hiu v k thut phân tích mng xã hi.
- Nghiên cu và phát trin thunh tp các phn t chính
yu trong mng xã hi d 
- c nghim da trên:
o Mng tham kho các bài báo trên Internet.
o Mng liên kt các trang web (web link)
- Hin thc thut toán tìm Key players ba.

1.4. Phm vi nghiên cu c tài
 tài tp trung vào tìm hiu và nghiên cu các v sau:
 Tìm hiu v mng xã hi và các v liên quan.
 Trin khai xây dng c nghim, xây dng ng dng
và tt gii thut cho bài toán n nht
trong mng liên kt các websites.
 Th nghii thut trên b d liu thc t
C th tài thc hin các ni dung sau:
 Nghiên cu các mô hình mng xã hi truyn thông.
 Tìm hihân tích mng xã hi.
 Tìm hiu mt s phn mm phân tích mng xã hi.
 Tìm hiu thun nh th ng
và vng) và các lo . T xây d
trình mô phng thut toán áp dnh phn t
chính yu trong mng xã hi.

-7-
 S  i c      
Youtube, Google+n cho mng xã hi ngày càng tr
ng, ph bi
- Nói mt cách khác, MXH là mng tp hp các công c, dch v trc
tuyn t - email, dio lun , blogs, chat, các
trang mng xã hi, các trang chia s hình n tr s
i gia nhi s dng. [8]

Hình 2.2: Mô hình mng xã hi Facebook.
Ngun: http://julianhopkins.net
2.2. Các Mng Xã hi thông dng hin nay.
2.2.1. Mng xã hi Twitter
a. Gii thiu tng quan
Twitter là mt mng xã hi vc chia s theo thi gian
thc, cho phép m i giao tip b   i nhng mu tin
ngn (ch 140 ký t).
-8-
T nhng li ích thc t rt ln nên vic s dng Twitter cho Internet
u mà bt c mt marketer n phi thc hin, nó
giúp cho vic kt ni và chia s n các khách hàng cùng s
dng Twitter (ngun http://forum.digitalmarketing.vn).
c thành lp  c s dng bi
nhi trong hu hc trên th gii. Dch v có sn trong
 p tc cp nht thêm.

Hình 2.3: Mô hình các thành viên ca mng Twitter.

digitalmarketing.
Listi dùng trong mi nhóm, nhóm có
th do bn t to.
Search   i dùng tìm kim các Tweet có liên quan
hoc cha cm t mà h m.
Timeline: Gia Facebook, Timeline hin th các
tweet ca bn và ca nhi b.
Trending Topic: Twitter s hin th c cho là 'hot' trong
th m hin ti, bn s th    c hin th
theo khu v ca bn.
-10-
Unfollow c v       ng cách
click vào nút Unfollow), bn s không th nhn các update t i
.

Hình 2.4: Mô hình phân bit Follower và Friend trong mng Twitter
Ngun: Twitter.com
2.2.2. Mng xã hi Facebook
a. Gii thiu tng quan
Facebook là mt website mng xã hi truy cp min phí do công ty
u hành. i dùng có th tham gia các mc
t chc theo thành phng hc và khu v liên kt và
giao tip vi khác. M kt bn và gi tin nhn
cho h, và cp nht trang h  thông báo cho bn bè
bit v chúng. Tên ca website nhc ti nhng cun s 
ghi tên nhng thành viên ca cng campus mà mt s ng i
hc và cao ng ti M n mng, phòng ban,

link, note
Like: Nó là mi, khi
bn click vào tc là b mình Like mt status, bình lun
hoc m các website khác (nu nút Facebook Like
c add vào website này).
Friends: Bn bè ca bn trong Facebook, bn có th yêu cu
kt bn vi mc li, mi có th yêu cu kt
bn vi b giúp bn suggest bn bè cho
i khác, hoc t tìm bn bè cho bn (nu bn mi bu s
dng).
New Feeds    i nht (thông tin, status,
 bn bè và các nhóm xã hi ca bn, nó s c cp
nht theo thi gian.
Tagn din mu
trong mt hình nh, video hoc bài vi  
(ngun http://digitalmarketing.vn/)
2.3. Các khái nin trong vic t chc mng xã hi
Trong phân tích mng xã hi, ta xem xét mng xã h th mng
bao gnh (nodes), các cnh (links). Node biu din tp các tác nhân,
-13-
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.3.1. Tnh
Trong lý thuy th, tp nh còn c gi là tp nút (nodes). Trong
phân tích mng xã hc bip các tác nhân (actors) hay
tp thc th Trong mng xã hi, tnh u
trúc ca các mng xã hi, các thành viên hay các ct nhóm

 th ng  th ng

Hình 2.8: Din t  th  th ng
i v th, mt thành phn quan trrng s ca
cnh. Trng s ca c   nh m
hay tn sut liên kt gi th. i vi các bài toán trong lý
thuy  th, trng s       gii quyt bài toán tìm
n nh th. A
v
B
D
C
E
A
B
D
C
E

Trích đoạn Thuật giải tìm Closeness Centrality Xây dựng hệ thống giải quyết bài toán tìm phần tử chính yếu

---