ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH

CHƯƠNG TRÌNH ĐÀO TẠO THẠC SĨ CNTT QUA MẠNG
---------------  ---------------

TÌM HIỂU MẠNG XÃ HỘI
XÂY DỰNG ỨNG DỤNG DEMO

Bộ môn

: Cơ Sở Dữ Liệu Nâng Cao

GVHD

: PGS-TS. Đỗ Phúc

Thực hiện : Nguyễn Khánh Ngọc
CH1001117


Thành phố Hồ Chí Minh - Tháng 08 Năm 2011


NHẬN XÉT CỦA GIẢNG VIÊN HƯỚNG DẪN

.........................................................................................................................
.........................................................................................................................
.........................................................................................................................
.........................................................................................................................
.........................................................................................................................
.........................................................................................................................

.........................................................................................................................
.........................................................................................................................
.........................................................................................................................
.........................................................................................................................
.........................................................................................................................


MỤC LỤC
Phần 1: Giới Thiệu Mạng Xã Hội
I. Khái niệm ............................................................................................................ 1
II. Lịch sử ................................................................................................................ 1
III. Cấu trúc và mục tiêu cảu mạng xã hội ............................................................. 2
IV. Phân tích mạng xã hội ...................................................................................... 3
IV. Biện pháp phân tích mạng xã hội ..................................................................... 4

Phần 2: Đồ thị và lưu trữ đồ thị trong cơ sơ dữ liệu quan hệ
I. Định nghĩa đồ thị .................................................................................................9
II. Các thuật toán trong đồ thị..................................................................................10
III. Lưu trữ đồ thị trong cơ sở dữ liệu quan hệ........................................................12
IV. Cài đặt ứng dụng Demo mạng xã hội................................................................16
1.Chức năng vẽ đồ thị .......................................................................................16
2. Chức năng thêm node, xóa node trực quan trên giao diện ..........................17
3. Chức năng phân tích mạng xã hội, tìm key player ......................................18
4. Xem và chỉnh sửa thông tin cá nhân của person trong mạng xã hội ...........20
5. Chức năng kết bạn và tìm những người có chung bạn bè với mình ............20
6. Chức năng tìm kiếm những người có chung sở thích ..................................21

Phần 3: Kết luận
Tài liệu tham khảo..........................................................................................................22



Phần I: Mạng xã hội
I.

Khái niệm

Mạng xã hội, hay gọi là mạng xã hội ảo,(social network) là dịch vụ nối kết các
thành viên cùng sở thích trên Internet lại với nhau với nhiều mục đích khác nhau
không phân biệt không gian và thời gian.
Mạng xã hội có những tính năng như chat, e-mail, phim ảnh, voice chat, chia sẻ
file, blog và xã luận. Mạng đổi mới hoàn toàn cách cư dân mạng liên kết với nhau và
trở thành một phần tất yếu của mỗi ngày cho hàng trăm triệu thành viên khắp thế giới.
Các dịch vụ này có nhiều phương cách để các thành viên tìm kiếm bạn bè, đối tác: dựa
theo group (ví dụ như tên trường hoặc tên thành phố), dựa trên thông tin cá nhân (như
địa chỉ e-mail hoặc screen name), hoặc dựa trên sở thích cá nhân (như thể thao, phim
ảnh, sách báo, hoặc ca nhạc), lĩnh vực quan tâm: kinh doanh, mua bán...
Hiện nay thế giới có hàng trăm mạng mạng xã hội khác nhau, với MySpace và
Facebook nổi tiếng nhất trong thị trường Bắc Mỹ và Tây Âu; Orkut và Hi5 tại Nam
Mỹ; Friendster tại Châu Á và các đảo quốc Thái Bình Dương. Mạng xã hội khác gặt
hái được thành công đáng kể theo vùng miền như Bebo tại Anh Quốc, CyWorld tại
Hàn Quốc, Mixi tại Nhật Bản và Yahoo! 360 tại Việt Nam.

II.

Lịch sử

Mạng xã hội xuất hiện lần đầu tiên năm 1995 với sự ra đời của trang Classmate với
mục đích kết nối bạn học, tiếp theo là sự xuất hiện của SixDegrees vào năm 1997 với
mục đích giao lưu kết bạn dựa theo sở thích.
Năm 2002, Friendster trở thành một trào lưu mới tại Hoa Kỳ với hàng triệu thành

viên ghi danh. Tuy nhiên sự phát triển quá nhanh này cũng là con dao hai lưỡi: server
của Friendster thường bị quá tải mỗi ngày, gây bất bình cho rất nhiều thành viên.
Năm 2004, MySpace ra đời với các tính năng như phim ảnh (embedded video) và
nhanh chóng thu hút hàng chục ngàn thành viên mới mỗi ngày, các thành viên cũ của
Friendster cũng lũ lượt chuyển qua MySpace và trong vòng một năm, MySpace trở
thành mạng xã hội đầu tiên có nhiều lượt xem hơn cả Google và được tập đoàn News
Corporation mua lại với giá 580 triệu USD.
Năm 2006, sự ra đời của Facebook đánh dấu bước ngoặt mới cho hệ thống mạng xã
hội trực tuyến với nền tảng lập trình "Facebook Platform" cho phép thành viên tạo ra
những công cụ (apps) mới cho cá nhân mình cũng như các thành viên khác dùng.
Facebook Platform nhanh chóng gặt hái được thành công vược bực, mang lại hàng
trăm tính năng mới cho Facebook và đóng góp không nhỏ cho con số trung bình 19
phút mà các thành viên bỏ ra trên trang này mỗi ngày.

5


III. Cấu trúc
1. Cấu trúc

và mục tiêu của một mạng xã hội.

Nút (node): Là một thực thể trong mạng. Thực thể này có thể là một cá nhân, một
doanh nghiệp hoặc một tổ chức bất kỳ nào đó
Liên kết (tie): là mối quan hệ giữa các thực thể đó. Trong mạng có thể có nhiều
kiểu liên kết. Ở dạng đơn giản nhất, mạng xã hội là một đơn đồ thị vô hướng các mối
liên kết phù hợp giữa các nút. Ta có thể biểu diễn mạng liên kết này bằng một biểu đồ
mà các nút được biểu diễn bởi các điểm còn các liên kết được biểu diễn bởi các đoạn
thẳng.
2. Mục tiêu


Tạo ra một hệ thống trên nền Internet cho phép người dùng giao lưu và chia sẻ
thông tin một cách có hiệu quả, vượt ra ngoài những giới hạn về địa lý và thời gian.
Xây dựng lên một mẫu định danh trực tuyến nhằm phục vụ những yêu cầu công
cộng chung và những giá trị của cộng đồng.
Nâng cao vai trò của mỗi công dân trong việc tạo lập quan hệ và tự tổ chức xoay
quanh những mối quan tâm chung trong những cộng đồng thúc đẩy sự liên kết các tổ
chức xã hội.
Sự ra đời ồ ạt của các mạng xã hội (Social Network) thời gian gần đây ở Việt Nam
cũng như trên toàn thế giới đã tạo ra một làn sóng mới kích thích sự phát triển của
kênh truyền thông cộng đồng.
Điểm nổi bật của Social Network mà ai cũng nhận thấy đó là tính kết nối và chia sẻ
rất mạnh mẽ. Nó phá vỡ những ngăn cách về địa lý, ngôn ngữ, giới tính lẫn quốc gia.
Những gì bạn làm, bạn nghĩ, cả thế giới có thể chia sẻ với bạn chỉ trong tích tắc.
Social Network site hay mạng xã hội là mạng được tạo ra để tự thân nó lan rộng trong
cộng đồng thông qua các tương tác của các thành viên trong chính cộng đồng đó. Mọi
thành viên trong mạng xã hội cùng kết nối và mỗi người là một mắt xích để tạo nên
một mạng lưới rộng lớn truyền tải thông tin trong đó. Về cơ bản, mạng xã hội giống
như một trang web mở với nhiều ứng dụng khác nhau. Mạng xã hội khác với trang
web thông thường ở cách truyền tải thông tin và tích hợp ứng dụng. Trang web thông
thường cũng giống như truyền hình, cung cấp càng nhiều thông tin, thông tin càng hấp
dẫn càng tốt còn mạng xã hội tạo ra các ứng dụng mở, các công cụ tương tác để mọi
người tự tương tác và tạo ra dòng tin rồi cùng lan truyền dòng tin đó.

6


IV.

Phân tích mạng xã hội


Một mạng xã hội là một cấu trúc xã hội tạo ra từ các cá nhân (hoặc tổ chức) gọi là
"nút", được gắn liền (kết nối) bằng một hoặc nhiều loại hình cụ thể của phụ thuộc lẫn
nhau , chẳng hạn như tình bạn , họ hàng , quan tâm, trao đổi tài chính, không thích,
hoặc mối quan hệ về niềm tin hoặc uy tín .
Phân tích mạng xã hội xem mối quan hệ xã hội về mặt lý thuyết mạng lưới bao
gồm các nút và các mối quan hệ (còn gọi là các cạnh, liên kết, hoặc kết nối). Nodes là
những diễn viên cá nhân trong mạng lưới, và quan hệ là những mối quan hệ giữa các
diễn viên. Kết quả là đồ thị dựa trên cấu trúc thường rất phức tạp . Có thể có nhiều
loại quan hệ giữa các nút. Nghiên cứu ở một số lĩnh vực học thuật đã chỉ ra rằng các
mạng xã hội hoạt động trên nhiều cấp độ, từ gia đình đến mức của các quốc gia, và
đóng một vai trò quan trọng trong việc xác định cách các vấn đề được giải quyết, tổ
chức đang chạy, và mức độ mà các cá nhân thành công trong việc đạt được mục tiêu
của họ.
Trong dạng đơn giản nhất, một mạng xã hội là một bản đồ của quan hệ quy định,
chẳng hạn như tình bạn, giữa các nút đang được nghiên cứu. Các nút mà một cá nhân
là như vậy, kết nối là các địa chỉ liên lạc xã hội của cá nhân. Mạng cũng có thể được
sử dụng để đo vốn xã hội - giá trị mà một cá nhân nhận được từ các mạng xã hội.
Những khái niệm này thường được hiển thị trong một sơ đồ mạng xã hội, nơi mà các
nút là các điểm và các mối quan hệ là những đường liên kết giữa các nút.
Phân tích mạng xã hội (liên quan đến mạng lưới lý thuyết ) đã nổi lên như một kỹ
thuật hiện đại quan trọng trong xã hội học . Nó cũng đã thu được một lượng đáng kể
trong nhân chủng học , sinh học , nghiên cứu truyền thông , kinh tế , địa lý , khoa học
thông tin , nghiên cứu tổ chức , tâm lý xã hội , và sociolinguistics , và đã trở thành một
chủ đề phổ biến của đầu cơ và nghiên cứu.
Mạng xã hội phân tích đã chuyển từ một phép ẩn dụ gợi ý để phân tích một cách
tiếp cận để mô hình, với báo cáo của chính lý thuyết, phương pháp của nó, phần mềm
phân tích mạng xã hội , và các nhà nghiên cứu. Các nhà phân tích lý do từ cả một
phần, từ cấu trúc liên quan đến cá nhân, từ hành vi thái độ. Họ thường hoặc mạng lưới
nghiên cứu toàn bộ (còn gọi là mạng lưới hoàn chỉnh), tất cả các mối quan hệ có quan

hệ xác định, hoặc các mạng cá nhân, các mối quan hệ mà mọi người quy định có,
chẳng hạn như "cộng đồng cá nhân của họ ". Một số phân tích xu hướng phân biệt
phân tích mạng xã hội:
Không có giả định rằng các nhóm là những khối xây dựng của xã hội: tiếp cận
được mở ra để nghiên cứu ít bị giới hạn hệ thống xã hội, từ nonlocal cộng đồng để liên
kết giữa các trang web .
7


Thay vì điều trị cá nhân (người, tổ chức, quốc gia) là đơn vị riêng biệt của phân
tích, nó tập trung vào cách cấu trúc của mối quan hệ ảnh hưởng đến cá nhân và các
mối quan hệ của họ.
Trái ngược với phân tích mà cho rằng xã hội hoá thành các chỉ tiêu xác định hành
vi, mạng lưới phân tích vẻ để xem mức độ mà các cấu trúc và thành phần của mối quan
hệ ảnh hưởng đến chỉ tiêu.
Hình dạng của một mạng xã hội sẽ giúp xác định tính hữu dụng của một mạng lưới
cho các cá nhân của mình. Nhỏ hơn, chặt chẽ hơn mạng có thể được ít hữu ích cho các
thành viên của họ hơn so với các mạng với nhiều kết nối lỏng lẻo cho các cá nhân bên
ngoài mạng chính. Mạng cởi mở hơn, có quan hệ nhiều và các kết nối xã hội, có nhiều
khả năng để giới thiệu những ý tưởng mới và cơ hội cho các thành viên của họ hơn so
với các mạng khép lại với nhiều mối quan hệ dự phòng. Nói cách khác, một nhóm
bạn, những người chỉ làm việc với nhau đã cùng chia sẻ những kiến thức và cơ hội.
Một nhóm các cá nhân với các kết nối đến thế giới xã hội khác có thể có truy cập vào
một phạm vi rộng hơn của thông tin. Nó là tốt hơn cho sự thành công cá nhân để có
các kết nối đến một loạt các mạng kết nối nhiều hơn là trong một mạng đơn. Tương tự
như vậy, cá nhân, tập thể dục có thể ảnh hưởng hoặc làm môi giới trong các mạng xã
hội của họ bằng cách cầu nối hai mạng mà không phải trực tiếp liên kết (được gọi là
làm đầy lỗ cấu trúc).
Sức mạnh của phân tích mạng xã hội bắt nguồn từ sự khác biệt của nó từ truyền
thống nghiên cứu khoa học xã hội, mà cho rằng đó là thuộc tính của vật chất diễn viên,

cho dù họ có thân thiện hay không thân thiện, thông minh hay ngu ngốc, vv, mà cá
nhân. Phân tích mạng xã hội tạo ra một cái nhìn khác, các thuộc tính của các cá nhân
ít quan trọng hơn mối quan hệ và quan hệ của họ với các diễn viên khác trong hệ
thống. Phương pháp này hóa ra là hữu ích cho việc giải thích nhiều hiện tượng trong
thế giới thực, nhưng lá phòng ít hơn cho cơ quan cá nhân, khả năng cho các cá nhân
gây ảnh hưởng đến thành công của họ, bởi vì rất nhiều của nó nằm bên trong cấu trúc
mạng của họ.
Mạng xã hội cũng đã được sử dụng để kiểm tra xem các tổ chức tương tác với
nhau, mô tả các kết nối nhiều thức liên kết với nhau điều hành, cũng như các hiệp hội
và các kết nối giữa người lao động cá nhân tại các tổ chức khác nhau. Ví dụ, trong các
tổ chức quyền lực thường đi kèm nhiều hơn từ mức độ mà một cá nhân trong một
mạng là trung tâm của mối quan hệ nhiều hơn so với tiêu đề công việc thực tế. Mạng
xã hội cũng đóng một vai trò quan trọng trong tuyển dụng, trong kinh doanh thành
công, và hiệu suất công việc. Networks cung cấp cách cho các công ty để thu thập
thông tin, ngăn chặn cạnh tranh, và thông đồng trong giá thiết hoặc chính sách

8


V.

Biện pháp trong phân tích mạng xã hội

Phân tích mạng xã hội là đo lường, đánh giá mối quan hệ giữa các cá nhân, nhóm
hay những tổ chức. Các nút trong mạng là những cá nhân hay nhóm người, còn các
đường liên kết để chỉ mối quan hệ giữa các cá nhân, nhóm người và tổ chức với nhau.
Phân tích mạng xã hội dựa trên phân tích trực quan và toán học trong mối quan hệ giữa
con người với nhau.
Để hiểu được mạng xã hội, chúng ta phải đánh giá vị trí của các thành phần trong
mạng. Phân tích mạng là tìm ra mức độ trung tâm của một nút. Điều này cho chúng ta

một cái nhìn tổng quan về vai trò khác nhau của các tác nhân tham gia vào mạng xã
hội. Tác nhân nào người kết nối, tác nhân nào là lãnh đạo, tác nhân nào là cầu nối, tác
nhân nào có ảnh hưởng lớn trong một mạng xã hội, tác nhân nào là tác nhân ngoại
biên(ít ảnh hưởng tới mạng)

Hãy xem xét mạng xã hội trên, 2 nút được kết nối với nhau nếu họ thường xuyên
nói chuyện với nhau hay tương tác với nhau theo một cách thức nào đó. Andre thường
liên lạc với Carol nhưng không liên lạc với Ike, vì thế giữa Andre và Carol có một
đường liên kết trực tiếp, không có liên kết trực tiếp giữa Andre và Ike.

9


Có 3 cách đo lường mức độ trung tâm của tác nhân trong mạng xã hội.
1. Degree Centrality

Những người nghiên cứu mạng xã hội đo lường hoạt động một nút trong mạng
bằng cách xem xét số lượng kết nối trực tiếp mà nút đó có. Trong mạng xã hội trên,
Diane có nhều kết nối trực tiếp nhất, cô ấy là mốt thành viên tích cực của mạng. Trong
mạng xã hội, những cá nhân hay tổ chức có nhiều kết nối thì càng có nhiều sức ảnh
hưởng. Nhưng đôi lúc chỉ số Degree cũng chưa phản ảnh được mức độ quan trọng của
một nút trong mạng. Ví dụ trong mạng Xã hội trên Diane có nhiều kết nối nhất, nhưng
nếu xem xét kỹ, chúng ta có thể nhận ra rằng cô ấy kết nối tới những người mà nhưng
người này đêu kết nối với nhau. Điều này co nghĩa là, họ chung một tổ chức xã
hội(người thân, bạn bè …). Dù không có Diane thì nhưng người này vẫn có thể liên lạc
được với nhau. Vì vậy để xét mức độ quan trọng của một nút trong mạng xã hội, chúng
ta cần kiểm tra thêm chỉ số betweennes.
Cho đồ thị G: = (V,E) với n đỉnh, chỉ số degree centrality CD(v) cho đỉnh v là:

Công thức dạng chuẩn:


2. Betweenness Centrality

Mức độ mà một nút nằm giữa các nút khác trong mạng. Biện pháp này có tính đến
các kết nối của các nút láng giềng của nút, cho một giá trị cao hơn cho các nút khác.
Biện pháp này phản ánh số lượng người một người là kết nối gián tiếp thông qua liên
kết trực tiếp của họ.
Trong khi Diane có nhiều kết nối chặt, Heather có ít kết nối hơn. Nhưng Heather lại
nắm giữ một vai trò quan trọng trong mạng xã hội này, cô ấy có một vị trí đặc biệt
trong mạng, là cầu nối giữa trong mạng, thông qua Heather, Ike và Jane mới có thể
tương tác với các thành viên còn lại trong mạng xã hội trên. Nếu không có Heather thi
Ike và Jane sẽ bị tách biệt ra khỏi mạng xã hội, không thể liên lạc được với nhưng
người khác trong mạng. Một nút có chỉ số “betweenness” cao sẽ có ảnh hưởng lớn và
có thể tác động đến toàn mạng xã hội.

Cho đồ thị G: = (V,E) với n đỉnh, chỉ số betweenness CB(v) cho đỉnh v được tính như
sau:
10


1. Cho mỗi cặp đỉnh (s,t), tính tất cả các đường đi ngắn nhất của chúng.
2. Với mỗi cặp đỉnh (s,t), xem xét tất cả các đường đi ngắn nhất đi qua đỉnh v.
3. Cộng tất cả các đường đi ngắn nhất này lại và chia cho tổng số các đường đi ngắn
nhất giữa các cặp đỉnh (s,t).

Dạng chuẩn

Lưu ý: nên triển khai công thức này sang dạng tổng

3. Closeness Centrality


Mức độ một cá nhân là gần tất cả các cá nhân khác trong một mạng (trực tiếp hoặc
gián tiếp). Nó phản ánh khả năng truy cập thông tin thông qua truyền thông chính thức
của các thành viên mạng lưới. Như vậy, sự gần gũi là nghịch đảo của tổng các khoảng
cách ngắn nhất giữa mỗi cá nhân và mọi người khác trong mạng.Con đường ngắn nhất
cũng có thể được gọi là "khoảng cách đo đạc".
Fernando và Garth có ít kết nối hơn Diane, nhưng với những kết nối gián tiếp và
trực tiếp của họ, cho phép Fernando và Grath liên lạc với tất các các thành viên còn lại
nhanh hơn những người khác. Họ có đường đi ngắn nhất đến những người khác trong
mạng, họ ở gần những người khác. Tóm lại nhưng thông tin lan truyền torng mạng xã

11


hội này sẽ thường xuyên đi qua Fernando và Garth, 2 người này thường xuyên giám
sát, nắm bắt được thông tin lan truyền trong mạng xã hội trên.
Cho đồ thị G: = (V,E) với n đỉnh, chỉ số closeness CC(v) cho đỉnh v được tính như
sau: nghịch đảo của tổng chiều dài các đường đi ngắn nhất từ v đến các đỉnh khác,
nghịch đảo là 1 hình thức tính ra giá trị tốt nhất cũng chính là giá trị lớn nhất.

Ngoài ra còn được tính bằng công thức sau

Công thức dạng chuẩn:

12


PHẦN II: Đồ Thị và lưu trữ đồ thị trong cơ sở dữ liệu quan hệ
I.


Khái niệm đồ thị

Đồ thị là một tập các đối tượng, được gọi là các nút hay đỉnh, một số nút được kết
nối bởi các liên kết, được gọi là các cạnh. Mỗi nút có thể có một tên, ví dụ một tên
người hay tổ chức nếu các nút đại diện cho con người hay tổ chức. Mỗi cạnh đi từ một
nút đến một nút khác biểu diễn mối quan hệ tương tác giữa các nút với nhau.
Đồ thị G = (V, E), trong đó:
•
•

V là tập hợp các đỉnh (vertex)
E ⊆ V × V là tập hợp các cạnh (edge).

Đồ thị vô hướng

Đồ thị vô hướng hoặc đồ thị G:=(V, E), trong đó
•

V, tập các đỉnh hoặc nút,

•

E, tập các cặp không thứ tự chứa các đỉnh phân biệt, được gọi là cạnh. Hai đỉnh
thuộc một cạnh được gọi là các đỉnh đầu cuối của cạnh đó.

Trong nhiều tài liệu, tập các cạnh bao gồm cả các cặp đỉnh không phân biệt, các
cạnh này được gọi là các khuyên. V (và E) thường là các tập hữu hạn, phần lớn các kết
quả nghiên cứu đã biết không đúng (hoặc khác) khi áp dụng cho đồ thị vô hạn (infinite
graph) vì nhiều luận cứ không dùng được trong trường hợp vô hạn.
Đồ thị có hướng


Đồ thị có hướng G là một cặp có thứ tự G:=(V, A), trong đó
•

V, tập các đỉnh hoặc nút,
13


•

A, tập các cặp có thứ tự chứa các đỉnh, được gọi là các cạnh có hướng hoặc
cung. Một cạnh e = (x, y) được coi là có hướng từ x tới y; x được gọi là điểm
đầu/gốc và y được gọi là điểm cuối/ngọn của cạnh.

Các cách biểu diễn đồ thị trong máy tính
1. Biểu diễn đồ thị bằng ma trận kề

Giả sử G = (V, E) là một đồ thị. Ta đánh số các đỉnh của đồ thị bằng các số tự
nhiên: 1, 2, ... , n. Xây dựng ma trận vuông biểu diễn đồ thị như sau:
Ma trận vuông An x n được gọi là ma trận kề của đồ thị G nếu:
∀ i, j ∈ V, A[i,j] = d , trong đó d là số cạnh nối đỉnh i với đỉnh j trong G.
2. Biểu diễn đồ thị bằng các danh sách kề

Với mỗi đỉnh của đồ thị ta xây dựng một danh sách móc nối chứa các đỉnh kề với đỉnh
này. Danh sách này được gọi là danh sách kề. Một đồ thị được biểu diễn bằng một
mảng các danh sách kề.
II.

Các thuật toán duyệt đồ thị


Duyệt theo chiều sâu (Depth-First Search)
Trong phương pháp này mỗi lần duyệt một đỉnh ta duyệt đến tận cùng mỗi nhánh rồi
mới chuyển sang duyệt nhánh khác. Giả sử G = (V, E) là một đồ thị vô hướng.
Ta bắt đầu duyệt từ một đỉnh x0 nào đó của đồ thị. Sau đó chọn x là đỉnh kề nào đó
của x0 và lặp lại quá trình duyệt đối với đỉnh x.
Giả sử ta đang xét đỉnh x. Nếu trong số các đỉnh kề với x, ta tìm được đỉnh y chưa
được duyệt thì ta sẽ xét đỉnh này và bắt đầu từ đó ta tiếp tục quá trình duyệt.
Duyệt theo chiều rộng (Breadth-First Search)
Trong phương pháp này việc duyệt có tính chất “lan rộng”. Một đỉnh được duyệt xong
ngay sau khi ta đã xét hết tất cả các đỉnh kề với nó. Đỉnh được xét càng sớm thì sớm
trở thành duyệt xong.
Tìm đường đi ngắn nhất
Xác định tuần tự các đỉnh có khoảng cách đến u0 từ nhỏ đến lớn.
1. Trước tiên đỉnh có khoảng cách nhỏ nhất đến u0 là u0.
2. Trong V\{u0} tìm đỉnh có khoảng cách đến u0 nhỏ nhất (đỉnh này phải là một trong
các đỉnh kề với u0) giả sử đó là u1
14


3. Trong V\{u0,u1} tìm đỉnh có khoảng cách đến u0 nhỏ nhất(đỉnh này phải là một
trong các đỉnh kề với u0 hoặc u1 )giả sử đó là u2
4. Tiếp tục như trên cho đến bao giờ tìm được khoảng cách từ u0 đến mọi đỉnh .
Nếu G có n đỉnh thì: 0 = d(u0,u0) < d(u0,u1) <= d(u0,u2) <= … <= d(u0,un-1)
Tìm cây khung ngắn nhất
Cho G là đồ thị có trọng số. Cây khung T của G được gọi là cây khung ngắn nhất (cây
tối đại ngắn nhất,cây bao trùm ngắn nhất, cây khung tối tiểu) nếu nó là cây khung của
G mà có trọng lượng nhỏ nhất.
Thuật toán Kruscal tìm cây khung ngắn nhất:
Cho G là đồ thị liên thông, có trọng số, n đỉnh.
Bước 1: Trước hết chọn cạnh ngắn nhất e1 trong các cạnhcủa G.

Bước 2: Khi đã chọn k cạnh e1,e2,…ek thì chọn tiếp cạnh ek+1 ngắn nhất trong các
cạnh còn lạicủa G sao cho không tạo thành chu trình với các cạnh đã chọn trước.
Bước3. Chọn đủ n-1 cạnh thì dừng.
Thuật toán Prim tìm cây khung ngắn nhất
Bước1.Chọn1 đỉnh bất kỳ v1 để có cây T1 chỉ gồm 1 đỉnh
Bước2.Khi đãchọn cây Tk thì chọntiếp cây Tk+1 =Tk ∪ ek+1. Trong đó ek+1 là cạnh
ngắn nhất trong các cạnh có một đầu mút thuộcTk và đầu mút kia không thuộcTk
Bước3.Chọn được cây Tn thì dừng.

15


III.

Cài đặt đồ thị trong cơ sở dữ liệu quan hệ

Ta sử dụng một đồ thị vô hướng không có trọng số để biễu diễn một mạng xã hội
đơn giản với các chức năng thêm một người dùng mới vào mạng xã hội, xóa người
dùng, cho phép người dùng kết bạn, tìm bạn, xóa bạn, tìm bạn có chung sở thích …
1.

Thiết kế bảng nodes và edges

Tạo 2 bảng Nodes và Edges để tổ chức một mạng xã hội trong cơ sở dữ liệu quan
hệ. Trong đó Nodes gồm các field Id là mã node và Name là Nhãn node.
Bảng Edges là danh sách các cạnh của đồ thị chứa thông tin liên kết giữa các node
với nhau. Field FromNode là node bắt đầu và ToNode là node đích.
Các phương thức thao tác trên các node trong mạng xã hội.
o


InsertNode: Thêm 1 người gia nhập mạng xã hội

DeleteNode: Xóa người dùng ra khỏi mạng xã hội, đồng thời xóa tất các các
liên kết đến người dùng này.
o GetAllNodes: lấy tất cả các node trong mạng
o Lấy các cạnh liên kết đến Node (tìm kiếm bạn, hay tổ chức, mà người này
tương tác)
o

Các phương thức thao tác trên các cạnh trong mạng xã hội.
Thêm Edge(tạo mốt liên kết giữa một Node với một node khác trong mạng xã
hội( ví dụ như kết bạn)
o Xóa Edge (Cắt đường liên kết, giữa 2 Node trong mạng xã hội)
o Sửa Edge(đối với đồ thị có trọng số)
o

16


2. Thiết kế bảng person chứa thông tin mở rộng cho node

Để mô phỏng một mạng Xã hội gồm những tác nhân là con người tương tắc lẫn
nhau, ta tạo thêm bảng Person để lưu trữ thông tin cá nhân của một node, quan hệ 1-1
với bảng node. Bảng person gồm các trường Id, Name: họ tên , Age tuổi, Email, Tel:
điện thoại.
3. Thiết kế bảng Favorites chứa danh mục sở thích của người dùng

Thiết kế bảng Favorites lưu trữ danh mục sở thích của person gồm 2 trường Id và
Name: tên sở thích.


17


4. Thiết kế bảng ImageProfile lưu trữ hình ảnh cá nhân của người dùng

Chúng ta thiết kế thêm bảng ImageProfile để lưu trử hình ảnh cá nhân của một Person,
và Bảng Favorites quang hệ nhiều nhiều với bảng Person đê lưu danh sách sở thích của
một person.

18


5. Cài đặt các thủ tục thao tác trên đồ thị
a. Thuật toán BFS

Viết procedure store cài đặt BFS trên SQL với tham số đầu vào là start node, và end
node, nếu end node = null thì tìm tất cả các node còn lại
+ Bắt đầu từ nút đầu vào, thám hiểm các nút làng giềng của nó, và đánh dấu là đã
viếng thăm.
+ Với mỗi nút gần nhất, thám hiểm những nút láng giếng chưa viếng thăm.
+ Tiếp tục lặp lại bước 2 cho đên khi nào toàn viếng thăm toàn bộ đồ thị hoặc viếng
thăm xong điểm cần đến (trường hợp endnode khác null).
Thông thường cài đặt BFS trong các ngôn ngữ lập trình sử dụng hàng đợi để xử ý
các nút viếng thăm tiếp theo. Tuy nhiên Sql là ngôn ngữ dựa trên tập hợp, trong Sql
chúng ta sử dụng một bảng chứa các nút được thám hiểm và kết tự nhiên với bảng
Node để thám hiểm các node còn lại. (Sử dụng kỹ thuật CTE, đệ quy trogn SQL).
b. Thuật toán Dijkstra

Do chúng ta tổ chức mạng xã hội là đồ thị không trọng số, xem như tất c ả các trọng
số là 1.

Bước 1. Gán T:=X và gắn các nhãn: Dodai[i]=0;
Nhan[k]=-1, ∀k∈X.

Dodai[k]= +∞?, ∀k∈X\{i};

Bước 2. Nếu j∉T thì dừng và giá trị Dodai[j] chính là độ dài đường đi ngắn nhất từ i
đến j và Nhan[j] là đỉnh nằm ngay trước j trên đường đi đó.
Bước 3. Chọn đỉnh v∈T sao cho Dodai[v] nhỏ nhất và gán T := T\{v}.
Bước 4. Với mọi đỉnh k∈T và có cạnh nối từ v đến k, nếu Dodai[k]>Dodai[v]+Lvk thì
Dodai[k]= Dodai[v]+Lvk và Nhan[k]=v
Cuối với mọi. Trở về bước 2.
Chú ý: Khi thuật toán dừng, nếu Dodai[j]= +∞? Thì không tồn tại đường đi từ i đến j,
nếu ngược lại thì Dodai[j] là độ dài đường đi ngắn nhất
Trong SQL, cũng có thể cài đặt thuật toán này sử dụng kỹ thuật đệ quy
CTE(common table expressions).
Dijkstra làm việc giống cơ chế của BFS, bắt đầu từ một nút và thám hiểm đồ thị.
Chúng ta sử dụng bảng tạm để lưu lại những nút nào chúng ta đã đi qua với khoảng
cách đã được tính. Thuật toán lặp lại đến khi viếng thăm hét các nút.

19


Khi kết thúc thuật toán, kết quả trả về là một bảng nút có chứa khoảng cách , và
đánh dấu lại nút trước đó( là nút mà chúng ta đã đi qua, trước khi đến nút hiện hành).
Vậy chúng ta sẽ có một đường liên kết giữa các nút. Sau đó chúng ta dùng CTE để lấy
đường dẫn này.
IV. Cài đặt ứng dụng Demo
1. Chức năng vẽ đồ thị:

mạng xã hội


Sử dụng hàm thư viện Microsoft Automatic Graph Layout để vẽ đồ thị. MSAGL
là một componet .Net được phát triển tại viện nghiên cứu Microsoft do Lev
Nachmanson phụ trách.
Các thành phần trong MSAGL:
Layout engine (Microsoft.MSAGL.dll): đầy là thành phần quan trọng gồm các
hàm giúp chúng ta thao tác trực quan với dồ thị.
o Drawing module (Microsoft.MSAGL.Drawing.dll): chứa những xử lý về thuộc
tính màu sắc của đồ thị, kiểu dòng… No cũng chữa những định nghĩa về lớp
Node, Edge, và Graph.
o Viewer control (Microsoft.MSAGL.GraphViewerGDIGraph.dll): chứa các
thành phần để hiển thị đồ thị lên giao diện.
o

20


2. Chức năng thêm node, xóa node trực quan trên giao diện

Chức năng này cho phép người dùng thêm một node vào đồ thị, xóa cạnh, hay xóa
một node trong đồ thị.
Muốn thêm một node ta click chuột phải chọn “Thêm người dùng”.
Muốn xóa một node ta click chuột phải vào node đó, chọn “xóa” (khi xóa node thi
các cạnh nối đến node này đêu bị xóa theo)

21


3. Chức năng phân tích mạng xã hội, tìm key player
a. Degree Centrality


Cho đồ thị G: = (V,E) với n đỉnh, chỉ số degree centrality CD(v) cho đỉnh v là:

Công thức dạng chuẩn:

22


b. Closeness Centrality

công thức dạng chuẩn

Ngoài ra còn được tính bằng công thức sau

23


4. Chức năng xem và chỉnh sửa thông tin cá nhân của person trong mạng xã hội

Click phải chuột trên một node, chọn “xem thông tin cá nhân”. Sẽ bật lên hộp thoại
thông tin cá nhân của node và thông tin với bạn bè, danh sách nhưng người có chung
bạn với node được chọn.

số bạn chung

5. Chức năng kết bạn và tìm những người có chung bạn bè với mình
Hộp thoại thông tin bạn bè này con cung cấp chức năng kết bạn, và xóa bạn. Ngoài
ra trong mã xã hội, chúng ta có nhu cầu tìm những nút có liên quan mạnh, nhưng
không kết nối trực tiếp, nói cách khác, chúng ta muốn tìm xem có bao nhiêu nút kết nối
được chia sẻ giữa 2 nút bất kỳ, tức là có bao nhiêu nút trung gian trực tiếp được chia sẻ

giữa 2 nút. Một ví dụ là trong mạng xã hội chúng ta được gợi ý kết bạn với những
người, những người đó là có chung một hay nhiều người bạn với chúng ta.
Thuật toán này đơn giản chỉ là ta bắt đầu từ nút hiện hành duyệt qua các nút bạn
của nút hiện hành, rồi tiếp tục duyệt tới nút bạn của các nút chúng ta vừa tìm được, với
độ dài của đường đi là 2, chúng ta sẽ tìm được những người có liên quan mạnh(những
24


người có quan hệ trực tiếp với bạn bè chúng ta, và có thể chúng ta quen những người
này).
6. Chức năng tìm kiếm những người có chung sở thích
Ngoài ra chúng ta còn có những tiêu chí khác để tìm những người có liên quan
mạnh với một người bằng cách dựa trên tiêu chí: chung sở thích, đã đi học cùng một
trường, làm việc tại cùng một công ty, thuộc cùng một nhóm lợi ích...
Form thông tin cá nhân bên dưới thê hiện thông tin chi tiết của một người torgn
mạng xã hội, bao gồm các thông tin cơ bản như họ tên, email, tuổi và điện thoại. Đồng
thời cũng có chức năng upload ảnh cá nhân, cho phép người dùng có thể đưa hình ảnh
của mình vào thông tin cá nhân.

Trên form thông tin cá nhân này cũng lưu trữ sở thích của người dùng, đồng thời
cung cấp thêm tính năng tìm bạn theo sở thích, hỗ trợ người dùng tìm ra trong mạng xã
hội nhừng người nào có cùng sở thích với mình

25