Mô hình phân tán cho thuật giải xác định đỉnh có sức ảnh hưởng lớn nhất trong đồ thị mạng xã hội

 c hi xảy r sự n truy n thông tin tr n mạng 
Hình 1. Mô h nh h ồ thị mạng x hội 
Nguyễn Hồ Duy Tri, Ngô Thanh Hùng 325 
B. Người dẫn dắt dư luận trong mạng xã hội 
1. Sức ảnh hưởng trong mạng x hội 
Sức ảnh hưởng h y còn gọi sức thuyết ph c củ một ỉnh A ối với một ỉnh B ư c nh gi ởi x c suất n 
truy n th nh công ý tưởng từ một ỉnh A ến ỉnh B N i c ch h c nếu trong mạng chỉ c A người ầu ti n chấp nhận 
ý tưởng th B sẽ chấp nhận ý tưởng với x c suất o nhi u ( hông qu n tâm ến thời i m B chấp nhận) 
Trong , sức ảnh hưởng trực tiếp từ ỉnh A ến ỉnh B x c suất n truy n th nh công ý tưởng trực tiếp từ A 
s ng B thông qu cạnh trỏ từ A ến B, ư c i u iễn ằng trọng số củ cạnh vA-B. Ngoài ra, sức ảnh hưởng ri ng phần từ 
 ỉnh A ến ỉnh B thông qu ường i P ại ư c nh gi ởi x c suất n truy n th nh công ý tưởng một c ch gi n tiếp 
từ A s ng B thông qu ường i P trong ồ thị ắt ầu từ A v ết thúc tại B, n sẽ ư c tính ằng tích c c cạnh nằm tr n 
 ường i P. 
PA-B = vA-X × vX-Y ×  × vZ-B 
Tổng qu t t c công thức tính sức ảnh hưởng (h y x c suất truy n ý tưởng th nh công) gi hai ỉnh trong ồ thị 
mạng x hội như s u: 
Gọi hai ỉnh cần tính A, B. Gi A v B c n ường i h c nh u ôi một, nghĩ từng ôi một c ít nhất một 
 i m h c v x c suất truy n th nh công tr n mỗi ường : P1A-B, P
2
A-B, , P
n
A-B 
Công thức tính x c suất n truy n th nh công ý tưởng từ A ến B : 
PA-B = 1 – (1 - P
1
A-B) × (1 - P
2
A-B) ×× (1 - P
n
A-B) 
C c công thức ư c i m nghiệm ằng mô h nh x c suất v cho ộ chính x c rất c o 
Hình 2. Sức ảnh hưởng trực tiếp gi c c ỉnh trong ồ thị mạng x hội 
Đối với c c số iệu cho như trong h nh 2, x c suất n truy n ý tưởng th nh công từ ỉnh 1 v 2 sẽ ư c 
tính như s u: 
X c ịnh c c ường i gi h i ỉnh 1 v 2, t ư c ường i thứ nhất thông qu c c ỉnh 1 – 3 – 5 – 4 – 2 Từ , 
tính ư c sức ảnh hưởng ri ng phần củ ường i n y : 
P
1
1-2 = v1-3 × v3-5 × v5-4 × v4-2 = 0,386 × 0,014 × 0,873 × 0,257 = 0,001212446844 
Đường i thứ h i từ ỉnh 1 ến ỉnh 2 : 1 – 3 – 4 – 2 Sức ảnh hưởng ri ng phần củ ường i n y ư c tính 
như s u: 
P
2
1-2 = v1-3 × v3-4 × v4-2 = 0,386 × 0,434 × 0,257 = 0,043053668 
Sức ảnh hưởng củ ỉnh 1 ến ỉnh 2 sẽ ằng: 
P1-2 = 1 – (1 – P
1
1-2) × (1 – P
2
1-2) = 1 – (1 – 0,001212446844) × (1 – 0,043053668) 
 = 0,0442139145601108 
Vậy x c suất n truy n th nh công ý tưởng từ ỉnh 1 ến ỉnh 2 4,42%. 
2. Người ẫn ắt ư uận 
Trong mạng x hội, người ẫn ắt ư uận thường người hởi ph t c c ý tưởng, c c qu n i m củ ản thân h y 
từ nh ng nguồn h c n ngo i mạng x hội v thông qu nh ng mối i n ết, nh ng mối qu n hệ củ m nh, họ c th n 
truy n chúng v gây ư c ảnh hưởng ớn ến cộng ồng Từ , t c th x c ịnh rằng người ẫn ắt ư uận người c 
tổng sức ảnh hưởng tới tất cả c c ỉnh ớn nhất trong ồ thị mạng x hội. 
Thuật giải t m người ẫn ắt ư uận ư c tr nh y như s u: 
Fore ch ( ỉnh I trong ồ thị): 
Tổng sức ảnh hưởng củ ỉnh I := 0; 
326 MÔ HÌNH PHÂN TÁN CHO THUẬT GIẢI XÁC ĐỊNH ĐỈNH CÓ SỨC ẢNH HƯỞNG LỚN NHẤT TRONG ĐỒ THỊ MẠNG XÃ HỘI 
Foreach ( ỉnh J ≠ I trong ồ thị): 
Tính sức ảnh hưởng củ ỉnh I ến ỉnh J; 
Cộng sức ảnh hưởng củ ỉnh I ến ỉnh J v o tổng sức ảnh hưởng củ ỉnh I; 
End; 
End; 
Đỉnh c tổng sức ảnh hưởng ớn nhất người ẫn ắt ư uận trong mạng x hội; 
C. Thuật giải xác định đỉnh có sức ảnh hưởng lớn nhất trong đồ thị mạng xã hội 
3. Giới thiệu Apache Spark 
Một trong nh ng mô h nh x ý iệu ớn rất phổ iến ư c s ng nhi u trong c c tính to n phân t n 
M pRe uce Đây một mô h nh uồng iệu, n thích h p v ư c ứng ng với số c c công c x ý iệu ớn 
hiện n y Nhưng cũng c nh ng ứng ng hông thích h p hi p ng mô h nh n y, nh ng ứng ng c ạng mô 
h nh ặp Trong mô h nh n y, qu tr nh x ý cứ ư c ặp i ặp ại Lúc mô h nh M pRe uce sẽ ộc ộ nhi u hạn chế 
th hiện qu việc mỗi ần thực thi sẽ một ần truy vấn ại iệu từ ĩ cứng, i u n y m cho cả qu tr nh ị chậm i 
rất nhi u B n cạnh , nh ng iệu ư c s ng nhi u ần trong qu tr nh thực thi hông ư c tải sẵn n ộ nhớ ệm 
 truy vấn m n ư c tải ại ối với mỗi th nh phần công việc ri ng iệt gây n n ộ trễ ớn Chính v thế chúng tôi chọn 
t m hi u v c i ặt x ý iệu ớn tr n fr mewor Ap che Sp r [1] Đư c cải tiến v hắc ph c nh ng huyết i m từ 
mô h nh H oop M pRe uce, Ap che Sp r s ng một ối tư ng ộ nhớ ặc iệt gọi RDD (Resi ient Distri ute 
D t set), n một tập h p chỉ ọc chứ c c oại ối tư ng iệu trong c c ngôn ng ập tr nh h y c c ớp m người 
 ùng tự ịnh nghĩ , ư c phân t n ưu tr ở c c nút tính to n (c c m y con trong mạng tính to n) Tập h p n y cũng c 
 hả năng mở rộng một c ch m m ẻo, tự cân ằng v hả năng chịu ỗi, ph c hồi hi c sự cố xảy r giống như H oop 
Khi th o t c RDD sẽ ư c Sp r tải n ộ nhớ ệm củ nh ng nút tính to n s ng nhi u ần qu c c qu trình tính 
to n song song, chính v thế tốc ộ củ Sp r c th nh nh h n H oop ến gấp 10 ần 
C c ối tư ng RDD trong Ap che Sp r hỗ tr h i oại phép tính ặc iệt : phép iến ổi (tr nsform tions) v 
phép t c ộng ( ctions) [2] C c phép iến ổi tr n RDD thường trả v một RDD mới, n sẽ o gồm c c phép tính c 
 ản s u: map – h m tính to n tr n từng phần t trong RDD, tư ng ứng với mỗi phần t sẽ trả v một ết quả, flatMap - 
h m tính to n tr n từng phần t trong RDD, tuy nhi n ối với mỗi phần t , ết quả trả v c th rỗng hoặc c nhi u h n 
một ết quả, filter – h m ọc c c phần t củ RDD theo i u iện B n cạnh , tr n RDD còn c nh ng phép tính t c 
 ộng, c c phép tính n y thường trả v một gi trị hoặc ghi iệu r hệ thống ưu tr n ngo i C c phép tính t c ộng 
thường ùng o gồm: collect – h m trả v nh s ch tất cả c c phần t trong RDD, count – h m ếm số ư ng c c phần 
t trong RDD, top – h m trả v một số ư ng cho trước c c phần t nằm ở ầu củ RDD, reduce – hàm tính toán song 
song tr n c c phần t củ RDD Do c chế “ zy ev u tion”, một phép tính iến ổi tr n RDD sẽ hông ư c thực thi 
ng y ập tức m chỉ ư c Sp r ghi nhận v o trong met t S u n y, hi chư ng tr nh cần thực thi một phép t c ộng 
tr n RDD, úc Sp r sẽ t m ại trong met t c c phép iến ổi ư c y u cầu trước tr n RDD n y v ần ư t 
thực thi chúng, s u sẽ thực thi phép t c ộng Nguy n nhân hiến Ap che Spar s ng c chế “ zy ev u tion” là 
giảm thi u ư c số quy tr nh tính toán song song phải thực thi, giúp thời gi n x ý ư c rút ngắn h n 
4. Thuật giải tuần tự x c ịnh ỉnh c sức ảnh hưởng ớn nhất trong ồ thị mạng x hội 
Đầu vào của thuật giải: tập ỉnh v tập cạnh củ ồ thị mạng x hội 
Đầu ra của thuật giải: ỉnh c sức ảnh hưởng ớn nhất trong ồ thị 
Ý tưởng: d iệu ồ thị mạng x hội o gồm tập ỉnh v tập cạnh ư c ọc v o hệ thống từ c c tập tin ưu tr Do 
 ặc tính iệu ễ gây ùng nổ số ư ng hi t m iếm ường i gi c c ỉnh, mỗi hi tính to n sức ảnh hưởng củ một 
 ỉnh phải vét cạn tất cả c c ường i từ ỉnh ến tất cả c c ỉnh còn ại, ằng c ch xét ần ư t từng ỉnh, từng cạnh 
một củ ồ thị Nh ng i u m cho việc tính to n tốn rất nhi u chi phí cũng như thời gi n thực thi Trong một iệu 
thực nghiệm m chúng tôi tiến h nh hảo s t, ồ thị mạng x hội o gồm 600 ỉnh, mỗi ỉnh c tối 30 cạnh trỏ ến 
c c ỉnh h c, s u hi tính to n số ư ng ường i tổng cộng trong ồ thị phải x ý n tới h n 3,5 triệu, một con số rất 
 ớn V vậy, tiết iệm chi phí, chúng tôi c i ặt thuật giải theo phư ng ph p tổ h p tất cả c c cạnh t m r to n ộ 
c c ường i c th củ ồ thị Lần ư t c c ường i n y sẽ ư c s ng tính to n sức ảnh hưởng củ từng ỉnh v 
qu t m r ỉnh c sức ảnh hưởng ớn nhất trong ồ thị. 
Thuật giải tuần tự: 
Dự theo nh ng phân tích tr n, thuật giải tuần tự ư c chúng tôi ư r giải quyết i to n x c ịnh ỉnh c sức 
ảnh hưởng ớn nhất trong ồ thị mạng x hội như s u: 
Đọc iệu ầu v o tập ỉnh v tập cạnh; 
Khởi tạo m trận sức ảnh hưởng Tn × n; 
Cập nhật sức ảnh hưởng trực tiếp từ c c cạnh v o Tn × n; 
Nguyễn Hồ Duy Tri, Ngô Thanh Hùng 327 
do 
Tạo ường i c m cạnh từ ường i c m – 1 cạnh v c c cạnh n, tính sức ảnh hưởng ri ng phần củ từng 
 ường i mới; 
Cập nhật sức ảnh hưởng v o m trận Tn × n; 
while (m < n – 1 or hông tạo ư c ường i mới); 
Tính sức ảnh hưởng củ từng ỉnh ự v o m trận Tn × n; 
So s nh v ết uận ỉnh c sức ảnh hưởng ớn nhất trong ồ thị mạng x hội; 
5. Song song h thuật giải x c ịnh ỉnh c sức ảnh hưởng ớn nhất trong ồ thị mạng x hội ằng Ap che Spark 
Tr n n n tảng Ap che Sp r với c c m y tính con ng v i trò c c n vị x ý trong hệ thống phân t n, gọi 
c c wor er v một m y tính với v i trò quản ý tài nguyên, thu thập c c iệu ết quả từ c c n vị v tính to n ết quả 
chung gọi master, chúng tôi ư r phư ng n song song h giải thuật tuần tự ở tr n như s u: 
 Bước 1: Tại m y m ster, tập tin ưu tr thông tin củ ồ thị sẽ ư c ọc v o ộ nhớ Khởi tạo m trận sức 
ảnh hưởng 2 chi u Tn × n. 
 Bước 2: Cũng tại m y m ster, một uồng x ý ri ng iệt sẽ ư c tạo r , c nhiệm v nhận thông tin c c 
 ường i tạo th nh v cập nhật sức ảnh hưởng v o m trận Tn × n Luồng x ý n y sẽ ư c thực thi song 
song, cùng úc với việc m ster phân chi t i nguy n cho c c wor er v chờ nhận ại ết quả c c ường i 
từ c c wor er 
Ở ước n y, m y m ster sẽ hởi tạo uồng x ý ấy thông tin từ c c cạnh cập nhật v o m trận Tn × n. 
 Bước 3: Song song với uồng x ý ở ước 2, thông qu RDD, m ster sẽ ư nh s ch cạnh ến tất cả 
các máy worker t m ra đường đi qua trung gian một đỉnh Kết quả từ c c wor er ư c trả v ại 
m ster Tại ây m ster sẽ hởi tạo uồng x ý ri ng ghi nhận ết quả v o m trận Tn × n. 
 Bước 4: M y m ster ư c ập tr nh ặp ại việc phân phối c c phần củ tập đường đi qua trung gian m 
– 1 đỉnh v tập cạnh cho c c wor er c c wor er t m đường đi qua trung gian m đỉnh. Kết quả ường i 
 ư c t m thấy m c c wor er trả v cho m ster sẽ ư c uồng x ý ồng thời cập nhật v o m trận Tn × n. 
Hình 3. Phân uồng x ý tại m y m ster 
 Bước 5: S u hi t m r tất cả c c ường i củ ồ thị v cập nhật ết quả v o m trận Tn × n. Máy master 
sẽ tính sức ảnh hưởng củ từng ỉnh trong ồ thị. So s nh sức ảnh hưởng củ c c ỉnh v ết uận ỉnh 
n o ỉnh c sức ảnh hưởng ớn nhất trong ồ thị mạng x hội 
Và trong nh ng ước thực hiện củ giải thuật tr n, c nh ng ước ư c chi nhỏ cho c c máy worker trong hệ 
thống phân t n x ý, c nh ng ước sẽ o m y master ứng r quản ý, thu thập c c iệu từ c c n vị v tính to n ết 
quả chung Thuật giải tr n ư c chúng tôi mô tả trực qu n trong s ồ s u với c c công việc o m ster x ý sẽ ư c ặt 
cạnh một h nh m y chủ m u c m, còn wor er sẽ c c m y tính con m u x nh ư ng: 
Phân phối c c phần củ tập đường đi 
qua trung gian m – 2 đỉnh v tập 
cạnh cho c c wor er c c wor er 
tìm đường đi qua trung gian m – 1 
đỉnh 
Phân phối c c phần củ tập đường đi 
qua trung gian m – 1 đỉnh v tập 
cạnh cho c c wor er c c wor er 
tìm đường đi qua trung gian m đỉnh 
Khởi tạo 
 uồng x ý 
song song 
Thông báo 
hoàn thành 
cập nhật 
Nhận thông tin c c ường i 
tạo th nh v cập nhật sức 
ảnh hưởng v o m trận Tn × n 
328 MÔ HÌNH PHÂN TÁN CHO THUẬT GIẢI XÁC ĐỊNH ĐỈNH CÓ SỨC ẢNH HƯỞNG LỚN NHẤT TRONG ĐỒ THỊ MẠNG XÃ HỘI 
Hình 4. S ồ x ý phân t n 
III. THỬ NGHIỆM 
A. Cấu hình thử nghiệm 
Chúng tôi c i ặt hệ thống phân t n th nghiệm tr n hệ thống m y chủ củ trường Đại học Công nghệ Thông 
tin, các máy ảo ư c cấp c cấu h nh giống nh u với tổng số nhân x ý 80 nhân v ộ nhớ RAM c ung ư ng 80GB. 
Hệ thống o gồm 10 m y ư c ết nối với nh u, trong c một m y vừ m y con với v i trò x ý, vừ m y chủ 
với v i trò quản ý cấp ph t t i nguy n, iệu; thu thập, tổng h p ết quả, x ý nh ng tính to n c c ộ C c m y chạy hệ 
 i u h nh U untu 16 04, ư c c i ặt Ap che Sp r 1.6.2. 
Nguyễn Hồ Duy Tri, Ngô Thanh Hùng 329 
B. Kết quả và đánh giá 
S u qu tr nh c i ặt v th nghiệm tr n hệ thống, chúng tôi c ư c nh ng ết quả tư ng ối hả qu n như số 
 iệu ư c ghi nhận trong ảng s u B n cạnh , chúng tôi c c i ặt th nghiệm thuật giải tr n ối với n n tảng tuần tự, 
 qu c ư c nh ng so s nh v ết quả ạt ư c tr n h i hệ thống 
Bảng 1. Kết quả th nghiệm giải thuật tr n n n tảng tuần tự v song song 
Số ỉnh củ 
 ồ thị 
Tổng số ường 
 i trong ồ thị 
Thời gi n x ý (giây) 
Song song Tuần tự 
600 3 549 444 341,324 426,346 
700 5 413 683 608,365 1 417,233 
800 9 481 402 1 241,276 7 015,631 
900 13 059 927 1 977,202 14 051,420 
1000 19 600 515 6 290,760 26 051,420 
Hình 5. Bi u ồ Thời gi n x ý tr n n n tảng tuần tự v song song 
Do i u iện hông cho phép n n chúng tôi chư th nghiệm ư c tr n nh ng tập iệu c số ư ng ớn h n n . 
Tuy nhi n, qu nh ng ết quả tr n chúng t thấy ư c phần n o hiệu quả củ thuật giải v ti m năng m tính to n song 
song, phân t n m ng ại 
IV. KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN 
Việc phân t n h giải thuật x c ịnh ỉnh c sức ảnh hưởng ớn nhất trong ồ thị mạng x hội giúp nâng c o 
 ư c tốc ộ thực thi cũng như tính to n củ hệ thống, n cạnh , n còn giúp cho việc x ý, tính to n tr n một ư ng 
 iệu ớn h n, m cho ết quả c ng chính x c v gi trị h n Đặc iệt ối với một v i oại iệu ớn ng y n y, việc 
tính to n tr n nh ng n n tảng nhỏ, tuần tự ng y c ng mất ần i ý nghĩ củ n Tính to n song song, phân t n, th y v o 
 , giúp ích rất nhi u trong việc giải quyết nh ng i to n phức tạp, òi hỏi tốc ộ nh nh v ộ chính x c c o 
Tuy nhi n, việc s ng thuật giải m ng tính vét cạn m ti u tốn h nhi u t i nguy n, chi phí cho việc tính to n, 
 i u n y cũng hiến cho việc c i ặt tri n h i trở n n h hăn v phức tạp h n. Trong thời gi n tới, nh m t c giả sẽ tiếp 
t c theo uổi hướng nghi n cứu v ồ thị h mạng x hội ằng nh ng th nghiệm mới, chẳng hạn như ư v o th m 
nh ng ặc trưng, yếu tố củ mạng x hội m hiện tại chư ư c ồ thị h , phần n o tăng tính chính x c củ nh ng 
tính to n, g p phần ư i to n n y p ng v o thực tế cuộc sống Ngo i r nh m sẽ t m hi u v p ng c c thuật to n 
mới th y thế thuật to n vét cạn nhằm tối ưu h n v mặt t i nguy n, chi phí. 
V. LỜI CẢM ƠN 
Nghi n cứu n y sản phẩm củ t i “Nghi n cứu c c ỹ thuật x ý iệu ớn, p ng cho việc x c ịnh 
nh ng c nhân c tầm ảnh hưởng trong mạng x hội” m số D2015-07, thuộc Trường Đại học Công nghệ Thông tin – 
ĐHQG TP.HCM. 
330 MÔ HÌNH PHÂN TÁN CHO THUẬT GIẢI XÁC ĐỊNH ĐỈNH CÓ SỨC ẢNH HƯỞNG LỚN NHẤT TRONG ĐỒ THỊ MẠNG XÃ HỘI 
VI. TÀI LIỆU THAM KHẢO 
[1] M. Zaharia, M. Chowdhury, M. J. Franklin, S. Shenker and I. Stoica, "Spark: Cluster Computing with Working Sets," in 
Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing, Boston, MA, 2010. 
[2] H. Karau, A. Konwinski, P. Wendell and M. Zaharia, “Learning spark: lightning-fast big data analysis”, O'Reilly Media, Inc., 
2015. 
A DISTRIBUTED MODEL OF SCALABLE ALGORITHM FOR 
IDENTIFYING THE MOST INFLUENCE NODE IN A SOCIAL NETWORK 
Nguyen Ho Duy Tri, Ngo Thanh Hung 
ABSTRACT— The discovery of key player in social networks has attracted the attention of researchers. In the previous research, 
we have proposed a method to identify the key player in a social network based on the sum of impact from a given node to all others. 
When implementing and applying such algorithm as a serial of instructions for a social network, which may be hundreds or 
thousands of nodes, it can be impractical to solve them on a single computer. To overcome such drawbacks, an algorithm for 
identifying a key player based on parallel computing is proposed in the paper. We test such approach and conclusions are drawn to 
describe the encouraging results we achieved.