Nhiều hệ thống khoa học thú vị có thể được biểu diễn dưới dạng mạng lưới, tập hợp các nút hoặc đỉnh được nối với nhau bằng các đường hoặc cạnh. Các ví dụ bao gồm internet và World Wide Web, mạng lưới trao đổi chất, mạng lưới thức ăn, mạng lưới thần kinh, mạng lưới truyền thông và phân phối, và mạng lưới xã hội. Nghiên cứu về các hệ thống mạng lưới đã có một lịch sử kéo dài nhiều thế kỷ, nhưng nó đã trải qua một sự gia tăng đặc biệt về sự quan tâm trong thập kỷ qua, đặc biệt là trong các ngành khoa học toán học, một phần là do sự sẵn có ngày càng tăng của dữ liệu quy mô lớn chính xác mô tả cấu trúc liên kết của mạng lưới trong thế giới thực. Các phân tích thống kê về dữ liệu này đã tiết lộ một số đặc điểm cấu trúc bất ngờ, chẳng hạn như tính bắc cầu mạng cao (1), phân phối bậc theo luật lũy thừa (2) và sự tồn tại của các họa tiết cục bộ lặp đi lặp lại (3); xem các tài liệu tham khảo 4-6 để biết các đánh giá.
Một vấn đề đã nhận được sự quan tâm đáng kể là việc phát hiện và mô tả đặc điểm của cấu trúc cộng đồng trong mạng lưới (7, 8), có nghĩa là sự xuất hiện của các nhóm đỉnh được kết nối dày đặc, chỉ với các kết nối thưa thớt hơn giữa các nhóm (Hình 1). Khả năng phát hiện các nhóm như vậy có thể có tầm quan trọng thực tiễn đáng kể. Ví dụ, các nhóm trong World Wide Web có thể tương ứng với các tập hợp trang web về các chủ đề liên quan (9); các nhóm trong mạng lưới xã hội có thể tương ứng với các đơn vị hoặc cộng đồng xã hội (10). Chỉ riêng việc tìm ra rằng một mạng lưới chứa các nhóm liên kết chặt chẽ có thể truyền tải thông tin hữu ích: nếu một mạng lưới trao đổi chất được chia thành các nhóm như vậy, chẳng hạn, nó có thể cung cấp bằng chứng cho một cái nhìn mô-đun về động lực học của mạng lưới, với các nhóm nút khác nhau thực hiện các chức năng khác nhau với một mức độ độc lập nhất định (11, 12).
Công trình trước đây về các phương pháp khám phá các nhóm trong mạng lưới chia thành hai dòng nghiên cứu chính, cả hai đều có lịch sử lâu đời. Đầu tiên, được gọi là phân vùng đồ thị, đã được theo đuổi đặc biệt trong khoa học máy tính và các lĩnh vực liên quan, với các ứng dụng trong điện toán song song và thiết kế mạch tích hợp, trong số các lĩnh vực khác (13, 14). Thứ hai, được xác định bằng các tên như mô hình khối, phân cụm階層(phân cấp) hoặc phát hiện cấu trúc cộng đồng, đã được các nhà xã hội học và gần đây hơn là các nhà vật lý, nhà sinh vật học và các nhà toán học ứng dụng theo đuổi, với các ứng dụng đặc biệt cho mạng lưới xã hội và sinh học (7, 15, 16).
Rất dễ để cho rằng hai dòng nghiên cứu này thực sự giải quyết cùng một câu hỏi, mặc dù bằng những phương tiện hơi khác nhau. Tuy nhiên, có những khác biệt quan trọng giữa các mục tiêu của hai nhóm khiến cho các phương pháp tiếp cận kỹ thuật khá khác nhau trở nên mong muốn. Một vấn đề điển hình trong phân vùng đồ thị là việc phân chia một tập hợp các nhiệm vụ giữa các bộ xử lý của một máy tính song song để giảm thiểu lượng giao tiếp giữa các bộ xử lý cần thiết. Trong một ứng dụng như vậy, số lượng bộ xử lý thường được biết trước và ít nhất là một con số gần đúng cho số lượng nhiệm vụ mà mỗi bộ xử lý có thể xử lý. Do đó, chúng ta biết số lượng và kích thước của các nhóm mà mạng lưới sẽ được chia thành. Ngoài ra, mục tiêu thường là tìm ra sự phân chia tốt nhất của mạng lưới bất kể liệu một sự phân chia tốt thậm chí có tồn tại hay không; có rất ít ý nghĩa trong một thuật toán hoặc phương pháp không phân chia mạng lưới trong một số trường hợp.
Phát hiện cấu trúc cộng đồng, ngược lại, có lẽ tốt nhất nên được coi là một kỹ thuật phân tích dữ liệu được sử dụng để làm sáng tỏ cấu trúc của các tập dữ liệu mạng lưới quy mô lớn, chẳng hạn như mạng lưới xã hội, dữ liệu internet và web hoặc mạng lưới sinh hóa. Các phương pháp cấu trúc cộng đồng thường giả định rằng mạng lưới quan tâm tự nhiên chia thành các nhóm nhỏ và công việc của người thử nghiệm là tìm ra những nhóm đó. Do đó, số lượng và kích thước của các nhóm được xác định bởi chính mạng lưới chứ không phải bởi người thử nghiệm. Hơn nữa, các phương pháp cấu trúc cộng đồng có thể thừa nhận một cách rõ ràng khả năng không có sự phân chia tốt của mạng lưới tồn tại, một kết quả tự nó được coi là thú vị vì ánh sáng mà nó chiếu vào cấu trúc liên kết của mạng lưới.
Bài viết này tập trung vào việc phát hiện cấu trúc cộng đồng trong các tập dữ liệu mạng lưới đại diện cho các hệ thống thực tế được quan tâm. Tuy nhiên, cả sự tương đồng và khác biệt giữa các phương pháp cấu trúc cộng đồng và phân vùng đồ thị sẽ thúc đẩy nhiều phát triển tiếp theo.