ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
TIỂU LUẬN CƠ SỞ DỮ LIỆU NÂNG CAO
DÙNG ĐỘ ĐO TRUNG TÂM ĐỂ NHẬN DẠNG
KEY PLAYER TRONG MẠNG XÃ HỘI
Giảng viên hướng dẫn : PGS.TS Đỗ Phúc
Học viên thực hiện : Nguyễn Thị Ngọc Diễm
MSHV : CH1101075
Lớp : Cao học khóa 6
TP Hồ Chí Minh, tháng 08 năm 2012
MỤC LỤC
I. Giới thiệu chung
Nghiên cứu mạng là một chủ đề nghiên cứu chủ động vì khả năng của việc
mô hình hóa nhiều hệ thống phức tạp trên thế giới thực. Mạng xã hội là đồ thị
của tương tác giữa các cá nhân, nhóm người. Một mạng lưới xã hội bao gồm
một tập hợp của các nút như người, tổ chức, hoặc các nhóm cùng với một tập
của liên kết tập hợp khái quát ý tưởng của một liên kết từ A đến B. Phân tích
mạng lưới xã hội cung cấp công cụ và phương pháp tiếp cận lý thuyết thăm dò
toàn diện của các mô hình tương tác giữa các cá nhân, nhóm và thậm chí tổ
chức.
Các mạng xã hội đã trở nên phổ biến gần đây với sự ra đời của các trang
web như MySpace, Friendster, Orkut, Twitter, Facebook. Số lượng người dùng
tham gia các mạng này là rất lớn và vẫn đang phát triển. 133 triệu blog được
lập chỉ mục bởi Technorati (là một trên web công cấp search engine trên blog
đầu tiên và là nơi cho blogger có thể sưu tập, đánh dấu và phân phối các bài
viết trực tuyến) kể từ khi năm 2002 và 900 ngàn bài viết được đăng trên blog
trong 24 giờ. Tháng 6 năm 2008, Technorati đã theo dõi các blog qua 81 ngôn
ngữ và có 77.7 triệu người truy cập tại Mỹ tháng 8 năm 2008. Xu hướng này
đang phát triển sẽ giúp các nhà nghiên cứu để biến sự quan tâm cho việc phân
tích các bài viết blog trong một số kích thước. Một vấn đề cơ bản liên quan đến
các mạng là phát hiện của các cụm hoặc cộng đồng. Một Blog, cũng được gọi

phương tiện truyền thông tương tác trực tuyến cũng như các bài đăng trên blog.
Có bài đăng trên blog nhiều hơn một khoảng thời gian. Có thể là một hoặc
nhiều hơn những lời hồi đáp cho bài viết trên blog. Các hiện tượng của việc
đăng các bài viết ngày càng tăng và cần phải được phân tích. Điều này dẫn đến
vấn đề xác định key player, những người có có nhiều phản hồi cho các bài
đăng trên blog của họ.
II.
4
III. Bài toán key player
Một mạng lưới xã hội thường được xem như là một đồ thị bởi vì cấu trúc của
nó rất phức tạp. Đo lường vị trí mạng là tìm kiếm các trung tâm của một nút. Các
biện pháp cung cấp cho chúng ta cái nhìn sâu sắc vào các vai trò khác nhau và
gom nhóm trong một mạng, như người liên kết, nhà lãnh đạo, cầu nối, và các key
player. Bài toán key player (KPP- Key Player Problem) có thể được phân ra làm
hai dạng dưới đây:
- KPP - 1: Với một mạng xã hội, tìm thấy một tập nút k (có thể được gọi
là tập kp thứ tự k), nếu loại bỏ, sẽ làm gián đoạn tối đa liên lạc giữa các
các nút còn lại. KPP - 1 là xác định các key player với mục đích của
một cái gì đó khuếch tán tối ưu thông qua mạng lưới bằng cách sử dụng
các key player như hạt giống.
- KPP - 2: Với một mạng xã hội, tìm thấy một kp -k để được tối đa kết
nối với tất cả các các nút. KPP - 2 là việc xác định các key player cho
mục đích của việc phá vỡ hoặc phân mảnh mạng bởi việc loại bỏ các
nút quan trọng.
Một phần của quá trình giải quyết những bài toán này là cung cấp những định
nghĩa của các khái niệm này dẫn đến các giải pháp khả thi và kết quả hữu ích. Ta
thấy 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 nếu không, làm cho khoảng cách giữa các nút lớn đến nổi như là bị
ngắt kết nối. Ngược lại, KPP-2 liên quan đến việc tìm kiếm các nút có thể đi đến
các nút còn lại sao cho càng nhiều càng tốt thông qua các liên kết trực tiếp hoặc

Độ trung tâm đo độ trung tâm khi một cá nhân được đặt trong một mạng xã hội.
Degree centrarity, Betweenness centrality, Closeness centrality và Eigenvector
centrality là bốn độ đo lường trung tâm được sử dụng rộng rãi trong phân tích
mạng.
1. Betweenness centrality
Đối với một đồ thị G = (V, E) với n đỉnh, Betweenness centrality cho đỉnh
v được xác định bởi:
6
Trong đó:

tổng shortest path từ đỉnh đến đỉnh của toàn network

tổng shortest path từ đỉnh đến đỉnh đi qua đỉnh
Betweenness centrality được định nghĩa như tổng tỷ số của các đường đi
ngắn nhất từ một nút tới một nút khác đi qua một nút cho trước. Như xem xét KPP
- 1, một nút với Betweenness centrality cao chịu trách nhiệm cho kết nối cặp nhiều
các nút thông qua con đường tốt nhất, và việc xóa nút đó sẽ gây ra việc nhiều cặp
nút trở nên tách biệt hơn. Xóa mà nút nên gây ra nhiều cặp nút để trở thành hoàn
toàn bị ngắt kết nối hoặc ít nhất kết nối sẽ xa hơn.
2. Degree centrality
Degree centrality của một nút là số các kết nối trực tiếp của nút đó. Theo
một định nghĩa khác Degree centrality được xem là số lượng mối quan hệ mà một
nút có, tức là số lượng các liên kết sự cố khi một nút. Đối với một đồ thị G = (V,
E) với n đỉnh, mức độ trung tâm của đĩa cho đỉnh v là:
Trong đó:

số đỉnh của đồ thị

các link trực tiếp của đỉnh v
3. Closeness centrality

của cùng tác giả đã giải thích làm thế nào các độ đo trung tâm có thể được áp dụng
cho xác định lưu lượng giao thông trên một cấu trúc mạng. Ref. [4] cung cấp một
đặc tính hình học của các key player được xác định với một độ đo intercentrality,
trong đó có vào tài khoản của cả hai của một cầu thủ trung tâm và đóng góp cho
trung tâm của những người khác. Các tác giả đã chơi game là lĩnh vực của họ cho
nghiên cứu của họ. Các kết quả được thể hiện như là một kết quả nghiên cứu của
8
họ. Ref. [6] cung cấp một cái nhìn sâu sắc vào vấn đề. Bài viết này có thể được sử
dụng như một vật liệu giới thiệu để biết chi tiết liên quan đến khu vực của các key
player như ý nghĩa của vấn đề chủ chốt, phân loại và khác nhau lĩnh vực ứng dụng
của khu vực. Bài báo này cũng thảo luận về về làm thế nào các biện pháp trung
tâm là hữu ích trong việc tìm kiếm chủ chốt. Phương pháp tiếp cận khác nhau
được áp dụng cho tìm thấy các key player cũng được giải thích trong bài báo này.
Ref. [1] được áp dụng cách tiếp cận lý thuyết thông tin để xác định bộ key player.
Các tác giả đề xuất một phương pháp mới nhằm tìm kiếm một tập hợp các key
player bằng cách sử dụng dữ liệu ngẫu nhiên các biện pháp. Ref. [3] kết hợp các
phương pháp hiện có trên tính toán giá trị chính xác và giá trị gần đúng của sự gần
gũi trung tâm và trình bày các thuật toán mới để xếp hạng các đỉnh đầu-k với trung
tâm của sự gần gũi cao nhất.
VI. Kết luận
Một key player là những người luôn luôn tỏa sáng và tham gia vào các hoạt
động cộng đồng. Trong vấn đề này, cách tiếp cận trung tâm được sử dụng xác định
các bộ của các key player trong weblog. Các mối quan hệ cũng như cách tương tác
trong một mạng xã hội sẽ luôn thay đổi. Như vậy, các công cụ mới cũng sẽ phát
triển để thích ứng tốt hơn với cộng đồng những người sử dụng mạng xã hội.
VII.Ứng dụng
Chương trình cho phép nhập vào đồ thị người dùng trên mạng xã hội và xuất ra
các độ đo trung tâm để tìm kiếm key player. Chương trình được viết bằng ngôn
ngữ đặc tả HTML và ngôn ngữ lập trình Javascript và có thể chạy trên các trình
duyệt Web như Google Chrome, Firefox, Opera và Safari.

closeness centrality for large - scale social networks", Springer
Lecture Notes in Computer Science, pp 186-195, 2008
[4] Coralio Ballester, Antoni Calvo - Armengol, Yves Zenou, "Who's
who in networks wanted: the key player", Econometrica, vol 74,
No. 5, pp 1403-1417, 2006
[5] Stephen P. Borgatti, "Centrality and network flow", Social
Networks, Vol 27, pp 55–71, 2005
[6] Stephen P. Borgatti, "The Key Player Problem" available at:
www.steveborgatti.com/ /borgatti%20-%20NAS%20-
17