ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
LỚP CAO HỌC TỪ XA QUA MẠNG K6
Môn học: Cơ sở dữ liệu nâng cao
Bài tiểu luận
MÔ HÌNH MẠNG XÃ HỘI
VÀ THUẬT TOÁN TÌM KEY LAYER
ỨNG DỤNG MÔ PHỎNG TÍNH TOÁN TÌM KEY LAYER
GVHD: PGS. TS: Đỗ Phúc
Học viên thực hiện:
Lê Hoài Nam
MSHV: CH1101106
Tháng 8 – 2012
Trang 1
Mục lục
Trang 2
I. Giới thiệu chung
Mạng xã hội có thể hiểu là một hệ thông kết nối giữa các thành viên với nhau
qua internet. Khi tham gia mạng xã hội, người dùng sẽ dễ dàng tìm thấy được mối
quan hệ với những người xung quanh mình, tìm bạn bè học cùng trường, đồng nghiệp
cùng công ty hoặc những người cùng sở thích v.v Nhờ những tính năng nổi trội,
hướng tới từng người dùng cụ thể mà mạng xã hội đã thu hút ngày càng nhiều người
sử dụng. Người dùng Internet dần chuyển qua sử dụng các mạng xã hội nhiều hơn các
ứng dụng khác. Và cũng vì đó mà lý thuyết và ứng dụng về mô hình mạng xã hội ngày
càng được các chuyên gia, nhà nghiên cứu đầu tư nhiều hơn nhằm tạo ra những mạng
xã hội tốt hơn.
Mô hình cơ bản của mạng xã hội là một đồ thị với các đỉnh và cạnh. Đỉnh là
các đối tượng trong mạng và cạnh là mối quan hệ giữa các đối tượng đó.
Để hiểu rõ hơn về mạng xã hội, báo cáo này sẽ trình bày lý thuyết cơ bản về mô
hình mạng xã hội, các đặt trưng của mạng xã hội và các thuật toán đề tìm key layer
trong mạng. Bên cạnh đó là ứng dụng mô phỏng giải quyết bài toán tìm keylayer trong

Trang 4
- Trọng số: dùng để biểu diễn mức độ mạnh/yếu của các liên kết trong mạng xã
hội. Trọng số có thể là :
o Mức độ tương tác giữa các thực thể trong quá trình hoạt động
o Số lượng các thay đổi giữa các thực thể.
o Đánh giá mực độ quan trọng của các liên kết
o Chi phí kết nối, trao đổi, khoảng cách giữa các thực thể.
- Key layers là các node đặc biệt hoặc có vai trò trọng tâm trong mạng. Có nhiều
loại giá trị dùng để tìm key layer tùy vào mục tiêu phân tích, gồm có:
o Degree Centrality: Thể hiện mức độ liên kết (vào / ra) của 1 node. Nó
thường dùng để đánh giá mưc độ kết nối của 1 thực thể và do đó nó còn
thể hiện mức độ ảnh hưởng và phân bố, xác định mưc độ truyền thông
tin và ảnh hưởng của 1 node tơi các node xung quanh.
o Betweeness Centrality: là số đường đi ngắn nhât đi qua 1 node chia cho
tổng số đường đi ngắn nhất trong toàn mạng. Dùng để hiện mức độ quan
trọng của 1 điểm trên mạng. Thường dùng khi cần xác định xem mức độ
ảnh hưởng khi loại bỏ 1 điểm ra khỏi mạng.
o Closeness Centrality: thể hiện cho độ dài của tổng tất cả các đường
ngắn nhất từ 1 điểm đến tất cả các điểm trên mạng. Được khi ttrong
trường hợp cần tìm nguồn thông tin quan trong và phổ biến trong toàn
mạng. Giá trị này càng nhỏ thì tốc độ truyền thông tin của node đó cang
cao.
o Clustering Coefficent: Hệ số gom cụm của 1 node là mực độ tập trung
của các node xung quanh nó.
3. Công thức tìm key layer và ví dụ minh họa
Cho mạng xã hội có mô hình như sau:
Trang 5
Ta tìm được ma trận kề cho đồ thị trên như sau
V1 V2 V3 V4 V5 V6
V

V6
Tìm betweeness centrality
Công thức
Trang 7
Trong đó:
o σ
st
là tổng số đường đi gắn nhất từ đỉnh s tới đỉnh t
o σ
st
(v) là số đường đi gắn nhất từ đỉnh s tới đỉnh t qua đỉnh v.
Áp dụng
Đỉnh Betweenness centrality
V1
V2 (tính tương tự như v1)
V3 (tính tương tự như v1)
V4 (tính tương tự như v1)
Trang 8
V5 (tính tương tự như v1)
V6 (tính tương tự như v1)
Tính closeness centrality
Công thức
Trong đó
o là số bước đi từ đỉnh t tới đỉnh v/chiều dài từ v tới t
Áp dụng
Đỉn
h
closeness centrality
V1
Trang 9

III. Cài đặt thuật toán tìm keylayer.
Theo công thức được trình bày ở phần trên, ta có thể cài đặt thuật toán tìm key
layer như sau.
o Thuật toán sẽ sử dụng cấu trúc dữ liệu chính là ma trận M để thể hiện
thông tin trong đồ thị.
o Hàm tìm đường và tính toán trong đồ thị. Sử dụng thuật toán dijitra để
tìm đường và áp dụng các công thức tính toán để tìm kết luận
Chú ý con trỏ cursor dùng để lưu trữ giá trị sau khi phân tích bao gồm số bước
đi numOfSteps, số đường đi ngắn nhất numOfWays và số đường đi ngắn nhất qua X
numOfWaysHaveX.
public void computingDirection(ComCursor cursor, int from, int
end,int except){
Trang 12
Vector<Integer> vec;
vec.add(from);
int c=0;
int n= numOfNode;
int countRoute = 0;
cursor.numOfSteps = 0;
cursor.numOfWays =0;
Vector<Integer> listParent;
listParent.add(-1);
Stack<TreeNode> tree;
tree.push(new TreeNode(from));
while (!vec.contains(end)){
int vsize = vec.size();
boolean canmore = false;
countRoute =0;
List<Integer>;
for (int j2 =0; j2<vec.size(); j2++){

2. Tìm Betweeness centrality
double bc =0;
int n= numOfNodes;
for (int i=0; i< n; i++){
for (int j=i+1; j<n; j++){
if (i==index || j == index) continue;
ComCursor cursor = new ComCursor();
computingDirection (cursor, i, j, index);
bc +=
((double)cursor.numOfWaysHaveX)/cursor.numOfWays;
}
}
return bc;
Trang 14
3. Tìm closeness centrality
double cc =0;
int n= numOfNodes;
for (int i=0; i< n; i++){
if (i==index) continue;
ComCursor cursor;
computingDirection (cursor, index, i, -1);
cc += cursor.numOfSteps;
}
return 1/cc;
4. Tìm clustering coefficent
int n= mNodes.size();
int k = 0;
for (int i=0; i<n; i++)
if (mMatrix[index][i]==1) k ++;
int e=0;

Kết quả tính toán các key value
DC : Degree Centrality
BC : Betweeness Centrality
Trang 17
CC : Closeness Centrality
CCoeff : Clustering Coeff
Node số 1:
DC(1) = 0.400000
BC(1) = 0.000000
CC(1) = 0.100000
CCoeff(1) = 1.000000
Node số 2:
DC(2) = 0.600000
BC(2) = 1.500000
CC(2) = 0.142857
CCoeff(2) = 0.666667
Node số 3:
DC(3) = 0.600000
BC(3) = 1.500000
CC(3) = 0.142857
CCoeff(3) = 0.666667
Node số 4:
DC(4) = 0.800000
BC(4) = 7.000000
CC(4) = 0.166667
CCoeff(4) = 0.166667
Node số 5:
DC(5) = 0.200000
BC(5) = 0.000000
CC(5) = 0.100000

[2] Bài giảng chương 5 của môn Cơ sở dữ liệu nâng cao
[3] Wikipedia – Mạng xã hội />%C3%A3_h%E1%BB%99i
[4] Wikipedia – Social network
/>[5] Wikipadia – Social network Analysis
/>Trang 20