Luận văn Thạc sĩ Khoa học máy tính: Nghiên cứu độ đo trung gian và thuật toán phát hiện cộng đồng trên mạng xã hội

ĐẠI HỌC THÁI NGUYÊN

TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN

THÔNG

DƯƠNG THỊ TÌNH

NGHIÊN CỨU ĐỘ ĐO TRUNG GIAN VÀ THUẬT TOÁN

PHÁT HIỆN CỘNG ĐỒNG TRÊN MẠNG XÃ HỘI

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên - 2020

LỜI CAM ĐOAN

Tôi xin cam đoan các kết quả nghiên cứu trong luận văn này là do tự

bản thân tôi tìm hiểu dưới sự hướng dẫn của PGS. TS. Đoàn Văn Ban. Các

chương trình thực nghiệm do chính bản thân tôi lập trình, các kết quả là hoàn

toàn trung thực. Các thông tin trích dẫn trong luận văn đã được chỉ rõ nguồn

gốc.

TÁC GIẢ LUẬN VĂN

Dương Thị Tình

LỜI CẢM ƠN

Để hoàn thành được luận văn này, tôi đã nhận được rất nhiều sự quan

tâm, giúp đỡ và góp ý quý báu của các cá nhân và tập thể.

Trước hết tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS. Đoàn

Văn Ban đã quan tâm, định hướng và đưa ra những góp ý chỉnh sửa quý báu

cho tôi trong quá trình làm luận văn tốt nghiệp.

Đồng thời tôi cũng xin chân thành cảm ơn sự góp ý chân thành của các

thầy, cô giáo Viện Công nghệ thông tin, các thầy, cô giáo Trường Đại học Công

nghệ thông tin và Truyền thông Thái Nguyên đã tạo mọi điều kiện thuận lợi

cho tôi hoàn thành đề tài này.

Dù đã rất cố gắng nhưng chắc chắn sẽ không tránh khỏi những thiếu sót

vì vậy rất mong nhận được sự góp ý của các thầy, cô và các bạn để luận văn

này được hoàn thiện hơn.

Tôi xin chân thành cảm ơn!

Thái Nguyên, tháng 08 năm 2020

Dương Thị Tình

MỤC LỤC

Trang

MỞ ĐẦU .......................................................................................................... 1 CHƯƠNG 1 MẠNG XÃ HỘI VÀ CÁC ĐỘ ĐO TRÊN ĐỒ THỊ MẠNG XÃ HỘI ............................................................................................................ 4 1.1. MẠNG XÃ HỘI ......................................................................................... 4 1.2. CẤU TRÚC CỘNG ĐỒNG MẠNG XÃ HỘI ...................................................... 8 1.3. CÁC ĐỘ ĐO TRÊN ĐỒ THỊ MẠNG XÃ HỘI .................................................. 11 1.3.1. Hệ số cố kết của mạng .................................................................. 12 1.3.2. Hệ số trung tâm vector đặc trưng .................................................. 13 1.3.3. Độ đo trung tâm của đỉnh .............................................................. 14 1.3.4. Hệ số trung gian của đỉnh ............................................................. 18 1.3.5. Độ đo trung gian của cạnh ............................................................ 20 1.4. THUẬT TOÁN TÍNH ĐỘ TRUNG GIAN ....................................................... 22 1.5. KẾT LUẬN CHƯƠNG ............................................................................... 26

CHƯƠNG 2 THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI ......................................................................................................................... 27 2.1. BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG TRÊN ĐỒ THỊ MẠNG XÃ HỘI ............... 27 2.2. THUẬT TOÁN PHÂN CỤM PHÂN CẤP ........................................................ 28 2.3. THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG DỰA TRÊN TỐI ƯU HOÁ ĐỘ ĐO ĐƠN THỂ ............................................................................................................... 30 2.4. THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG DỰA VÀO ĐỘ ĐO TRUNG GIAN ...... 30 2.5. PHÁT HIỆN CÁC CỘNG ĐỒNG GỐI NHAU .................................................. 33 2.5.1. Phát hiện các k-cliques trong mạng xã hội ................................... 34 2.5.2. Thuật toán phát hiện k-clique........................................................ 36 2.5.3. Thuật toán EAGLE ....................................................................... 38 2.5.4. Đánh giá thuật toán ....................................................................... 43 2.6. KẾT LUẬN CHƯƠNG 2............................................................................. 44

CHƯƠNG 3 ỨNG DỤNG THUẬT TOÁN GIRVAN-NEWMAN TRONG PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI .......................................... 45

3.1. MÔ TẢ BÀI TOÁN PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI ........................ 45 3.2. CHƯƠNG TRÌNH PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI .......................... 45 3.2.1. Bộ cơ sở dữ liệu ............................................................................ 45 3.2.2. Môi trường thử nghiệm ................................................................. 47 3.2.3. Thử nghiệm và đánh giá ................................................................ 49 3.3. KẾT LUẬN CHƯƠNG 3............................................................................. 54

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN ................................................... 55 TÀI LIỆU THAM KHẢO ............................................................................ 56

DANH MỤC CÁC HÌNH VẼ

Hình 1.1. Mạng xã hội Facebook ...................................................................... 7

Hình 1.2. Mạng xã hội Zing me ........................................................................ 7

Hình 1.3. Mô hình mạng lưới cộng tác của các nhà khoa học làm việc tại SFI 9

Hình 1.4. Đồ thị có 4 đỉnh và 5 cạnh .............................................................. 15

Hình 1.5. Những đồ thị hình sao, bánh xe có số đỉnh 3, 4, 5, 6, 7 .................. 17

Hình 1.6. Đồ thị mạng xã hội đơn giản gồm 7 nút ......................................... 21

Hình 2.1. Phát hiện cộng đồng mạng sử dụng Girven-Newman .................... 32

Hình 2.2. Ví dụ 1-clique, 2-clique và 3-clique................................................ 35

Hình 2.3. 2-cliques, 2-clan và 2-club .............................................................. 36

Hình 2.4. (a), (b). Mạng ban đầu ..................................................................... 40

Hình 2.5. (c). Các cộng đồng được phát hiện bởi thuận toán của Newman ... 41

Hình 2.6.(d). Các cộng đồng được phát hiện bởi thuật toán k-clique ............. 41

Hình 2.7.(e). Các cộng đồng thể hiện sự chồng chéo và phân cấp rõ ràng được phát hiện bởi thuật toán EAGLE ..................................................................... 42

Hình 3.1. Mô phỏng số cộng đồng tìm được trong đồ thị simple_network. ... 49

Hình 3.2. Mô phỏng số cộng đồng tìm được trong bộ dữ liệu dolphin. ......... 50

Hình 3.3. Mô phỏng số cộng đồng tìm được trong bộ dữ liệu karate. ............ 50

Hình 3.4. Mô phỏng số cộng đồng tìm được trong bộ dữ liệu football. ......... 51

Hình 3.5. Mô phỏng kết quả tìm kiếm cộng đồng trên bộ dữ liệu amazon_small ......................................................................................................................... 51

DANH MỤC CÁC BẢNG

Bảng 3.1. Mô tả chi tiết về các bộ dữ liệu được sử dụng trong phát hiện cộng đồng mạng ....................................................................................................... 47

Bảng 3.2. Thông tin phần cứng được sử dụng ................................................ 48

Bảng 3.3. Bảng tổng hợp kết quả của 2 thuật toán Girvan-Newman và k-cliques trên các bộ dữ liệu khác nhau .......................................................................... 53

1

MỞ ĐẦU

1. Lý do chọn đề tài

Sự phát triển vượt bậc của công nghệ thông tin làm cho lượng thông tin

được lưu trữ trên các thiết bị nhớ không ngừng tăng lên. Những đồ thị lớn và

mạng (networks) là những mô hình toán học tự nhiên cho những đối tượng

tương tác với nhau như mối quan hệ giữa con người trong mạng xã hội, các cấu

trúc phân tử trong mạng sinh học, mạng biểu diễn gene, ... Trong thực tế, cỡ

của các mạng như thế khá lớn mà khả năng phân tích, khai thác các tính chất

của chúng lại rất hạn chế. Mặt khác, xu thế phát triển công nghệ và ngày càng

xuất hiện nhiều loại hình truyền thông mạng xã hội dẫn đến sự thay đổi về hành

vi của con người trong xã hội và hình thành những cộng đồng trực tuyến. Hành

vi con người thay đổi dẫn đến nhiều hình thức kinh doanh, tiếp thị, dịch vụ và

kể cả trong lĩnh vực giáo dục, an ninh, chính trị cũng thay đổi theo từ cách tiếp

cận cho đến việc quản lý người dùng.

Sự phát triển nhanh chóng của các mạng xã hội kéo theo sự bùng nổ dữ

liệu trên mạng xã hội. Đây là một nguồn thông tin hết sức hữu ích, liên tục được

cập nhật. Một đặc trưng bản chất của mạng xã hội là tính cộng đồng. Mạng xã

hội và bài toán phát hiện cộng đồng mạng xã hội là nội dung nghiên cứu mang

tính thời sự, là nhu cầu bức thiết trong thời điểm hiện nay và nó đang thu hút

được rất nhiều sự quan tâm của các nhà khoa học thuộc các lĩnh vực khác nhau

như xã hội học, khoa học máy tính, kinh tế, sinh học, …

Do đó, việc đánh giá một sự vật, hiện tượng theo từng cộng đồng có ý

nghĩa to lớn trong việc xác định mối quan tâm của từng nhóm đối tượng. Vì em

quyết định lựa chọn đề tài “Nghiên cứu độ đo trung gian và thuật toán phát

hiện cộng đồng trên mạng xã hội” để nghiên cứu làm luận văn thạc sĩ của

mình.

2

2. Mục đích nghiên cứu

Những mục tiêu nghiên cứu của luận văn:

- Tìm hiểu mạng xã hội, cấu trúc cộng đồng trên đồ thị mạng xã hội và

các phương pháp tìm kiếm cấu trúc cộng đồng mạng xã hội

- Nghiên cứu các độ đo trên đồ thị mạng xã hội và tìm hiểu các thuật

toán phát hiện cấu trúc cộng đồng trên mạng xã hội

- Xây dựng ứng dụng phát hiện cộng đồng mạng xã hội ở tập dữ liệu đã

được công bố trên mạng.

3. Đối tượng nghiên cứu

- Lý thuyết đồ thị

- Mạng xã hội và mô hình cộng đồng mạng xã hội

- Thuật toán Girvan-Newman phát hiện cộng đồng mạng

4. Phạm vi nghiên cứu

+ Lý thuyết:

- Kỹ thuật khai phá dữ liệu đồ thị,

- Các thuật toán phát hiện cấu trúc cộng đồng của mạng xã hội.

+ Thực nghiệm:

- Thực nghiệm chương trình phát hiện cộng đồng mạng dựa trên họ các

thuật toán Girvan-Newman và k-cliques

- Áp dụng chương trình để phát hiện cộng đồng mạng trên một số bộ dữ

liệu mạng xã hội trực tuyến.

5. Ý nghĩa khoa học

3

Đây là một hướng nghiên cứu lý thuyết và ứng dụng về phân tích và phát

hiện cộng động mạng xã hội.

6. Phương pháp nghiên cứu

- Phương pháp nghiên cứu lý thuyết: Sưu tập các tài liệu có liên quan

đến đề tài, nghiên cứu để hiểu sâu các nội dung vấn đề cần nghiên cứu.

- Phương pháp nghiên cứu thực nghiệm: Cài đặt thử nghiệm kiểm thử

chương trình

- Phương pháp trao đổi khoa học: Trao đổi nội dung nghiên cứu với giáo

viên hướng dẫn, với các đồng nghiệp để đề xuất và giải quyết các nội dung luận

văn đề ra.

7. Cấu trúc đề tài

Luận văn được chia thành các phần chính như sau:

Chương 1: Mạng xã hội và các độ đo trên đồ thị mạng xã.

Chương 2: Thuật toán xác định cấu trúc cộng đồng mạng.

Chương 3: Ứng dụng thuật toán GN trong phát hiện cộng đồng mạng

xã hội

Kết luận và hướng phát triển

4

CHƯƠNG 1

MẠNG XÃ HỘI VÀ CÁC ĐỘ ĐO TRÊN ĐỒ THỊ MẠNG XÃ HỘI

Mạng xã hội là một tập hợp các thực thể được kết nối với nhau thông qua

các mối quan hệ, mối liên kết, ... Phân tích mạng xã hội là xem xét các mối

quan hệ xã hội dựa vào lý thuyết đồ thị bao gồm các đỉnh và các cạnh (còn được

gọi là các liên kết hoặc kết nối). Các đỉnh được xem là những cộng đồng riêng

lẻ trên mạng, và các cạnh là các mối quan hệ giữa các cộng đồng. Cộng đồng

mạng xã hội là một tập hợp các cá nhân (tác nhân, thực thể) tương tác với nhau

thông qua các phương tiện truyền thông cụ thể, có khả năng vượt qua những

ranh giới địa lý và chính trị để theo đuổi lợi ích hay mục tiêu chung. Chương

này giới thiệu khái quát về mạng xã hội và các độ đo phúc vụ cho phân tích,

phát hiện cộng đồng trên đồ thị mạng xã hội.

1.1. Mạng xã hội

Mạng xã hội là một cấu trúc xã hội xã hội được tạo ra từ các thực thể, tác

nhân (actor) hoặc các tổ chức được liên kết, kết nối bởi một hoặc nhiều quan

hệ với nhau [3], [4], [27]. Theo Fortunato và các cộng sự [25] mạng xã hội là

một tập hợp các thực thể được kết nối với nhau bằng một tập hợp các mối quan

hệ, liên kết, như quan hệ bạn bè, gia đình, cộng sự hay trao đổi thông tin,…

Các mối quan hệ giữa các thực thể có thể mang nhiều nội dung khác nhau từ

sự tương trợ, trao đổi thông tin cho đến việc trao đổi hàng hóa, các dịch vụ, …

Mạng cung cấp nhiều cách khác nhau để các tổ chức thu thập thông tin, cạnh

tranh với nhau trong việc thiết lập giá kinh doanh hoặc chính sách, … Mạng xã

hội thường có những đặc tính như sau [11], [25], [26]:

 Dựa vào người dùng (User-based): Trước khi các mạng xã hội như

Facebook hoặc MySpace trở thành chuẩn mực, các trang web dựa trên nội

dung được cập nhật bởi người dùng và được các khách truy cập Internet

5

để đọc, tham khảo thông tin. Không có người dùng, mạng sẽ là một không

gian trống chứa đầy các diễn đàn, ứng dụng và phòng trò chuyện trống.

Hướng của nội dung đó được xác định bởi bất kỳ ai tham gia vào cuộc

thảo luận. Đây là những gì làm cho các mạng xã hội trở nên thú vị và năng

động hơn nhiều đối với người dùng Internet thông thường.

 Tương tác (Interactive): Một đặc điểm khác của các mạng xã hội hiện đại

là các thực thể thường xuyên tương tác thông qua các mối liên kết. Điều

này có nghĩa là một mạng xã hội không chỉ là một bộ sưu tập các phòng

chat, diễn đàn, …, các trang web như Facebook còn chứa đầy các ứng

dụng chơi trò chơi, quảng cáo, bán hàng online, phổ biến tin tức, … Các

mạng xã hội trở thành trò tiêu khiển mà nhiều người dùng lựa chọn nhiều

hơn trên truyền hình bởi vì nó không chỉ là giải trí, học tập, trao đổi công

việc và đó còn là cách thức để mọi người kết nối, tương tác với nhau.

 Hướng đến cộng đồng (Community-driven): Mạng xã hội được xây dựng

và phát triển từ các khái niệm về cộng đồng. Điều này có nghĩa là giống

như các cộng đồng hoặc các nhóm xã hội trên toàn thế giới được thành lập

dựa trên thực tế là các thành viên có niềm tin hoặc sở thích chung, có

chung điểm chung, ...

 Các mối quan hệ (Relationships): Không giống như các trang web trong

quá khứ, các mạng xã hội phát triển mạnh về các mối quan hệ. Càng có

nhiều mối quan hệ trong mạng, các thực thể càng thiết lập được vai trò

trung tâm của mạng đó. Tồn tại tính địa phương, mối quan hệ giữa các

thực thể có xu hướng tạo thành các cụm (cộng đồng). Đồng thời tạo môi

trường cho việc tương tác và chia sẻ thông tin giữa các thành viên trong

mạng như người thân, đồng nghiệp, gia đình, bạn bè, người hâm mộ, …

 Cảm xúc về nội dung (Emotion over content): Một đặc điểm độc đáo khác

của mạng xã hội là yếu tố cảm xúc. Mặc dù các trang web trong quá khứ

6

tập trung chủ yếu vào việc cung cấp thông tin cho khách truy cập, nhưng

mạng xã hội ngày nay thực sự mang đến cho người dùng sự an toàn về

mặt cảm xúc và cảm giác rằng dù có chuyện gì xảy ra, bạn bè của họ vẫn

ở trong tầm kiểm soát.

Trong mạng có nhiều kiểu liên kết như liên kết vô hướng, liên kết một

chiều, liên kết hai chiều, … Ta có thể biểu diễn mạng mạng xã hội bằng một

đồ thị (được gọi là đồ thị mạng xã hội) mà các thực thể được biểu diễn bởi các

đỉnh, còn các liên kết được biểu diễn bởi các cạnh. Trong đó với hai đỉnh A và

B có cạnh nối với nhau là thể hiện mối quan hệ giữa chúng. Ngoài ra, các liên

kết này còn có thể đánh trọng số để biểu diễn độ mạnh yếu của mối liên kết.

Mạng xã hội phát triển rất nhanh chóng, với số lượng người tham gia và mối

quan hệ với nhau rất lớn đòi hỏi phải có những phương pháp nghiên cứu phù

hợp về mạng xã hội.

Ví dụ 1.1.

Mạng xã hội Facebook là mạng xã hội được coi là phổ biến nhất hiện

nay, Facebook là mạng xã hội miễn phí do công ty Facebook Inc điều hành.

Người sử dụng có thể tham gia các mạng lưới được tổ chức theo thành phố, nơi

làm việc, trường học và khu vực để liên kết và giao tiếp với người khác trên thế

giới. mọi người đều có thể kết bạn và gửi tin nhắn cho nhau, và cập nhật thông

tin của mình cho bạn bè biết. Tên của Facebook nhắc tới những cuốn sổ lưu

niệm dùng để ghi tên những thành viên của cộng đồng campus mà một số

trường đại học và cao đẳng tại Mỹ đưa cho các sinh viên mới vào trường, phòng

ban, và nhân viên để có thể làm quen với nhau trong khuôn viên trường.

7

Hình 1.1. Mạng xã hội Facebook

Zing me là một trong những mạng xã hội phố biến hiện nay tại Việt Nam,

nó có khả năng kết nối người dùng trên phạm vi rộng lớn, đồng thời khi sử

dụng bạn có thể tham gia các trò chơi, tiện ích, tính năng kết nối cộng đồng mà

ứng dụng đang sở hữu. Ngoài ra ở Việt Nam còn có thể kể đến mạng xã hội

Zalo.

Hình 1.2. Mạng xã hội Zing me

8

Trên mạng, một số đỉnh có liên kết chặt chẽ với nhau tạo thành từng cụm,

và giữa các cụm đó được nối với nhau chỉ bằng một vài cạnh khác. Tính chất

đó của các mạng trên thực tế được gọi là tính cộng đồng (community) [1], [9].

Đây là một tính chất quan trọng của mạng xã hội và đang ngày càng được nhiều

người quan tâm nghiên cứu, phân tích cấu trúc cộng đồng của mạng xã hội bởi

tần quan trọng của chúng. Khả năng phát hiện và phân tích các cộng đồng sẽ

cung cấp cho chúng ta những sự giúp đỡ vô giá để hiểu biết và hình dung được

những cấu trúc, tính chất đặc trưng của mạng xã hội.

1.2. Cấu trúc cộng đồng mạng xã hội

Cấu trúc cộng đồng mạng xã hội (Community social structure) gọi tắt là

cộng đồng mạng xã hội là một tập hợp các tác nhân tương tác thông qua các

phương tiện truyền thông cụ thể, có khả năng vượt qua những ranh giới địa lý

và chính trị để theo đuổi lợi ích hay mục tiêu chung. Cộng đồng là một nhóm

các thực thể có những tính chất tương tự nhau, liên kết chặt chẽ với nhau hơn

và cùng đóng một vai trò nhất định trong mạng xã hội. Một cộng đồng được

mô tả như một nhóm các đỉnh (đồ thị con) cùng chia sẻ các thuộc tính chung

hoặc đóng vai trò tương tự trong một mạng. Một cộng đồng có thể được định

nghĩa là một tập hợp các đỉnh có mật độ liên kết giữa các đỉnh cao và mật độ

liên kết thấp với phần còn lại của mạng. Nói một cách khác một cộng đồng

được tạo ra bởi một tập hợp các tác nhân có tương tác thường xuyên với nhau

hơn so với cá nhân khác ngoài cộng đồng. Do vậy, nó thường là một tập hợp

như: bạn bè, đồng nghiệp, nhóm những người có cùng sở thích, cùng chuyên

môn, mối quan tâm, … [1], [3], [9], [14], [26], ...

Ví dụ 1.2.

Hình 1.3. hiển thị các thành phần kết nối lớn nhất trong mạng lưới các

cộng tác nghiên cứu của các nhà khoa học làm việc tại Viện Santa Fe (SFI). Đồ

9

thị bao gồm 118 đỉnh đại diện cho các nhà khoa học làm việc tại SFI và các

cộng tác viên của họ. Các cạnh được liên kết giữa các nhà khoa học khi họ đã

công bố cùng với nhau ít nhất một bài báo. Ở mạng này ta quan sát được một

số cộng đồng, mỗi cộng đồng biểu hiện cho những tác giả đã cùng nhau công

bố một hay nhiều bài báo khoa học. Mặt khác ta cũng thấy giữa các cộng đồng

trong mạng trên chỉ có một số ít mối liên kết. Các đỉnh cùng màu là cùng một

cộng đồng theo các lĩnh vực nghiên cứu của SFI.

Hình 1.3. Mô hình mạng lưới cộng tác của các nhà khoa học làm việc tại SFI

Trong mạng xã hội, việc trích xuất, phát hiện được những cấu trúc cộng

đồng là rất hữu ích vì nó giúp chúng ta nghiên cứu được cấu trúc tổng thể của

mạng. Khái niệm của khám phá, phát hiện cộng đồng tương tự như phân vùng

(phân cụm) đồ thị nhưng có một số khác biệt như trong phân vùng đồ thị, số

lượng nhóm và kích thước của chúng đã được biết trước, nhưng trong trường

hợp phát hiện ra cộng đồng, chúng ta không biết về số lượng cộng đồng trong

mạng và cộng đồng cũng có thể không cùng kích cỡ với nhau.

10

Một số ứng dụng chính của bài toán phát hiện cộng đồng mạng xã hội

[1], [3], [4] , [14], [25] là:

- Phát hiện cộng đồng có thể được sử dụng trong tư vấn thông tin và xác

định được những cộng đồng có cùng một số quan tâm, sở thích tương tự.

- Cộng đồng cũng sẽ giúp chúng ta hiểu cấu trúc của mạng xã hội, làm rõ

các thuộc tính và chức năng của mạng.

- Phát hiện các cộng đồng để hiểu hành vi của mạng xã hội trong quy mô

lớn vì nó sẽ làm rõ các quá trình chia sẻ thông tin và truyền bá thông tin.

- Các phương pháp phát hiện cộng đồng có lợi thế lớn trong việc định

tuyến nhận thức trong xã hội và ngăn chặn thông tin độc hại trên mạng

xã hội.

- Các cộng đồng trong mạng sinh học giúp chúng ta hiểu các cơ chế cơ

bản kiểm soát các quá trình thay đổi của các tế bào.

- Trong các cộng đồng mạng của các khách hàng có cùng sở thích có thể

được sử dụng để tạo ra hệ thống tư vấn thông tin để nâng cao hiệu quả

của sản xuất, kinh doanh.

- Có thể dễ dàng hiểu được các cấu trúc của các đồ thị phức tạp với sự trợ

giúp của các cộng đồng được phát hiện.

- Mạng xã hội loài người thể hiện cấu trúc cộng đồng mạnh mẽ. Một mạng

lưới có cấu trúc cộng đồng mạnh bao gồm các cộng đồng, các cộng đồng

này có nhiều kết nối trong đó và ít kết nối giữa các cộng đồng. Cấu trúc

cộng đồng không chỉ ảnh hưởng đến sự lây lan của bệnh truyền nhiễm

trong cộng đồng nhưng cũng bảo vệ mạng khỏi dịch bệnh quy mô lớn.

- Trong hệ sinh học và hệ chăm sóc sức khỏe, có nhiều thuật toán phát

hiện cộng đồng được phát triển cho các mạng xã hội cũng có thể được

mở rộng thành công cho các mạng sinh học. Ví dụ phát hiện cộng đồng

11

được sử dụng trong Calderone để so sánh các mạng tương tác Alzheimer

và Parkinson.

1.3. Các độ đo trên đồ thị mạng xã hội

Theo quan điểm cấu trúc, chúng ta có thể mô hình hóa các mối quan hệ

trong mạng xã hội như là đồ thị vô hướng G = (V, E), với V là tập các đỉnh và

E là tập các cạnh, được gọi là đồ thị mạng xã hội. Tập V biểu diễn cho các

thành viên (tác nhân) của mạng xã hội, còn E thể hiện mối quan hệ xã hội giữa

các thành viên với nhau. Dựa vào lý thuyết đồ thị, cấu trúc mạng xã hội cũng

có thể được biểu diễn thông qua ma trận liền kề A = (Aij) ∈ {0, 1}n×n, với n =

|V| và Aij = 1 nếu hai đỉnh i và j có cạnh nối giữa chúng (có liên kết - quan hệ

trực tiếp với nhau), ngược lại Aij = 0.

Để áp dụng được kỹ thuật khai phá dữ liệu trong phân tích mạng xã hội

và phát hiện cộng đồng thì trước tiên phải định nghĩa được độ đo khoảng cách

(distance measure) giữa các đỉnh, cạnh của đồ thị. Khi các cạnh của đồ thị được

gắn nhãn thì các nhãn này có thể được sử dụng như là độ đo khoảng cách, tùy

thuộc vào những gì mà chúng đại diện. Nhưng khi các cạnh không có nhãn,

như đồ thị “bạn bè” thì cần phải định nghĩa độ đo khoảng cách giữa các đỉnh.

Giả thiết mạng xã hội được biểu diễn bởi một đồ thị G = (V, E), trong đó

V là tập các đỉnh, E là tập các cạnh. Trước tiên ta quy ước, những đỉnh gần

nhau (closed) nếu chúng có cạnh nối trực tiếp giữa chúng, ngược lại là những

đỉnh xa nhau (distant). Khoảng cách giữa đỉnh x và y  V, ký hiệu là d(x, y),

có thể định nghĩa d(x, y) theo hai cách:

 d(x, y) = 0 nếu (x, y)  E, ngược lại là d(x, y) = 1.

 Hoặc d(x, y) = 1 nếu có cạnh nối giữa chúng, và bằng  khi chúng xa

nhau, không có cạnh nối giữa chúng.

12

Tuy nhiên, cả hai trường hợp trên đều không phải là định nghĩa độ đo

khoảng cách thực sự (metric), bởi chúng không thỏa mãn bất đẳng thức tam

giác. Dễ nhận thấy, nếu có cạnh nối A với B và cạnh nối B với C, thì không có

gì đảm bảo có cạnh nối A với C.

Có nhiều độ đo (measures) khác nhau được sử dụng để phân loại, phân

tích, đánh giá đồ thị mạng xã hội. Chúng thường được sử dụng bởi các nhà

nghiên cứu và người dùng thương mại để phân tích các đặc điểm của mạng xã

hội được xem xét. Các phép đo quan trọng nhất được xác định phần lớn đều

dựa trên lý thuyết đồ thị. Tasleem Arif [4] sử dụng các hệ số cố kết mạng và hệ

số trung tâm vector đặc trưng [24] để phân tích, đánh giá mạng xã hội. Freeman

[12] đề xuất một tập các độ đo (Measures) xác định độ trung tâm của các đỉnh,

cạnh trên đồ thị, như hệ số trung tâm trực tiếp theo bậc của đỉnh, hệ trung tâm

lân cận và độ trung gian (Betweenness) và được sử dụng nhiều trong phân tích

mạng xã hội và phát hiện các cộng đồng.

1.3.1. Hệ số cố kết của mạng

Trong phân tích mạng xã hội có rất nhiều hệ số để so sánh các mạng xã

hội với nhau, một trong những hệ số quan trọng nhất đó là hệ số cố kết (Density,

Cohesion) [4]. Khi hệ số cố kết của mạng càng lớn, mức độ gắn kết, sự chặt

chẽ của các mối quan hệ giữa các thực thể (tác nhân) trong mạng càng lớn, và

do đó, sự tương trợ, hỗ trợ, … giữa các tác nhân cũng càng nhiều, càng hiệu

quả hơn, sự điều tiết của mạng đối với hành vi của tác nhân cũng cũng mạnh

mẽ hơn và ngược lại. Một cách tổng quát, tính cố kết của mạng lưới là tỷ lệ

giữa tổng các mối liên hệ thực tế trong mạng và tổng các mối quan hệ lý thuyết

của nó (tức là tổng các mối quan hệ có thể có của mạng). Hệ số cố kết của đồ

thị G, được tính như sau:

(1.1)

𝐷𝐺 =

2 𝑘 𝑛 (𝑛−1)

13

Trong đó, k là tổng các mối liên hệ thực tế của mạng, k = |E| và n = |V|.

Giá trị của hệ số này chạy từ 0.00 - 1.00. Càng gần tới giá trị 1.00 thì tính cố

kết của mạng lưới càng mạnh và do đó sự tương trợ, sự trao đổi thông tin, …

giữa các thành viên trong mạng được diễn ra càng tốt và ngược lại. Theo Scott

[27], hệ số cố kết của mạng lưới phụ thuộc vào số lượng tác nhân của nó, tức

là khi càng có nhiều tác nhân thì hệ số cố kết của nó càng nhỏ và ngược lại. Đối

với những đồ thị đầy đủ (clique) thì hệ số cố kết là tuyệt đối, tức là DG = 1.00.

1.3.2. Hệ số trung tâm vector đặc trưng

Dựa trên ý tưởng là những tác nhân có vị trí trung tâm, có tầm ảnh hưởng

hay nổi tiếng trên mạng là những tác nhân có quan hệ với nhiều tác nhân mà

bản thân những tác nhân đó cũng là tác nhân trung tâm (có tầm ảnh hưởng hay

nổi tiếng). Do vậy, độ trung tâm không chỉ phụ thuộc vào số các đỉnh liền kề

mà còn phụ thuộc vào độ trung tâm của những đỉnh liền kề với những đỉnh đó.

Độ trung tâm hay vị thế (status) của đỉnh thường xác định tổng quát theo quan

hệ đệ quy (recursively related) theo các độ trung tâm hoặc vị thế mà chúng có

mối liên kết (trực tiếp hoặc gián tiếp) với nhau. Độ đo đó được gọi là độ trung

tâm vector đặc trưng (Eigenvector centrality) [24].

Giả thiết A = (Aij) là ma trận liền kề không âm của đồ thị có hướng G =

(V, E). Độ trung tâm vector đặc trưng xi của đỉnh i được định nghĩa như sau:

(1.2) xi = Ai1x1 + Ai2x2 + … + Ainxn, i = 1, 2, …, |V| = n

Độ trung tâm của mỗi đỉnh xi là một hàm của những đỉnh có liên kết

với đỉnh đó. Tập các phương trình (1.2) được thể hiện theo ma trận (AT là ma

trận chuyển vị của A) là:

AT x = x (1.3)

14

Độ trung tâm của mỗi đỉnh được xác định theo hàm tuyến tính độ trung

tâm của những đỉnh có liên kết với đỉnh đó.

Khi nghiên cứu sức mạnh của các cộng đồng trên mạng xã hội, vị thế của

tác nhân được tăng lên bởi những đề cử (nominations) từ những người nhận

được nhiều đề cử khác. Trong cộng đồng mạng truyền thông, những người nhận

được nhiều trao đổi thông tin từ những người khác sẽ có nhiều nguồn thông tin

là có giá trị và tốt hơn.

Khi xét độ trung tâm của đỉnh i: cùng với tập các đỉnh lân cận của nó là

N(i), ta có:

𝑗∈𝑁(𝐼) = ∑ 𝐴𝑖𝑗

𝑗

(1.4) 𝑥𝑖 = ∑ 𝑥𝑗 𝑥𝑗

Độ trung tâm vector đặc trưng được định nghĩa theo cách này phụ thuộc

vào số các đỉnh lân cận |N(i)| và số các liên kết với nó là xj, j ∈ N(i). Cần lưu ý

rằng j  N(i) thì Aij = 0 nên ta có công thức (1.4).

Hệ phương trình (1.2) cho nghiệm là vector đặc trưng x khác 0 khi ma

trận A có giá trị đặc trưng là 1. Độ đo vector đặc trưng là độ đo trung tâm chuẩn

để phân tích mạng xã hội [11], [26], [27].

1.3.3. Độ đo trung tâm của đỉnh

Chúng ta xét một đồ thị vô hướng G = (V, E) bất kỳ (liên thông hoặc

không liên thông). Xét cặp đỉnh (vi, vj) bất kỳ, không phân biệt thứ tự. Giữa

chúng có thể có một hoặc nhiều đường đi. Nếu có đường đi giữa chúng thì độ

dài đường đi là bằng số cạnh (tổng trọng số trên các cạnh đối với đồ thị có trọng

số) trên đường đi đó. Trong số các đường đi đó sẽ có một số đường đi ngắn

nhất. Nếu (vi, vj), (vj, vi)  E, thì đường đi ngắn nhất sẽ có độ dài là 1. Trường

hợp đường đi ngắn nhất lớn hơn 1 thì chắc chắn phải có ít nhất một đỉnh khác

nằm trên đường đi ngắn nhất nối giữa vi với vj và những đỉnh này có tiềm năng

15

để điều khiển sự liên thông hay truyền thông (Control communications) giữa

các đỉnh vi, vj.

Ví dụ 1.3.

Xét đồ thị ở Hình 1.4. Giữa v1 và v3 có 2 đường đi ngắn nhất có độ dài

là 2, một đi qua v2, còn đường kia đi qua v4 và những đỉnh này có tiềm năng

điều khiển sự liên thông giữa các đỉnh v1, v3.

v3

v2 v4

v1

Hình 1.4. Đồ thị có 4 đỉnh và 5 cạnh

Chúng ta nghiên cứu và khái quát hóa khái niệm “khoảng giữa”, hay “độ

trung gian” (Betweenness) trong lý thuyết đồ thị [5]. Trước tiên xét một đỉnh

vk V và cặp các đỉnh (vi, vj) bất kỳ không phân biệt thứ tự với i  j  k.

Chúng ta định nghĩa độ trung gian (khoảng giữa) bộ phận của đỉnh vk đối

với (vi, vj), ký hiệu là Bij(vk) như sau:

 Nếu giữa vi và vj không có đường đi thì Bij(vk) = 0

 Ngược lại, nếu giữa chúng có đường đi, nghĩa là chúng liên thông với

nhau qua một số đường đi. Khi đó xác suất trao đổi, quan hệ giữa chúng

là 1/gij, với gij là số đường đi ngắn nhất giữa vi và vj. Như vậy, tiềm năng

mà vk điều khiển (control) thông tin trao đổi (mối quan hệ) giữa vi với vj

được xác định bằng chính bằng xác suất mà vk nằm trên những đường đi

ngắn nhất giữa chúng. Ký hiệu gij(vk) là số đường đi ngắn nhất có đi qua

vk, ta có

(1.5) Bij(vk) = gij(vk) / gij

16

Ví dụ 1.4.

Trên Hình 1.4., v2, v4 có xác suất nằm trên 2 đường đi ngắn nhất giữa v1

và v2 là ½. Như vậy, nếu vk nằm trên tất cả các đường đi ngắn nhất giữa vi và

vj thì Bij(vk) = 1. Trong những trường hợp này, thì vk là cần thiết để điều khiển

mối liên kết giữa vi và vj.

Để xác định được độ trung tâm (centrality) tổng thể của đỉnh vk trên đồ

thị thì cần phải tính tổng tất cả các độ trung gian bộ phận của vk đối với tất cả

các cặp đỉnh trên đồ thị.

Định nghĩa 1.1. Độ trung tâm của đỉnh vk trong đồ thị G = (V, E), ký hiệu là

C(vk) được xác định như sau:

, với |V| = n (1.6) C(vk) =

Nếu vk xuất hiện trên tất cả các đường đi ngắn nhất giữa hai đỉnh vi, vj

thì C(vk) tăng lên 1. Trường hợp vk chỉ xuất hiện trên một số đường đi ngắn

nhất giữa hai đỉnh vi, vj thì C(vk) sẽ tăng lên với một giá trị tương ứng là tỉ số

những lần xuất hiện trên những đường đi ngắn nhất giữa vi, vj như công thức

(1.5).

Độ trung tâm của đỉnh vk, C(vk) chính là hệ số tiềm năng để điều khiển

sự liên kết giữa các đỉnh trên đồ thị.

Việc tính C(vk) phụ thuộc vào hai yếu tố chính:

1. Sắp xếp các cạnh để xác định vị trí của vk và những đường đi ngắn

nhất giữa các cặp đỉnh.

2. Số đỉnh n trên đồ thị.

Chúng ta nhận thấy, độ trung tâm của đỉnh vk đạt được giá trị cực đại khi

mọi đỉnh khác trong G đều có cạnh nối với vkvà vk nằm trên tất cả các đường

17

đi ngắn nhất có độ dài lớn hơn 1. Những đồ thị như thế sẽ có dạng hình sao

(Star) hoặc bánh xe (wheel) như Hình 1.5 trong đồ thị, khi mọi đỉnh đều đến

được (có đường đi) tới tất cả các đỉnh khác (trực tiếp hoặc gián tiếp đi qua vk)

thì số đường đi giữa chúng là n * (n – 1)/2, trong đó có n-1 được nối với vk.

Vậy, độ trung tâm của đỉnh vk cực đại sẽ là

= (1.7) max C(vk) =

Ví dụ 1.5. Những đồ thị hình sao và bánh xe có số đỉnh 3, 4, 5, 6, 7.

Hình 1.5. Những đồ thị hình sao, bánh xe có số đỉnh 3, 4, 5, 6, 7

Một số độ đo “trung tâm” chuẩn:

𝑡∈𝑉

𝑐𝑙𝑜𝑠𝑒𝑛𝑒𝑠 𝑐𝑒𝑛𝑡𝑟𝑎𝑙𝑖𝑡𝑦 (𝑆𝑎𝑏𝑖𝑑𝑢𝑠𝑖, 1966) 𝐶𝐶(𝑣) = ∑ 1 𝑑𝐺(𝑣, 𝑡)

𝑔𝑟𝑎𝑝ℎ 𝑐𝑒𝑛𝑡𝑟𝑎𝑙𝑖𝑡𝑦 (𝐻𝑎𝑔𝑒 𝑎𝑛𝑑 𝐻𝑎𝑟𝑎𝑟𝑦, 1995) 𝐶𝐺(𝑣) = 1 𝑚𝑎𝑥𝑡∈𝑉𝑑𝐺(𝑣, 𝑡)

𝑠≠𝑣≠𝑡∈𝑉

𝐶𝑆(𝑣) = ∑ 𝜎𝑠𝑡(𝑣) 𝑠𝑡𝑟𝑒𝑠𝑠 𝑐𝑒𝑛𝑡𝑟𝑎𝑙𝑖𝑡𝑦 (𝑆ℎ𝑖𝑚𝑏𝑒𝑙, 1953)

𝑠≠𝑣≠𝑡∈𝑉

𝜎𝑠𝑡(𝑣) 𝜎𝑠𝑡

𝑏𝑒𝑡𝑤𝑒𝑒𝑛𝑛𝑒𝑠𝑠 𝑐𝑎𝑛𝑡𝑟𝑎𝑙𝑖𝑡𝑦 𝐶𝑆(𝑣) = ∑

(𝐹𝑟𝑒𝑒𝑚𝑎𝑛 1977; 𝐴𝑛𝑡ℎ𝑜𝑛𝑖𝑠𝑠𝑒, 1971)

18

Những độ đo trung tâm chuẩn chỉ ra rằng cạnh đó có thể đi tới những

cạnh khác trên những đường đi ngắn nhất tương ứng.

1.3.4. Hệ số trung gian của đỉnh

Độ đo trung tâm của mạng hay đồ thị được xác định theo hai cách. Cách

thứ nhất dựa vào lý thuyết đồ thị, trung tâm của đồ thị được đánh giá theo bậc

(degree), hay độ lân cận của các đỉnh trong đồ thị. Những đỉnh có bậc cực đại

có thể được xem như là tâm điểm của đồ thị. Đo theo cách này thì việc ứng

dụng sẽ bị hạn chế, bởi nó chỉ áp dụng được cho những bài toán như thiết kế

truyền thông với mục đích là nhằm đạt được hiệu quả truyền thông cực đại.

Cách thứ hai là dựa vào ưu thế trội (domination) của các đỉnh. Một thực thể

(đỉnh) có ưu thế trội là thực thể có thể điều khiển sự truyền thông trên mạng

(đồ thị).

Theo quan điểm của Freeman [12], một tác nhân nào đó trong mạng có

thể ít gắn kết với các thành viên khác trong mạng (tức hệ số trung tâm trực tiếp

thấp, bậc của đỉnh không cao), cũng không "gần gũi" lắm với mọi thành viên

trong mạng (tức hệ số trung tâm lân cận thấp), nhưng lại là "cầu nối" (bridge),

là "trung gian" cần thiết trong mọi cuộc trao đổi trong mạng. Nếu một tác nhân

đóng được vai trò trung gian càng lớn trong mạng lưới, tác nhân đó sẽ càng ở

vị trí thuận lợi trong việc "kiểm soát" mọi giao dịch, mọi thông tin trong mạng;

tác nhân đó cũng tác động đến mạng một cách dễ dàng bằng cách thanh lọc

hoặc "lái" thông tin lưu chuyển trong mạng theo hướng có lợi cho mình nếu

muốn; đồng thời tác nhân đó cũng đứng ở vị trí tốt nhất để thúc đẩy sự phối

hợp giữa các thành viên khác trong mạng. Freeman [12] đã đề xuất độ đo trung

tâm trung gian (betweenness centrality) gọi tắt là độ đo trung gian của một đối

tượng trong mạng xã hội là số các cá thể có thể trao đổi với nhau thông qua đối

tượng đó. Những đỉnh (cá thể) xuất hiện trên nhiều đường đi ngắn nhất giữa

19

các đỉnh có độ trung gian cao hơn những đỉnh không nằm trên những đường đi

ngắn nhất đó.

Chúng ta xét một đồ thị liên thông G = (V, E) bất kỳ (những đỉnh độc lập

không cần xét). Xét cạnh (cặp đỉnh) (vi, vj) bất kỳ, không phân biệt thứ tự đỉnh

đầu, đỉnh cuối. Giữa chúng có thể có một hoặc nhiều đường đi. Nếu có đường

đi giữa chúng thì độ dài đường đi là bằng số cạnh (tổng trọng số trên các cạnh

đối với đồ thị có trọng số) trên đường đi đó. Trong số các đường đi đó sẽ có

một số đường đi ngắn nhất. Nếu (vi, vj), (vj, vi)  E, thì đường đi ngắn nhất sẽ

có độ dài là 1. Trường hợp đường đi ngắn nhất có độ dài (tổng số cạnh trên

đường đi) lớn hơn 1 thì chắc chắn phải có ít nhất một đỉnh khác nằm trên đường

đi ngắn nhất nối giữa vi với vj và những đỉnh này có tiềm năng để điều khiển

sự liên thông hay truyền thông (control communications) giữa các đỉnh vi, vj.

Cho trước đồ thị G = (V, E) có n đỉnh, độ trung gian CB(v) của đỉnh v

được xác định như sau:

- Với mỗi cặp đỉnh (s, t), tính tất cả các đường đi ngắn nhất nối giữa chúng

- σst;

- Với mỗi cặp đỉnh (s, t), tính phân số giữa những đường đi ngắn nhất σst(v)

có đi qua v và số các đường đi ngắn nhất từ s tới t là σst(v)/σst;

- Tính tổng các phân số của tất cả các cặp đỉnh (s, t).

Ta ký hiệu σst là số đường đi ngắn nhất đi từ s tới t, và σst(v) là số đường

đi ngắn nhất đi từ s tới t và có đi qua v. Khi đó độ đo trung gian kí hiệu là CB(v)

của đỉnh v sẽ được tính như sau:

𝑠≠𝑡≠𝑣

(1.8) CB(v) = ∑ 𝜎𝑠𝑡(𝑣) /𝜎𝑠𝑡

Hệ số này cũng đi từ 0.00 đến 1.00. Khi một tác nhân nào đó có hệ số

trung tâm trung gian càng gần đến 1.00 thì số lượng quan hệ giữa các tác nhân

20

khác phải "thông qua" tác nhân này càng nhiều và do đó ảnh hưởng của tác

nhân này trên mạng cũng càng lớn.

Chúng ta nhận thấy, độ trung tâm của đỉnh v đạt được giá trị cực đại khi

mọi đỉnh khác trong G đều có cạnh nối với v và v nằm trên tất cả các đường đi

ngắn nhất có độ dài lớn hơn 1. Những đồ thị như thế sẽ có dạng hình sao (star)

hoặc hình bánh xe (wheel) [7],[12].

Tuy nhiên, việc sử dụng những độ đo này chỉ phù hợp cho những mạng,

trong đó khái niệm độ trung gian (Betweenness) được xem là quan trọng trong

tiềm năng ảnh hưởng tới quá trình xử lý sự liên kết giữa các đỉnh. Như trong

nghiên cứu các mạng truyền thông (Communication Network), vấn đề quan

trọng là cần xác định những cạnh có tiềm năng điều khiển truyền thông để đảm

bảo mạng truyền thông hiệu quả và bền vững.

1.3.5. Độ đo trung gian của cạnh

Chúng ta đã nghiên cứu ba độ đo C(vk) để xác định những tâm điểm của

đồ thị và chúng được ứng dụng trong nhiều mục đích khác nhau. Tuy nhiên,

việc sử dụng những độ đo này chỉ phù hợp cho những mạng, trong đó khái niệm

độ trung gian (Betweenness) được xem là quan trọng trong tiềm năng ảnh

hưởng tới quá trình xử lý sự liên kết giữa các đỉnh. Như trong nghiên cứu các

mạng truyền thông (Communication Network), vấn đề quan trọng là cần xác

định những cạnh có tiềm năng điều khiển truyền thông để đảm bảo mạng truyền

thông hiệu quả và bền vững.

Chúng ta định nghĩa độ đo “độ trung gian” (Betweenness) các cạnh trên

đồ thị như sau.

Định nghĩa 1.2. Độ trung gian của cạnh (a, b) là số các cặp đỉnh x và y mà cạnh

(a, b) nằm trên đường đi ngắn nhất nối giữa x và y.

21

Lưu ý: x, y có thể trùng với a, b.

Ta hình dung, cạnh (a, b) giữa hai cộng đồng thì a và b không nằm trong

cùng một cộng đồng. Một cạnh nằm giữa hai cộng đồng (được xem như là cầu

nối giữa hai cộng đồng đó), do vậy số các đường đi ngắn nhất đi qua cạnh đó

thường là khá lớn.

Ví dụ 1.6. Xét đồ thị

Hình 1.6. Đồ thị mạng xã hội đơn giản gồm 7 nút

Trên đồ thị ở Hình 1.6., cạnh (B, D) có độ trung gian là lớn nhất, bởi nó

nằm trên 12 đường đi ngắn nhất nối giữa các nút A, B, và C với D, E, F, và G,

3 × 4 = 12. Cạnh (D, F ) chỉ có 4 đường đi ngắn nhất nối giữa các nút A, B, C

và D với F.

Độ trung gian của cạnh e, ký hiệu là CB(e), được xác định như sau:

𝑠≠𝑡

𝛿𝑠𝑡 𝛿𝑠𝑡(𝑒)

(1.9) 𝐶𝐵(e) = ∑

Với hai đỉnh s, t  V, cạnh e  E và st(e) là số đường đi ngắn nhất đi từ

đỉnh s tới đỉnh t và đi qua cạnh e.

Độ đo trung gian của đỉnh v cũng có thể tính thông qua công thức tính

1

độ đo trung gian của cạnh e.

𝑒∈Γ(v)

2

∑ (1.10) 𝐶𝐵(𝑣) = 𝐶𝐵(e) − (𝑛 − 1)

22

Trong đó, Γ(v) là tập các cạnh kề với v và n là số đỉnh của thành phần

chứa v.

1.4. Thuật toán tính độ trung gian

Để tính độ trung gian của các đỉnh, cạnh thường phải thực hiện qua 2

bước:

1. Tính độ dài và số đường đi ngắn nhất giữa các cặp đỉnh

2. Tính tổng tất cả các độ trung gian của các cạnh.

Công việc chính của quá trình này là phát hiện tất cả các đường đi ngắn

nhất từ đỉnh tới gốc. Định nghĩa tập tiền tố của đỉnh v trên các đường đi ngắn

nhất từ s như sau:

(1.11) 𝑃𝑠(𝑣) = {𝑢 ∈ 𝑉: {𝑢, 𝑣} ∈ 𝐸, 𝑑𝐺(𝑠, 𝑢) = 𝑑𝐺(𝑠, 𝑢) + 𝑤(𝑢, 𝑣)}.

Bổ đề 1.1 (Tổ hợp của đường đi ngắn nhất) For s v ∈ V

𝑠≠𝑣≠𝑡∈𝑉

(1.12) 𝐶𝐵(𝑣) = ∑ 𝛿𝑠𝑡(𝑣)

Chứng minh. Theo giả thiết tất cả các trọng số đều là số dương, cạnh cuối của

đường đi ngắn nhất đi từ s tới v là cạnh (u, v) ∈ E sao cho dG(s, u

Từ Bổ đề 1.1 suy ra, số đường đi ngắn nhất đi từ s tới v kết thúc bằng

cạnh này đúng bằng số đường đi ngắn nhất đi từ s tới u.

Sự phụ thuộc của s ∈ V vào một đỉnh v ∈ V , được định nghĩa như sau:

𝑡∈𝑉

𝛿𝑠(𝑣) = ∑ 𝛿𝑠𝑡(𝑣)

Bổ đề 1.2 Nếu tồn tại đúng một đường đi ngắn nhất đi từ s ∈ V tới mọi đỉnh t

∈ V, thì sự phụ thuộc của s vào v ∈ V sẽ là

𝑤∶𝑣∈𝑃𝑠(𝑤)

(1.13) 𝛿𝑠(𝑣) = ∑ (1 + 𝛿𝑠(𝑤))

23

Để thực hiện thuật toán tính độ đo trung gian của các đỉnh trên đồ thị một

cách hiệu quả, người ta thường sử dụng phương pháp duyệt theo chiều rộng

BFS (Breadth-First Search) [11].

Thuật toán duyệt theo chiều rộng tìm kiếm các đường đi ngắn nhất từ

đỉnh gốc qua các cạnh tới tất cả các đỉnh khác trong đồ thị. Các cạnh giữa các

mức của quá trình duyệt BFS bắt đầu từ đỉnh gốc X sẽ tạo thành đồ thị định

hướng, phi chu trình, được gọi DAGX. Brandes đề xuất thuật toán duyệt theo

chiều rộng [21] bắt đầu từ mỗi đỉnh x  V và tính độ đo trung gian của các cạnh

trên đồ thị DAGx. Với mỗi đỉnh v trên DAGx, khoảng cách của đỉnh v đến gốc

x, được ký hiệu là dv, là số các cạnh trên đường đường đi ngắn nhất từ x đến v.

Thuật toán nhanh xác định trung tâm của độ trung gian FABC (Faster

Algorithm for Betweenness Centrality) trên đồ thị không có trọng số [5] được

thực hiện như sau.

Thuật toán FABC: Thuật toán thực hiện 4 bước.

Bước 1 – Khởi tạo giá trị biến chung

CB[r] ← 0, r ∈ V ;

for r ∈ V do{

Bước 2 – Khởi tạo biến cục bộ

S ← empty stack; Q ← empty queue;

P [w] ← empty list, w ∈ V ;

σ[t] ← 0, t ∈ V ; σ[r] ← 1;

d[t] ← ∞, t ∈ V ; d[r] ← ∞;

enqueue r → Q;

}

24

Bước 3 – Duyệt theo BFS

while Q not empty do{

dequeue v ← Q;

push v → S;

for all neighbor w of v do{

// w được tìm thấy lần đầu

if d[w] = ∞ then {

enqueue w → Q;

d[w] ← d[v] + 1;}

if d[w] = d[v] + 1 then {

σ[w] ← σ[w] + σ[v];

append v → P [w];

}

}

Bước 4 – Tích lũy vào CB

δ[v] ← 0, v ∈ V ;

while S not empty do

pop w ← S;

for all v ∈ P [w] do {

δ[v] ← δ[v] +σ[v]/σ[w](1 + δ[w]);

if w != r then

CB[w] ← CB[w] + δ[w];

25

}

Sau phần khởi tạo các giá trị cho mảng CB[v], v  V, stack S, và 3 mảng

bổ sung. Mảng σ xác định số đường đi ngắn nhất từ mỗi đỉnh tới gốc r của cây

các đường đi ngắn nhất, mảng d đo khoảng cách của mỗi đỉnh từ gốc cây BFS.

Đối với đồ thị không có trọng số, đây chính là số cạnh cực tiểu giữa mỗi đỉnh

và gốc của cây. Ban đầu, khoảng cách của các đỉnh và gốc đều gán bằng ∞.

Mảng P, là danh sách liên kết, mỗi đỉnh v là một danh sách liên kết P[v], chứa

tất cả các đỉnh đứng trước v trong cây duyệt theo chiều rộng BFS. Bước 3 và

Bước 4 là các thành phần chính của thuật toán.

Bước 3 duyệt theo chiều rộng BFS từ gốc cho trước để tìm đường đi ngắn

nhất tới tất cả các đỉnh khác. Trong bước này, mỗi phần tử được đặt vào một

hàng đợi khi nó được tìm thấy. Khi duyệt theo chiều rộng, khoảng cách từ gốc

s tới từng đỉnh v được tính. Với mỗi đỉnh v được tìm thấy trong lần duyệt BFS

sẽ tương ứng với một danh sách các đỉnh cha, những đỉnh gần gốc hơn. Tất cả

những đường đi ngắn nhất đi qua đỉnh cha của các đỉnh v và những đỉnh này

được tích lũy vào σ[v].

Ở công thức (1.7), σst(v) xác định số đường đi ngắn nhất đi từ s đến t mà

có qua v và σst là số đường đi ngắn nhất đi từ s đến t. Nếu không có đường đi

ngắn nhất đi từ s đến t và qua v thì σst(v) = 0.

Bước 4 tính độ trung gian CB (betweenness centrality) kỹ thuật tích lũy phụ

thuộc (dependency accumulation technique) của Brandes [5].

Trong [5] đã chứng minh được quan hệ sau:

{𝑤 |𝑣∈𝑃𝑠(𝑤)}

𝜎𝑠𝑣 𝜎𝑠𝑤

(1.14) 𝛿𝑠(𝑣) = ∑ (1 + 𝛿𝑠(𝑤)).

26

Từ đó suy ra rằng không cần thiết phải tính lâu hơn tổng của tất cả các

phụ thuộc cặp như quan hệ đệ qui. Ngoài ra ở đây có thể tính δs(w), thông qua

thuật toán tìm đường đi ngắn nhất từ gốc s đến một đỉnh còn lại của đồ thị.

Phân tích độ phức tạp

Kích thước bộ nhớ của stack, queue và các mảng σ và d là O(|V| ), nghĩa

là cỡ của các cấu trúc bổ sung được giới hạn bằng số đỉnh V của đồ thị. Bộ nhớ

cần thiết cho mảng liên kết được giới hạn bởi số cạnh E, đó là O(|E|). Bởi mỗi

lần duyệt BFS được tính độc lập, chỉ cần duy trì một bản copy của những cấu

trúc này, Bước 2 thực hiện duyệt cây BFS qua O(|V| + |E|) bước tính toán.

Không gian bộ nhớ của mảng CBcủa thuật toán là O(|V| + |E|). Do vậy, độ phức

tạp tính toán của việc duyệt cây BFS là O(|V| + |E|) và của việc tích lũy sự phụ

thuộc (dependency accumulation) cũng vào khoảng O(|V| + |E|), số các bước

cực đại được xác định bởi số đỉnh cha là O(|E|), và số đỉnh con tương ứng là

O(|V|). Vậy, độ phức tạp của thuật toán sẽ là O(|V|2 +|V| * |E|). Trong trường

hợp |E|>|V|, thì độ phức tạp của thuật toán sẽ là O(|V| * |E|).

1.5. Kết luận chương

Trong nội dung chương này học viên đã trình bày giới thiệu về mạng xã

hội và các đặc tính của mạng xã hội, cộng đồng mạng xã hội và phát hiện cộng

đồng mạng xã hội, tiếp theo là các độ đo trong mạng xã hội, thuật toán xác định

độ đo trung gian trên mạng xã hội. Ở chương tiếp theo của luận văn học viên

sẽ trình bày về cấu trúc cộng đồng mạng xã hội, một số phương pháp phát hiện

cộng đồng và tập trung vào thuật toán Girvan-Newman, sử dụng độ đo trung

gian để phát hiện cấu trúc cộng đồng mạng xã hội.

27

CHƯƠNG 2

THUẬT TOÁN PHÁT HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI

Hầu hết các phương pháp phát hiện cấu trúc cộng đồng trên mạng xã hội

đều tập trung vào việc nghiên cứu các mối liên kết giữa các thực thể để xác

định các cộng đồng. Trong chương này luận văn giới thiệu những thuật toán

phổ biến phát hiện cộng đồng trên đồ thị mạng xã hội như thuật toán phân cụm

đồ thị, thuật toán Girvan-Newman, sử dụng độ đo trung gian để phát hiện cấu

trúc cộng đồng mạng xã hội và thuật toán phát hiện các cộng đồng gối nhau.

2.1. Bài toán phát hiện cộng đồng trên đồ thị mạng xã hội

Bài toán: Phát hiện cộng đồng trong mạng xã hội và đưa ra danh sách những

đỉnh mạng thuộc từng cộng đồng đó.

Đầu vào: Đồ thị mạng xã hội G = (V, E) gồm tập V có các đỉnh: v1, v2,…, vn

và tập E các liên kết E = {(vi,vj)}.

Đầu ra: Tập các cộng đồng Ci và tập hợp các đỉnh thuộc các cộng đồng đó:

{C1, C2,..., Ck}.

Mục tiêu của bài toán là từ các mạng xã hội cho trước, phát hiện được

các cấu trúc cộng đồng nằm trong đó và tìm hiểu về mối liên hệ bên trong các

cộng đồng cũng như giữa các cộng đồng với nhau, mối liên hệ đó có ảnh hưởng

thế nào đến cấu trúc của toàn mạng xã hội. Một tập hợp các đỉnh trên đồ thị

được coi là một cộng đồng nếu mật độ cạnh bên trong nó cao hơn so với mật

độ của các cạnh giữa đỉnh của nó và những cạnh bên ngoài.

Phát hiện cộng đồng mạng xã hội là một trong những lĩnh vực nghiên

cứu quan trọng nhất trong bài toán phân tích mạng xã hội. Phát hiện cộng đồng

mạng xã hội có tầm quan trọng lớn trong xã hội học, sinh học và khoa học máy

tính. Phát hiện cộng đồng mạng xã hội gặp thách thức lớn đặc biệt sự phức tạp

28

tính toán bị chi phối bởi hai yếu tố chính. Yếu tố đầu tiên phải kể đến là kích

thước của mạng xã hội rất lớn. Yếu tố thứ hai liên quan đến bản chất của mạng

xã hội là động, có cấu trúc phát triển tăng dần theo thời gian. Chính những

thách thức này đã thu hút được một số lượng lớn các nhà nghiên cứu.

Phát hiện cộng đồng nhằm mục đích nhóm các đỉnh liên kết mạnh theo

các mối quan hệ giữa chúng để tạo thành các đồ thị con từ đồ thị ban đầu. Các

mạng xã hội thường được mô hình hoá dưới dạng đồ thị nên việc phát hiện

cộng đồng trên mạng xã hội dựa trên cơ sở lý thuyết đồ thị còn được gọi là bài

toán phân vùng đồ thị hay phân cụm đồ thị.

Trong nhiều thập kỷ qua, số các giải pháp phát hiện cấu trúc cộng đồng

trên mạng xã hội đã được nghiên cứu là rất nhiều và thường xuyên [1], [2], [3],

[20], [25].

Về cơ bản các thuật toán này được chia thành bốn nhóm thuật toán chính

và dưới đây sẽ trình bày các thuật toán chính của các phương pháp này.

2.2. Thuật toán phân cụm phân cấp

Nhóm thuật toán phát hiện cộng đồng truyền thông bao gồm các thuật

toán phân cụm theo đồ thị, phân cụm phân cấp, phân cụm phân hoạch, phân

cụm theo phổ và thuật toán phân chia.

Đồ thị có thể chứa cấu trúc phân cấp, mỗi cộng đồng có thể là một tập

hợp các cụm nhỏ ở các cấp độ khác nhau [11], [17]. Trong các trường hợp như

vậy, các kỹ thuật phân cụm phân cấp được sử dụng để xác định cộng đồng nhiều

cấp của đồ thị. Kỹ thuật phân cụm phân cấp dựa trên đo độ tương tự của đỉnh.

Chúng không cần xác định trước kích thước và số lượng các cộng đồng. Nhưng

chất lượng phát hiện cộng đồng không cao do việc lựa chọn độ đo tương tự của

đỉnh. Thuật toán sắp xếp dữ liệu đã cho thành cấu trúc có dạng hình cây, cây

29

này được xây dựng theo kỹ thuật đệ quy, cây phân cụm xây dựng theo hai

phương pháp Bottom-up và Top - down.

Thuật toán phân cụm phân cấp điển hình sử dụng chiến lược phân cụm

Top - down là thuật toán BIRCH (Balanced iterative reducing and clustering

using hierarchies) [31].

Đầu vào: Cơ sở dữ liệu gồm n đối tượng, ngưỡng T, k

Đầu ra: k cụm dữ liệu

Bước 1. Thuật toán duyệt tất cả các đối tượng trong cơ sở dữ liệu và khởi tạo

một cấu trúc cây. Một đối tượng được chèn vào đỉnh lá gần nhất tạo thành cụm

con. Nếu đường kính của cụm con này lớn hơn ngưỡng T thì đỉnh lá được tách.

Khi một đối tượng thích hợp được chèn vào đỉnh lá, tất cả các đỉnh trỏ tới gốc

của cây được cập nhật với các thông tin cần thiết.

Bước 2. Nếu cây hiện thời không có đủ bộ nhớ thì tiến hành xây dựng một cây

nhỏ hơn bằng cách điều khiển bởi tham số T, khi tăng tham số T thì đồng thời

sẽ làm nhập một số cụm con thành cụm lớn, làm cho cây nhỏ hơn.

Bước 3. Thực hiện phân cụm, các đỉnh lá của cây lưu giữ các đại lượng thống

kê của các cụm con. Thuật toán sử dụng các đại lượng thống kê này để áp dụng

một số kỹ thuật phân cụm như k-means.

Bước 4. Phân phối lại các đối tượng dữ liệu bằng cách dùng các đối tượng trọng

tâm cho các cụm đã được khám phá từ bước 3.

Thuật toán BIRCH gặp một số nhược điểm như: chất lượng của các cụm

không được tốt, tham số T có ảnh hưởng rất lớn tới chất lượng phân cụm.

Hạn chế đối với các thuật toán phân cụm đồ thị là các thuật toán phân

cụm thường phụ thuộc vào khoảng cách cơ bản giữa các điểm để lựa chọn các

điểm dữ liệu nào có quan hệ là gần nhau với mỗi điểm khác và các điểm dữ liệu

30

nào không có quan hệ hoặc có quan hệ là xa nhau với các điểm khác. Các thuật

toán phân cụm đồ thị có độ phức tạp rất lớn khi thực hiện việc xác định nghiệm

tối ưu toàn cục cho bài toán phân cụm dữ liệu.

2.3. Thuật toán phát hiện cộng đồng dựa trên tối ưu hoá độ đo đơn thể

Độ đo đơn thể (Modularity) [1], [3], [13] được sử dụng để đánh giá chất

lượng thuật toán phát hiện cộng đồng, độ đo có giá trị càng lớn thể hiện độ

chính xác của thuật toán càng cao, chất lượng việc phát hiện cộng đồng được

đánh giá là tốt. Thuật toán tìm kiếm tham lam của Newman [13], là thuật toán

đầu tiên được đề xuất nhằm tối ưu hóa độ đo đơn thể (mô đun). Đây là một kỹ

thuật tích tụ, trong đó ban đầu mỗi đỉnh thuộc về một mô đun riêng biệt, sau đó

chúng được hợp nhất lặp lại dựa trên mức độ tăng các mô đun. Thuật toán có

độ phức tạp thời gian tính toán là 𝑂(𝑛3), với n là số đỉnh của đồ thị. Thuật toán

tìm kiếm tham lam điển hình là thuật toán Louvain.

Thuật toán đơn thể hóa Louvain (Louvain modularity) được đề xuất bởi

Blondel và các cộng sự [17] là một thuật toán heuristic tìm kiếm tham lam để

phát hiện các cộng đồng ở đồ thị có trọng số và dựa trên tối ưu hoá độ đo đơn

thể. Nó gán các cộng đồng khác nhau cho mỗi đỉnh và lặp lại việc hợp nhất các

đỉnh dựa trên mức độ tăng của độ đo đơn thể. Nếu không đạt được, thì đỉnh vẫn

ở trong cấu trúc cộng đồng của chính nó. Thuật toán được lặp đi lặp lại cho đến

khi không thể cải tiến thêm nữa. Độ phức tạp tính toán của thuật toán là

O(nlogn).

2.4. Thuật toán phát hiện cộng đồng dựa vào độ đo trung gian

Bài toán phát hiện cộng đồng tập trung vào việc từ một đồ thị mạng xã

hội, tìm ra những cụm, nhóm cộng đồng có mối liên hệ chặt chẽ với nhau. Qua

trực quan có thể dễ dàng tìm ra những nhóm cộng đồng có độ trung tâm (tập

trung) cao, nhưng không phải cộng đồng nào cũng được hình thành bằng các

31

mối liên hệ chặt chẽ và dễ thấy, một số cộng đồng có thể được hình thành ẩn.

Điều quan trọng là phải tìm được sự phân phối của các cạnh giữa các đỉnh, từ

đó đưa ra các cộng đồng tồn tại trong mạng xã hội.

Thay vì việc tìm kiếm những đỉnh trong đồ thị có độ gắn kết cao với nhau,

phương pháp phát hiện cộng đồng bằng thuật toán phân chia được đưa ra như

một cách giải quyết hữu hiệu. Để tránh các khuyết điểm của phương pháp phân

cụm phân cấp, thay vì cố gắng để xây dựng một giải pháp tìm cạnh trung tâm

của cộng đồng, chúng ta đi tìm những cạnh có độ trung gian cao nhất, cạnh đó

được gọi tên là cạnh nối (cầu nối) giữa các cộng đồng. Girvan-Newman [17]

cho rằng khi các cộng đồng được gắn kết với nhau thì đường đi giữa cộng đồng

này đến cộng đồng khác sẽ đi qua các cạnh nối giữa các cộng đồng với tần suất

cao. Mục đích chính của thuật toán là tìm những cạnh nối đó. Thay vì việc xây

dựng cộng đồng bằng cách thêm vào các cạnh có độ trung tâm cao nhất, chúng

ta sẽ xây dựng bằng cách loạn bỏ dần dần các cạnh nối (cầu nối) từ đồ thị ban

đầu. Khi đó, các cộng đồng trong mạng sẽ bị ngắt kết nối với nhau, ta có thể

xác định được cách phân vùng đồ thị thành các phần nhỏ riêng biệt. Để làm

được việc này, điều quan trọng nhất của thuật toán là việc tính toán như thế

nào, sử dụng tính chất nào để phát hiện ra những cạnh nối này, từ đó loại bỏ

chúng ra khỏi đồ thị. Thuật toán lần đầu tiên được đề xuất bởi Freeman [12].

Theo Freeman, các cạnh nối được coi là cạnh có số lượng con đường ngắn nhất

giữa các cặp đỉnh khác nhau chạy qua nó. Cạnh nối có ảnh hưởng rất lớn đến

dòng chảy của thông tin giữa các đỉnh khác, đặc biệt là trong trường hợp thông

tin lưu truyền trong mạng chủ yếu theo con đường ngắn nhất. Thuật toán điển

hình nhất trong các thuật toán chia này là thuật toán Girvan-Newman [13, 20].

Thuật toán Girvan-Newman (GN) duyệt qua mỗi đỉnh (nút) v một lần và

tính số đường đi ngắn nhất từ v tới những đỉnh khác có đi qua từng cạnh đó. Tư

32

tưởng chính của thuật toán GN được thực hiện theo kỹ thuật phân cụm phân

cấp.

Input: Đồ thị mạng xã hội G = (V, E)

Output: Tập các cộng đồng

Bước 1. Tính độ trung gian của tất cả các cạnh trong mạng,

Bước 2. Tìm những cạnh có độ trung gian lớn nhất và loại bỏ chúng,

Bước 3. Tính lại độ trung gian của tất cả các cạnh trong các thành phần còn lại,

Bước 4. Lặp lại từ bước 2 cho đến khi đến khi không có cạnh nào vượt qua

ngưỡng của độ độ trung gian cho trước hoặc không còn cạnh trung gian.

Ví dụ 2.2. Sử dụng thuật toán GN để phát hiện cộng đồng cho đồ thị sau

Hình 2.1. Phát hiện cộng đồng mạng sử dụng Girven-Newman

Thuật toán Girvan-Newman khá đơn giản và dễ hiểu. Toàn bộ thuật toán

có thể được biểu diễn trong một dendrogram, ở đây ta có thể hiểu là thuật toán

đi từ gốc đến các lá. Các nhánh của cây biểu diễn cho các phép loại bỏ cạnh để

chia đồ thị thành các cộng đồng riêng rẽ.

33

Thuật toán Girvan-Newman đưa lại kết quả tương đối tốt trong nhiều

trường hợp, mặc dù vậy nó vẫn gặp phải một số nhược điểm:

1. Thuật toán Girvan-Newman sử dụng phương pháp loại trừ đến khi

không có cạnh nào vượt qua ngưỡng của độ trung gian cao nhất, vì vậy nên số

lượng cộng đồng hoàn toàn không kiểm soát trước được. Bên cạnh đó, thuật

toán sử dụng nhiều phép phân vùng, khó có thể xác định được phép phân vùng

nào mang lại hiệu quả tốt nhất.

2. Do tại mỗi lượt thực hiện, thuật toán tính lại độ trung gian của mỗi

cạnh liên quan sau khi xóa đi cạnh có độ trung gian lớn nhất nên độ phức tạp

thời gian là khá cao. Giả sử với đồ thị n đỉnh, số cạnh phải xóa đi khỏi đồ thị là

m cạnh thì ta cần lượng thời gian tính toán O(mn) cho mỗi lần lặp. Tổng thời

gian chạy thuật toán O(m2n). Trong trường hợp xấu nhất, mỗi đỉnh được chia

ra thành một cộng đồng riêng rẽ thì độ phức tạp thời gian của thuật toán sẽ lên

đến O(n3).

3. Trên thực tế, mỗi đơn vị nút mạng có thể thuộc vào rất nhiều cộng

đồng khác nhau. Ví dụ với một cá nhân A, đóng góp vai trò là một nút trên

mạng xã hội có thể thuộc vào nhiều nhóm: Bạn cùng lớp, đồng nghiệp cùng

công ty, anh em họ hàng trong gia đình… Nhưng với cách phân chia của

Girvan-Newman không giải quyết được hiện tượng chồng chéo cộng đồng trên.

2.5. Phát hiện các cộng đồng gối nhau

Trong thực tế trên mạng xã hội nói riêng, mạng truyền thông nói chung

thì phần lớn các cộng đồng không rời nhau hoàn toàn mà chúng có thể gối nhau

(overlap), chồng lấp hay giao nhau trong một phạm vi nào đó, nghĩa là một số

đỉnh có thể thuộc nhiều hơn một cộng đồng. Ví dụ mạng cộng tác trong nghiên

cứu khoa học (collaboration networks), một tác giả có thể tham gia nghiên cứu

cùng với một số nhà khoa học khác trong nhiều nhóm khác nhau, hay trong

34

mạng logic-sinh học (bio-logical networks), một protein có thể tương tác với

nhiều nhóm của các protein khác [1], [14].

Để phát hiện những cộng đồng vừa gối nhau vừa phân cấp, thuật toán

EAGLE (agglomerativE hierarchicAl clusterinG based on maximaL cliquE)

[14] đề cập đến tập các cliques cực đại và thực hiện theo kỹ thuật gộp nhóm

(tích tụ dần). Đồ thị G có clique C là tập các đỉnh của một đồ thị con đầy đủ

thuộc G, sao cho có cạnh nối giữa hai đỉnh bất kỳ của C và đường đi ngắn nhất

giữa hai đỉnh v, w bất kỳ đó đều có độ dài 1  d(v, w)  k.

Cộng đồng mạng có mật độ liên kết tương đối dày đặc, khi tập các đỉnh

(một cộng đồng) liên kết với phần còn lại của mạng nhiều hơn, mật độ liên kết

của một clique là cao nhất trong tất cả các tập đỉnh con của đồ thị (mạng).

Những cộng đồng có mật độ liên kết dày đặc này sẽ chứa đựng một clique lớn

gọi là tâm (lõi) của cộng đồng.

2.5.1. Phát hiện các k-cliques trong mạng xã hội

Trong mạng xã hội, có những nhóm con cố kết (cohesive subgroups) với

nhau như các nhóm công tác, các đội thể thao, đảng phái chính trị, các giáo

phái, hay những tổ chức bí mật như các các nhóm mafia, hay nhóm khủng bố,

… Những nhóm cố kết như vậy được thể hiện trong lý thuyết đồ thị bằng các

cliques hay k-clique (phường hội), k-club (câu lạc bộ) và k-clan (phe phái), ...

Định nghĩa 2.1. Trong đồ thị G = (V, E), với v, w  V, đường trắc địa

(geodesics) là đường đi ngắn nhất nối hai đỉnh và khoảng cách giữa hai đỉnh,

ký hiệu là g(v, w) là độ dài của đường trắc địa.

Định nghĩa 2.2. Tập con cực đại các đỉnh C  V được gọi là k-clique, nếu với

mọi cặp đỉnh v, w (v  w) thuộc C thì 1 ≤ g(v, w) ≤ k.

35

Nói cách khác, k-cliques là tập các đỉnh của đồ thị con của một đồ thị

mà giữa hai đỉnh bất kỳ đều có đường đi đến được nhau với độ dài nhỏ hơn

hoặc bằng k. Tập cực đại theo nghĩa không còn đỉnh nào khác trong đồ thị có

khoảng cách nhỏ hơn hoặc bằng k tới các đỉnh của đồ thị con đó.

Hiển nhiên, 1-clique là đồng nhất với clique, bởi khoảng cách giữa hai

đỉnh bằng 1, nghĩa là có cạnh nối chúng với nhau. 2-clique tạo thành đồ thị con

đầy đủ với độ dài các đường đi là 1 hoặc 2. Khoảng cách đường đi bằng 2 trong

mạng xã hội có thể được xem như quan hệ “Bạn của bạn” (friend of a friend)

hay các websites giống như LinkedIn, mỗi thành viên có thể liên kết qua 2 hay

3 cấp.

Ví dụ 2.3. Hình 2.2. minh họa về 1-clique, 2-clique và 3-clique.

Hình 2.2. Ví dụ 1-clique, 2-clique và 3-clique

Mô hình k-clique cũng có một số hạn chế như một số đỉnh có thể cách

xa nhóm, nghĩa là khoảng cách giữa hai đỉnh có thể tương ứng với đường đi

bao gồm những đỉnh không nằm trong k-clique. Ví dụ, đồ thị trên Hình 2.3, có

2-cliques là C = {v1,v2, v3, v4, v5}, trong đó có hai đỉnh 4, 5 có khoảng cách

là v2 (đi qua đỉnh v6), nhưng đỉnh v6 lại không nằm trong C. Để khắc phục

những hạn chế đó, người ta sử dụng khái niệm đường kính (diameter) dựa trên

mô hình k-clan và k-club. Đường kính của đồ thị G = (V, E) được xác định bởi

36

diam(G) = max g(u, v) với mọi u, v ∈ V.

Định nghĩa 2.3. Một k-club là tập con S các đỉnh của đồ thị G sao cho đồ thị

con được cảm sinh bởi S có đường kính nhỏ hơn hoặc bằng k. Hay nói cách

khác, k-Club tương tự như k-clique nhưng định nghĩa chặt hơn. Các đỉnh trên

đường dẫn ngắn nhất phải thuộc về đồ thị con đó

Định nghĩa 2.4. k-Clan là một k-clique, mà đối với tất cả các đường dẫn ngắn

nhất trong đồ thị con , khoảng cách nhỏ hơn hoặc bằng k.

Hệ quả: mọi k-clan là k-club và k-clique. 𝑘 − 𝐶𝑙𝑎𝑛 = 𝑘 −𝐶𝑙𝑖𝑞𝑢𝑒 ⋂ 𝑘 − 𝐶𝑙𝑢𝑏

Lưu ý, để tìm tất cả các k-clan, trước tiên hãy tìm tất cả k-clique S, sau đó loại

bỏ những k-clique có khoảng cách lớn hơn k trong đồ thị con cảm sinh.

Hình 2.3. 2-cliques, 2-clan và 2-club

2.5.2. Thuật toán phát hiện k-clique

Khai phá dữ liệu đồ thị để làm rõ hơn cấu trúc của đồ thị mạng xã hội,

thông qua phân tích các nhóm con cố kết của mạng trên cơ sở phát hiện các k-

clique. Với thuật toán hai pha (two-phase) tìm các cộng đồng k-clique như sau:

Input: Đồ thị G và khoảng cách k.

Output: các k-clique được bao phủ.

Tìm tất cả các k-clique lớn nhất trong đồ thị.

1. 1.1 Xác định bậc kth của đồ thị.

1.2 Áp dụng thuật toán tìm clique lớn nhất.

37

2. Tìm các k-clique được bao phủ trong đồ thị G.

2.1 Áp dụng thuật toán bao phủ.

Thuật toán tìm k-clique cực đại

Biến đổi đồ thị G = (V, E) sang đồ thị G = (V, E)k sao cho với mọi i, j

V, d(i, j) ≤ k. Đồ thị G = (V, E)k được tạo ra từ bậc kth của đồ thị G có cùng

tập đỉnh như G và một cạnh mới giữa hai đỉnh nếu giữa chúng có một liên kết

với độ dài lớn nhất là k.

Tìm đồ thị con đầy đủ lớn nhất của một đồ thị cho trước chính là bài toán

tìm clique cực, bằng cách đi tìm giới hạn dưới của bài toán cực đại với các

phương pháp heuristics [17] và tìm kiếm (meta-heuristic) Tabu Search [27].

Giả sử n = |S| là lực lượng (số đỉnh) của clique S và Ak(S) là tập con các

đỉnh có k cạnh liên thuộc trong S. Vậy định nghĩa A(S) là tập các đỉnh liền kề

𝑛 với các đỉnh của S và A(S) có thể chia thành các nhóm con:A(S) = ⋃ 𝑘=1

𝐴𝑘(𝑆)

Tập hợp số các đỉnh |V| của đồ thị bằng tổng số đỉnh liên thuộc A(S) và

𝑛 𝑘=1

. không liên thuộc A0(S), ta có ∑ |𝐴𝑘(𝑆)| + 𝑛

Gọi N(S) là tập lân cận khi chúng sinh ra clique S’ trong tập S và:

N+ (S) = {S´ : S´= S ∪{vi}, vi ∈ An(S)}

N– (S) = {S´ : S´= S \{vi}, vi ∈ S}

N0 (S) = {S´ : S´= S ∪{vi}\{vk}, vi ∈ An-1(S), vk ∈ S}

Khi S là clique hiện thời thì S* là clique cực đại đã tìm được, T là danh

sách trong bảng tabu và N(S) là các cấu trúc lân cận.

Thuật toán: Clique cực đại theo đánh giá (heuristic)Tabu: Input: Gk, đồ thị con đầy đủ (clique) S

Output: clique S*

1. T = ∅; S* = S;

38

2. while {

2.1.

2.2. cập nhật T;}

2.2.1. if (N+(S) \ T ≠ null) then chọn S’ là cực đại else if (N0(S) \ T ≠ null) then {chọn S’ là cực đại; else {chọn S’ trong N–(S) là cực đại;

cập nhật T; }

2.3. cập nhật S = S’ ;

2.4. if (|S| > |S*|) S* = S;

3. };

4. return S*;

Tìm một clique lớn nhất trong đồ thị Gk tương đương với việc tìm một

k-clique lớn nhất trong đồ thị G. Để tạo ra một tập hợp lớn hơn với các k-clique

cực đại, bằng cách thuật toán bắt đầu nhiều lần (multi-start) để gọi thuật toán

tìm clique cực đại theo đánh giá Tabu [27].

2.5.3. Thuật toán EAGLE

Để phát hiện những cộng đồng vừa gối nhau vừa phân cấp, thuật toán

EAGLE (agglomerativE hierarchicAl clusterinG based on maximaL cliquE)

[14] đề cập đến tập các cliques cực đại và thực hiện theo kỹ thuật gộp nhóm

(tích tụ dần). Đồ thị G có clique C là tập các đỉnh của một đồ thị con đầy đủ

thuộc G, sao cho có cạnh nối giữa hai đỉnh bất kỳ của C và đường đi ngắn nhất

giữa hai đỉnh v, w bất kỳ đó đều có độ dài 1  d(v, w)  k.

Cộng đồng mạng có mật độ liên kết tương đối dày đặc, khi tập các đỉnh

(một cộng đồng) liên kết với phần còn lại của mạng nhiều hơn, mật độ liên kết

của một clique là cao nhất trong tất cả các tập đỉnh con của đồ thị (mạng).

Những cộng đồng có mật độ liên kết dày đặc này sẽ chứa đựng một clique lớn

gọi là tâm (lõi) của cộng đồng.

Thuật toán EAGLE được thực hiện qua hai giai đoạn:

39

1. Tạo ra một cây dendrogram:

a) Tìm tất cả các cliques cực đại trên mạng và bỏ qua những clique

cực đại thứ cấp, những clique còn lại và các đỉnh thứ cấp (bao

gồm một đỉnh duy nhất) được thực hiện như là những cộng đồng

khởi tạo ban đầu, tính độ tương đồng giữa các cặp cộng đồng,

b) Chọn những cặp cộng đồng có độ tương đồng cực đại và kết hợp

chúng thành một cộng đồng mới, tính độ tương đồng giữa cộng

đồng mới các cộng đồng khác,

c) Lặp lại bước b. cho đến khi chỉ còn lại một cộng đồng.

2. Chọn những vị trí cắt thích hợp để chia cây dendrogram thành các

cộng đồng:

Xác định độ đo phù hợp để đánh giá quá trình phân cụm và độ đo sự phân

chia của các cộng đồng gối nhau [13], với độ đo được sử dụng là EQ được định

nghĩa như sau:

𝐸𝑄 = ] (2.10) [𝐴𝑣𝑤 − 1 2𝑚 𝑘𝑣𝑘𝑤 2𝑚 1 𝑂𝑣𝑂𝑤 ∑ 𝑖 ∑ 𝑣∈𝐶𝑖,𝑤∈𝐶𝑖

Trong đó, Ov là số các cộng đồng có chứa đỉnh v.

Trong thuật toán EAGLE, độ tương đồng S giữa cộng đồng C1 và C2

được định nghĩa như sau:

𝑣∈𝐶1,𝑤∈𝐶2,𝑣≠𝑤

𝑆 = ] (2.11) ∑ [𝐴𝑣𝑤 − 1 2𝑚 𝑘𝑣𝑘𝑤 2𝑚

Trong đó, Avw là phần tử của ma trận liền kề của đồ thị mạng (đồ thị vô

1

hướng, không trọng số). Nếu có cạnh nối v với w thì Avw = 1, ngược lại Avw =

2

0. Tổng số cạnh trên mạng là 𝑚 = và mức độ của đỉnh v là kv. ∑ 𝐴𝑣𝑤 𝑣𝑤

40

Khi mỗi đỉnh chỉ thuộc một cộng đồng thì EQ = 0, EQ có giá trị cao sẽ

thể hiện cấu trúc cộng đồng nhiều hơn.

Ví dụ 2.4. Đồ thị (mạng) ban đầu Hình 2.4.(a) có 23 đỉnh, để mô phỏng mộ đồ

thị có các cộng đồng chồng chéo và phân cấp, ta loại bỏ cạnh nối các đỉnh 9

và 13 và thêm các cạnh nối giữa đỉnh 10, 15 và 10, 13 Hình 2.4.(b).

Hình 2.4. (a), (b). Mạng ban đầu

Thuật toán nhanh tìm cấu trúc cộng đồng của Newman [20] phân vùng

mạng dựa trên tối ưu hóa mô dun tìm thấy được ba cộng đồng, áp dụng thuật

toán nhiều lần sẽ tìm thấy các cộng đồng con bên trong cộng đồng lớn đã tìm

được trong Hình 2.5.(c). Nhưng sự chồng chéo của các cộng đồng không được

thể hiện rõ ràng.

41

Hình 2.5. (c). Các cộng đồng được phát hiện bởi thuận toán của Newman

Với thuật toán k-clique trong Hình 2.6.(d). cho thấy các cấu trúc cộng

đồng được tìm thấy rõ ràng hơn nhưng không thể hiện rõ sự phân cấp.

Hình 2.6.(d). Các cộng đồng được phát hiện bởi thuật toán k-clique

42

Thuật toán EAGLE cần tìm tất cả các cliques trong mạng, với các cliques

cực đại sẽ phát hiện những cộng đồng gối nhau và phân cấp, tuy nhiên không

phải tất cả các cliques cực đại được sử dụng. Những clique cực đại mà đỉnh của

chúng là đỉnh của những cliques cực đại lớn hơn, được gọi là cliques cực đại

thứ cấp (subordinate maximal cliques). Trong hình 2.7.(e), thuật toán tìm thấy

các cấu trúc cộng đồng thể hiện sự chồng chéo và phân cấp rõ ràng, cộng đồng

này được chia thành hai cộng đồng nhỏ hơn và có các đỉnh chung là 10, 11, 12.

Hình 2.7.(e). Các cộng đồng thể hiện sự chồng chéo và phân cấp rõ ràng

được phát hiện bởi thuật toán EAGLE

Ví dụ 2.5. Trong Hình 2.6.(d) hai đỉnh 4 và 23 tạo thành một clique cực đại thứ

cấp, bởi đỉnh 4 là đỉnh của cliques cực đại lớn hơn là {1, 2, 3, 4, 5, 6} và đỉnh

23 là đỉnh của cliques cực đại khác lớn hơn bao gồm, {18, 20, 21, 23}, {18, 20,

22, 23} và {18, 19, 22, 23}. Các clique cực đại thứ cấp thường có kích cỡ (số

đỉnh) nhỏ và có thể dẫn đến những kết quả thuật toán không mong muốn.

43

Với k là một giới hạn (ngưỡng) được đặt ra để loại bỏ những cliques cực đại

có số đỉnh nhỏ hơn k, và sẽ loại bỏ đi những cliques cực đại không phải là thứ cấp.

Giá trị của k nhỏ thì những cliques cực đại thứ cấp bị bỏ qua, ngược lại giá trị của

k cao thì những cliques cực đại không phải là thứ cấp bị sót lại. Giới hạn của k trong

các mạng lớn từ 3 đến 6, trong Hình 2.6. giá trị giới hạn thích hợp là 3 và 4.

2.5.4. Đánh giá thuật toán

Tiếp theo chúng ta phân tích độ phức tạp của thuật toán. Giả sử n là số

đỉnh của đồ thị mạng, s là số clique cực đại được khởi tạo ban đầu của thuật

toán và h là số cặp clique cực đại có quan hệ lắng giềng (neighbors) với nhau

(hai cliques liên kết với nhau bởi một số cạnh hoặc gối nhau). Chúng ta xét giai

đoạn đầu của thuật toán. Trong Bước 1., chúng ta cần thực hiện O(n2) phép toán

để tính độ tương tự giữa từng cặp cộng đồng được khởi tạo ban đầu. Ở Bước

2., ta chỉ xét những cặp cộng đồng lắng giềng của nhau. Mỗi phép chọn phải

thực hiện h phép toán và thời gian kết nối chúng nhiều nhất là O(n). Vậy, số

phép toán cần thiết để thực hiện giai đoạn một của thuật toán là O(n2 + (h +

n)s). Giai đoạn hai cần tính giá trị EQ tương ứng với mỗi độ phủ. Trong cài đặt,

chúng ta tính giá trị EQ cho lần phát hiện đầu tiên và cập nhật lại sau mỗi lần

kết nối hai cộng đồng được lựa chọn để tạo ra một cộng đồng mới. Thời gian

cập nhật nhiều nhất là cỡ n2. Ngoài ra, chúng ta cần tìm tất cả các cliques cực

đại trên đồ thị mạng. Đây là bài toán được biết là bài toán không phải đa thức.

Tuy nhiên, trong các mạng thực tế, việc tìm tất cả các cliques cực đại là khá

đơn giản bởi chúng khá thưa (sparseness). So với thuật toán phát hiện nhanh k-

clique của Newman thì thuật toán EAGLE thực hiện chậm hơn. Do vậy, vấn đề

là cần cải tiến EAGLE để toán phát hiện nhanh k-clique trên các mạng thực tế.

44

2.6. Kết luận chương 2

Chương 2 trình bày bài toán phát hiện cộng đồng, gồm những thuật toán

phân cụm phân cấp đồ thị, thuật toán phát hiện cộng đồng dựa vào độ trung

gian và GIRVAN-NEWMAN, thuật toán phát hiện cộng đồng gối nhau

EAGLE dựa vào tập các clique cực đại. Thuật toán GIRVAN-NEWMAN

được ứng dụng thực nghiệm để phát hiện cộng đồng trong mạng xã hội thực

được trình bày ở chương 3.

45

CHƯƠNG 3

ỨNG DỤNG THUẬT TOÁN GIRVAN-NEWMAN TRONG PHÁT

HIỆN CỘNG ĐỒNG MẠNG XÃ HỘI

3.1. Mô tả bài toán phát hiện cộng đồng mạng xã hội

Bài toán: Phát hiện cộng đồng trong mạng xã hội và đưa ra danh sách những

nút mạng thuộc từng cộng đồng đó.

Đầu vào: Đồ thị mạng xã hội G = (V, E) gồm tập V có đỉnh: v1, v2,…,vn và tập

E các liên kết E = {(vi,vj)}.

Đầu ra: Tập các cộng đồng Ci và tập hợp các đỉnh thuộc các cộng đồng đó: {C1,

C2,...,Cn}

Mục tiêu của bài toán là từ các mạng xã hội cho trước được biểu diễn

bằng đồ thị, phát hiện được các cấu trúc cộng đồng nằm trong đó và tìm hiểu

về mối liên hệ bên trong các cộng đồng cũng như giữa các cộng đồng với nhau,

mối liên hệ đó có ảnh hưởng thế nào đến cấu trúc của toàn mạng xã hội.

3.2. Chương trình phát hiện cộng đồng mạng xã hội

3.2.1. Bộ cơ sở dữ liệu

Hiện nay có rất nhiều bộ cơ sở dữ liệu về mạng xã hội được cung cấp

miễn phí. Trong luận văn này, tôi sử dụng các bộ cơ sở dữ liệu như sau:

- Simple_network và p_n: Đây là bộ dữ liệu gồm 14 đỉnh và 17 cạnh được tạo

ra nhằm mục dích demo về mối quan hệ cộng đồng trong mạng.

- Karate: Mạng xã hội về mối quan hệ bạn bè giữa 34 thành viên trong một câu

lạc bộ karate tại một trường đại học ở Hoa Kỳ vào những năm 1977. Bộ dữ liệu

này gồm 34 đỉnh và 78 cạnh. Bộ dữ liệu này được Zachary cùng các cộng sự

xây dựng vào năm 1977 [28].

46

- Dolphins: là một mạng xã hội vô hướng về mối quan hệ giữa 62 con cá heo

trong một cộng đồng sống ở New Zealand được Lusseau cùng các cộng sự xây

dựng năm 2003 [10]. Bộ dữ liệu này gồm 62 đỉnh và 159 cạnh.

- Football: là mạng các trận bóng đá giữa các trường đại học trong kỳ mùa thu

năm 2000 của Mỹ. Bộ dữ liệu này được Girvan và Newman xây dựng năm

2002 [19] bao gồm 115 đỉnh và 613 cạnh.

- Amazon: là mạng mua sắm sản phẩm trực tuyến. Bộ dữ liệu Amazon được

xây dựng dựa trên việc theo dõi các sản phẩm thường được cùng mua với nhau.

Trong bộ dữ liệu này, mỗi đỉnh đại diện cho một sản phẩm và mỗi cạnh tương

ứng là các sảm phẩm thường được mua với nhau. Bộ dữ liệu bao gồm 2 loại,

bộ Amazon_small bao gồm 3,225 đỉnh và 10,262 cạnh.

- Youtube: là một mạng chia sẻ video nổi tiếng trên thế giới được xây dựng bởi

Google. Trong bộ dữ liệu Youtube, mỗi người sử dụng được đại diện bởi một

đỉnh, mỗi thành viên này đều thuộc một hoặc nhiều nhóm quan hệ bạn bè được

biểu diễn bởi các cạnh. Bộ dữ liệu này bao gồm 4,890 đỉnh, 20,787 cạnh.

- DBLP: đây là mạng cộng tác giữa các nhà khoa học, trong mạng này, mỗi

đỉnh thể hiện một tác giả và mỗi cạnh kết nối các tác giả với nhau nếu giữa họ

đã có chung một bài báo. Bộ dữ liệu này bao gồm 10824 đỉnh, 38732 cạnh đối

với DBLP_small.

Các bộ dữ liệu: Amazon, Youtube, DBLP đều được Jaewon Yang và Jure

Leskovec xây dựng năm 2015 [30].

47

Bảng 3.1. Mô tả chi tiết về các bộ dữ liệu được sử dụng trong phát hiện

cộng đồng mạng

Bộ dữ liệu Số đỉnh Số cạnh Số cộng đồng

Simple_network 14 17 4

P_n 14 24 -

dolphins 62 1,159 2

football_network 115 613 12

karate 34 78 2

Amazon_small 3,225 10,262 -

Dblp_small 10,824 38,732 -

Youtube_small 4,890 20,787 -

Amazon_big 334,863 925,872 75,149

Dblp_big 317,080 1,049,866 13,477

3.2.2. Môi trường thử nghiệm

Thuật toán Girvan-Newman, thuật toán Louvian và thuật toán tìm

EAGLE trong phát hiện cộng đồng đều sử dụng chung môi trường thử nghiệm

như sau:

- Phần cứng: Các thông tin về phần cứng được sử dụng trong luận văn thể hiện

ở bảng 3.2.

48

Bảng 3.2. Thông tin phần cứng được sử dụng

Thông tin phần cứng Chỉ số

CPU i7-4790 24 core 2.4GHz

RAM 64GB DDR4 tốc độ bus:2666Mhz

GPU Không

SSD 1TB NVME tốc độ 3GB/s

OS Ubuntu 20.04 phiên bản 64bit

- Phần mềm và ngôn ngữ lập trình

Các thuật toán được sử dụng để phát hiện cộng đồng mạng đều được lập

trình bằng ngôn ngữ Python phiên bản 3.7. Trình biên dịch python và các thư

viện mặc định đều được cài đặt thông qua phần mềm Anaconda được tải về tại

địa chỉ: https://www.anaconda.com/distribution/

Chúng tôi sử dụng trình hỗ trợ soạn thảo lập trình (IDE) là Pycharm bản

Community (Free) được tải về tại:

https://www.jetbrains.com/pycharm/download

- Thư viện hỗ trợ

Để hỗ trợ cho việc đọc, ghi và biểu diễn đồ thị chúng tôi sử dụng thư

viện có sẵn là networkx của python, nếu chưa có thư viên này thì chúng ta có

thể cài thông qua lệnh: “pip install networkx”. Phiên bản networkx được

sử dụng trong luận văn này là bản 2.4

Để hiển thị đồ thị cũng như lưu lại dưới dạng tệp tin ảnh thì chúng tôi sử

dụng thư viên matplotlib có sẵn trong Anaconda. Nếu chưa có, chúng ta có thể

49

cài đặt thư viện matplotlib theo dòng lệnh “conda install

matplotlib”. Phiên bản được sử dụng trong luận văn này là bản 3.2.0

3.2.3. Thử nghiệm và đánh giá

- Đối với bộ cơ sở dữ liệu nhỏ (<200 đỉnh):

Hình 3.1. mô phỏng số cộng đồng tìm được dựa theo 2 thuật toán Girvan-

Newman và EAGLE trên bộ dữ liệu simple network, trong đó hình (a) sử dụng

thuật toán Girvan-Newman và hình (b) sử dụng thuật toán EAGLE.

Có thể thấy, trên hình (b) có một số đỉnh không được tô màu, các đỉnh

này có thể thuộc nhiều cộng đồng khắc nhau, do thuật toán EAGLE tìm cộng

đồng gối nhau trong đồ thị nên có một số đỉnh sẽ có thể vừa thuộc cộng đồng

này, vừa thuộc cộng đồng kia, như trong hình 3.1b, đỉnh 7 có thể thuộc cộng

đồng {1,2,3} hoặc cộng đồng {4,5,6} hoặc kết hợp với đỉnh 8 cho ra cộng đồng

mới là {7,8}.

Hình 3.1. Mô phỏng số cộng đồng tìm được trong đồ thị simple_network.

Kết quả phát hiện cộng đồng của 2 thuật toán Girvan-Newman và

EAGLE đối với bộ dữ liệu dolphin được trình bày trong hình 3.2.

50

Hình 3.2. Mô phỏng số cộng đồng tìm được trong bộ dữ liệu dolphin.

Trong đó, (a) và (b) lần lượt là kết quả tìm kiếm cộng đồng của 2 thuật

toán Girvan-Newman và EAGLE.

Hình 3.3. Mô phỏng số cộng đồng tìm được trong bộ dữ liệu karate.

51

Hình 3.4. Mô phỏng số cộng đồng tìm được trong bộ dữ liệu football.

Hình 3.3. và hình 3.4. thể hiện kết quả tìm kiếm cộng đồng của 2 thuật

toán đã nêu. Nhìn hình ảnh kết quả ta có thể thấy, thuật toán Girvan-Newman

cho kết quả tốt hơn thuật toán EAGLE, tuy nhiên đối với bộ dữ liệu nhỏ rất khó

có thể nhìn ra điều đó, để có cái nhìn tổng quan hơn, chúng ta xét đến các bộ

dữ liệu lớn.

- Đối với bộ cơ sở dữ liệu lớn (>3000 đỉnh):

Hình 3.5. Mô phỏng kết quả tìm kiếm cộng đồng trên bộ dữ liệu

amazon_small

52

Như hình 3.5. chúng ta có thể thấy kết quả tìm kiếm cộng đồng bằng

thuật toán Girvan-Newman (hình (a)) cho cộng đồng rõ ràng và chính xác hơn

so với thuật toán EAGLE (hình (b)). Việc hiển thị các đồ thị lớn là một vấn đề

khó khăn, đây cũng là một thách thức lớn đối với các nhà khoa học.

Để so sánh một cách chi tiết và rõ ràng hơn giữa hai thuật toán Girvan-

Newman và EAGLE. Chúng ta có thể theo dõi bảng 3.3.

53

Bảng 3.3. Bảng tổng hợp kết quả của 2 thuật toán Girvan-Newman và k-cliques trên các bộ dữ liệu khác nhau

EAGLE

Girvan-Newman

Bộ dữ liệu

Số đỉnh

Số cạnh

Cộng đồng đúng

Thời gian

Thời gian

Cộng đồng

Cộng đồng

(giây)

(giây)

4

~0

5

~0

4

14

17

simple_network

3

~0

3

~0

3

14

24

p_n

2

~0

3

~0

3

34

78

karate

2

~0

4

~0

4

62

159

dolphins

12

0.02

6

~0

4

115

613

football

-

1.27

57

0.18

205

3,225

10,262

amazon_small

-

23.17

95

6.7

63

4,890

20,787

youtube_small

-

27.23

241

0.278

1,441

10,824

38,732

dblp_small

4.2

109,192

317,080

1,049,866

13,477

1199

112,043

dblp_big

5.45

213,951

334,863

925,872

75,149

541.17

215,108

amazon_big

54

Nhìn bảng 3.3. chúng ta có thể thấy thời gian chạy của thuật toán EAGLE

nhanh hơn nhiều so với thuật toán Girvan-Newman. Do thuật toán EAGLE tìm

kiếm cộng đồng gối nhau, do đó số lượng cộng đồng tìm được bằng thuật toán

này thường lớn hơn so với thuật toán Girvan-Newman. Đối với 3 bộ dữ liệu

amazon_small, dblp_small và youtube_small, hiện tại chưa có công bố về số

lượng cộng đồng và danh sách cộng đồng chính xác của các bộ dữ liệu này, đo

đó cột “Cộng đồng đúng” ở 3 bộ dữ liệu này được ký hiệu bởi dấu “-”. ~0 tương

ứng là thời gian thực hiện của thuật toán xấp xỉ bằng 0 giây.

3.3. Kết luận chương 3

Chương này trình này thử nghiệm 2 thuật toán phát hiện cộng đồng là

Girvan-Newman và EAGLE. Qua quá trình thử nghiệm, chúng ta rút ra được

một số nhận xét sau:

- Về độ chính xác: Thuật toán Girvan-Newman cho kết quả tốt hơn thuật toán

EAGLE.

- Về thời gian chạy: Thuật toán Girvan-Newman chậm hơn thuật toán tìm kiếm

EAGLE.

- Với các bộ dữ liệu chứa đồ thị có kích thước rất lớn (hơn 1 triệu đỉnh và hơn

2 triệu cạnh) thì thuật toán Girvan-Newman không thể xử lý được.

55

KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN

Kết luận

Mạng xã hội và bài toán phát hiện cộng đồng trong mạng xã hội là những

vấn đề được nhiều nhà nghiên cứu quan tâm trong thời đại hiện nay. Luận văn

tập trung nghiên cứu độ đo trung gian và thuật toán phát hiện cộng đồng trên

mạng xã hội. Các kết quả chính mà luận văn đạt được như sau:

 Trình bày mạng xã hội và các các độ đo trên đồ thị mạng xã hội.

 Giới thiệu thuật toán phát hiện cấu trúc cộng đồng trên mạng xã hội: thuật

toán phân cụm đồ thị, thuật toán Girvan–Newman, thuật toán phát hiện k-

cliques, thuật toán EAGLE phát hiện cộng đồng gối nhau.

 Thử nghiệm thuật toán Girvan-Newman và thuật toán tìm EAGLE để phát

hiện cộng đồng trong mạng xã hội. Các thuật toán được chạy trên các bộ

dữ liệu chuẩn kích thước số đỉnh và số cạnh khác nhau.

Hướng phát triển

- Áp dụng cho vùng dữ liệu lớn và tổng quan hơn như các mạng xã hội

Facebook, Twitter, Google… Nhưng đòi hỏi cấu hình máy chủ phải rất lớn.

- Cài đặt và thử nghiệm các thuật toán khác như CONGA.

56

TÀI LIỆU THAM KHẢO

Tài liệu Tiếng Việt

ĐỒNG TRÊN MẠNG XÃ HỘI, Báo cáo đề tài VAST01.09/14-15, 2015

[1]. Đoàn Văn Ban (chủ nhiệm đề tài), PHÂN TÍCH, PHÁT HIỆN CẤU TRÚC CỘNG

[2]. Hoàng Thị Thanh Giang, Nguyễn Thị Thúy Hạnh, Nguyễn Hoàng Huy, So

sánh một số thuật toán phân cụm phổ cho dữ liệu biểu diễn gene, Tạp chí

Khoa học và Phát triển, tập 13, số 6: 1008-1015, 2015.

[3]. Lê Minh Tiến, Tổng quan phương pháp phân tích mạng xã hội trong nghiên

cứu xã hội, Tạp chí Khoa học Xã hội, số 09, tr. 66-77, 2006.

Tài liệu tiếng Anh

[4]. Arif, T., The Mathematics of Social Network Analysis: Metrics for

Academic Social Networks, International Journal of Computer

Applications Technology and Research, Volume 4 - Issue 12, 889 - 893,

(2015), ISSN: 2319-8656.

[5]. Brandes, U., A faster algorithm for betweenness centrality. Journal of

Mathematical Sociology, 25(2):163-177. (2001).

[6]. Brandes, U., Pich, C., Centrality estimation in large networks. International

Journal of Bifurcation and Chaos. (2007).

[7]. Cavique, Luís, Armando B. Mendes, and Jorge MA Santos. "An algorithm

to discover the k-clique cover in networks." Portuguese Conference on

Artificial Intelligence. Springer, Berlin, Heidelberg, 2009.

[8]. Chuan Shi, Yanan Cai, Di Fu, Yuxiao Dong, Bin Wu, A link clustering

based overlapping community detection algorithm, Data & Knowledge

Engineering 87 (2013) 394–404

57

[9]. Clauset, A., Newman, M. E., and Moore, C.: Finding community structure

in very large networks. Physical Review E, 70(6):066111, (2004).

[10]. D. Lusseau, K. Schneider, O. J. Boisseau, P. Haase, E. Slooten, and S. M.

Dawson, Behavioral Ecology and Sociobiology 54, 396-405 (2003).

[11]. Dutta, K.: Graph Theoretic Approach to Social Network Analysis,

International Journal of Scientific Research in Science and Technology, (4)

2: 1550-1557, (2018).

[12]. Freeman, L.C. A set of measures of centrality based on betweenness.

Sociometry 40, 35-41, 1977

[13]. Girvan, M., Newman, M. E. J.: Community structure in social and biological

networks, Proceedings of the National Academy of Sciences of the United

States of America, Vol.99, No.12, pp. 7821-7826 (2002).

[14]. Gregory, S.: An Algorithm to Find Overlapping Community Structure

in Networks. In: Kok, J.N., Koronacki, J., López de Mántaras, R., Matwin,

S., Mladeni$, D., Skowron, A. (eds.) PKDD 2007. LNCS (LNAI), vol.

4702, pp. 91–102. Springer, Heidelberg (2007)

[15]. Huawei Shen, Xueqi Cheng, Kai Cai, and Mao-Bin Hu, Detect overlapping

and hierarchical community structure in networks, Physica A 388 (2009)

1706-1712.

[16]. Johnson D.S.: Approximation algorithms for combinatorial problems,

Journal of Computer and System Science, 9, 256-278 (1974)

[17]. Kernighan, B. W., and Lin, S.: An efficient heuristic procedure for

partitioning graphs. Bell system technical journal, 49(2), 291-307 (1970).

[18]. M. E. J. Newman, Mixing patterns in networks. Phys. Rev. E 67, 026126

(2003).

58

[19]. M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. USA 99, 7821-7826

(2002).

[20]. M.E.J. Newman and M. Girvan (2003), Finding and evaluating

community structure in networks. Preprint cond-mat/0308217.

[21]. Nam, P. Nguyen., Thang, N. Dinh., Ying, Xuan., and My T. Thai.: Adaptive

algorithms for detecting community structure in dynamic social networks,

in INFOCOM, 2011 Proceedings IEEE, pp. 2282 - 2290, (2011).

[22]. Newman, Mark EJ. "Fast algorithm for detecting community structure in

networks." Physical review E 69.6 (2004): 066133

[23]. Nicosia, Vincenzo, et al. "Extending the definition of modularity to directed

graphs with overlapping communities." Journal of Statistical Mechanics:

Theory and Experiment 2009.03 (2009): P03024.

[24]. Ruhnau, B.: Eigenvector-centrality – a node-centrality? Social Networks

22(4): 357-365 (2000).

[25]. Santo Fortunato (2010), Community detection in graphs, Technical

Report, Complex Networks and Systems Lagrange Laboratory, ISI

Foundation, Torino, ITALY, arXiv:0906.0612v2 (2010).

[26]. Scott, J.: Social network analysis: a Handbook. London: SAGE publications,

(1991).

[27]. Soriano P., Gendreau M.: Tabu search algorithms for the maximum clique,

In: Clique, Coloring and Satisfiability, Second Implementation Challenge

DIMACS, Johnson D.S., Trick M.A. (Eds.), 221-242 (1996)

[28]. W. W. Zachary, An information flow model for conflict and fission in small

groups, Journal of Anthropological Research 33, 452-473 (1977).

59

[29]. Wikipedia, Link: https://vi.wikipedia.org/wiki/Cư_dân_mạng, Truy cập

ngày 14 tháng 3 năm 2020.

[30]. Yang, Jaewon, and Jure Leskovec. "Defining and evaluating network

communities based on ground-truth." Knowledge and Information Systems

42.1 (2015): 181-213.

[31]. Zhang, T., Ramakrishnan, R., Livny, M.: "BIRCH: an efficient data

clustering method for very large databases". Proceedings of the 1996 ACM

SIGMOD international conference on Management of data - SIGMOD'96.

pp. 103-114. doi:10.1145/233269.233324, (1996).

[32]. Zhao, F. and Tung, A. K.: Large scale cohesive subgraphs discovery for

social network visual analysis. VLDB, pages 85-96, (2012).