Đại Học Quốc Gia Tp. Hồ Chí Minh
Trường Đại Học Công Nghệ Thông Tin

Báo cáo môn học Cơ Sở Dữ Liệu Nâng Cao
TÌM HIỂU MẠNG XÃ HỘI VÀ CÁC KỸ THUẬT
PHÂN TÍCH
GVHD : PGS.TS Đỗ Phúc
Học Viên : Đỗ Duy Phúc
Mã Học Viên: CH1101122
Lớp: Cao Học K6
Tháng 8 năm 2012
Lời Mở Đầu
Ngành nghiên cứu các mạng lưới là một chủ đề nghiên cứu sôi động và thu hút bởi khả
năng mô hình hóa của chúng cho nhiều hệ thống phức tạp trong thế giới thực. Trong đó,
mạng xã hội là một trong những đối tượng nghiên cứu phức tạp và thú vị nhất. Đặc biệt là
với sự xuất hiện và phát triển mạnh mẽ của các trang mạng xã hội ảo hiện nay trên
Internet.
Với khả năng thu hút người dùng mạnh mẽ và đông đảo, các trang mạng xã hội tuy ảo
nhưng lại là nơi thu nhặt được lượng thông tin khổng lồ từ người dùng ở thế giới thật.
Khi phân tích khối lượng thông tin này, chúng ta sẽ có được nhiều thông tin, tri thức quý
giá cho nghiên cứu khoa học và ứng dụng vào thực tiễn.
Bài viết này sẽ giới thiệu về mạng xã hội, đồng thời giới thiệu các khái niệm và kỹ thuật
phân tích nhằm thu nhận các thông tin ở nhiều khía cạnh khác nhau của một mạng xã hội.
Các thông tin thu được sẽ cho ta một cái nhìn thấu đáo về bản chất của các mạng lưới, về
các cá thể, tổ chức tham gia vào đó và mối quan hệ giữa chúng. Điều này có thể giúp ích
cho các nhà khoa học nghiên cứu về bản chất xã hội hay hỗ trợ các nhà quản lý trong việc
đưa ra các quyết định, chính sách ảnh hưởng đến các thành phần trong mạng lưới do
mình kiểm soát.

Mục Lục


tích có phương pháp các mạng xã hội. Cách phân tích này nhìn các quan hệ xã hội theo
quan điểm lý thuyết đồ thị, bao gồm các nốt (node - đại diện các tác nhân đơn lẻ trong
mạng) và các ràng buộc (tie – đại diện các mối quan hệ giữa các cá thể, như là tình bạn,
họ hàng, vị trí trong tổ chức, quan hệ đôi lứa, v.v…) Và các mô hình này thường được
biễu diễn dưới dạng sơ đồ mạng (giống như đồ thị), nơi các nốt được biểu diễn thành các
điểm, còn các ràng buộc biểu diễn thành các đường thẳng nối giữa các điểm.
SNA sẽ ánh xạ và đo đạt các mối quan hệ và dòng thông tin giữa các tác nhân (như là con
người, các nhóm, các tổ chức, giữa các máy tính, URL, và các thực thể khác có kết nối
thông tin và tri thức với nhau). Các kết quả phân tích này thường rất hữu ích cho các nhà
tư vấn quản lý trong rất nhiều lĩnh vực.
Để thấu hiểu được đặc tính của các mạng lưới và các cá thể tham gia vào trong mạng đó,
chúng ta cần đánh giá vị trí của các tác nhân trong mạng. Viêc đo đạc định vị mạng lưới
là công việc đi tìm độ trung tâm (centrality) của một nốt. Các kết quả đo đạt này sẽ cho
chúng ta cái nhìn thấu đáo về các vai trò và các phân nhóm khác nhau trong một mạng
lưới: ai là những người kết nối, những ai là chuyên gia, những ai là người dẫn đầu, những
ai là cầu nối, ai biệt lập, nơi đâu là các cụm nhóm và ai tham gia trong đó, ai là phần lõi
trung tâm của mạng lưới, và ai đang nằm ở vùng biên của mạng,v.v…

II.1. Các mục tiêu phân tích mạng xã hội phổ biến
Mạng “Kite Network”
Chúng ta hãy xem xét một mạng xã hội, mạng “Kite Network” ở trên, được phát triển
bởi David Krackhardt, một nhà nghiên cứu hàng đầu về các mạng xã hội. Hai nốt trong
mạng được nối với nhau nếu chúng thường “nói chuyện” với nhau, hoặc tương tác theo
một cách nào đó. Andre thường tương tác với Carol, nhưng lại không có với Ike. Vì thế
Andre và Carol được nối với nhau, và không có liên kết được vẽ giữa Andre và Ike.
Mạng lưới này cho ta thấy một cách hiệu quả sự phân biệt rõ ràng giữa ba phép đo đạc về
độ trung tâm cá thể phổ biến: Độ trung tâm cấp bậc (Degree Centrality), Độ trung
tâm trung gian (Betweenness Centrality), và Độ trung tâm kề cận (Closeness
Centrality).
II.1.1. Độ trung tâm cấp bậc - Degree Centrality


Một mạng lưới có độ tập trung rất cao thường bị thống trị bởi một hoặc một vài nốt trung
tâm. Nếu những nốt này bị loại bỏ hoặc tổn hại, mạng lưới có thể nhanh chống bị phân
mảnh thành nhiều phần con tách biệt. Một nốt có tính trung tâm cao lại trở thành một
điếm chết. Một mạng tập trung xung quanh một điểm trung tâm nhiều kết nối có thể sụp
đổ một cách bất ngờ và đột ngột nếu điểm trung tâm đó bị vô hiệu hoặc loại bỏ đi. Các
điểm trung tâm là các nốt có cấp bậc (degree) và tính trung gian (betweeness) cao.
Một mạng lưới ít tập trung sẽ không có điểm chết nào. Nó sẽ có khả năng chịu đựng và
đàn hồi cao hơn với các cuộc tấn công có chủ đích hoặc các sự sụp đổ bất thường. Vì
nhiều nốt và liên kết có thể bị đứt gãy và sụp đỗ thì mạng lưới vẫn cho phép các nốt còn
lại tiếp tục chạm được đến các nốt còn lại trong mạng bằng con đường khác. Mạng lưới
kiểu này sẽ khó bị sụp đổ bất ngờ.
II.1.5. Hệ số cụm - Clustering Coefficient
Trong lý thuyết đồ thị, hệ số cụm (clustering coefficient) là một thước đo mức độ xu
hướng kết nhóm lại với nhau của các nốt trong đồ thị. Có bằng chứng cho thấy rằng trong
các mạng lưới trong cuộc sống thật, cụ thể là các mạng xã hội, những nốt có xu hướng
tạo các nhóm liên kết chặc chẽ thường có đặc tính là có mật độ tương đối cao các mối
ràng buộc [1]. Xác suất xuất hiện các mối ràng buộc này thường có xu hướng lớn hơn
mức xác suất trung bình một ràng buộc được thiết lập ngẫu nhiên giữa hai nốt [2].
II.1.6. Phần tử chủ chốt - Key players
Phần tử chủ chốt (key player) là các phần tử trong mạng được cho là quan trọng khi
được xem xét theo một vài tiêu chuẩn. Việc xác định các phần tử chủ chốt là một trong
những mục tiêu quan trọng khi phân tích các mạng xã hội.
Chúng thường thường xác định được dựa trên hai yêu cầu sau:
- Thứ nhất, các phần tử chủ chốt là các nốt mà nếu bị loại bỏ khỏi mạng sẽ gây việc
gián đoạn tối đa việc trao đổi thông tin giữa các nốt. Khi theo tiêu chí này, việc
xác định dựa trên mục đích phát tán thứ gì đó một cách tối ưu trên mạng bằng

cách sử dụng các phần tử chủ chốt như là các điểm gieo thông tin ban đầu. Độ
trung tâm trung gian (Betweenness Centrality) phù hợp với tiêu chí này.

là cạnh nối đỉnh i với đỉnh j. Tập đỉnh láng giềng N
i
cho một đỉnh v
i

được định nghĩa là tập các đỉnh có liên kết trược tiếp đến v
i
, công thức toán học:
Ta gọi k
i
là số lượng các đỉnh, |N
i
|, trong tập láng giềng N
i
.
Khi đó hệ số cụm C
i
cho một đỉnh v
i
được tính bằng tỉ lệ giữa các liên kết giữa các đỉnh
trong tập đỉnh láng giềng chia cho số lượng các liên kết có thể tồn tại giữa chúng. Với
một đồ thị có hướng, e
ij
phân biệt với e
ji
, và vì thế với mỗi tập láng giềng N
i
sẽ có k
i
(k

* Hệ số cụm của từng nút và toàn bộ mạng xã hội
* Tim tập các key players ( chủ thể chủ chốt ) trong mạng xã hội
Bài giải:
- Đồ thị cho mạng xã hội là:
Đồ thị G
- Ma trận kề (adjacency matrix):
+( + + + + +
+( ( ( ) ) )
+ ( ( ( ) )
+ ( ( ( ) )
+ ) ( ( ( (
+ ) ) ) ( )
+ ) ) ) ( )
- Liệt kê tất cả đường đi ngắn nhất giữa 2 đỉnh bất kỳ trong đồ thị, ta có:
[V1, V2, V4]
[V1, V2, V4, V5]
[V1, V2, V4, V6]
[V1, V3, V4]
[V1, V3, V4, V5]
[V1, V3, V4, V6]
[V2, V1]
[V2, V3]
((
[V2, V4, V6]
[V3, V1]
[V3, V4, V5]
[V4, V2]
[V4, V3]
[V4, V5]
[V4, V6]

2. Tính Clustering Coefficient (Hệ số cụm)
, Tính hệ số cụm cho từng nút
-

7$/7/80/
(
+(
+
+
+
+
+
, Tính hệ số gom cụm cho toàn mạng
3. Tìm key player:
Dựa vào các nốt có giá trị tốt nhất ở các tiêu chí Degree Centrality, Beetweeness
Centrality và Closeness Centrality để tìm tập key player:
Ta có:
Max(C
D
(V)) = {V4}
Max(C
B
(V)) = {V4}
Max (C
C
(V)) = {V4}
 Tập key player = {V4}
III.4 Chương trình demo
Để hỗ trợ kiểm tra các công thức trên, một chương trình demo được viết để tính toán tự
động các kết quả. Chương trình demo được viết bằng ngôn ngữ ruby. Hiện tại do mục