..

TRANG BÌA
BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CƠNG NGHỆ TP. HCM
---------------------------

PHAN HỒNG TRUNG

TÌM TẦM ẢNH HƯỞNG CỦA BÀI BÁO
KHOA HỌC TRONG MẠNG TRÍCH DẪN
LUẬN VĂN THẠC SĨ
Chuyên ngành: Cơng Nghệ Thơng Tin
Mã số ngành: 60480201

TP. HỒ CHÍ MINH, tháng 08 năm 2017


BÌA TRONG
HEADER

BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC CƠNG NGHỆ TP. HCM
---------------------------

PHAN HỒNG TRUNG

TÌM TẦM ẢNH HƯỞNG CỦA BÀI BÁO
KHOA HỌC TRONG MẠNG TRÍCH DẪN
LUẬN VĂN THẠC SĨ
Chuyên ngành: Công Nghệ Thông Tin

Mã số ngành: 60480201

CÁN BỘ HƯỚNG DẪN KHOA HỌC: PGS.TS.ĐỖ PHÚC

TP. HỒ CHÍ MINH, tháng 08 năm 2017


HỘI ĐỒNG ĐÁNH GIÁ LUẬN VĂN
CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ TP. HCM

Cán bộ hướng dẫn khoa học: PGS.TS.ĐỖ PHÚC

Luận văn Thạc sĩ được bảo vệ tại Trường Đại học Công nghệ TP.HCM
ngày 19 tháng 11 năm 2017.
Thành phần Hội đồng đánh giá Luận văn Thạc sĩ gồm:
Họ và tên

Chức danh Hội đồng

1

PGS.TS.Vũ Đức Lung

Chủ tịch

2

PGS.TS.Võ Đình Bảy


Phản biện 1

3

TS.Vũ Thanh Hiền

Phản biện 2

4

TS.Cao Tùng Anh

Ủy viên

5

TS.Văn Thiên Hoàng

Ủy viên, Thư ký

TT

Chủ tịch Hội đồng đánh giá LV

PGS.TS.Vũ Đức Lung


TRƯỜNG ĐH CƠNG NGHỆ TP.HCM

CỘNG HỊA XÃ HỘI CHỦ NGHĨA VIỆT NAM


VIỆN ĐÀO TẠO SAU ĐẠI HỌC

Độc lập – Tự do – Hạnh phúc
TP. HCM, ngày 18 tháng 08 năm 2017

NHIỆM VỤ LUẬN VĂN THẠC SĨ
Họ tên học viên: .............. PHAN HỒNG TRUNG

Giới tính: ........................ Nam

Ngày, tháng, năm sinh: .........................01/03/1968

Nơi sinh: .............. Đồng Tháp

Chuyên ngành: ................... Công Nghệ Thông Tin

MSHV: .............. 1541860051

I- Tên đề tài:

TÌM TẦM ẢNH HƯỞNG CỦA BÀI BÁO KHOA HỌC
TRONG MẠNG TRÍCH DẪN
II- Nhiệm vụ và nội dung:
1. Cài đặt OrientDB, Scala, Apache Spark, IntelliJ IDEA.
2. Thu thập, tổ chức và lưu trữ dữ liệu đồ thị trong OrientDB.
3. Chuyển từ đồ thị trong OrientDB thành đồ thị trong GraphX để phân tích.
4. Tìm tầm ảnh hưởng của một bài báo.
5. Tìm bài báo có tầm ảnh hưởng nhiều nhất.
6. Xác định độ lan tỏa của một bài báo theo thời gian.

7. Biểu diễn trực quan đồ thị.
8. Mở rộng hệ thống trên Apache Spark Cluster gồm nhiều máy tính.
III- Ngày giao nhiệm vụ:

15/03/2017

IV- Ngày hồn thành nhiệm vụ:

18/08/2017

V- Cán bộ hướng dẫn:

PGS.TS. Đỗ Phúc

CÁN BỘ HƯỚNG DẪN

KHOA QUẢN LÝ CHUYÊN NGÀNH

(Họ tên và chữ ký)

(Họ tên và chữ ký)

PGS.TS.Đỗ Phúc


-i-

LỜI CAM ĐOAN

Tơi xin cam đoan đây là cơng trình nghiên cứu của riêng tôi. Các số liệu, kết quả

nêu trong Luận văn là trung thực và chưa từng được ai cơng bố trong bất kỳ cơng trình
nào khác.
Tơi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận văn này đã được
cảm ơn và các thông tin trích dẫn trong Luận văn đã được chỉ rõ nguồn gốc.

Học viên thực hiện Luận văn
(Ký và ghi rõ họ tên)

Phan Hồng Trung


- ii -

LỜI CÁM ƠN

Xin gửi lời cảm ơn chân thành đến Thầy, PGS.TS. Đỗ Phúc, đã cho tôi một đề tài
rất thú vị và đã nhiệt tình hướng dẫn, cung cấp tài liệu, kiến thức, gợi ý, góp ý rất hữu
ích trong q trình làm Luận văn.
Xin chân thành cảm ơn các Thầy:
 PGS.TS. Võ Đình Bảy
 PGS.TS. Quản Thành Thơ
 PGS.TS. Lê Hoàng Thái
 TS. Nguyễn Sinh Kế
 TS. Nguyễn An Khương
 TS. Đặng Trường Sơn
 TS. Trần Đức Khánh
đã cung cấp cho tơi nhiều tri thức q báu trong suốt khóa học, nhờ đó tơi có thể
hồn thành tốt đề tài Luận văn.
Xin chân thành cảm ơn nhà trường, các phòng, khoa, đặc biệt là Phòng Đào Tạo
Sau Đại Học đã nhiệt tình giúp đỡ và hỗ trợ trong suốt khóa học.

Kính chúc Thầy, Cơ nhiều sức khỏe.
TP. Hồ Chí Minh, ngày 18 tháng 08 năm 2017
Phan Hồng Trung


- iii -

TÓM TẮT
Big Data và Graph Databases là hai nội dung nghiên cứu mới, hấp dẫn và đầy
tiềm năng. Tuy nhiên, qua thông tin trên Internet, tại Việt Nam việc ứng dụng và khai
thác Big Data cũng như Graph Databases còn khá mới mẻ và chưa đúng với tiềm năng
và tầm quan trọng của nó. Nhiều doanh nghiệp Việt Nam đang nắm trong tay nguồn Big
Data nhưng chưa biết cách khai thác đúng mức. Vì vậy chọn một đề tài để có thể nghiên
cứu và ứng dụng được cả hai kỹ thuật trên là điều cấp thiết. Đó là lý do tơi chọn đề tài
“TÌM TẦM ẢNH HƯỞNG CỦA BÀI BÁO KHOA HỌC TRONG MẠNG
TRÍCH DẪN”. Với đề tài này tơi có thể:
 Dùng kỹ thuật Graph Databases để tổ chức, lưu trữ và truy vấn mạng
trích dẫn do bản chất của mạng trích dẫn là một đồ thị.
 Dùng kỹ thuật Big Data để phân tích và xử lý mạng trích dẫn do mạng
trích dẫn thực nghiệm trong đề tài này khá lớn.
Mục tiêu của đề tài là nghiên cứu, ứng dụng Big Data và Graph Databases; góp
phần để nước nhà bắt kịp xu hướng của thế giới trong việc khai thác, ứng dụng chúng
trong thực tiễn. Cụ thể, trong đề tài này tôi xây dựng hệ thống Citation Network
Explorer (CNE) để tìm tầm ảnh hưởng của bài báo khoa học trong mạng trích dẫn. Hệ
thống CNE bao gồm các chức năng chính sau:
1. Tải cơ sở dữ liệu đồ thị vào hệ thống xử lý Big Data.
2. Biểu diễn trực quan đồ thị.
3. Tìm tầm ảnh hưởng của một bài báo.
4. Tìm bài báo có tầm ảnh hưởng nhiều nhất.
5. Tìm thành phần liên thơng chứa một bài báo.

6. Xác định độ lan tỏa của một bài báo theo thời gian.
Trong đề tài này, tôi triển khai những kỹ thuật mới như sau:
 Sử dụng cơ sở dữ liệu đồ thị, cụ thể là OrientDB, để tổ chức, lưu trữ
mạng trích dẫn các bài báo khoa học.


- iv  Dùng nền tảng Apache Spark để khai thác Big Data, cụ thể là sử dụng
GraphX để phân tích mạng trích dẫn.
 Dùng ngơn ngữ lập trình Scala kết hợp với Play Framework để xây dựng
ứng dụng.
 Dùng thư viện VisJs để biểu diễn trực quan mạng trích dẫn.
Ngồi ra, tơi cũng trình bày kết quả thực nghiệm một số chức năng chính của hệ
thống CNE để đo đạc thời gian xử lý của các chức năng trên những đồ thị với qui mô
khác nhau.
Cuối cùng là phần đánh giá kết quả thực hiện đề tài so với dự định ban đầu cũng
như những kinh nghiệm thu thập được. Ngồi ra trong phần này tơi cũng đề nghị một số
định hướng phát triển, mở rộng đề tài.


-v-

ABSTRACT
Big Data and Graph Databases are two new, exciting and potential research
topics. However, through information on the Internet, in Vietnam the application and
exploitation of Big Data as well as Graph Databases is still quite new and not true with
its potential and importance. Many Vietnamese enterprises are in the hands of Big Data
but do not know how to exploit properly. Therefore, it is imperative to choose a topic to
study and apply both techniques. That's why I chose the topic “FIND INFLUENCE
OF SCIENTIFIC PAPERS IN A CITATION NETWORK”. With this topic I can:
 Using Graph Databases to organize, store, and query citation networks

because the nature of citation networks is a graph.
 Using Big Data technology to analyze and process citation networks
because of the citation network experiment in this thesis quite large.
The objectives of the research are to study, apply Big Data and graph database;
Contribute to the country to catch up with the trend of the world in exploiting, applying
them in practice. Specifically, on this topic I built the Citation Network Explorer
(CNE) application to find the influence of scientific papers in the large citation network.
The CNE application includes the following functions:
1. Load graph databases into the Big Data processing system.
2. Visualize graphs.
3. Find the influence of a paper.
4. Find the most influential paper.
5. Find the connected component that contains a paper.
6. Find the propagation of a paper over time.
In this topic, I am deploying the following new techniques:
 Using the graph database, namely the OrientDB, to organize, store
citation networks of scientific papers.
 Using Apache Spark to exploit Big Data, specifically using GraphX to


- vi analyze citation networks.
 Using Scala programming language in combination with Play Framework
to build applications.
 Using VisJs library to visualize the citation network.
In addition, I also present experimental results of some of the major functions of
the CNE system to measure the processing time of functions on graphs with different
scales.
Finally, that is the evaluation of the results of the project against the original plan
as well as the experience gained. In addition, in this section I also propose some
orientations of expanding the topic.



- vii -

MỤC LỤC
LỜI CAM ĐOAN..................................................................................................................i
LỜI CÁM ƠN .......................................................................................................................ii
TÓM TẮT ........................................................................................................................... iii
ABSTRACT ......................................................................................................................... v
MỤC LỤC ..........................................................................................................................vii
DANH MỤC CÁC TỪ VIẾT TẮT ...................................................................................xi
DANH MỤC CÁC BẢNG ................................................................................................xii
DANH MỤC CÁC HÌNH ............................................................................................... xiii
DANH MỤC CÁC BIỂU ĐỒ ...........................................................................................xv
DANH MỤC CÁC THUẬT TOÁN ................................................................................xvi
CHƯƠNG 1:TỔNG QUAN ................................................................................................ 1
1.1. Đặt vấn đề và lý do chọn đề tài................................................................................. 1
1.2. Mục tiêu của đề tài .................................................................................................... 4
1.2.1. Mục tiêu tổng quát ............................................................................................. 4
1.2.2. Mục tiêu cụ thể ................................................................................................... 5
1.3. Nội dung nghiên cứu ................................................................................................. 5
1.4. Các phương pháp nghiên cứu ................................................................................... 6
1.4.1. Phương pháp tổng luận ...................................................................................... 6
1.4.2. Phương pháp so sánh ......................................................................................... 6
1.4.3. Phương pháp nghiên cứu tính khả thi ............................................................... 6
1.4.4. Phương pháp nghiên cứu mơ phỏng ................................................................. 6
1.4.5. Phương pháp phân tích và thiết kế thuật tốn................................................... 6
1.5. Đóng góp của đề tài................................................................................................... 7
1.6. Các cơng cụ và cơng trình nghiên cứu tiêu biểu có liên quan đến đề tài................ 7
1.6.1. Các cơng cụ phân tích mạng trích dẫn .............................................................. 7

1.6.2. Các cơng trình nghiên cứu liên quan ................................................................ 9
CHƯƠNG 2: CƠ SỞ LÝ THUYẾT .................................................................................11
2.1. Một số định nghĩa liên quan đến đề tài ..................................................................11


- viii 2.1.1. Mạng trích dẫn .................................................................................................11
2.1.2. Mạng trích dẫn các bài báo khoa học..............................................................12
2.1.3. Tầm ảnh hưởng ................................................................................................13
2.2. Cơ sở dữ liệu đồ thị và OrientDB ...........................................................................17
2.2.1. Khái quát về cơ sở dữ liệu đồ thị.....................................................................17
2.2.2. Cơ sở dữ liệu đồ thị là gì?................................................................................17
2.2.3. Sự phát triển của cơ sở dữ liệu đồ thị..............................................................18
2.2.4. Khái quát về OrientDB ....................................................................................20
2.2.5. Lý do chọn OrientDB ......................................................................................21
2.3. Big Data ...................................................................................................................25
2.3.1. Khái quát về Big Data......................................................................................25
2.3.2. Đặc trưng của Big Data ...................................................................................25
2.3.3. Ứng dụng của Big Data ...................................................................................27
2.3.4. Tác động của Big Data ....................................................................................28
2.4. Hadoop .....................................................................................................................28
2.5. Apache Spark...........................................................................................................30
2.5.1. Khái quát về Apache Spark .............................................................................30
2.5.2. Sự phát triển của Apache Spark ......................................................................31
2.5.3. Tính năng của Apache Spark ..........................................................................31
2.5.4. Các thành phần của Apache Spark..................................................................31
2.6. Ngơn ngữ lập trình Scala ........................................................................................33
2.6.1. Khái qt về ngơn ngữ Scala...........................................................................33
2.6.2. Các tính năng của ngơn ngữ Scala ..................................................................33
2.7. Web MVC với Play Framework ............................................................................35
2.7.1. Các nền tảng xây dựng ứng dụng web bằng Scala.........................................35

2.7.2. Play Framework ...............................................................................................35
2.8. Biểu diễn trực quan đồ thị với VisJs ......................................................................36
2.8.1. Khái quát về các thư viện biểu diễn trực quan đồ thị .....................................36
2.8.2. VisJs Framework .............................................................................................36


- ix CHƯƠNG 3: PHÂN TÍCH & THIẾT KẾ HỆ HỐNG ....................................................38
3.1. Yêu cầu của hệ thống ..............................................................................................38
3.2. Sơ đồ kiến trúc hệ thống CNE ................................................................................38
3.3. Thiết kế cơ sở dữ liệu ..............................................................................................39
3.3.1. Thu thập dữ liệu ...............................................................................................39
3.3.2. Thiết kế cơ sở dữ liệu đồ thị trong OrientDB .................................................41
3.3.3. Chương trình đọc text file và chuyển thành cơ sở dữ liệu đồ thị...................42
3.3.4. Tiền xử lý dữ liệu .............................................................................................46
3.3.5. Đồ thị kết quả ...................................................................................................47
3.4. Thiết kế chức năng ..................................................................................................47
3.4.1. Các sơ đồ UML của hệ thống CNE ................................................................48
3.4.2. Các thuật toán quan trọng ................................................................................63
CHƯƠNG 4:HIỆN THỰC & THỰC NGHIỆM .............................................................76
4.1. Hiện thực..................................................................................................................76
4.1.1. Giao diện chính ................................................................................................76
4.1.2. Giao diện của chức năng “Find papers” .........................................................78
4.1.3. Giao diện của chức năng “Visualize the whole graph” .................................79
4.1.4. Giao diện của chức năng “Find the propagation of a paper over time” ........79
4.2. Thực nghiệm............................................................................................................80
4.2.1. Kiến trúc của hệ thống thực nghiệm ...............................................................80
4.2.2. Cài đặt hệ thống ...............................................................................................81
4.2.3. Cách chạy hệ thống thực nghiệm ....................................................................81
4.2.4. Kết quả thực nghiệm........................................................................................82
CHƯƠNG 5: KẾT LUẬN & HƯỚNG PHÁT TRIỂN ...................................................87

5.1. Những thách thức khi thực hiện đề tài ...................................................................87
5.2. Kinh nghiệm thu thập được khi thực hiện đề tài....................................................88
5.3. Ưu nhược điểm của hệ thống Citation Network Explorer ....................................89
5.3.1. Nhược điểm của hệ thống................................................................................89
5.3.2. Ưu điểm của hệ thống......................................................................................89


-x5.4. Hướng phát triển trong tương lai ............................................................................90
TÀI LIỆU THAM KHẢO .................................................................................................91
PHỤ LỤC ...............................................................................................................................


- xi -

DANH MỤC CÁC TỪ VIẾT TẮT
Viết Tắt Thuật Ngữ
ACID

Tiếng Anh

Tiếng Việt

Atomicity, Consistency,
Isolation, Durability

Bốn thuộc tính đặc trưng của một
transaction
Mạng đánh giá ấn phẩm khoa học

Bibliometric

networks
CNE

Citation Network Explorer

Chương trình khám phá Mạng Trích
Dẫn

Db

Database

Cơ sở dữ liệu

DBMS

Database Management
System

Hệ quản trị cơ sở dữ liệu

GDBMS

Graph DBMS

Hệ quản trị cơ sở dữ liệu đồ thị
Đồ thị

Graph
Graph DB


Graph Database

Cơ sở dữ liệu đồ thị

RDBMS

Relational DBMS

Hệ quản trị cơ sở dữ liệu quan hệ

Replication

Nhân bản: sao chép dữ liệu lên
nhiều server

Sharding

Phân mảnh dữ liệu: chia nhỏ dữ liệu
thành nhiều phần, mỗi phần có thể
lưu trên một hoặc nhiều server

Transaction

Là tập hợp các thao tác được xem là
một đơn vị công việc không thể chia
nhỏ


- xii -


DANH MỤC CÁC BẢNG
Bảng 1.1 – So sánh hiệu quả khi tìm kiếm bạn bè trong RDBMS và Neo4J .................... 4
Bảng 2.1 – Bảng xếp hạng 24 hệ quản trị cơ sở dữ liệu đồ thị trong tháng 04/2017 ......19
Bảng 2.2 – So sánh OrientDB và Neo4j ............................................................................21
Bảng 3.1 – Chi tiết các lớp Paper và Reference. ...............................................................41
Bảng 3.2 – Danh mục các hàm của chương trình đọc text file.........................................42
Bảng 3.3 – Bảng mô tả các chức năng trong sơ đồ UseCase. ..........................................49
Bảng 3.4 – Danh sách các thuật toán quan trọng. .............................................................63
Bảng 4.1 – Các chức năng của menu Tasks. .....................................................................77


- xiii -

DANH MỤC CÁC HÌNH
Hình 1.1 – Mối quan hệ bạn bè trên mạng xã hội Facebook. ............................................. 2
Hình 1.2 – Sự phát triển của các loại cơ sở dữ liệu từ tháng 01/2013 – 05/2015 .............. 3
Hình 2.1 – Biểu diễn mối quan hệ trích dẫn: di trích dẫn dj..............................................11
Hình 2.2 – Ví dụ về mạng trích dẫn. ..................................................................................12
Hình 2.3 – Ví dụ tầm ảnh hưởng của bài báo trong mạng trích dẫn. ...............................14
Hình 2.4 – Đồ thị trước và sau khi thực hiện thuật tốn PageRank. ................................15
Hình 2.5 – Chất lượng của quan hệ tham khảo .................................................................16
Hình 2.6 – Cơ sở dữ liệu đồ thị ..........................................................................................18
Hình 2.7 – Các tổ chức tiêu biểu đang sử dụng OrientDB ...............................................20
Hình 2.8 – Phân mảnh class Client thành 3 cluster. ..........................................................23
Hình 2.9 – Năm đặc trưng của Big Data ...........................................................................25
Hình 2.10 – Các thành phần của Hadoop ..........................................................................29
Hình 2.11 – Các thành phần của Apache Spark ................................................................32
Hình 3.1 – Sơ đồ kiến trúc hệ thống CNE. ........................................................................39
Hình 3.2 – Cấu hình máy chạy chương trình tạo cơ sở dữ liệu đồ thị. ............................46

Hình 3.3 – Sơ đồ UseCase..................................................................................................48
Hình 3.4 – Sơ đồ Class của hệ thống CNE........................................................................52
Hình 3.5 – Sơ đồ Squence của chức năng loadGraph.......................................................54
Hình 3.6 – Sơ đồ Squence của chức năng visualizeGraph. ..............................................55
Hình 3.7 – Sơ đồ Squence của chức năng calculatePageRank.........................................56
Hình 3.8 – Sơ đồ Squence của chức năng getInformation. ..............................................57
Hình 3.9 – Sơ đồ Squence của chức năng getMaxRanks. ................................................57
Hình 3.10 – Sơ đồ Squence của chức năng findConnectedComponents.........................58
Hình 3.11 – Sơ đồ Squence của chức năng findPropagation. ..........................................59
Hình 3.12 – Sơ đồ Package. ...............................................................................................60
Hình 3.13 – Sơ đồ Component...........................................................................................61
Hình 3.14 – Sơ đồ Deployment. ........................................................................................62
Hình 3.15 – Thuật tốn Find Connected Component với id = 10, chưa vào vòng lặp. ..68


- xiv Hình 3.16 – Thuật tốn Find Connected Component với id = 10, xong lần lặp 1. .........68
Hình 3.17 – Thuật toán Find Connected Component với id = 10, xong lần lặp 2. .........69
Hình 3.18 – Thuật tốn Find Connected Component với id = 10, xong lần lặp 3. .........69
Hình 3.19 – Thuật tốn Find Propagation theo hướng In với id = 10, chưa vào vịng lặp.
.................................................................................................................................71
Hình 3.20 – Thuật toán Find Propagation theo hướng In với id = 10, xong lần lặp 1. ...71
Hình 3.21 – Thuật tốn Find Propagation theo hướng In với id = 10, xong lần lặp 2. ...72
Hình 3.22 – Thuật tốn Find Propagation theo hướng In với id = 10, xong lần lặp 3. ...72
Hình 4.1 – Giao diện chính của hệ thống CNE. ................................................................76
Hình 4.2 – Giao diện của chức năng “Find papers”..........................................................78
Hình 4.3 – Giao diện của chức năng “Visualize the whole graph”. .................................78
Hình 4.4 – Giao diện của chức năng “Find the propagation of a paper over time”. .......79
Hình 4.5 – Sơ đồ kiến trúc của hệ thống thực nghiệm......................................................81



- xv -

DANH MỤC CÁC BIỂU ĐỒ
Biểu đồ 3.1 – Thời gian chuyển đổi nội dung text file thành cơ sở dữ liệu đồ thị. .........45
Biểu đồ 4.1 – Thời gian xử lý của chức năng loadGraph. ................................................83
Biểu đồ 4.2 – Thời gian xử lý của chức năng calculatePageRank. ..................................84
Biểu đồ 4.3 – Thời gian xử lý của chức năng findConnectedComponent. ......................84
Biểu đồ 4.4 – Thời gian xử lý của chức năng findPropagation. .......................................85
Biểu đồ 4.5 – Thời gian xử lý của chức năng visualizeGraph..........................................86


- xvi -

DANH MỤC CÁC THUẬT TỐN
Thuật tốn 3.1 – Thuật toán của hàm prepareGraph(). .....................................................42
Thuật toán 3.2 – Thuật toán của hàm importNodes(). ......................................................43
Thuật toán 3.3 – Thuật toán của hàm createEdges(). ........................................................44
Thuật toán 3.4 – Thuật toán của hàm main().....................................................................44
Thuật toán 3.5 – Thuật toán Pregel. ...................................................................................66
Thuật toán 3.6 – Thuật toán Find Connected Component. ...............................................67
Thuật toán 3.7 – Thuật toán Find Propagation. .................................................................70
Thuật toán 3.8 – Thuật toán Load Graph...........................................................................73
Thuật toán 3.9 – Thuật toán Traverse Graph.....................................................................74
Thuật toán 3.10 – Thuật toán Visualize Graph của lớp TasksController.........................75
Thuật toán 3.11 – Thuật toán Visualize Graph của lớp Index. .........................................75


-1-

CHƯƠNG 1:


TỔNG QUAN
1.1. Đặt vấn đề và lý do chọn đề tài
Chúng ta đang ở trong thời đại bùng nổ thông tin. Dữ liệu đang gia tăng rất lớn
trong các lĩnh vực khác nhau. Đơn cử về Facebook, cứ 60 giây thì có 510.000 nhận xét
được đăng, 293.000 trạng thái được cập nhật và 136.000 ảnh được tải lên
(zephoria.com, 2017).
Dưới sự gia tăng bùng nổ của dữ liệu toàn cầu, thuật ngữ Big Data được sử dụng
chủ yếu để mô tả tập hợp dữ liệu có kích thước rất lớn, khả năng phát triển nhanh,
không thể thu thập, quản lý và xử lý bởi các công cụ phần mềm/phần cứng truyền
thống. So với các tập dữ liệu truyền thống, Big Data thường bao gồm các khối dữ liệu
phi cấu trúc1 cần phân tích tức thời. Big Data mang lại những cơ hội để khám phá
những giá trị mới, giúp chúng ta hiểu biết sâu sắc về các giá trị tiềm ẩn của dữ liệu và
cũng phải gánh chịu những thách thức mới. Ví dụ, làm thế nào để tổ chức, quản lý và xử
lý Big Data hiệu quả.
Big Data là một lĩnh vực mới, đang phát triển và đầy tiềm năng. Theo báo cáo
mới nhất của tổ chức MarketsandMarkets, thị trường Big Data dự kiến sẽ tăng từ 28,65
tỷ USD trong năm 2016 lên 66,79 tỷ USD vào năm 2021, với tốc độ tăng trưởng hàng
năm (Compound Annual Growth Rate - CAGR) là 18,45% (marketsandmarkets.com,
2016).
Mặt khác, sự phát triển nhanh chóng của Internet, mạng xã hội, báo điện tử…
làm cho mối liên hệ giữa các thực thể dữ liệu trở nên phức tạp đến nổi khơng thể tổ
1

Có thể chia dữ liệu thành 3 loại:
1. Có cấu trúc: như cơ sở dữ liệu quan hệ.
2. Bán cấu trúc: như tài liệu XML, JSON.
3. Phi cấu trúc: như file văn bản, hình ảnh, âm thanh, video, …



-2chức hiệu quả trên các hệ cơ sở dữ liệu quan hệ (RDBMS) phổ biến hiện tại. Ví dụ, mối
quan hệ bạn bè trên mạng xã hội Facebook, như trong Hình 1.1, rất phức tạp và khơng
thể tổ chức hiệu quả trên các hệ cơ sở dữ liệu quan hệ. Để giải quyết thách thức của việc
tổ chức, lưu trữ và truy vấn những dữ liệu như vậy nhiều hệ quản trị cơ sở dữ liệu
NoSql (Not only Sql) ra đời (Eric Redmond, Jim R. Wilson, 2012). Các hệ quản trị cơ
sở dữ liệu NoSql được chia thành 4 loại:
1. Key-Value Stores. Ví dụ: Amazon DynamoDB, Voldemort, Tokyo.
2. Column Stores. Ví dụ: Bigtable, Hbase, Cassandra.
3. Document Databases. Ví dụ: CouchDB, MongoDB.
4. Graph Databases. Ví dụ: Neo4J, OrientDB.

Hình 1.1 – Mối quan hệ bạn bè trên mạng xã hội Facebook.
(Nguồn: />

-3Trong đó, loại Graph Databases – cơ sở dữ liệu đồ thị, chuyên dùng để tổ chức,
lưu trữ và truy vấn dữ liệu có dạng đồ thị, có tốc độ phổ biến nhanh nhất. Theo thống kê
của DB-Engines, đến tháng 01/2015, cơ sở dữ liệu quan hệ không tăng, các loại cơ sở
dữ liệu NoSql đều tăng, đặc biệt cơ sở dữ liệu đồ thị đã gia tăng độ phổ biến hơn 5 lần
kể từ tháng 01/2013 như trong Hình 1.2 (Andlinger, 2015).

Hình 1.2 – Sự phát triển của các loại cơ sở dữ liệu từ tháng 01/2013 – 05/2015
(Nguồn: />Các mối quan hệ phức tạp giữa các thực thể dữ liệu, như quan hệ bạn bè trên
Facebook, trước kia không thể xử lý hiệu quả trên loại cơ sở dữ liệu quan hệ thì nay tổ
chức dễ dàng và xử lý hiệu quả trên loại cơ sở dữ liệu đồ thị như Neo4J hoặc OrientDB.
Bảng 1.1 so sánh hiệu quả khi tìm kiếm bạn bè giữa RDBMS, hệ quản trị cơ sở dữ liệu
quan hệ, và Neo4J. Depth2 có nghĩa là tìm bạn của bạn, Depth3 có nghĩa là tìm bạn của
bạn của bạn… Trong các trường hợp, thời gian thực thi của Neo4J đều nhanh hơn
RDBMS. Đặc biệt, khi Depth = 5 thì RDBMS khơng thể hồn thành trong khi Neo4J
cho kết quả rất ấn tượng chỉ 2,132 giây!
Có thể nói, Big Data và Graph Databases là hai nội dung nghiên cứu mới, hấp

dẫn và đầy tiềm năng. Tuy nhiên, qua thông tin trên Internet, tại Việt Nam việc ứng


-4dụng và khai thác Big Data cũng như Graph Databases còn còn khá mới mẻ và chưa
đúng với tiềm năng và tầm quan trọng của nó. Nhiều doanh nghiệp Việt Nam đang nắm
trong tay nguồn Big Data nhưng chưa biết cách khai thác đúng mức. Vì vậy chọn một
đề tài để có thể nghiên cứu và ứng dụng được cả hai kỹ thuật trên là điều cấp thiết. Đó là
lý do tơi chọn đề tài “TÌM TẦM ẢNH HƯỞNG CỦA BÀI BÁO KHOA HỌC
TRONG MẠNG TRÍCH DẪN”2. Với đề tài này tơi có thể:
 Dùng kỹ thuật Graph Databases để tổ chức, lưu trữ và truy vấn mạng
trích dẫn do bản chất của mạng trích dẫn là một đồ thị.
 Dùng kỹ thuật Big Data để phân tích và xử lý mạng trích dẫn do mạng
trích dẫn thực nghiệm trong đề tài này khá lớn.
Bảng 1.1 – So sánh hiệu quả khi tìm kiếm bạn bè trong RDBMS và Neo4J
(Nguồn: />
RDBMS

Neo4J

execution time(s)

execution time(s)

2

0.016

0.01

~2,500


3

30.267

0.168

~110,000

4

1543.505

1.359

~600,000

5

Unfinished

2.132

~800,000

Depth

Records returned

1.2. Mục tiêu của đề tài

1.2.1. Mục tiêu tổng quát
Mục tiêu tổng quát của đề tài là nghiên cứu, ứng dụng Big Data và cơ sở dữ liệu
đồ thị để bắt kịp xu hướng của thế giới trong việc khai thác, ứng dụng chúng trong thực
tiễn.
2

Những khái niệm liên quan đến đề tài như: mạng trích dẫn, tầm ảnh hưởng... sẽ được trình bày chi tiết ở Chương 2.


-5-

1.2.2. Mục tiêu cụ thể
Mục tiêu cụ thể của đề tài là xây dựng hệ thống Citation Network Explorer
(CNE) để tìm tầm ảnh hưởng của bài báo khoa học trong mạng trích dẫn. Cụ thể, hệ
thống CNE bao gồm các chức năng sau:
1. Tải cơ sở dữ liệu đồ thị vào hệ thống xử lý Big Data.
2. Biểu diễn trực quan đồ thị.
3. Tính PageRank cho các đỉnh trên đồ thị.
4. Tìm tầm ảnh hưởng của một bài báo.
5. Tìm bài báo có tầm ảnh hưởng nhiều nhất.
6. Tìm thành phần liên thông chứa một bài báo.
7. Xác định độ lan tỏa của một bài báo theo thời gian.

1.3. Nội dung nghiên cứu
Để thực hiện đề tài, những nghiên cứu sau đây cần được thực hiện:
1. Nghiên cứu cách thu thập dữ liệu bài báo khoa học và xây dựng mạng trích
dẫn.
2. Nghiên cứu về mạng trích dẫn và các thuật toán xác định tầm ảnh hưởng của
bài báo trong mạng trích dẫn.
3. Nghiên cứu về cơ sở dữ liệu đồ thị, OrientDB và các nền tảng biểu diễn trực

quan đồ thị.
4. Nghiên cứu về Big Data, Apache Spark, GraphX, ngơn ngữ lập trình Scala.
5. Xây dựng hệ thống Citation Network Explorer để khai thác mạng trích dẫn
các bài báo khoa học.
6. Nghiên cứu cách triển khai hệ thống trên Apache Spark Cluster gồm nhiều
máy tính.