TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

LUẬN VĂN THẠC SĨ
Nghiên cứu bài tốn Phân tích mạng xã hội

ĐẶNG THỊ KIM DUNG
Ngành Khoa học dữ liệu

Giảng viên hướng dẫn:

PGS.TS. Nguyễn Thị Kim Anh

Viện:

Công nghệ Thông tin và Truyền thông

HÀ NỘI, 2021


TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI

LUẬN VĂN THẠC SĨ
Nghiên cứu bài tốn Phân tích mạng xã hội

ĐẶNG THỊ KIM DUNG
Ngành Khoa học dữ liệu

Giảng viên hướng dẫn: PGS.TS. Nguyễn Thị Kim Anh
Chữ ký của GVHD

Viện:

Công nghệ Thông tin và Truyền thông

HÀ NỘI, 2021


CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập – Tự do – Hạnh phúc

BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ
Họ và tên tác giả luận văn: Đặng Thị Kim Dung
Đề tài luận văn: Nghiên cứu bài toán Phân tích mạng xã hội
Chuyên ngành: Khoa học dữ liệu
Mã số SV: CA190041
Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác
nhận tác giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày
…………………… với các nội dung sau:
1. Bổ sung ý nghĩa của bài luận văn này với nghiệp vụ ngân hàng tại
Chương số 3, Mục 3.1, trang 52
2. Làm rõ thuật toán sử dụng trong bài.
3. Hiệu chỉnh và bổ sung nội dung trong mục Tài liệu tham khảo
4. Hiệu chỉnh đánh số và tiêu đề tại Mục 2.3.3 của chương 2 trang 37.
5. Hiệu chỉnh các thuật ngữ trong luận văn
6. Hiệu chỉnh lại một số hình vẽ mờ trở nên rõ nét hơn
7. Hiệu chỉnh một số lỗi soạn thảo trong luận văn.

Giáo viên hướng dẫn

PGS.TS Nguyễn Thị Kim Anh


Ngày tháng năm
Tác giả luận văn

Đặng Thị Kim Dung

CHỦ TỊCH HỘI ĐỒNG

PGS.TS Thân Quang Khoát


LỜI CAM ĐOAN
Tôi xin cam đoan: Luận văn thạc sỹ Khoa học dữ liệu “Nghiên cứu
bài tốn Phân tích mạng xã hội” do tơi thực hiện và trình bày dưới sự
hướng dẫn của PGS.TS. Nguyễn Thị Kim Anh, Viện Công nghệ Thông
tin và Truyền thông – Trường Đại học Bách Khoa Hà Nội. Đây là cơng
trình nghiên cứu hồn tồn trung thực, khơng vi phạm bất cứ điều gì trong
Luật Sở hữu trí tuệ và Pháp luật Việt Nam. Nếu sai, tơi hồn tồn chịu
trách nhiệm trước Pháp luật.
Tất cả các bài báo, khóa luận, tài liệu, cơng cụ phần mềm của các tác
giả khác được sử dụng lại trong bài luận này đều được chỉ dẫn tường minh
về tác giả và đều có trong danh mục tài liệu tham khảo.

Hà Nội, ngày 20 tháng 12 năm 2021

Tác giả

Đặng Thị Kim Dung


LỜI CẢM ƠN

Theo học và tìm hiểu sâu hơn về ngành Khoa học dữ liệu là mơ ước
của tôi. Do đó, tơi đã đăng kí học cao học ngành Khoa học dữ liệu tại
trường Đại Học Bách Khoa Hà Nội.
Để hồn thành luận văn thạc sĩ này, tơi xin bày tỏ sự cảm kích đặc
biệt tới Cơ giáo hướng dẫn của tôi là PGS.TS Nguyễn Thị Kim Anh người đã định hướng, trực tiếp dẫn dắt và cố vấn cho tôi trong suốt thời
gian thực hiện đề tài nghiên cứu khoa học. Trong thời gian thực hiện, tôi đã
gặp rất nhiều vấn đề. Tuy nhiên, cùng sự động viên và giúp đỡ của cơ Kim
Anh, tơi đã hồn thành bài luận.
Đồng thời, tơi xin tỏ lịng biết ơn đến cha mẹ, người thân và bạn bè
đã luôn bên cạnh ủng hộ, động viên tôi trong cuộc sống cũng như trong
thời gian hoàn thành luận văn thạc sĩ.
Xin chân thành cảm ơn tất cả mọi người!

Hà Nội, ngày 19 tháng 12 năm 2021

Tác giả

Đặng Thị Kim Dung


MỤC LỤC
DANH MỤC HÌNH VẼ........................................................................................ iii
DANH MỤC BẢNG BIỂU....................................................................................v
LỜI MỞ ĐẦU........................................................................................................1
CHƯƠNG 1: CƠ SỞ LÝ THUYẾT.......................................................................2
1.1. Khái niệm về mạng xã hội...........................................................................2
1.2. Lịch sử mạng xã hội.....................................................................................5
1.3. Một số lý thuyết đồ thị trong phân tích mạng xã hội...................................6
1.3.1 Định nghĩa đồ thị....................................................................................6
1.3.2. Các loại đồ thị.......................................................................................7

1.3.3. Cấu phần của đồ thị...............................................................................9
1.4. Một số lý thuyết về tính chất của mạng xã hội.......................................... 11
1.4.1. Lý thuyết ràng buộc yếu (strength of weak ties - SWT).......................12
1.4.2. Lỗ trống cấu trúc (Structural holes)....................................................13
1.4.3 Lý thuyết của Coleman về trung tâm xã hội (Coleman social capitalCSC)...............................................................................................................14
1.4.4. Tính chất thế giới nhỏ (small- world)..................................................14
1.4.5. Phân phối lũy thừa trong scale-free network......................................16
1.5. Thu thập thông tin mạng xã hội................................................................. 17
1.6. Kết luận chương......................................................................................... 18
CHƯƠNG 2: BÀI TỐN PHÂN TÍCH MẠNG XÃ HỘI..................................20
2.1. Phương pháp trích xuất mạng con............................................................. 20
2.1.1. Thành phần..........................................................................................21
2.1.2. Cliques.................................................................................................26
2.1.3. K-cores.................................................................................................27
2.2. Một số thước đo thống kê mô tả đặc trưng cho mạng xã hội.....................29
2.2.1. Khoảng cách trong mạng....................................................................29
2.2.2. Sức mạnh của nút trong mạng.............................................................30
2.2.3. Hệ số phân cụm mạng.........................................................................30
2.3. Bài toán phát hiện cộng đồng trong mạng xã hội...................................... 31
i


2.3.1. Giới thiệu bài toán phát hiện cộng đồng............................................. 31
2.3.2. Mục tiêu bài toán phát hiện cộng đồng............................................... 36
2.3.3. Các thuật toán quan trọng trong bài toán “Phát hiện cộng đồng”....37
2.4. Xác định nút quan trọng trong cộng đồng qua tính trung tâm...................47
2.4.1. Mức độ trung tâm theo bậc (Degree centrality)..................................48
2.4.2. Khoảng cách trung tâm (Closeness centrality)...................................49
2.4.3. Vị trí trung tâm (Betweenness centrality)............................................ 50
2.5. Kết luận chương......................................................................................... 50

CHƯƠNG 3: MÔ HÌNH THỰC NGHIỆM......................................................... 52
3.1. Ý nghĩa của bài tốn trong ngân hàng........................................................ 52
3.2. Dữ liệu đầu vào bài toán............................................................................ 53
3.3. Các đặc điểm của mạng............................................................................. 56
3.4. Phát hiện cộng đồng trong mơ hình mạng................................................. 59
3.5. Phát hiện nút quan trọng............................................................................ 63
3.5.1. Phát hiện nút quan trọng trên toàn bộ mạng.......................................63
3.5.2. Phát hiện nút quan trọng ứng với từng cộng đồng..............................65
3.6. Kết luận chương......................................................................................... 66
KẾT LUẬN.......................................................................................................... 69
TÀI LIỆU THAM KHẢO.................................................................................... 70

ii


DANH MỤC HÌNH VẼ
Hình 1.1.Ví dụ cơ bản của mơ hình mạng.............................................................3
Hình 1.2.Một số hình ảnh về đồ thị........................................................................6
Hình 1.3.Sơ đồ mạng máy tính đa kênh thoại........................................................7
Hình 1.4.Các loại đồ thị cơ bản..............................................................................8
Hình 1.5. Ví dụ về đồ thị vịng, đồ thị đầy đủ, đồ thị hai phía, đồ thị bánh xe......9
Hình 1.6. Hình ảnh ví dụ về đồ thị.........................................................................9
Hình 1.7. Ví dụ minh họa về tính chồng chéo...................................................... 12
Hình 1.8. Ví dụ minh họa về tính chất bắc cầu. Liên kết giữa A và G được gọi là
mối liên kết bắc cầu.............................................................................................. 13
Hình 1. 9. Hình ảnh minh họa lý thuyết cấu trúc lỗ............................................. 14
Hình 1.10. Hình vẽ biểu diễn khi tạo một kết nối ngẫu nhiên trong mạng được phân

cụm....................................................................................................................... 15
Hình 1.11. Hình ảnh về mạng ngẫu nhiên (trái) và mạng khơng có quy mơ (phải)

17
Hình 2.1. Ví dụ về thành phần trong mạng.......................................................... 22
Hình 2.2. Ví dụ khả năng tiếp cận........................................................................ 23
Hình 2.3. Hình ảnh ví dụ thành phần mạnh và yếu trong đồ thị..........................24
Hình 2.4. Hình ảnh ví dụ thành phần liên thơng mạnh........................................ 25
Hình 2.5. Hình ảnh ví dụ thành phần liên thơng yếu............................................ 25
Hình 2.6. Hình ảnh ví dụ về Cliques.................................................................... 26
Hình 2.7. Hình ảnh ví dụ cliques thực tế chồng lên nhau.................................... 27
Hình 2.8. Hình ảnh ví dụ về k-cores..................................................................... 28
Hình 2.9. Hình ảnh ví dụ phân cộng đồng............................................................ 32
Hình 2.10. Hình ảnh ví dụ tính tốn mơ đun mạng.............................................. 39
Hình 2.11. Hình ảnh mơ tả cho hai giai đoạn của thuật tốn. Đầu tiên tối ưu hóa
mơ đun và các cộng đồng được tìm thấy được tổng hợp thành một mạng..........42
Hình 2.12. Chi tiết thuật tốn Louvain

[44]

............................................................ 44

Hình 2.13. Ví dụ cộng đồng khơng liên thơng

[44]

................................................ 44

[44]

Hình 2.14. Chi tiết các bước thuật tốn Leiden ............................................... 46
Hình 2.15. Hình ảnh ví dụ về bậc......................................................................... 48
iii



Hình 3.1. Hình ảnh một phần về mạng được xây dựng trên bộ dữ liệu đầu vào . 56

Hình 3.2. Số lượng nút trung bình ứng với mỗi khoảng cách l............................57
Hình 3.3. Phân bố bậc trong mạng. Hình trái là hình vẽ số lượng nút với bậc tương

ứng trong mạng G. Hình phải là số lượng nút với bậc vào và bậc ra tương ứng
trong mạng G........................................................................................................ 57
Hình 3.4. Hình vẽ mơ tả bậc vào và ra của mạng.................................................58
T

N

Hình 3.5. Hình vẽ mơ tả phân phối cạnh của đồ thị G và G ............................58
Hình 3.6. Hình vẽ mơ tả tương quan số lần chuyển tiền và số tiền......................59
Hình 3.7. Phân phối của bậc vào và bậc ra........................................................... 59

iv


DANH MỤC BẢNG BIỂU
Bảng 2.1. Ma trận kề của đồ thị........................................................................... 39
Bảng 3.1. Bảng mô tả 5 thành phần lớn nhất trong mạng.................................... 54
Bảng 3.2. Bảng mô tả số lượng nút của các thành phần nhỏ nhất........................55
Bảng 3.3. Bảng mô tả số lượng nút có bậc bằng 1 trong thành phần lớn nhất.....55
Bảng 3.4. Bảng tham số đường kính và mật độ của mạng G............................... 56
Bảng 3.5. Thống kê mô tả các tham số của ba mạng đầu vào..............................60
Bảng 3.6. Bảng so sánh các chỉ số phân cụm của ba mạng đầu vào....................61
Bảng 3.7. Cơng ty có số lượng quan hệ cao nhất................................................. 63

Bảng 3.8. Khách hàng có chỉ số khoảng cách trung tâm tốt nhất........................64
Bảng 3.9. Bảng mô tả 5 cộng đồng lớn nhất được phát hiện và những nút quan
trọng trong cộng đồng.......................................................................................... 65

v



LỜI MỞ ĐẦU
Trong thế kỉ XXI, đi cùng sự phát triển của internet và công nghệ
thực tế ảo, rất nhiều ứng dụng mới phục vụ đời sống và sinh hoạt của con
người đã ra đời. Đi kèm với đó, ta có được rất nhiều dữ liệu của người
dùng. Dữ liệu có thể là dữ liệu có cấu trúc hoặc dữ liệu phi cấu trúc. Nhiệm
vụ của những nhà khoa học dữ liệu là trích xuất tri thức từ dữ liệu thơ đó.
Đối với ngành ngân hàng nói chung và ngân hàng VietinBank nói
riêng, hầu hết các bài tốn phân tích đều dựa trên các dữ liệu có cấu trúc.
Nhược điểm của bài tốn phân tích này là ta đã khơng xem xét đến yếu tố
mối quan hệ giữa các khách hàng.
Vì nguyên do trên, trong bài luận văn thạc sĩ khoa học của tôi, tôi lựa
chọn đề tài “Nghiên cứu bài tốn Phân tích mạng xã hội” với mục tiêu xây
dựng một mạng lưới thể hiện mối quan hệ của toàn bộ khách hàng trong
ngân hàng VietinBank.
Việc nghiên cứu này giúp tôi làm quen với dữ liệu phi cấu trúc, đặc
biệt là dữ liệu mạng. Ngoài ra, từ mạng xã hội xây dựng trên cộng đồng
khách hàng này, tôi hướng tới mục tiêu đơn giản nhất là tìm kiếm những
khách hàng quan trọng trong mạng lưới nhằm xây dựng những chính sách
chăm sóc riêng.

1



CHƯƠNG 1: CƠ SỞ LÝ THUYẾT

Mạng xã hội là một khái niệm đã được phát triển từ đầu thế kỉ XX
bởi các nhà xã hội học. Theo thời gian, các nhà nghiên cứu về mạng xã hội
đã đưa ra hệ thống lý thuyết, tính chất và các phương pháp phân tích mạng
xã hội. Trong chương đầu tiên, tơi sẽ đi sâu vào khái niệm của mạng xã
hội, các phương pháp tiếp cận để xác định tập nút và định dạng mối quan
hệ của các nút với mạng xã hội được xây dựng theo từng mục tiêu khác
nhau. Tiếp đó, tơi đưa ra một số lý thuyết về đồ thị được ứng dụng trong
mạng xã hội. Thứ ba, tôi đưa ra các tính chất nổi tiếng của mạng xã hội đã
được các nhà xã hội học đưa ra. Cuối cùng, tôi nêu lên những phương pháp
thu thập dữ liệu để xây dựng mạng xã hội.
1.1. Khái niệm về mạng xã hội
Hiện nay, cùng với sự phát triển mạnh mẽ của hệ thống Internet, các
công nghệ như thực tế ảo, Internet của vạn vật (Internet of Things - IOT)
cũng phát triển theo. Điều này dẫn đến có rất nhiều dữ liệu ta có thể có
được. Việc phân tích dữ liệu trở nên quan trọng và phát triển hơn. Có rất
nhiều phương pháp có thể giúp ta trích xuất tri thức từ dữ liệu. Trong đó, ta
có thể kể tới các phương pháp phân tích mạng xã hội.
Mạng xã hội xung quanh chúng ta có rất nhiều, có thể kể đến một số
mạng xã hội phổ biến như Facebook, Youtube,… đang kéo theo số người
dùng ngày càng lớn. Đi cùng đó, các nguồn thơng tin từ tương tác xã hội
đang đóng một vai trò khá lớn trong việc phát hiện, theo dõi và đánh giá
một sự kiện, hiện tượng. Nguồn tin đa dạng, tổng hợp với một số lượng
lớn, liên tục thay đổi và phát triển theo thời gian đã khiến cho lượng dữ
liệu này trở nên đáng tin cậy và mang giá trị sử dụng lớn.
Đầu tiên, tôi xin đưa ra khái niệm về mạng xã hội. Theo nghị định số
72/2013/NĐ-CP ngày 15/7/2013 của Chính phủ về quản lý, cung cấp, sử dụng
dịch vụ internet và thông tin trên mạng quy định thì mạng xã hội (social

2


network) là hệ thống thông tin cung cấp cho cộng đồng người sử dụng
mạng các dịch vụ lưu trữ, cung cấp, sử dụng, tìm kiếm, chia sẻ và trao đổi
thơng tin với nhau, bao gồm dịch vụ tạo trang thông tin điện tử cá nhân,
diễn đàn (forum), trò chuyện (chat) trực tuyến, chia sẻ âm thanh, hình ảnh
và các hình thức dịch vụ tương tự khác.
Theo John Scott và cộng sự

[1][2]

đã định nghĩa mạng xã hội như

sau: Mạng xã hội là tập hợp các nút trong một xã hội và được liên kết bởi
một hoặc nhiều mối quan hệ.

Hình 1.1.Ví dụ cơ bản của mơ hình mạng

Như vậy, cấu phần cơ bản của một mạng xã hội gồm hai phần là nút
và liên kết - hay gọi là cạnh.
Các nút - hay còn gọi là các thành phần của mạng là đơn vị được kết
nối bởi các mối quan hệ. Về ngun tắc, bất kì đơn vị nào có thể kết nối
được với đơn vị khác đều có thể coi là nút. Trong mạng xã hội, các nút
thường là con người, cơng ty, trường học, quốc gia, hay tính cách,…
Thơng tin các nút thường là những thông tin thu thập trong nghiên cứu
khoa học tiêu chuẩn như nhân khẩu học, thái độ, hành vi,… và bao gồm cả
thông tin về thời điểm nút hoạt động (có thay đổi theo thời gian).
Thực tế, việc xác định các nút cần thiết cho bài tốn phân tích mạng
là một thách thức khơng hề nhỏ. Ví dụ ta muốn phân tích nghiên cứu về

bệnh tim thông qua mạng xã hội, nhưng bản thân bên trong mỗi đối tượng
được nghiên cứu lại có sự phức tạp và khó khăn riêng.
Laumann và cộng sự (1983)[3] đã đề xuất ba cách tiếp cận để giải
quyết vấn đề thu thập dữ liệu này.
Cách thứ nhất, cách tiếp cận dựa trên vị trí. Ta coi những tác nhân là
một thành viên thuộc một tổ chức hoặc giữ một vị trí cụ thể. Những thành
3


viên này sẽ được thu thập vào dữ liệu nghiên cứu. Với ví dụ trên, ta có thể
lấy những thành viên trong mạng là các nhà nghiên cứu hoặc bác sĩ làm
việc trong các khoa tim mạch, hoặc các thành viên của một hiệp hội các
chuyên gia nghiên cứu về tim mạch.
Cách thứ hai là tiếp cận dựa trên sự kiện nhằm xác định ranh giới
của mạng. Ở ví dụ trên, ta có thể xác định các nhà nghiên cứu tham gia ít
nhất hai sự kiện về tim mạch trong hai năm qua.
Cách thứ ba, ta có thể tiếp cận dựa trên mối quan hệ. Ta bắt đầu từ một
tập nhỏ dựa trên các nút được coi là phạm vi quan tâm. Sau đó, ta mở rộng ra
bao gồm những người có mối quan hệ cụ thể với những người thuộc phạm
vi trước đó. Ở ví dụ trên, ta có thể xác định những nhà khoa học tham gia một
hội nghị quan trọng là phạm vi quan tâm. Sau đó ta xem xét thêm các mối
quan hệ với các nhà nghiên cứu này, có thể là các cộng tác viên của họ, những
cộng sự, đồng tác giả,… Cách tiếp cận dựa trên mối quan hệ này phổ

biến nhất trong nghiên cứu mạng Ego.
Ba cách tiếp cận trên không loại trừ lẫn nhau và thông thường, các
nhà nghiên cứu sẽ sử dụng kết hợp để xác định phạm vi.
Các mối quan hệ trong mạng có thể là mối quan hệ về tình bạn, quan
hệ thương mại, liên kết web, trích dẫn, luồng thông tin,…
Theo Borgatti và cộng sự (2009)


[4]

đã xác định bốn phạm trù quan

hệ. Đầu tiên là sự tương đồng. Sự tương đồng xảy ra khi hai nút liên kết
với nhau có các tính chất giống nhau nhất định. Ví dụ như đặc điểm nhân
khẩu học, hành vi hoặc là thành viên một tổ chức/nhóm nào đó.
Thứ hai là các mối quan hệ xã hội như quan hệ họ hàng, quan hệ bạn
bè, quan hệ tình cảm,... Đây là một trong những mối quan hệ thường được
nghiên cứu nhiều nhất trong mạng xã hội. Ví dụ, Casciaro và cộng sự
(1999)[5] đã xây dựng mạng dựa trên quan hệ cảm xúc (thích hay khơng)
của các đối tượng nghiên cứu.
Thứ ba là quan hệ tương tác. Điều này đề cập tới quan hệ dựa trên
4


hành vi, chẳng hạn như hai người nói chuyện với nhau, giúp đỡ nhau hoặc
có thể người này theo dõi người kia trên mạng xã hội Facebook.
Cuối cùng là luồng. Luồng là mối quan hệ dựa trên sự trao đổi hoặc
chuyển đổi giữa các nút. Giống như tương tác, luồng các mối quan hệ vẫn
có thể xảy ra những mối quan hệ xã hội khác và ta thường giả định chúng
cùng tồn tại.
1.2. Lịch sử mạng xã hội
Phân tích mạng xã hội có nguồn gốc lý thuyết trong cơng việc của
những nhà xã hội học thời kì đầu như Georg Simmel và Émile Durkheim.
Đây là hai tác giả đã viết về tầm quan trọng của việc nghiên cứu các mối
quan hệ của các cá nhân trong xã hội.
Khái niệm mạng xã hội được sử dụng từ đầu thế kỉ XX nhằm chỉ các
mối quan hệ phức tạp giữa các thành viên trong một xã hội hoặc giữa các

cá nhân đến toàn cầu.
Năm 1930, Jacob Moreno và Helen Jennings đã đưa ra các phương pháp
[6]

phân tích cơ bản . Năm 1954, John Arundel Barnes bắt đầu sử dụng thuật
ngữ này một cách có hệ thống để biểu thị các kiểu ràng buộc, bao gồm các
khái niệm được công chúng sử dụng theo truyền thống và các khái niệm được
sử dụng bởi các nhà khoa học xã hội như các nhóm bị ràng buộc (ví dụ: bộ
lạc, gia đình) và các phạm trù xã hội (ví dụ như giới tính, dân tộc).

Các học giả như Ronald Burt, Kathleen Carley, Mark Granovetter,
David Krackhardt, Edward Laumann, Anatol Rapoport, Barry Wellman,
Douglas R. White và Harrison White đã mở rộng việc sử dụng phân tích
mạng xã hội có hệ thống[7].
Phân tích mạng xã hội đã được sử dụng rộng rãi trong nghiên cứu về
[8]

việc tiếp thu ngơn ngữ thứ hai ở nước ngồi . Ngay cả trong nghiên cứu
trong văn học, phân tích mạng đã được Anheier, Gerhards và Romo, Wouter
De Nooy và Burgert Senekal áp dụng. Thật vậy, phân tích mạng xã hội đã
5


tìm thấy các ứng dụng trong các lĩnh vực học thuật khác nhau, cũng như
các ứng dụng thực tế như chống rửa tiền và khủng bố.
Tiếp tới, với sự phát triển của hệ thống internet hiện nay, phân tích
mạng xã hội đang đi sâu và phát triển trên các hệ thống mạng xã hội như
Facebook, Twiter, Youtube,…
1.3. Một số lý thuyết đồ thị trong phân tích mạng xã hội
Lý thuyết đồ thị là một lĩnh vực nghiên cứu đã có từ lâu và có nhiều

ứng dụng hiện đại. Những tư tưởng cơ bản của lý thuyết đồ thị được đề
xuất vào những năm đầu của thế kỷ XVIII bởi nhà tốn học người Thụy Sỹ
- Leonhard Euler.
Phân tích mạng xã hội áp dụng rất nhiều lý thuyết đồ thị để phân
tích. Dưới đây, tơi xin đi qua một số khái niệm cơ bản trong đồ thị. Tiếp
sau đó là những lý thuyết cơ bản trong mạng xã hội.
1.3.1 Định nghĩa đồ thị
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối giữa
các đỉnh đó.
Người ta thường ký hiệu đồ thị G = (V, E).
Trong đó, V là tập các đỉnh (Vertex) và E là tập các cạnh (Edge). Có
thể coi E là tập các cặp (u, v) với u và v là hai đỉnh của V.

Hình 1.2.Một số hình ảnh về đồ thị

Đồ thị xuất hiện trong đời sống rất nhiều, ta có thể kể tới như sơ đồ
mạng giao thông biểu diễn các đường giao thông với nhau cũng là một loại

6


đồ thị. Hay sơ đồ mạng internet mô tả sự kết nối internet của các máy tính.
Ngồi ra, sơ đồ mạng xã hội cũng là một loại đồ thị.
1.3.2. Các loại đồ thị
Trong thực tế, có rất nhiều loại đồ thị có thể có. Ví dụ như đơn đồ
thị, đa đồ thị, đồ thị có hướng, đồ thị khơng hướng,…. Ta có các định nghĩa
về các đồ thị như dưới đây.
Đồ thị G được gọi là đơn đồ thị vô hướng nếu giữa hai đỉnh u, v V (V
khác rỗng) có nhiều nhất là 1 cạnh thuộc E (E khác rỗng) được nối từ đỉnh
u tới đỉnh v. Như vậy, trong đơn đồ thị vô hướng, các cặp cạnh trong tập E

sẽ khơng tính tới thứ tự các đỉnh.
Đồ thị G được gọi là đa đồ thị vô hướng nếu giữa hai đỉnh u và v thuộc
V (V khác rỗng) có thể có nhiều hơn 1 cạnh thuộc E (E khác rỗng) nối từ đỉnh

u tới đỉnh v.
Như vậy, mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào
cũng là đơn đồ thị vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh
nối giữa một cặp đỉnh nào đó.

Hình 1.3.Sơ đồ mạng máy tính đa kênh thoại

Đồ thị G được gọi là đồ thị vô hướng nếu các cạnh thuộc E là khơng
có hướng, tức là cạnh nối hai đỉnh u và v bất kỳ cũng là cạnh nối hai đỉnh v
và u. Hay nói cách khác, tập E gồm các cặp (u, v) khơng tính thứ tự của cặp
đỉnh (u, v).
Đồ thị G được gọi là đồ thị có hướng nếu các cạnh thuộc E là có hướng.
Điều này có nghĩa là có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã
có cạnh nối từ đỉnh v tới đỉnh u. Như vậy, tập E gồm các cặp (u, v) có tính
7


thứ tự: (u, v) ≠ (v, u). Trong đồ thị có hướng, các cạnh được gọi là các
cung. Đồ thị vơ hướng cũng có thể coi là đồ thị có hướng nếu như ta coi
cạnh nối hai đỉnh u và v bất kỳ tương đương với hai cung (u, v) và (v, u).
Đồ thị

Đơn đồ thị

Đa đồ thị


Có
hướng

Vơ
hướng

Hình 1.4.Các loại đồ thị cơ bản

Như vậy, ta có thể có đơn đồ thị vơ hướng, đơn đồ thị có hướng, đa
đồ thị vơ hướng, đa đồ thị có hướng.
Một số dạng đồ thị đơn vơ hướng đặc biệt có thể kể tới như đồ thị
vòng, đồ thị đầy đủ, đồ thị hai phía, đồ thị bánh xe,...
Đồ thị vịng Cn (cycle graph): Là đơn đồ thị vô hướng G = (V, E) với
tập đỉnh V: {1, 2, 3,…, n} và tập cạnh E = {(1, 2); (2, 3); ….; (n – 1, n); (n,
1)}.
Đồ thị đầy đủ Kn (complete graph): Là đơn đồ thị vơ hướng mà giữa
hai đỉnh bất kì của nó ln tồn tại cạnh nối.
Đồ thị hai phía Km, n (bipartite graph): đây là đồ thị có tập đỉnh phân
hoạch thành hai tập con không giao nhau V=X Y sao cho mọi cạnh nối một
đỉnh thuộc X với một đỉnh thuộc Y.

8


Hình 1.5. Ví dụ về đồ thị vịng, đồ thị đầy đủ, đồ thị hai phía, đồ thị bánh xe

Đồ thị bánh xe Wn (wheel graph): đây là đơn đồ thị vô hướng thu được
từ đồ thị Cn-1 bằng cách thêm một đỉnh n nối với n-1 đỉnh của đồ thị Cn-1.

1.3.3. Cấu phần của đồ thị

Đồ thị G = (V, E) với tập đỉnh V = {1, 2, 3, ..., n} và các tập cạnh
E = {e1, e2, …, en}.
Đây là một cấu trúc rời rạc, các tập V và E là những tập hữu hạn, có
nghĩa là có thể đánh số thứ tự 1, 2, 3... cho các phần tử trong tập V và tập E.

Hình 1.6. Hình ảnh ví dụ về đồ thị

9