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

Kỷ yếu Hội nghị Khoa học Quốc gia lần thứ IX ―Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR'9)‖; Cần Thơ, ngày 4-5/8/2016

DOI: 10.15625/vap.2016.00040

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

Nguyễn Hồ Duy Tri, Ngô Thanh Hùng

Phòng Thí nghiệm Hệ thống Thông tin, Trường Đại học Công nghệ Thông tin – ĐHQG TPHCM

tringuyen@uit.edu.vn, hungnt@uit.edu.vn

TÓM TẮT—Vấn đề xác định key player trong các mạng xã hội đang thu hút sự quan tâm của nhiều nhà nghiên cứu trên thế giới.

Trong một nghiên cứu trước đây, chúng tôi đã đề xuất một phương pháp mới để xác định key player dựa vào tổng sức ảnh hưởng

của mỗi đỉnh tới tất cả các đỉnh còn lại. Tuy nhiên việc cài đặt thuật toán trên các nền tảng tuần tự hoặc đa luồng không thể áp

dụng được với các mạng xã hội có từ hàng trăm, hàng ngàn node trở lên, trong khi các mạng xã hội thông thường có số lượng node

là lớn hơn rất nhiều. Chính vì vậy chúng tôi xây dựng và trình bày trong bài báo này một thuật toán xác định key player trên nền

tảng phân tán. Thuật toán đã được cài đặt trên Spark. Bài báo cũng trình bày hiệu quả của thuật toán phân tán so với thuật toán

tuần tự qua một số thử nghiệm.

Từ khóa— Scalable algorithm, Spark, key player, the most influence node, social network.

I. GIỚI THIỆU

Tại Việt N m, ối tư ng gi nhập, s ng mạng x hội ng y c ng nhi u, với nhi u nh ng hoạt ộng v m c ích

h c nh u So với c c phư ng tiện thông tin, i n ạc truy n thống như hệ thống ph t th nh, truy n h nh, o giấy th

mạng x hội c nhi u ưu i m vư t trội, tuy nhi n nội ung ại h i m so t v c th gây ảnh hưởng ớn ến nhi u

người Nước t hiện ng nước c ư ng truy cập mạng x hội F ce oo nhi u thứ 15 tr n thế giới củ F ce oo , c

hoảng 30 triệu người ùng thường xuy n tr n F ce oo , v con số n y còn tăng trưởng mỗi ng y Phư ng ph p x c ịnh

sức ảnh hưởng củ một c nhân trong mạng x hội ư c t c giả Ngô Thanh Hùng nghi n cứu trong một công tr nh

h c trước ây, tuy nhi n, ối với iệu mạng x hội hiện n y, một òi hỏi cấp thiết phải ư c x ý nh nh với một

hối ư ng vô cùng ớn c th m ng ại hiệu quả v gi trị cao. Trong bài báo này, chúng tôi cố gắng th nghiệm

phư ng ph p song song h giải thuật x c ịnh sức ảnh hưởng củ một c nhân trong mạng x hội ối với cộng ồng, qu

t m r người ẫn ắt ư uận

II. 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

A. Mô hình hóa đồ thị mạng xã hội

D iệu mạng x hội s ng trong i o ư c mô h nh h ưới ạng ồ thị c hướng, với ỉnh củ ồ thị i u

iễn nh ng người ùng trong mạng, cạnh nối gi c c ỉnh th hiện sự n truy n thông tin gi c c người ùng Hướng

củ cạnh cho iết chi u hướng n truy n củ thông tin v trọng số củ cạnh th hiện sự ảnh hưởng củ một người ến

một người h 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 v_A-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.

P_A-B= v_A-X× v_X-Y× … × v_Z-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 : P¹_A-B, P²_A-B, …, Pⁿ

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 :

P_A-B= 1 – (1 - P¹_A-B) × (1 - P²_A-B) ×…× (1 - Pⁿ

)

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-2= v_1-3× v_3-5× v_5-4× v_4-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²_1-2= v_1-3× v_3-4× v_4-2= 0,386 × 0,434 × 0,257 = 0,043053668

Sức ảnh hưởng củ ỉnh 1 ến ỉnh 2 sẽ ằng:

P_1-2= 1 – (1 – P¹_1-2) × (1 – P²_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;

Đỉ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 T_{n × n}

;

Cập nhật sức ảnh hưởng trực tiếp từ c c cạnh v o T_{n × n}

;

Nguyễn Hồ Duy Tri, Ngô Thanh Hùng

327

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 T_{n × 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 T_{n × 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 T_{n × 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 T_{n × 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 T_{n × 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 T_{n × 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 T_{n × n}

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

Khởi tạo

uồng x ý

song song

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 T_{n × n}

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

Thông báo

hoàn thành

cập nhật

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 T_{n × 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:

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

Thời gi n x ý (giây)

Số ỉnh củ Tổng số ường

ồ thị

i trong ồ thị

Song song

341,324

Tuần tự

600

700

800

900

1000

3 549 444

5 413 683

9 481 402

13 059 927

19 600 515

426,346

608,365

1 417,233

7 015,631

14 051,420

26 051,420

1 241,276

1 977,202

6 290,760

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.

7 trang yennguyen 12/04/2022 5400

Download

Bạn đang xem tài liệu "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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên

File đính kèm:

mo_hinh_phan_tan_cho_thuat_giai_xac_dinh_dinh_co_suc_anh_huo.pdf