Tìm Hiểu Một Số Giải Thuật Tìm Kiếm Cộng Đồng Trong Mạng Xã Hội Và Áp Dụng Vào Bài Toán Khai Phá Quy Trình

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ HỒNG HẠNH

TÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM CỘNG ĐỒNG

TRONG MẠNG XÃ HỘI VÀ ÁP DỤNG VÀO BÀI TOÁN

KHAI PHÁ QUY TRÌNH

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

Hà Nội - 2016

ĐẠI HỌC QUỐC GIA HÀ NỘI

TRƢỜNG ĐẠI HỌC CÔNG NGHỆ

NGUYỄN THỊ HỒNG HẠNH

TÌM HIỂU MỘT SỐ GIẢI THUẬT TÌM KIẾM CỘNG ĐỒNG

TRONG MẠNG XÃ HỘI VÀ ÁP DỤNG VÀO BÀI TOÁN

KHAI PHÁ QUY TRÌNH

Ngành: Công nghệ thông tin

Chuyên ngành: Hệ thống thông tin

Mã số: 60.48.01.04

LUẬN VĂN THẠC SỸ CÔNG NGHỆ THÔNG TIN

NGƢỜI HƢỚNG DẪN KHOA HỌC: PGS.TS Nguyễn Trí Thành

Hà Nội - 2016

i

LỜI CAM ĐOAN

Tác giả xin cam đoan kết quả đạt đƣợc trong luận văn là sản phẩm của

riêng cá nhân Tác giả và đƣợc sự hƣớng dẫn khoa học của PGS.TS Nguyễn Trí

Thành, không sao chép lại của ngƣời khác. Trong toàn bộ nội dung của luận văn,

những điều trình bày của cá nhân hoặc đƣợc tổng hợp của nhiều nguồn tài liệu.

Tất cả các tài liệu tham khảo đều có xuất xứ rõ ràng và đƣợc trích dẫn hợp pháp.

Tác giả xin hoàn toàn chịu trách nhiệm và chịu mọi hình thức kỷ luật theo

quy định cho lời cam đoan của mình.

Hà Nội, ngày tháng năm 2016

HỌC VIÊN

Nguyễn Thị Hồng Hạnh

ii

LỜI CẢM ƠN

Lời đầu tiên, em xin gửi lời cảm ơn chân thành và sâu sắc nhất tới thầy

PGS.TS Nguyễn Trí Thành, ngƣời thầy đã trực tiếp hƣớng dẫn tận tình và đóng

góp những ý kiến quý báu cho em trong suốt quá trình thực hiện luận văn tốt

nghiệp này.

Em xin gửi lời cảm ơn đến các thầy cô giáo Trƣờng Đại học Công nghệ -

- Đại học Quốc gia Hà Nội, đã tận tâm truyền đạt những kiến thức quý báu làm

nền tảng cho em trong công việc và cuộc sống. Qua đây, em cũng xin cảm ơn

sinh viên Nguyễn Duy Kiên – Trƣờng Đại học Công nghệ Hà Nội đã hỗ trợ và

giúp đỡ em về mặt kỹ thuật.

Cuối cùng, em xin đƣợc cảm ơn cha mẹ, ngƣời thân, ban bè và đồng

nghiệp của em tại Sở Nông nghiệp và PTNT tỉnh Hƣng Yên, những ngƣời đã

luôn bên em, khuyến khích và động viên em trong cuộc sống và học tập.

HỌC VIÊN

Nguyễn Thị Hồng Hạnh

iii

MỤC LỤC

DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT ....................................................... v

DANH MỤC CÁC BẢNG................................................................................... vi

MỞ ĐẦU............................................................................................................... 7

CHƢƠNG 1.TỔNG QUAN VỀ KHAI PHÁ QUY TRÌNH ................................ 9

1.1 Khai phá quy trình........................................................................................ 9

1.1.1 Sự cần thiết của KPQT ........................................................................ 10

1.1.2 Mục tiêu của KPQT ............................................................................. 11

1.1.3 Mô hình quy trình và nhật ký sự kiện.................................................. 11

1.1.4 Các bài toán KPQT.............................................................................. 12

1.1.5 Các khía cạnh của KPQT..................................................................... 13

1.1.6 Các ứng dụng của KPQT..................................................................... 14

1.1.7 Một số thách thức đối với lĩnh vực KPQT .......................................... 14

1.2 Khía cạnh tổ chức trong KPQT.................................................................. 15

1.3 Bài toán toán khai phá khía cạnh tổ chức .................................................. 18

1.3.1 Trong thực tế........................................................................................ 18

1.3.2 Trong luận văn ..................................................................................... 18

1.4 Ý nghĩa của luận văn.................................................................................. 20

1.4.1 Về mặt khoa học .................................................................................. 20

1.4.2 Về mặt thực tiễn................................................................................... 21

CHƢƠNG 2. CÁC GIẢI THUẬT TÌM KIẾM CỘNG TRONG MXH............. 22

2.1 Cộng đồng mạng xã hội ............................................................................. 22

2.1.1 Nguyên nhân hình thành cộng đồng MXH.......................................... 22

2.1.2 Các loại cộng đồng trong MXH........................................................... 23

2.1.3 Các loại cấu trúc cộng đồng................................................................. 23

2.2 Các phƣơng pháp phát hiện cộng đồng...................................................... 24

2.2.1 Ứng dụng.............................................................................................. 24

2.2.2 Các loại giải thuật ................................................................................ 25

2.3 Các giải thuật tìm kiếm cộng đồng chồng chéo......................................... 28

2.4 Lựa chọn giải thuật tìm kiếm..................................................................... 30