tailieunhanh - Mô hình lực cho biểu diễn đồ thị phân nhóm

Bài viết Mô hình lực cho biểu diễn đồ thị phân nhóm đề xuất một giải pháp vẽ đồ thị giúp hiển thị một cách rõ nét cấu trúc phân nhóm của dữ liệu cũng như sự liên kết giữa các nhóm. Bài viết tập trung vào khía cạnh hiển thị thông tin và giả sử rằng dữ liệu đã được phân nhóm theo một tiêu chí nào đó. | Kỷ yếu Hội nghị Quốc gia lần thứ VIII về Nghiên cứu cơ bản và ứng dụng Công nghệ thông tin (FAIR); Hà Nội, ngày 9-10/7/2015 MÔ HÌNH LỰC CHO BIỂU DIỄN ĐỒ THỊ PHÂN NHÓM Trương Quốc Định1, Taoufiq Dkaki2 1 Khoa Công nghệ thông tin & Truyền thông, Trường Đại học Cần Thơ 2 Institut de Recherche en Informatique de Toulouse tqdinh@, dkaki@ TÓM TẮT - Đồ thị (graph) là cấu trúc cho phép mô hình hóa nhiều loại dữ liệu phức tạp thuộc nhiều lĩnh vực trong thế giới thực. Bên cạnh đó, đồ thị còn là cấu trúc được sử dụng chủ yếu cho việc biểu diễn thông tin. Khi biểu diễn một lượng lớn thông tin thì việc xác định được các nhóm dữ liệu cũng như mối liên hệ giữa các nhóm là một mục tiêu quan trọng cần đạt được. Trong bài báo này, chúng tôi đề xuất một giải pháp vẽ đồ thị giúp hiển thị một cách rõ nét cấu trúc phân nhóm của dữ liệu cũng như sự liên kết giữa các nhóm. Trong phạm vi nghiên cứu của bài báo này chúng tôi chỉ tập trung vào khía cạnh hiển thị thông tin và giả sử rằng dữ liệu đã được phân nhóm theo một tiêu chí nào đó. Chúng tôi đề xuất giải pháp vẽ đồ thị dựa trên mô hình lực (energy-based model) trong đó các nhóm sẽ được hiển thị trong các vùng riêng biệt và không trùng lắp. Các vùng hiển thị riêng biệt không trùng lắp này có thể do người dùng tự định nghĩa hoặc do giải thuật tự tính toán. Trong cả hai trường hợp, giải pháp do chúng tôi đề xuất đều làm nổi bật được cấu trúc phân nhóm cũng như cấu trúc tổng thể của dữ liệu. Từ khóa - Đồ thị, đồ thị phân nhóm, vẽ đồ thị. I. GIỚI THIỆU Vẽ đồ thị tự động là lĩnh vực nghiên cứu sôi động kể từ nhiều thập niên trở lại đây và trở nên quan trọng hơn rất nhiều khi cấu trúc đồ thị ngày càng được ứng dụng nhiều trong thực tế bởi lẽ nó có thể mô hình hóa cho đa dạng các loại dữ liệu phức tạp. Thật vậy, cấu trúc đồ thị đã chứng minh được tầm quan trọng của mình trong rất nhiều lĩnh vực như: mạng xã hội [1], kỹ nghệ phần mềm [2], thiết kế mạch điện [3], thiết kế cơ sở dữ liệu [4] Một cách tổng quát hơn, cấu .