ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
T
NGUYỄN THÀNH ĐỆ
CHUYÊN ĐỀ CÔNG NGHỆ TRI THỨC
Đề Tài:
HỆ THỐNG TÌM KIẾM ĐỒ THỊ THÔNG MINH
TRÊN FACEBOOK
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: CH1101073
Niên Khóa: Khóa 6
KHÓA LUẬN TỐT NGHIỆP THẠC SĨ
Báo cáo chuyên đề Công Nghệ Tri Thức
Thaùng 10 – 2013
ĐẠI HỌC QUỐC GIA THÀNH PHỐ HỒ CHÍ MINH
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
T
NGUYỄN THÀNH ĐỆ
CHUYÊN ĐỀ CÔNG NGHỆ TRI THỨC
Đề Tài:
HỆ THỐNG TÌM KIẾM ĐỒ THỊ THÔNG MINH
TRÊN FACEBOOK
Chuyên ngành: KHOA HỌC MÁY TÍNH
Mã số: CH1101073
Niên Khóa: Khóa 6
GVPT: GS.TSKH. Hoàng Văn Kiếm
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 2
Báo cáo chuyên đề Công Nghệ Tri Thức
Thaùng 10 – 2013
Mục Lục
CHUYÊN CÔNG NGH TRI TH CĐỀ Ệ Ứ 1

Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 3
Báo cáo chuyên đề Công Nghệ Tri Thức
Hình 4. Quan hệ có hướng và kiểu quan hệ trang 18
Hình 5. Thuộc tính của cơ sở dữ liệu đồ thị trang 19
Hình 6. Đường đi(Paths) trang 20
Hình 7. Ví dụ truy vấn đồ thị trang 21
Hình 8. Kết quả tìm kiếm trang 22
Hình 9. Tìm nới yêu thích trang 23
Hình 10. Tìm người dựa trên sở thích trang 24
Hình 11. Nhóm và danh sách bạn bè trang 28
Hình 12. Dựa vào Tag trang 28
Hình 13. Mẫu tìm kiếm trên Facebook trang 31
Hình 14. Thiết lập tìm kiếm đồ thị trang 36
Hình 15. Thiết lập chó nhóm Basic Info và Work and Education trang 37
Hình 16. Mở rộng của việc tìm kiếm trang 37
Hình 17. Mở rộng của việc tìm kiếm 2 trang 37
Hình 18. Kết quả truy vấn 1 trang 39
Hình 19. Kết quả truy vấn 2 trang 40
Hình 20. Kết quả truy vấn 3 trang 41
Hình 21. Kết quả truy vấn 4 trang 42
Hình 22. Kết quả truy vấn 5 trang 43
Hình 23. Kết quả truy vấn 6 trang 44
Hình 24. Kết quả truy vấn 7 trang 45
Hình 25. Kết quả truy vấn 8 trang 46
Hình 26. Kết quả truy vấn 9 trang 46
Hình 27. Kết quả truy vấn 10 trang 47
Hình 28. Quảng cáo trên Graph Search trang 48
Hình 29. Quảng cáo trên Graph Search 2 trang 51
Hình 30. Mô hình cấu hình TAO của Facebook trang 52
Hình 31. Các mối quan hệ của Nút trang 53

1.1. Giới thiệu và đặt vấn đề
Tìm kiếm ngữ nghĩa là một khái niệm mà đã được biết đến từ lâu trong tin
học, nhưng các ứng dụng của nó đến bây giờ mới thật sự thấy rõ. Mặc dù các hệ
thống tìm kiếm lớn như Google, Yahoo, Bing, Ask.com rất hiệu quả trong việc
giúp người dùng thu thập thông tin như chúng vẫn thực sự chưa hiệu quả với việc
tìm kiếm theo ngữ nghĩa. Ví dụ, chúng ta nhập một đoạn tìm kiếm sau vào google
“bố của thủ tướng Nguyễn Tấn Dũng”, ta nhận được một danh sách kết quả
khoảng 2.810.000 kết quả liên quan đến thông tin tìm kiếm này. Chúng ta cũng
nhận kết quả tương tự khi sử Yahoo, Bing, Ask.com để tìm kiếm cụm từ trên. Như
vậy kết quả này quả thật là thiếu chính xác và không hiệu quả, làm hoang mang
tâm lý người tìm kiếm thống tin, việc thu thập thông tin vô cùng khó khăn.
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 6
Báo cáo chuyên đề Công Nghệ Tri Thức
Tìm kiếm theo ngữ nghĩa giúp cho chúng ta có một kết quả chính xác hơn
rất nhiều. Và kỹ thuật này đã được áp dụng trong Facebook, mà Facebook gọi đó
là Graph Search.
Graph Search là gì? Là một công nghệ của Facebook để tìm kiếm người
và vật mà được kết nối trong mạng xã hội.
Mục đích của Graph Search trên Facebook:
- Tìm người mà có cùng sở thích với bạn
- Khám phá thế giới qua ảnh
- Khám phá nhà hàng,shop, cafes, âm nhạc và nhiều hơn thế nữa
Để thực hiện được việc tìm kiếm theo ngữ nghĩa trên xã hội. Thì chúng ta
phải có một kỹ thuật lưu trữ dữ liệu hợp lý, dữ liệu đó phải có kết nối với nhau và
đảm bảo được hiệu năng và hiệu quả của việc tìm kiếm. Như chúng ta đã biết các
kỹ thuật lưu trư như lưu trữ bằng tập tin, bằng cơ sở dữ liệu quan hệ, bằng cơ sở
dữ liệu không quan hệ(NOSQL), lưu trữ dạng Key-Value[6] và bây giờ là lưu trữ
dạng đồ thị. Việc lưu trữ các dữ liệu có kết nối chỉ hiệu quả nhất khi chúng ta chọn
cơ sở dữ liệu đồ thị để lưu trữ. Và lúc này, các thuật toán đồ thị chúng ta rất dễ
dàng để áp dụng, việc tìm kiếm ngữ nghĩa trên dữ liệu có kết nối có tính hiệu quả

nói riêng và hệ thống tìm kiếm ngữ nghĩa nói chung.
CHƯƠNG 2. CÁC THUẬT TOÁN ĐỒ THỊ VÀ CƠ SỞ DỮ LIỆU ĐỒ THỊ
NEO4J
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 8
Báo cáo chuyên đề Công Nghệ Tri Thức
Trong chương này em sẽ giới thiệu một vài thuật toán tìm kiếm đồ thị[7]
mà em được biết và ứng dụng của thuật toán đồ thị trong cơ sở dữ liệu đồ thị
Neo4j. Mặc dù, Facebook cũng đã công bố các kỹ thuật quản lý dữ liệu đồ thị trên
mạng xã hội của công ty này nhưng Neo4j là một cơ sở dữ liệu tiêu biểu cho cơ sở
dữ liệu đồ thị.
2.1. Tìm kiếm theo chiều sâu
Tư tưởng chính là Giả sử chúng ta đang xét trên đồ thị G(V,E). Từ một đỉnh
u

€V hiện thời nào đó ta sẽ thăm tới đỉnh kề v của u và quá trình được lặp lại đối
với đỉnh v. ở bước tổng quát, giả sử hiện tại đang xét đỉnh u
0
, chúng ta sẽ có hai
khả năng sẽ xảy ra:
- Nếu như tồn tại một đỉnh v
0
kề với u
0
mà chưa được thăm thì đỉnh v
0
đó sẽ trở
thành đỉnh đã thăm và quá trình tìm kiếm lại bắt đầu từ đỉnh v
0
đó.
- Ngược lại, nếu mọi đỉnh kề với u

thông với u sẽ được viếng thăm. Thủ tục Visit(u) là thao tác trên đỉnh u trong từng
bài toán đặt ra cụ thể.
2.2. Thuật toán tìm kiếm theo chiều rộng
Thuật toán này thực ra là sự cải biến về thứ tự duyệt đỉnh trên đồ thị của
tìm kiếm theo chiều sâu bằng cách thay vì dùng một STACK thì ta lại dùng một
hàng đợi QUEUE để kết nạp đỉnh được thăm. Như vậy, đỉnh được thăm càng sớm
sẽ càng sớm trở thành duyệt xong (cơ chế First In First Out - Vào trước ra trước).
Thủ tục được mô tả dưới đây:
Procedure BFS(u);
Begin
Queue:=Empty
Kết nạp u vào Queue;
Daxet[u]:=True;
While Queue<>Empty do
Begin
Lấy v từ Queue;
Visit(v);
For w

Kề(v) do
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 10
Báo cáo chuyên đề Công Nghệ Tri Thức
If not Daxet[w] then
Begin
Kết nạp w vào Queue;
Daxet[w]:=True;
End;
End;
End;
Ta có thủ tục tìm kiếm theo chiều rộng là:

2.2: Chuyển x từ Open sang Close.
2.3 : if (x là mục tiêu) then
Dừng và kết luận: tìm được lời giải.
2.4: Xét các đỉnh kế y của x, xử lý như sau:
TH1: y là đỉnh mới (không thuộc Open và không
thuộc Close)
g(y) = g(x) + w(x,y);
pre(y) = x;
Lưu lại y trong Open;
TH2: y thuộc Open
If g(x) + w(x,y) < g(y) then
{
g(y) := g(x) + w(x,y);
pre(y) := x;
}
}
2.4. Thuật toán A*
Cho một đồ thị có trọng số dương: G = (V, E), ký hiệu trọng số là w.a, z V.
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 12
Báo cáo chuyên đề Công Nghệ Tri Thức
Tìm đường đi ngắn nhất từ a đến z.
Biết thêm thông tin sau đây: từ mỗi đỉnh x, có có một ước lượng “khoảng cách”
từ x đến mục tiêu. Ký hiệu giá trị này là h(x).
Các ký hiệu:
• Với x thuộc V, đặt g(x) = độ dài lộ trình được tìm thấy từ a đến x,
h(x): như giả thiết,
f(x) = g(x) + h(x)
• Open = tập hợp các đỉnh được duyệt tới nhưng chưa xét các đỉnh kế.
• Close = tập các đỉnh đã được duyệt và cũng đã xét các đỉnh kế của nó.
• Pre(x) = đỉnh kế trước x trên lộ trình đến x.

nhưng vì phạm vi của bài chuyên đề nên em chỉ trình bày một vài thuật toán mà
được áp dụng cho phần cơ sở dữ liệu đồ thị ở phần sau.
2.5. Cơ sở dữ liệu đồ thị Neo4j
Mạng xã hội đồ thị của Facebook – Cơ sở dữ liệu nằm bên dưới máy tìm
kiếm đồ thị(Graph Search) đã được công bố. Nó chỉ là một trong những cơ sở dữ
liệu đồ thị(Graph databases) được sử dụng cho các dữ liệu lớn, phức tạp, dữ liệu
được kết nối. Neo4j là một cơ sở dữ liệu khác dẫn đầu về cơ sở dữ liệu đồ thị, mã
nguồn mở và được nhiều hãng sử dụng như Cisco, Adobe, Squidoo, Intuit.
Neo4j không phải là công nghệ mà các nhà phát triển của Facebook dùng
cho sản phẩm của họ, nhưng nó đại diện cho một cơ sở dữ liệu đồ thị mới để xử lý
các dữ liệu kết nối phức tạp hơn cả cơ sở dữ liệu Nosql. Một vài mã nguồn cho cơ
sở dữ liệu đồ thị như InfiniteGraph, InfoGrid, OrientDB, BigData, DEX,
HyperGraphDB, OQGraph and ArangoDB.
Cơ sở dữ liệu đồ thị là một loại của cơ sở dữ liệu NOSQL mà nó có thêm
phần xử lý cho dữ liệu có kết nối. Dữ liệu có kết nối là phổ biến trong mạng xã
hội, mạng lưới logistics(dành cho các gói định tuyến), đồ thị giao dịch tài chính(để
phát hiện gian lận), mạng viễn thông, tối ưu hóa quảng cáo, máy giới thiệu, tin
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 14
Báo cáo chuyên đề Công Nghệ Tri Thức
sinh học, và rất nhiều lĩnh vực khác nữa. Nên việc lựa chọn Cơ sỡ dữ liệu đồ thị
cho các ứng dụng có liên quan đến lĩnh vực trên là hợp lý và mang lại hiểu quả
cao.
2.5.1. Giới thiệu về Cơ sở dữ liệu đồ thị Neo4j
Cơ sở dữ liệu đồ thị Neo4j là một cơ sở dữ liệu mã nguồn mở được phát
triển bởi(Neo4j) dựa trên ý tưởng lý thuyết đồ thị. Nó được thiết kế dựa trên cơ sở
dữ liệu quan hệ. Tối ưu hóa bằng cấu trúc dữ liệu đồ thị thay vì là dữ liệu bảng.
Khi làm việc với Neo4j, cơ sở dữ liệu ứng dụng của bạn sẽ được biểu diễn
bằng đồ thị, như đồ thị dưới đây:
Hình 1. Cơ sở dữ liệu Neo4j
Nền tảng của mô hình đồ thị là nút(nodes) và các mối quan hệ(relationships) của

Người được follow Quan hệ follows đi vào, độ sâu 1
Người block Quan hệ block đi ra, độ sâu 1
Người được block Quan hệ block đi vào, độ sâu 1
- Thuộc tính(properties): Cả hai nút(nodes) và mối quan hệ(relationship) đều có
thể có thuộc tính(properties). Thuộc tính là khóa-giá trị mà khóa là chuỗi. Giá
trị thuộc tính có thể là giá trị của một kiểu dữ liệu nào đó hoặc có thể làm
mảng của một kiểu dữ liệu nào đó. Ví dụ giá trị string, int[] là giá trị hợp lệ của
thuộc tính. Chú ý rằng NULL không là giá trị hợp lệ của giá trị thuộc tính.
Nulls có thể được thay thế là sự vắng mặt của khóa.
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 17
Báo cáo chuyên đề Công Nghệ Tri Thức
Hình 5. Thuộc tính của cơ sở dữ liệu đồ thị
- Đường đi(Paths): Một đường kết nối có thể qua nhiều nút với việc kết nối qua
các mối quan hệ, thông thường là một truy vấn hay kết quả phép duyệt
Hình 6. Đường đi(Paths).
Đường đi ngắn nhất có độ dài bằng 0, là độ thì có một nút.
2.5.2. Duyệt đồ thị trên Neo4j
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 18
Báo cáo chuyên đề Công Nghệ Tri Thức
Duyệt đồ thị có nghĩa là viến thăm các nút, những mối quan hệ theo một số
luật. Hầu như các trường hợp chỉ là một đồ thị con được viến thăm. Như bạn đã
biết mối quan tâm lớn nhất của đồ thị là nút và mối quan hệ của nút.
Neo4j cung cấp cho chúng ta API mà cho phép chúng ta duyệt đồ thị theo
nhiều phép duyệt khác nhau. Chúng ta có thể duyệt theo chiều rộng, duyệt theo
chiều sâu, A* và Dijkstra.
Neo4j cung cấp một framework cho duyệt đồ thị. Ngoài ra cũng có lựa
chọn khác ở Neo4j cho phép duyệt đồ thị hoặc truy vấn đồ thị bằng ngôn ngữ truy
vấn Cypher và Grelin.
2.5.3. Một vài ví dụ sử dụng truy vấn với Neo4j
Ở phần này em xin trình bày một vài ví dụ để làm rõ các truy vấn đến cơ sở dữ

Ví dụ 3: Lấy tất cả thành viên của tất cả các nhóm
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 20
Báo cáo chuyên đề Công Nghệ Tri Thức
Trong Cypher:
START refNode=node(16)
MATCH refNode<-[:ROOT]->root, p=root<-[PART_OF*0 ]-()<-
[:MEMBER_OF]-user
RETURN user.name, min(length(p))
ORDER BY min(length(p)), user.name
Kết quả:
Ví dụ 4. Cho đồ thị sau:
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 21
Báo cáo chuyên đề Công Nghệ Tri Thức
Hình 7. Ví dụ về truy vấn đồ thị
- Để tìm kiếm bạn của bạn của Joe.
Câu truy vấn như sau:
START joe=node:node_auto_index(name = "Joe")
MATCH joe-[:knows*2 2]-friend_of_friend
WHERE not(joe-[:knows]-friend_of_friend)
RETURN friend_of_friend.name, COUNT(*)
ORDER BY COUNT(*) DESC, friend_of_friend.name
Kết quả trả về như sau:
Hệ Thống Tìm Kiếm Đồ Thị Thông Minh Facebook – Nguyễn Thành Đệ – CH1101073 Trang 22
Báo cáo chuyên đề Công Nghệ Tri Thức
Hình 8. Kết quả tìm kiếm
- Tìm nơi ưu thích
Ví dụ cho đồ thị sau:
Hình 9. Tìm nơi yêu thích
Tìm kiếm những nơi mà người dùng thích:
 Xác định có ai thích nơi x không.