Mạng xã hội là một tập hợp các thực thể được kết nối với nhau bằng
một tập hợp các mối quan hệ hay liên kết, như mối quan hệ bạn bè, gia
đình, mối quan hệ kinh doanh, quá trình lây lan bệnh tật, sự phát tán tin
tức, các biểu đồ cộng tác, mạng ngữ nghĩa cho mô tả ngôn ngữ, . . . Mạng
xã hội thường được biểu diễn dưới dạng đồ thị, trong đó các nút (đỉnh)
biểu diễn cho các thực thể và các cạnh biểu diễn cho mối quan hệ giữa các
thực thể với nhau. Khai phá đồ thị là quá trình phát hiện, truy xuất và
phân tích các mẫu không tầm thường trong dữ liệu dưới dạng cấu trúc đồ
thị. Ngày nay, khai phá dữ liệu đồ thị nổi lên như một kỹ thuật quan trọng
trong xã hội học hiện đại, đã có những đóng góp vô cùng quan trọng trong
nhiều lĩnh vực như: nhân chủng học, sinh học, nhân khẩu học, nghiên cứu
truyền thông, kinh tế, địa lý, lịch sử, khoa học thông tin, khoa học máy
tính, . . .
Trong lĩnh vực khai phá đồ thị, việc phân tích và phát hiện cấu trúc
cộng đồng mang nhiều ý nghĩa quan trọng và có rất nhiều ứng dụng cả
trong lý thuyết lẫn thực tiễn. Cấu trúc cộng đồng (cộng đồng) được hiểu
là một nhóm các thực thể trong mạng có những tính chất tương tự nhau,
liên kết chặt chẽ với nhau và cùng đóng một vai trò nhất định đối với mỗi
bài toán thực tế. Việc phát hiện và phân tích các cộng đồng trên đồ thị
mạng xã hội sẽ cung cấp cho chúng ta những thông tin quý giá để hiểu
1
biết sâu sắc hơn và hình dung rõ ràng hơn những cấu trúc của mạng.
Trong những năm gần đây, việc phân tích và phát hiện cấu trúc cộng
đồng là một trong những lĩnh vực nghiên cứu chính trong khai thác, phân
tích dữ liệu đồ thị nói chung và đồ thị mạng xã hội nói riêng. Đặc biệt,
trong bối cảnh bùng nổ thông tin, vấn đề này lại càng thu hút các học
giả nối tiếng của nhiều lĩnh vực khoa học khác nhau. Nhiều thuật toán
phát hiện cấu trúc cộng đồng trên đồ thị mạng xã hội được nhiều người
tập trung nghiên cứu và phát triển ứng dụng. Song hầu hết các thuật toán
trên đều có độ phức tạp khá lớn do phải tính các độ đo khác nhau ở mỗi
bước xử lý. Một cách tiếp cận mới là thuật toán lan truyền nhãn (LPA)
[74], có ưu điểm: thời gian tính toán gần tuyến tính và chỉ cần dựa vào
một chút thông tin tiên nghiệm ban đầu về cấu trúc mạng. Nhưng nhược
điểm chính của phương pháp này là sử dụng hàm heuristic, không tạo ra
lời giải duy nhất, kết quả chỉ mang tính gần đúng. LPA phù hợp với loại
bài toán có dữ liệu cực kỳ lớn. Nhiều cải tiến đã được thực hiện trên LPA
để cải thiện tính ổn định và nâng cao hiệu quả của các thuật toán phát
hiện cấu trúc cộng đồng trên đồ thị mạng xã hội.