Phân tích mạng xã hội và vấn đề key player
Lời nói đầu
Với nhu cầu ngày càng lớn về lưu trữ và xử lý thông tin, dường như cơ sử dữ liệu quan
hệ tỏ ra khó đáp ứng được nhu cầu xử lý nhanh trong một kho dữ liệu khổng lồ. Chính vì
nhu cầu đó, cơ sở dữ liệu đồ thị ra đời. Dữ liệu được lưu trữ dạng đồ thì, làm tăng tính
mêm dẻo và linh hoạt trong việc truy xuất dữ liệu
Ứng dụng rõ rệt nhất của dữ liệu đồ thì là áp dụng trong các mạng xã hội, một kiểu mô
hình hóa xã hội thực vào một kiểu quan hệ ảo trên mạng internet. Trên đó, cũng có các
mối quan hệ cha-con, đồng nghiệp, bạn bè, người yêu……
Bài tiểu luận ngắn ngủi này trình bày khái quát về phân tích các đặc tính của một mạng
xã hội và nhấn mạnh đến vấn đề tìm Key player, nút đóng vai trò quan trọng trong mạng
xã hội
Bài báo cáo gồm hai phần chính.
Phần một: Phân tích các đặc tính của một mạng xã hội
Phần hai: Các vấn đề phát sinh trong việc tìm key player
Xin chân thành cảm ơn (thầy) PGS.TS Đỗ Phúc, GV trực tiếp hướng dẫn em hoàn
thành bài tiểu luận này, do thời gian ngắn ngủi, bài viết còn sơ xài và còn nhiều thiếu xót,
mong độc giả đóng góp để tác giả sửa chữa những thiếu xót đó. Mọi đóng góp xin gửi về
email:
Hồ Chí Minh ngày 18 tháng 08 năm 2012
Xin chân thành cảm ơn.
Vũ Công Tâm-CH1101129 1
Phân tích mạng xã hội và vấn đề key player
Mục lục
NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN

trong một xã hội Manuel Castellshas gọi là các mạng xã hội. SNA có một lịch sử lâu dài
trong khoa học xã hội, mặc dù phần lớn các công việc của nó có cũng đến từ các nhà toán
học, vật lý, nhà sinh vật học và các nhà khoa học máy tính (bởi vì họ cũng ghiên cứu mạng
lưới các loại khác nhau)
Ý tưởng rằng về mối quan hệ giữa các mạng trong xã hội không còn mới lạ, Nhờ có SNA
mà viẹcphổ biến rộng rãi dữ liệu sẵn có và tiến bộ trong tính toán và phương pháp luận trở
nên dễ dàng hơn.
2 Phạm vi ứng dụng
Phân tích mạng còn được ứng dụng trong nhiều lĩnh vực vượt ra ngoài khoa học xã hội,
mặc dù những tiến bộ lớn nhất nói chung đã liên quan đến việc nghiên cứu cấu trúc được
tạo ra bởi con người Các nhà khoa học máy tính thực nghiệm đã sử dụng (và thậm chí phát
triển mới) phương pháp phân tích để nghiên cứu các trang web, lưu lượng truy cập
Internet, phổ biến thông tin, vv Một ví dụ trong cuộc sống là việc sử dụng mạng lưới phân
tích để nghiên cứu những chuỗi thức ăn các hệ sinh thái khác nhau.
Vũ Công Tâm-CH1101129 5
Phân tích mạng xã hội và vấn đề key player
Trong ví dụ này, các nhà nghiên cứu đã thu thập đượcmột lượng dữ liệu rất lớn bằng việc
liên kết giữa các trang web và họ đã phát hiện ra rằng Web bao gồm một lõi dày đặc liên
kết giữa các trang, trong khi hầu hết các trang web khác hoặc là được gắn liên kết hoặc là
đã được gắn liên kết tới nhân đó.
3 Ứng dụng thực tế
Các doanh nghiệp sử dụng SNA để phân tích và cải thiện luồng thông tin liên lạc trong tổ
chức của họ, hoặc với mạng lưới các đối tác và khách hang của họ.
Cơ quan thực thi pháp luật (và quân đội) sử dụng SNA để xác định các mạng lưới tội phạm
và khủng bố từ dấu vết của truyền thông mà họ thu thập được, và sau đó xác định các key
player trong các mạng này
Những mạng xã hội như Facebook sử dụng các yếu tố cơ bản của SNA để xác định và đề
nghị những người bạn tiềm năng dựa vào thông tin về bạn bè của bạn bè (friends of
friends).
Vũ Công Tâm-CH1101129 6

II.1.1 Degree centrality:
Bậc của một nút (bán bậc trong hoặc bán bậc ngoài) là số cạnh liên kết tới nút đó Trong
một đồ thị vô hướng không có khái niệm bậc vào và bậc ra
Hữu ích trong việc đánh giá mà các nút làtrung tâm để lây lanthông tin và ảnh hưởng đến
người khác ngaytrong khu phốcủa họ.
II.1.2 Đường đi và đường đi ngắn nhất
Vũ Công Tâm-CH1101129 9
Phân tích mạng xã hội và vấn đề key player
Một đường đi giữa hai nút là một sự liên tục không tuần hoàn để nối giữa 2 nút
Đường đi ngắn nhất(shortest path) giữa hai nút là con đường kết nối hai nút với số lượng
ngắn nhất của các cạnh (cũng được gọi là khoảng cách giữa các nút - distancebetween)
Trong hình trên, giữacác nút 1 và 4 có hai con đường ngắn nhấtcó chiều dài 2: {1,2,4} và
{1,3,4}. Các con đường còn lại là {1,2,3,4}, {1,3,2,4}, {1,2,5,3,4}và {1,3,5,2,4} (đường
dài nhất- longest path)
Con đường ngắn hơn (shorter path)được mong đợi khi tốc độgiao tiếp hoặc trao đổi mong
muốn
Vũ Công Tâm-CH1101129 10
Phân tích mạng xã hội và vấn đề key player
II.1.3 Betweenesscentrality
Số đường đi ngắn nhất đi qua một nút trên tất cả con đường ngắn nhất trong mạng
Đôi khi bình thường như vậy màgiá trị cao nhất là 1
Ý nghĩa: Hiển thị những nút có nhiều khả nănglà con đường thông tin liên lạcgiữa các nút
khác
Ngoài ra hữu ích trong việc xác định vị trí, nơi mà mạng của ta sẽ phá nếu cắt bỏ nút này.
(Nút nào sẽ bị cô lập nếu nút 3 và 5 không xuất hiện?)
II.1.4 Closeness centrality
Vũ Công Tâm-CH1101129 11
Phân tích mạng xã hội và vấn đề key player
Chiều dài trung bình của tất cả đường đi ngắn nhất từ một nút tới tất cả các nút khác trong
mạng (ví dụ như thế nào hoa bia nhiều trung bình phải mất đạt được tất cả các nút khác)

Một phần của quá trình giải quyết những vấn đề này là cung cấp các khái niệm để dẫn đến
các giải pháp khả thi và kết quả hữu ích. Tuy nhiên, ta có thể thấy rõ ràng rằng KPP-1 liên
quan đến việc phân mảnh một mạng lưới thành các thành phần, hoặc suy ngược lại, làm
cho khoảng cách giữa các nút quá lớn để mạng hầu như bị đứt quãng. Ngược lại, KPP-2
liên quan đến việc tìm kiếm các nút có thể đạt đến các nút còn lại càng nhiều càng tốt
thông qua các liên kết trực tiếp hoặc đường dẫn ngắn
Vấn đề đầu tiên, KPP-1, phát sinh trong một số ngữ cảnh.Một ví dụ điển hình trong bối
cảnh y tế công cộng là vấn đề tiêm chủng / kiểm dịch. Với một bệnh truyền nhiễm lây
truyền từ người sang người, và cho rằng nó là không khả thi để chủng ngừa và / hoặc kiểm
Vũ Công Tâm-CH1101129 14
Degree
Betweenness
Closeness
Eigenvector
Phân tích mạng xã hội và vấn đề key player
dịch toàn bộ dân số, tập hợp con của các thành viên nên được chủng ngừa / kiểm dịch để
tối đa cản trở sự lây lan của nhiễm trùng? Một ví dụ trong bối cảnh quân sự là lựa chọn
mục tiêu. Với một mạng lưới của những kẻ khủng bố phải phối hợp để gắn kết hiệu quả
tùy viên, và cho rằng chỉ có một số nhỏ có thể được can thiệp (ví dụ, bằng cách bắt giữ
hoặc mất uy tín), những người thân mà nên được lựa chọn để tối đa làm gián đoạn mạng?
Vấn đề thứ hai, KPP-2, phát sinh trong bối cảnh y tế công cộng khi một cơ quan y tế cần
phải chọn một tập hợp nhỏ của các thành viên dân số để sử dụng như là hạt giống cho sự
khuếch tán của các hoạt động hoặc thái độ thúc đẩy sức khỏe, chẳng hạn như sử dụng
thuốc tẩy để làm sạch kim tiêm. Trong bối cảnh quản lý tổ chức, vấn đề xảy ra khi quản lý
muốn thực hiện một sáng kiến thay đổi và cần có được một tập hợp nhỏ thông tin từ nhà
lãnh trước, có thể thực hiện bằng cách chơi 1 môn thể thao với họ vào cuối tuần. Trong bối
cảnh quân sự,
Ở cái nhìn đầu tiên, cả hai KPP-1 và KPP-2 sẽ xuất hiện để được giải quyết dễ dàng bằng
cách sử dụng một số khái niệm lý thuyết đồ thị, chẳng hạn như cutpoints và cutsets, hoặc
thông qua các phương pháp phân tích mạng xã hội, chẳng hạn như tìm kiếm núttrung tâm.

6
7
8
9
10
11
12
Node 1 có bậc trung tâm (degree centrality) cao nhất trên tất cả các biện pháp xem xét, bao
gồm cả betweenness centrality.Tuy nhiên, xóa nút 1 có hiệu lực tương đối ít trên mạng.
Khoảng cách giữa các cặp nút nhất định làm tăng, nhưng nó là rõ ràng rằng sự thông tin
giữa tất cả các điểm vẫn có thể có phân mảnh. Ngược lại, xóa 8 nút, mà không có
betweenness cao nhất, là hiệu quả hơn.Loại bỏ 8 chia đồ thị thành năm mảnh vỡ không có
liên quan (thành phần).
Đối với KPP-2, hình ảnh sáng hơn một chút. Nếu chúng ta xây dựng KPP-2 về đến hầu hết
các nút trực tiếp, mức độ trung tâm là tối ưu.Nếu chúng ta xây dựng nó trong điều kiện đạt
được các nút trêntới bước m, sau đó chúng ta có thể dễ dàng xác định một biện pháp mới
của trung tâm là đếm số lượng các nút trong m khoảng cách của một nút cho trước.
I.1.4 L ự a Ch ọ n Nhóm V ấ n Đ ề
Việ c lựa chọn nhóm vấn đề, đã được thảo luậnnhư là nhóm vấn đề trung tâm tại Everett
và Borgatti (1999), đề cập đến thực tế là lựa chọn một tập hợp của các nút, như một toàn
thể để giải quyết KPP-1 hoặc KPP-2, Sự khác nhau hoàn toàn từ lựa chọn mộtsố nút riêng
biệt như nhau đó là giải pháp tối ưu cho KPP. Để bắt đầu, hãy xem xét KPP-1.Hình bên
dưới cho thấy một đồ thị trong có các nút h và I là các nút riêng lẻ, đó là các nút tốt nhất để
Vũ Công Tâm-CH1101129 16
Phân tích mạng xã hội và vấn đề key player
xóa đi và làm phân mảnh mạng. Tuy nhiên, xóa i sẽ làm mạng ít phân mảnh hơn xóa h, vì
khi xóa h sẽ làm cho r trở thành cô lập Ngược lại, xóa m với h làm số lượng phân mảnh gia
tăng, nhưng m không hiệu quả như i. Nguyên nhân i và h là không tốt như i và m và i và h
là không quan trọng trong vai tròtrong mạng liên lạc của chúng(i và h) - chúng kết nối các
bên thứ ba cùng với nhau. Trong một nghĩa nào đó, tính trung tâm của một nút là do tính

13
14
15
16
17
18
19
20
21
22
23
24
27
2829
30
31
32
34
35
36
37
38
39
40
42
43
45
46
47
4849

90
91
92
93
95
96
97
98
99
100
101
102
104
105
106
107
108
109
113
115
116
117
118
120
122
123
124
125
126
127

165
166
167
169
171
172
173
174
175
177
178
180
182
183
184
185
187
188
189
190
191
192
193
194
196
197
199
200
202
203

245
246
251
252
254
255
256
258
260
273
275
277
280
285
287
290
295
298
Vũ Công Tâm-CH1101129 18
1. Select k nodes at random to populate set S
2. Set F = fit using appropriate key player metric
3. For each node u in S and each node v not in S
a. DELTAF = improvement in fit if u and v were swapped
4. Select pair with largest DELTAF
a. If DELTAF <= then terminate
b. Else, swap pair with greatest improvement in fit and set F = F + DELTAF
5. Go to step 3
Phân tích mạng xã hội và vấn đề key player
Hình tam giác hướng lên dùng chỉ người Mỹ gốc Phi, hình tam giác đi xuống dùng chỉ
người Puerto Rico, và hình vuông xác định tất cả những người khác.

Group
Size
Number
Reached
Percent
Reached
1 16 8.3
2 27 14.0
3 36 18.7
4 43 22.3
5 49 25.4
6 55 28.5
7 61 31.6
8 67 34.7
9 72 37.3
10 77 39.9
11 82 42.5
12 87 45.1
13 92 47.7
14 97 50.3
I.1.6.2 Đới với khủng bố
Tập dữ liệu khủng bố, được biên soạn bởi Krebs (2001), bao gồm một mạng lưới người
quen giả định trong số 74 nghi can khủng bố. Theo mục đích của phân tích này, chỉ có các
thành phần chính được sử dụng, bao gồm 63 cá nhân
Câu hỏi đầu tiên chúng tôi yêu cầu những người cần được cô lập để làm gián đoạn mạng
lớn nhất. Hãy giả định rằng chúng tôi chỉ có thể cô lập ba người (A,B,C trong hình dưới).
Chạy chương trình tìmKeyPlayer với 3 nút đó (các nút A, B, và C). Loại bỏ các nút này
mang lại một phân mảnh có số đo 0,59, và phá vỡ các đồ thị với 7 thành phần nhỏ.
Câu hỏi thứ hai là chúng ta muốn phổ biến thông tin nhất định, chúng ta cần tiếp xúc
những nút nào để tất cả những nút còn lại có thể tiếp xúc được thông tin đó?Chúng ta giả