ĐẠ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

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

DANH MỤC KÝ HIỆU VÀ TỪ VIẾT TẮT
STT
I
1
2
3
4
5
6
II
1
2
3
4
5
6
7
8
9
10
11

Chữ viết tắt
Tiếng việt
CNTT
HTTT
KCTC
KPQT
MHQT
MXH

eXtensible Event Stream
EXtensible Markup Language


vi
DANH MỤC CÁC BẢNG
Bảng 2.1 So sánh các loại cấu trúc cộng đồng .................................................... 24
Bảng 2.2 Các phƣơng pháp tính khoảng cách hai cụm ....................................... 26
Bảng 3.1 Bảng mô tả các thuộc tính của một phần dữ liệu sự kiện .................... 36
Bảng 3.2 Thứ tự thực hiện nhiệm vụ của từng ngƣời trong mỗi trƣờng hợp ..... 40
Bảng 3.3 Ma trận 𝑀𝑕 mối quan hệ ..................................................................... 40
Bảng 3.4 Ma trận đỉnh kề 𝑀𝑎 ............................................................................. 41
Bảng 3.5 Danh sách đỉnh kề ................................................................................ 42
Bảng 3.6 Ma trận 𝑀𝑠 độ tƣơng tự ....................................................................... 43
Bảng 3.7 Tính mật độ các phân vùng tại ngƣỡng cắt t=1 ................................... 43
Bảng 3.8 Tính mật độ các phân vùng tại ngƣỡng cắt t=0.7(KN1)...................... 44
Bảng 3.9 Tính mật độ các phân vùng tại ngƣỡng cắt t=0.7(KN2)...................... 44
Bảng 3.10 Danh sách các cộng đồng đƣợc tìm thấy ........................................... 45
Bảng 4.1 Chi tiết chỉ số phần cứng và hệ điều hành ........................................... 46
Bảng 4.2 Thông tin phần mềm và tập dữ liệu đầu vào ....................................... 46
Bảng 4.3 Đánh giá kết quả chƣơng trình thực nghiệm ....................................... 48
Bảng 4.4 Đánh giá chất lƣợng các cộng đồng .................................................... 50
DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
Hình 1.1 Tổng quan về KPQT ............................................................................ 10
Hình 1.2 Quá trình phát hiện mô hình quy trình từ nhật ký sự kiện ................... 11
Hình 1.3 Các bài toán KPQT .............................................................................. 13
Hình 1.4 Các ứng dụng KPQT trong các lĩnh vực .............................................. 14
Hình 1.5 Mô hình tổ chức đƣợc phát hiện từ các nhật ký sự kiện ...................... 19
Hình 2.1 Các loại cấu trúc cộng đồng ................................................................. 24
Hình 2.2 Các phƣơng pháp phân cụm thứ bậc .................................................... 26

phát hiện ra mạng xã hội (MXH) giữa những phòng, đơn vị, cá nhân tham gia
vào quy trình kinh doanh từ nhật ký sự kiện. Việc phân tích và đánh giá những
mối quan hệ này giúp nhà quản lý có cái nhìn chính xác về các quy trình hiện có
trong tổ chức của họ. Trong mô hình MXH, các đỉnh đại diện cho phòng, đơn vị
hay con ngƣời, mối quan hệ giữa các đỉnh đƣợc biểu diễn dƣới dạng cạnh. Vấn
đề chồng chéo nhiệm vụ giữa những ngƣời tham gia vào quy trình là một thách
thức mang tính thời sự đối với các doanh nghiệp. Hậu quả của vấn đề này mang
lại thiệt hại về kinh tế và quy trình kinh doanh hoạt động kém thông suốt. Với
một doanh nghiệp quy mô lớn, mô hình MXH sẽ kích thƣớc lớn bao gồm nhiều
đỉnh và mật độ kết nối giữa các đỉnh dày đặc. Để tìm ra đƣợc những ngƣời có sự
chồng chéo về nhiệm vụ trong MXH có kích thƣớc lớn vẫn là một bài toán khó,
đã và đang đƣợc khoa học quan tâm, nghiên cứu.
Để giải quyết những thách thức trên, tác giả đề xuất phƣơng pháp áp dụng
giải thuật tìm kiếm cộng đồng vào bài toán khái phá quy trình. Ý tƣởng của đề
xuất là sử dụng các kỹ thuật của KCTC để phát hiện mô hình MXH từ tập nhật
ký sự kiện. Sau đó, sử dụng giải thuật tìm kiếm cộng đồng chồng chéo để tìm ra
các cộng đồng có cấu trúc chồng chéo. Hiệu quả của đề xuất này là giúp đơn
giản hóa cấu trúc mạng tức là chia một mạng có kích thƣớc lớn thành các mạng


8
có kích thƣớc nhỏ và sự kết nối chặt chẽ hơn [7]. Do mục tiêu của luận văn tìm
ra các cộng đồng chồng chéo nên Tác giả chỉ tập trung vào các giải thuật tìm
kiếm cộng đồng chồng chéo, là loại cấu trúc cộng đồng xuất hiện phổ biến
trong thực tế.
Các nhiệm vụ chính của Luận văn sẽ thực hiện:
1. Nghiên cứu tổng quan về lĩnh vực KPQT và giải thuật tìm kiếm cộng
đồng trong MXH những năm gần đây.
2. Phát biểu bài toán KCTC và đề xuất mô hình giải quyết bài toán.
3. Xây dựng chƣơng trình thực nghiệm dựa trên mô hình đề xuất trong

với các doanh nghiệp, bởi khách hàng là ngƣời trả tiền cho các sản phẩm, dịch
vụ của họ. Hầu hết, doanh nhân của mọi quốc gia trên thế giới đều nhận thức
đầy đủ về tầm quan trọng của khách hàng và họ luôn cố gắng phục vụ khách
hàng chu đáo nhất. Thực tế cho thấy, nhu cầu và mong muốn của khách hàng
thƣờng xuyên thay đổi. Điều này đã tác động rất lớn đến các doanh nghiệp, tạo
ra một thị trƣờng cạnh tranh, tất cả họ đều có chung một mục đích là đáp ứng tốt
nhất những yêu cầu thay đổi thƣờng xuyên này. Đây là là một thách thức lớn
nhất mà mỗi doanh nghiệp hàng ngày phải đối mặt. Do đó, để có thể cạnh tranh
thuận lợi, các doanh nghiệp cần phải nghiên cứu, thay đổi và cải tiến quy trình
kinh doanh phù hợp với thực tế.
Kinh doanh thông minh (Business intelligence) là một hƣớng nghiên cứu
quan trọng, trong đó có sử dụng dữ liệu đƣợc lƣu trữ trong các hệ thống thông
tin (HTTT). Sự xuất hiện “nền kinh tế số” đã làm thay đổi hai vấn đề là quá
trình điều hành kinh doanh và đánh giá hiệu suất công việc. Hầu hết, các doanh
nghiệp có quy mô lớn đều sử dụng các HTTT để hỗ trợ toàn hộ hay một phần
của quy trình kinh doanh. Dữ liệu sinh ra từ quá trình này đƣợc lƣu lại gọi là
nhật ký sự kiện. Các hệ thống ERP, WFM, CRM, SCM, B2B đều là kết quả của
sự cải tiến công nghệ và quá trình kinh doanh trong thực tế. Ngày nay, các
HTTT trở lên liên quan mật thiết hơn với các quy trình kinh doanh mà chúng hỗ
trợ. Một quy trình kinh doanh giúp điều hành hiệu quả các lĩnh vực quản lý hậu
cần, quản lý bán hàng, quản lý nhân lực, ... Sự gia tăng các hệ thống lƣu trữ
thông tin giúp quy trình kinh doanh đạt hiệu quả, hỗ trợ khả năng truy nhập và
phân tích dữ liệu. Việc trích lọc ra các thông tin có giá trị nhằm cải thiện khả
năng ra quyết định và mô hình quy trình vẫn là một vấn đề đƣợc các doanh
nghiệp quan tâm. Thực tế, việc tràn ngập các thông tin đã gây ra áp lực, thách
thức lớn trong việc trích lọc ra những thông tin có giá trị. KPQT giúp trích lọc
và phân tích dữ liệu để tìm ra mối liên quan giữa những đối tƣợng dữ liệu.
Ý tƣởng KPQT đƣợc các nhà khoa học Cook và Wolf đã nghiên cứu các
từ năm 1998. Sau đó, Herbst và Karagianis cũng đƣa các vấn đề KPQT trong nội
dung liên quan quản lý luồng công việc. Trong hội thảo về kinh doanh thông

giấy có thể khác xa so với thực tế, tùy theo từng nhà quản lý có thể nhìn thấy
hoặc không nhìn thấy vấn đề này. Kết quả là một loạt các đơn vị chức năng hoạt
động yếu kém do không đáp ứng đƣợc yêu cầu, đòi hỏi từ thực tế. KPQT tìm ra
những tồn tại, hạn chế trong hoạt động kinh doanh một cách nhanh chóng, giúp
nhà quản lý có thể ra quyết định chính xác trong các công việc.


11

Hình 1.2 Quá trình phát hiện mô hình quy trình từ nhật ký sự kiện
Hình 1.2 cho thấy dữ liệu hoạt động của doanh nghiệp sẽ đƣợc lƣu lại
trong các HTTT, áp dụng các kỹ thuật KPQT để trích xuất ra các thông tin có
giá trị hay mô hình quy trình.
- Tạo ra sự khách quan, giảm thiểu rủi ro: Nhà quản lý có thể có những ý
kiến chủ quan cũng nhƣ có sự thiên vị hay kỳ vọng quá mức về một vấn đề nào
đó. Những sai lệch này dẫn đến một loạt các cuộc họp gây lãng phí thời gian,
tiền bạc và tạo ra sự mâu thuẫn nội bộ. Kết quả của những phƣơng án giải quyết
có thể không phù hợp với thực tế. KPQT giúp các doanh nghiệp có cơ sở tin
tƣởng những giải pháp cho những vấn đề phức tạp của doanh nghiệp.
1.1.2 Mục tiêu của KPQT: Mục tiêu chính của KPQT là phát hiện, phân
tích và hiểu các quy trình kinh doanh dựa trên các bản ghi các hoạt động tại thời
một thời điểm xác định, thông tin này đƣợc lƣu trong các tập nhật ký sự kiện.
KPQT giúp trích lọc các thông tin liên quan, phát hiện ra mô hình quy trình mới
từ các dữ liệu sự kiện, đƣợc lƣu trong các HTTT lớn [1]. Quá trình này bao gồm
các kỹ thuật, công cụ và phƣơng thức để phát hiện, giám sát, cải thiện các quy
trình trong thực tế [36].
1.1.3 Mô hình quy trình và nhật ký sự kiện:
a) Mô hình quy trình (MHQT): Trong bối cảnh khoa học HTTT, một mô
hình là đại diện phi vật chất của thế giới thực, đƣợc sử dụng cho một mục đích
cụ thể [31]. Các mô hình đƣợc sử dụng để làm giảm độ phức tạp bằng cách biểu

hoặc tối ƣu hóa [36]. Trong đó:
Đầu vào: Nhật ký sự kiện.
Đầu ra: Mô hình quy trình.
Kiểm tra sự phù hợp của mô hình quy trình: Kỹ thuật này sử dụng mô
hình quy trình đang tồn tại và so sánh với dữ liệu lƣu trong nhật ký sự kiện,
nhằm kiểm tra sự phù hợp của mô hình quy trình với thực tế. Trong đó:
Đầu vào: Nhật ký sự kiện, Mô hình quy trình.
Đầu ra: Các độ đo phù hợp.
Tăng cường mô hình quy trình: Đây là kỹ thuật mở rộng hay cải tiến mô
hình quy trình đang tồn tại sử dụng thông tin về quy trình thực đƣợc ghi lại
trong các nhật ký sự kiện.
Đầu vào: Mô hình quy trình hiện có, Nhật ký sự kiện.


13
Đầu ra:Mô hình quy trình đƣợc bổ sung.

Hình 1.3 Các bài toán KPQT
Hình 1.3 biểu diễn sự tƣơng tác giữa KPQT, dữ liệu nhật ký sự kiện và
nền tảng phân tích. Khai phá nhật ký sự kiện hay sự các quy trình kinh doanh
thực để phát hiện ra sự tắc nghẽn, đứt đoạn của quy trình. Trong KPQT, sự
tƣơng tác giữa những thực thể theo một quy luật logic, do đó những kết quả của
lĩnh vực này mang lại là rất lớn đối với lĩnh vực kinh doanh thông minh.
1.1.5 Các khía cạnh của KPQT: Mở rộng MHQT khi bổ sung các khía
cạnh, bao gồm:
Khía cạnh tổ chức: tập trung vào các thông tin về các nguồn tài nguyên ẩn
dƣới các nhật ký. Các nguồn tài nguyên này bao gồm con ngƣời, hệ thống hay
vai trò hay bộ phận liên quan và sự liên hệ giữa các yếu tố đó. Mục tiêu của khía
cạnh này là để xây dựng cấu trúc tổ chức bằng cách phân lớp ngƣời tham gia
quy trình theo vai trò, đơn vị, đồng thời biểu diễn MXH.

lĩnh vực kinh doanh.
1.1.7 Một số thách thức đối với lĩnh vực KPQT
- Mục đích sử dụng: KPQT là một công nghệ cần phải đƣợc đặt trong bối
cảnh cụ thể thì mới làm nổi bật lên giá trị của lĩnh vực này. Các lợi ích của
KPQT mang lại nhƣ tăng hiệu quả hoạt động của doanh nghiệp, quản lý rủi ro và
bảo đảm quá trình, giảm thiểu sai sót, kiểm soát chất lƣợng dịch vụ.


15
- Các bản ghi sự kiện bị lỗi và thiếu: Đối với các bản ghi không chính xác
của nhật ký sự kiện có thể đƣợc sinh ra do sự cố phần mềm, đột biến ngƣời
dùng, lỗi phần cứng hoặc bị cắt xén các trƣờng hợp của quy trình trong lúc trích
lọc dữ liệu. Các bản ghi bị sai trong nhật ký sự kiện đƣợc coi là một biểu hiện lạ
trong một hiện tƣợng đƣợc gọi là bản ghi bị lỗi. Các bản ghi bị lỗi đƣợc lƣu lại
chính xác và thƣờng hiếm khi xảy ra [1]. Các bản ghi sự kiện lỗi này sẽ làm tăng
độ phức tạp của mô hình quy trình. Các đề xuất KPQT vì thế mà đƣa ra những
sự phân tích và mô hình không đúng.
- Chất lượng nhật ký sự kiện: Việc thu thập dữ liệu và tiền xử lý dữ liệu là
một thách thức trƣớc khi bắt đầu KPQT, vì chất lƣợng của dữ liệu ảnh hƣởng
lớn đến kết quả của KPQT. Chất lƣợng của các nhật ký sự kiện sẽ ảnh hƣởng
chủ yếu tới chất lƣợng khai phá và tái cấu trúc các mô hình quy trình. Các hệ
thống quy trình kinh doanh và quản lý luồng công việc tạo ra các nhật ký sự kiện
với chất lƣợng cao nhất [36].
- Mô hình quy trình phức tạp: Các quy trình trong thực tế thƣờng rất
phức tạp. Việc biểu diễn chúng bằng hình học có thể dẫn các mô hình có độ
phức tạp cao và rất khó hiểu. Hai mô hình quy trình phức tạp điển hình đƣợc gọi
là quy trình Lasagna và Spaghetti [1]. Giảm độ phức tạp của mô hình là một
thách thức lớn và đang là đối tƣợng nghiên cứu ngày nay [23].
- Các loại hình quy trình: KPQT chỉ có thể đƣợc áp dụng đối với các quy
trình đƣợc kiểm soát hoàn toàn bằng HTTT. Trong thực tế, các quy trình chỉ cần

này là tìm ra cấu trúc tổ chức bằng cách phân lớp ngƣời tham gia vào quy trình
trong các giới hạn của các đơn vị, vai trò của từng ngƣời, mối quan hệ của
những ngƣời tham gia vào quy trình.
- Vai trò KCTC: Các kỹ thuật này giúp phát hiện cấu trúc tổ chức, phân
tích MXH, cấp phát tài nguyên và khai phá vai trò từng cá thể, nhóm hay tổ
chức trong MXH. Khai phá khía cạnh tổ chức là phân tích những thông tin đƣợc
tiết lộ từ khía cạnh tổ chức. Kỹ thuật này bao gồm việc phát hiện các MXH, cấu
trúc tổ chức và hành vi của tổ chức [2]. Các kỹ thuật khai phá này tạo nên nền
tảng đối với các nhiệm vụ sau:
+ Chứng thực: tập trung vào kiểm soát truy nhập giúp đảm bảo chỉ những
cá nhân, đơn vị nào đƣợc chứng thực có vai trò mới đƣợc phép thực hiện các
hoạt động trong quy trình.
+ Kiểm soát tài nguyên: tập trung vào những ràng buộc sau khi truy nhập
dữ liệu nhƣ ngƣời hay nhóm ngƣời sẽ nắm giữ và sử dụng dữ liệu.
+ Tái cơ cấu tổ chức:
Phân tách: ràng buộc liên quan tới quy trình giới hạn các khả năng của
các đơn vị khi thực hiện các hoạt động, giúp giảm rủi ro khi gặp lỗi.
Sát nhập: đây là sự ràng buộc hai chiều, sắp xếp các chủ thể, tác vụ vào
cùng một nhóm các hoạt động cụ thể.
+ Kiểm soát xung đột: ngăn các luồng thông tin mang tính nhạy cảm giữa
những đối thủ cạnh tranh hay các phòng, ban là những đơn vị tham gia vào quy
trình kinh doanh.


17
- Phân tích MXH: Jacob Levy Moreno đã đƣa ra khái niệm mô hình
MXH vào năm 1932-1938, ông đã nghiên cứu mô hình MXH các trƣờng học
dành cho nhóm học sinh nữ tại Hudson, NewYork [30]. MXH là một mô hình
đƣợc biểu diễn dƣới dạng đồ thị, là phƣơng pháp biểu diễn dữ liệu và các mối
quan hệ của các dữ liệu này dƣới dạng đồ thị. Phát hiện MXH từ nhật ký sự kiện

với nhau hơn những ngƣời khác. Giá trị độ đo Working together là số lần hai
ngƣời thực hiện nhiệm vụ trong cùng một trƣờng hợp.


18
- Độ đo dựa trên loại nhiệm vụ: tập trung vào tính chất công việc cần phải
thực hiện. Hai ngƣời thực hiện các nhiệm vụ tƣơng tự nhau sẽ có mối quan hệ
mật thiết hơn. Độ đo Similar task sử dụng hàm tính khoảng cách Hamming, …
để tính khoảng cách giữa các nhiệm vụ.
- Độ đo dựa trên loại sự kiện: Các sự kiện tƣơng ứng với sự thực hiện các
nhiệm vụ. Tuy nhiên, có những sự kiện tƣơng ứng với hoạt động chỉ đƣợc giao
giữa ngƣời i sang ngƣời j và không có chiều ngƣợc lại. Mối quan hệ này thể hiện
sự phân cấp quyền lực.
1.3 Bài toán toán khai phá khía cạnh tổ chức
1.3.1 Trong thực tế: Hầu hết, các doanh nghiệp và tổ chức đều đang gặp
phải vấn đề liên quan đến sự chồng chéo, trùng lắp, phân công chƣa rõ ràng,
chƣa hợp lý về chức năng, nhiệm vụ giữa các cá nhân, bộ phận. Đây là những
vấn đề đƣợc coi là những thách thức vì nhà quản lý đã nhìn thấy, nhƣng chƣa
tìm đƣợc cách giải quyết tối ƣu. Những thách thức này là nguyên nhân dẫn đến
giảm doanh thu và hiệu suất công việc, tăng chi phí cho các nhiệm vụ thống kê,
phân tích viết báo cáo lập kế hoạch, quy hoạch liên quan đến những vấn đề tổ
chức.
Nguyên nhân: Chƣa thống nhất về phân công nhiệm vụ giữa các phòng,
ban, đơn vị; cách nhìn chủ quan của nhà quản lý đối với việc phân công nhiệm
vụ; thiếu tiêu chuẩn để phân định rõ ràng; tính chất phức tạp, đa dạng của công
việc; việc đáp ứng những mong muốn thay đổi theo ngày của khách hàng cũng
là nguyên nhân làm cho những cơ cấu tổ chức trƣớc đó trở lên lạc hậu.
Giải pháp trong thực tế: Rà soát, nghiên cứu, phân tích, đánh giá và làm
rõ chức năng, nhiệm vụ của từng bộ phận để tìm ra sự chồng chéo.
1.3.2 Trong luận văn: Dựa trên những thách thức của bài toán trong thực

nhiều vai trò khác nhau trong quy trình, mỗi hoạt động chỉ đƣợc thực hiện bởi
duy nhất một ngƣời.

Hình 1.5 Mô hình tổ chức được phát hiện từ các nhật ký sự kiện


20
- Nền tảng khoa học:
Wil M.P. van der Aalst et al. đã áp dụng các kỹ thuật phân tích MXH vào
việc phân tích mối quan hệ giữa những ngƣời tham gia vào quy trình từ nhật ký
sự kiện [8]. Bài nghiên cứu đã đề xuất ra các loại độ đo có thể sử dụng để xây
dựng mô hình MXH và giới thiệu công cụ MiSoN (Mining Social Network).
Năm 2012, hai tác giả Diago R. Ferreira và Cláudia Alves đã đề xuất đơn giản
hóa mô hình quy trình bằng cách sử dụng độ đo Modularity để phát hiện ra các
cộng đồng trong MXH. Nhóm tác giả đã sử dụng công cụ ProM để thực hiện ý
tƣởng này [20].
- Phương pháp giải quyết:
Phƣơng pháp để giải quyết bài toán trong luận văn dựa trên những kết quả
nghiên cứu của các nhà khoa học Wil M.P van der Aalst et al. và Diago R.
Ferreira et al.. Điểm mới trong đề xuất của Tác giả là áp dụng giải thuật tìm
kiếm cộng đồng chồng chéo trong MXH. Đề xuất này xuất phát từ hiện tƣợng
chồng chéo nhiệm vụ giữa những ngƣời thuộc cùng một tổ chức trong thực tế.
Tuy nhiên, để không làm mất tính tổng quát cấu trúc tổ chức phân cấp nhƣng
vẫn phản ánh đƣợc sự chồng chéo của các cộng đồng trong thực tế, Tác giả sử
dụng giải thuật Phân vùng theo cạnh của Ahn et al., 2010.
Tổng quát các bƣớc giải quyết:
(1) Tiền xử lý dữ liệu: Loại bỏ các thông tin bị lỗi, nhiễu, những thông tin
không có giá trị khai phá, chuyển về định dạng chuẩn XES 1.0.
(2) Xây dựng MXH: Sử dụng các độ đo để xây dựng MXH từ tập nhật ký
sự kiện.

22
CHƢƠNG 2. CÁC GIẢI THUẬT TÌM KIẾM CỘNG TRONG MXH
2.1 Cộng đồng mạng xã hội
Hơn một thập kỷ trƣớc, các mạng phức tạp (hay cộng đồng MXH) đã trở
thành chủ đề đƣợc quan tâm và nghiên cứu trong một số hệ thống lớn. Cộng
đồng là một nhóm các đỉnh mà có cùng một số thuộc tính và vai trò trong tổ
chức. Nhóm gồm các đỉnh có nhiều kết nối với nhau nếu chúng thuộc cùng một
cộng đồng và ít kết nối đến các đỉnh khác nếu chúng không thuộc cùng một
cộng đồng [5]. Sự tƣơng tác giữa các phần tử trong MXH hay mạng lƣới sinh
học đƣợc biểu diễn bằng các liên kết và đỉnh. Một cộng đồng hay còn gọi là một
cụm là một nhóm các đỉnh có nhiều kết nối với nhau hơn các đỉnh khác trong
mạng [22]. Các mạng lƣới thƣờng đƣợc biểu diễn theo cấu trúc mô-đun (hay
cộng đồng). Một số cộng đồng thƣờng liên quan mật thiết tới các đơn vị chức
năng của hệ thống. Nhiều hệ thống trong thực tế có thể đƣợc biểu diễn dƣới
dạng mô hình MXH nhƣ nhƣ mạng điện thoại, các trang MXH, sự di chuyển của
động vật, sự tƣơng tác của các phân tử, … . Một hiện tƣợng thƣờng đƣợc quan
sát thông qua các loại mạng khác nhau là sự hiện diện của các cấu trúc cộng
đồng tiềm ẩn. Các đỉnh có thể đƣợc tập hợp lại thành nhóm sao cho những đỉnh
trong nhóm có sự tƣơng tác lẫn nhau và các nhóm khác nhau thƣờng ít khi tƣơng
tác.
2.1.1 Nguyên nhân hình thành cộng đồng MXH:
Theo nghiên cứu của Pew Internet & American Life Project, hơn 93% cả
thiếu niên (12-17 tuổi) và thanh niên (18-29 tuổi) ở Mỹ sử dụng Internet hàng
ngày, trong đó có hơn 70% số ngƣời dùng các MXH. Một trang web tạo ra một
cộng đồng xã hội, nơi gồm những ngƣời quan tâm đến cùng một chủ đề hay chỉ
là sự quan tâm đến nhau. Các thành viên sẽ tạo các tiểu sử cá nhân trực tuyến và
một số loại dữ liệu khác. Họ giao tiếp với ngƣời khác bằng âm thanh, văn bản,
tin nhắn, video trực tuyến và các loại dịch vụ khác nhƣ MXH. Ngày nay, có
nhiều chuyên trang về MXH nhƣ Facebook, Orkut, Twitter, Bebo, Myspace,
Friendster, hi5, Linkedin và Bharatstudent, …. Những website này đƣợc biết

ngoài ra chủ đề này còn đƣợc đề cập trong các bài nghiên cứu của Danon et al.,
2007; Fortunato và Castellano, 2009; Newman, 2004a; Porter et al., 2009;
Schaeffer, 2007. Để xác định cấu trúc cộng đồng, phải phân tích các mối quan
hệ dƣới dạng cấu trúc hình học giữa các cộng đồng. Loại cấu trúc cộng đồng
đƣợc phân loại theo sự bao phủ các phần tử của các cộng đồng, một số loại cấu
trúc điển hình:
Cấu trúc cộng đồng không chồng chéo: Một đỉnh chỉ thuộc vào duy nhất
một cộng đồng [6]. Các cộng đồng đỉnh này không có sự liên hệ, tách rời nhau
và chỉ có hoặc không có các cạnh trung gian giữa chúng.
Cấu trúc cộng đồng chồng chéo: các cộng đồng trong thực tế có khuynh
hƣớng chồng chéo các đỉnh, tức là một đỉnh có thể thể thuộc nhiều cộng đồng.
Đỉnh đƣợc gọi là đỉnh chồng chéo nếu thuộc sở hữu nhiều hơn một cộng đồng
[7]. Phát hiện các cộng đồng nối chồng chéo đang là một thách thức đối với
những nhà nghiên cứu bởi sự không có sự phân chia rõ ràng giữa các đỉnh và
cộng đồng.