Bài toán Clique lớn nhất - Ứng dụng và những thách thức tính toán - Đàm Thanh Phương

Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 9 BÀI TOÁN CLIQUE LỚN NHẤT - ỨNG DỤNG VÀ NHỮNG THÁCH THỨC TÍNH TOÁN Đàm Thanh Phương*, Ngô Mạnh Tưởng, Khoa Thu Hoài Trường Đại học Công nghệ thông tin và Truyền thông – ĐH Thái Nguyên TÓM TẮT Bài toán clique lớn nhất là một bài toán kinh điển của lý thuyết đồ thị và có nhiều ứng dụng. Nhiều vấn đề trong các mạng xã hội, sinh học, tài chính được giải quyết thông qua bài toán tìm kiếm các clique trong đồ thị. Clique và phân vùng clique cũng được sử dụng như một công cụ phân cụm hay phân loại dữ liệu. Tuy nhiên các bài toán thực tế thường được mô hình hoá bằng đồ thị rất lớn và cần phải có bộ nhớ lưu trữ đủ lớn cho quá trình thực hiện các thuật toán. Qua bài báo này, chúng tôi sẽ thảo luận bốn ứng dụng và xác định những thách thức tính toán đến từ lý thuyết cũng như thực hành. Từ khoá: Cliques, tựa clique, phân vùng clique, tập độc lập, bài toán clique lớn nhất, bài toán tập độc lập lớn nhất. GIỚI THIỆU* Một đơn đồ thị vô hướng G là cặp ( ),V E bao gồm tập hữu hạn, khác rỗng các đỉnh V và tập hữu hạn ( có thể rỗng) các cạnh E V V⊆ × là các cặp không có thứ tự hai phần tử phân biệt của V . Trong bài báo này, chúng ta chỉ xét các đơn đồ thị vô hướng như trên và để vắn tắt, sẽ gọi chung là đồ thị. Hai đỉnh ,u v V∈ được gọi là hai đỉnh kề nếu ( ),u v E∈ , nghĩa là một cạnh của đồ thị. Một đồ thị được gọi là đầy đủ nếu có cạnh giữa hai đỉnh bất kỳ. Đồ thị bù của G là đồ thị ( ),G V E= , có cùng tập đỉnh V và tập cạnh ( ) ( ){ }, , , , ,E i j i j V i j i j E= ∈ ≠ ∉ . Đồ thị được gọi là liên thông nếu tồn tại đường đi giữa hai đỉnh bất kỳ. Các thành phần liên thông của đồ thị là các đồ thị con liên thông cực đại. Độ dài của đường đi dài nhất trong số tất cả các đường đi ngắn nhất giữa hai đỉnh bất kỳ được gọi là đường kính. Mật độ của đồ thị được xác định bởi giá trị: 2 2 E V V− . Hai đồ thị ( ) ( )1 1 1 2 2 2, , ,G V E G V E= = được gọi là đẳng cấu nếu tồn tại một song ánh 1 2:V Vφ → thoả mãn: : ( ) ( ) ( )( )1 2, ,u v E u v Eφ φ∈ ⇔ ∈ . * Tel: 0912 998749, Email: dtphuong@ictu.edu.vn Với mỗi tập con S V⊂ , đồ thị con sinh bởi S được định nghĩa là ( ) ( ),G S S E S S= ∩ × Một tập đỉnh S được gọi là một clique nếu ( )G S là đồ thị đầy đủ. Chúng ta cũng phân biệt giữa clique cực đại là clique không thuộc bất cứ một clique nào rộng hơn nó, với clique lớn nhất là clique có số phần tử lớn nhất. Một tập đỉnh S được gọi là một tập độc lập (tập ổn định) nếu hai đỉnh bất kỳ của S không kề nhau. Định nghĩa clique có thể tổng quát hoá cho khái niệm tựa clique. Một tựa clique hay γ -clique của đồ thị là tập đỉnh Cγ thoả mãn đồ thị con ( )G Cγ là liên thông và có ít nhất ( )1 2 q qγ −     (1) cạnh, trong đó q Cγ= và [ ]0,1γ ∈ . Trong trường hợp đặc biệt, khi 0γ = , ( )G Cγ có thể không có cạnh nào và khi 1γ = thì Cγ là một clique của G . Tô màu đồ thị là phân chia tập đỉnh thành các tập ổn định rời nhau. Trong khi phủ clique là phân vùng tập đỉnh thành các clique rời nhau. Sau đây, ta gọi một phủ clique là phân vùng clique. Bài toán clique lớn nhất là bài toán tìm clique lớn nhất trong đồ thị đã cho. Ta ký hiệu số phần tử của clique lớn nhất trong đồ thị G là Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 10 ( )Gω và gọi là chỉ số clique. Tương tự bài toán tập ổn định lớn nhất là bài toán tìm tập ổn định có số phần tử lớn nhất trong đồ thị. Chỉ số ổn định là số phần tử của tập ổn định lớn nhất, ký hiệu là ( )Gα . Số màu hay sắc số của đồ thị ( )Gχ là số nhỏ nhất các tập ổn định cần để tô màu đồ thị. Tương tự, số nhỏ nhất các clique cần để phân vùng clique đồ thị G được gọi là chỉ số phủ clique và ký hiệu ( )Gχ . Bài toán clique lớn nhất và bài toán phủ clique là một trong 21 bài toán mà Richard Karp đã chứng minh là NP đầy đủ Nghĩa là, trừ khi P = NP, các thuật toán chính xác giải bài toán có thời gian tăng theo hàm mũ với số đỉnh của đồ thị. Vì một clique trong G cũng là một tập ổn định trong G nên ta có ( ) ( )G Gα ω= (2) Hơn nữa ta cũng có các kết quả sau: ( ) ( )G Gχ χ= (3) ( ) ( )G Gω χ≤ (4) ( ) ( )G Gα χ≤ (5) Dễ thấy số tập ổn định cần thiết để phủ đồ thị bằng số clique cần thiết để phủ đồ thị bù nên ta có đẳng thức (3). Vì vậy việc tìm sắc số đồ thị và chỉ số phủ clique là tương đương và tuỳ thuộc vào ứng dụng ta sẽ sử dụng bài toán phù hợp. Hai trong các đỉnh của clique lớn nhất không thể nằm cùng trong một tập ổn định nào. Vì vậy để phân chia tập đỉnh của đồ thị thành các tập ổn định rời nhau thì số tập ổn định ít nhất phải bằng số đỉnh của clique lớn nhất. Từ đó ta có bất đẳng thức (4). Bất đẳng thức (5) có được từ (2), (3), (4) với chú ý rằng đồ thị bù của đồ thị G chính là đồ thị G . Trong bài báo này chúng tôi thảo luận về các thách thức tính toán liên quan đến clique, tựa clique và phân vùng clique phát sinh từ bốn ứng dụng: Đồ thị các cuộc gọi, lý thuyết mã, đối sánh cấu trúc phân tử và giả thuyết Keller. ĐỒ THỊ CUỘC GỌI Các công ty điện thoại thường phải đối mặ với các tập dữ liệu khổng lồ. Ví dụ dữ liệu cuộc gọi đường dài của công ty AT&T trong năm 1999: xấp xỉ 300 triệu cuộc gọi một ngày, tương đương với yêu cầu không gian lưu trữ khoảng 20 terabytes một năm [1]. Việc phân tích tập dữ liệu này lại rất quan trọng cho công ty trong việc nghiên cứu mẫu khách hàng và tối ưu hoá hoạt động của họ. Cho một tập dữ liệu cuộc gọi trong một khoảng thời gian (ví dụ xếp từ các ngày đến các tháng). Chúng ta có thể xây dựng một đồ thị gọi là đồ thị cuộc gọi như sau: Mỗi người sử dụng điện thoại đại diện cho một đỉnh của đồ thị, mỗi cuộc gọi là một cạnh có hướng. Kết quả là ta được một đa đồ thị có hướng bởi vì một người A có thể gọi cho người B nhiều lần. Các tựa clique vô hướng của đồ thị này có thể cung cấp thông tin về nhóm người có mối liên kết cao. Đồ thị có hàng triệu đỉnh thường được gọi là đồ thị lớn. Ngay cả việc hiển thị trực quan trên màn hình hay các phân tích thống kê cơ bản là các nhiệm vụ khó khăn. Với các đồ thị rất lớn, chúng thường không phù hợp với bộ nhớ RAM của máy tính hoặc thậm chí vào bộ nhớ chính. Vì thế, thuật toán bộ nhớ mở rộng đã được phát triển. Đồ thị cuộc gọi có các tính chất quan trọng đặc biệt sau [2], [3]: - Đồ thị rất lớn, tới hàng triệu đỉnh. - Đồ thị có mật độ rất thấp, trong khoảng 0,0000001 - Đồ thị thường không liên thông, mặc dù chứa thành phần liên thông lớn - Đường kính vô hướng thấp, trong khoảng ( )log n - Bậc vào ind và bậc ra outd của đỉnh phân phối theo luật: ( ) inin inP d d γ−
với [2,3]inγ ∈ và ( ) outout outP d d γ−
với 2outγ < , ở đây ( )P d là tỷ số của số đỉnh có bậc d trên tổng số đỉnh của đồ thị. Trong [3], Abello đã nghiên cứu đồ thị cuộc gọi trong 1 ngày với các cuộc gọi cố định tại AT&T và nhận được một đồ thị cuộc gọi với Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 11 53 triệu đỉnh và 170 triệu cạnh. Để khai thác cấu trúc ở trên, tác giả đã phải thực hiện tiền xử lý mở rộng. Các phân tích thuật toán của đồ thị đó là rất quan trọng. Tuy nhiên, các thuật toán được biết đến không áp dụng tốt trên đồ thị như vậy. Điều này dẫn chúng ta đến thử thách đầu tiên. Thách thức 1 (Thuật toán cho các đồ thị cực lớn với mật độ rất thấp): Thiết kế một thuật toán hiệu quả cùng với tập dữ liệu cho bài toán γ -clique lớn nhất trong đồ thị lớn có các tính chất như đồ thị cuộc gọi. Các đồ thị tương tự đồ thị cuộc gọi có thế kể đến như đồ thị internet, đồ thị SMS, đồ thị từ mạng xã hội ĐỒ THỊ TRONG LÝ THUYẾT MÃ Bài toán cần quan tâm là: gửi một thông điệp qua kênh truyền có độ nhiễu cao với độ tin cậy lớn nhất có thể. Trong lý thuyết mã, người ta mong muốn tìm được một mã nhị phân đủ lớn có thể khắc phục một số lỗi nhất định với kích thước đã cho của từ nhị phân. Với từ nhị phân thể hiện bởi véc tơ ( )0,1 nu ∈ , ký hiệu ( )eF u là tập hợp tất cả các véc tơ có thể thu được từ u do một lỗi e nào đó, chẳng hạn mất hoặc chuyển vị các bit. Chú ý rằng các phần từ của ( )eF u không nhất thiết có độ dài n vì có thể là kết quả của việc mất bit. Tập con ( )0,1 nC ⊆ được gọi là mã sửa lỗi e nếu ( ) ( ) ; ,e eF u F v u v C∩ = ∅ ∀ ∈ với u v≠ . Bài toán đặt ra là tìm tập mã sửa lỗi lớn nhất, nghĩa là số phần tử của C là lớn nhất. Xét đồ thị gồm tập đỉnh là tập tất cả các véc tơ nhị phân ( )0,1 nu ∈ và có cạnh ( ),u v khi ( ) ( )e eF u F v∩ ≠ ∅ . Theo cách này, mỗi cạnh thể hiện sự xung đột với mã sửa lỗi e . Đồ thị như vậy được gọi là đồ thị xung đột. Theo cấu trúc của đồ thị, một mã sửa lỗi tương đương với một tập ổn định trong G . Vì vậy mã sửa lỗi lớn nhất có thể tìm được thông qua việc giải bài toán tập độc lập lớn nhất trong đồ thị G vừa đề cập. Các cận dưới tốt của kích thước mã là điều có ý nghĩa đặc biệt cho các mã bất đối xứng, chẳng hạn như các mã sửa lỗi trong kênh Z ( các thành phần khác không của mọi véc tơ có thể thay đổi từ 1 đến 0). Vì điều này, một số phương pháp phân vùng đã được đề xuất, bằng cách phân vùng tập ổn định nhỏ nhất trên đồ thị xung đột [4]. Việc tìm kiếm các cận dưới tốt cho kích thước mã như trên và thuật toán phân vùng tập ổn định phù hợp là một thách thức cần thiết phải giải quyết. Thách thức 2: (Thuật toán cho các đồ thị xung đột trong lý thuyết mã) Thiết kế thuật toán hiệu quả cho bài toán phân vùng tập ổn định tối thiểu phù hợp với đồ thị xung đột ứng dụng trong lý thuyết mã. Một số ví dụ khác trong đó phân vùng clique tối thiểu được sử dụng như những cận dưới là các bài toán phủ bắt buộc, trong đó tập các điểm yêu cầu phải được phủ bởi tập điểm tiềm năng. Như bài toán vị trí xe cứu thương hay bài toán lát ỨNG DỤNG TRONG BÀI TOÁN SO KHỚP CẤU TRÚC PHÂN TỬ Trong ngành công nghiệp dược phẩm và hoá chất nông nghiệp, bài toán xác định mối quan hệ cấu trúc giữa các cặp cấu trúc phân tử ba chiều là một bài toán quan trọng. Những cấu trúc phân tử ba chiều có thể được thể hiện bằng đồ thị. Ví dụ đối với cấu trúc Protein, các đỉnh của đồ thị được cho bởi các thành phần cấu trúc thứ cấp xoắn α và phiếm nếp gấp β , trong khi các cạnh được định nghĩa thông qua liên kết góc và khoảng cách giữa chúng [5]. Hơn nữa các đỉnh và cạnh đều được gán nhãn tương ứng với các kiểu nguyên tử và khoảng cách giữa các nguyên tử. Cho một cặp đồ thị đã được gán nhãn ( ) ( )1 1 1 2 2 2, ; ,G V E G V E= = . Khi đó xây dựng đồ thị C , gọi là đồ thị tương ứng của hai đồ thị trên, như sau: Nếu hai đỉnh 1 1 2 2,v V v V∈ ∈ có cùng nhãn thì cặp 1 2v v là một đỉnh của C ; Hai đỉnh 1 2v v và ' ' 1 2v v có liên kết cạnh nếu các cạnh ( )'1 1 1,v v E∈ và ( )'2 2 2,v v E∈ có nhãn giống nhau. Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 12 Với một cặp cấu trúc phân tử ba chiều, một đồ thị con chung lớn nhất trong hai đồ thị tương ứng của chúng liên hệ đến tập lớn nhất các nguyên tử có khoảng cách phù hợp. Vì vậy đồ thị con chung lớn nhất là một độ đo sự tương tự cấu trúc và cho thông tin quan trọng về hai phân tử. Theo cách xây dựng đồ thị C tương ứng từ hai đồ thị mô tả hai phân tử, ta nhận thấy đồ thị con giữa hai đồ thị 1 2,G G tương đương với clique trong đồ thị C . Vì vậy ta có thể tìm đồ thị con chung lớn nhất giữa hai đồ thị 1 2,G G thông qua việc giải bài toán clique lớn nhất trong đồ thị C tương ứng. Thách thức 3 (Thuật toán cho đồ thị tương ứng với mật độ thấp): Thiết kế thuật toán hiệu quả cho bài toán clique lớn nhất trên đồ thị tương ứng phát sinh từ bài toán so khớp cấu trúc phân tử hoá học ba chiều. Những thách thức tương tự cũng xảy ra khi tính toán clique lớn nhất cho bài toán ghép protein, trong đó người ta muốn tìm hiểu xem hai loại protein hình thành liên kết ổn định hay không, hoặc để so sánh các cấu trúc protein. [7] GIẢ THUYẾT KELLER Giả thuyết Keller liên quan đến giả thuyết Minkowski, trong đó nói rằng bài toán lưới lát n
bởi các khối đơn vị, tồn tại hai khối cùng (n-1) mặt. Định lý Minkowski đã được chứng minh bởi Hajos năm 1950. Keller đề xuất tổng quát hoá định lý Minkowski bằng cách bỏ giả sử lưới. Trong thực tế, Prron đã chứng minh điều này là đúng với 6n ≤ . Tuy nhiên với 8n ≥ , giả sử lưới là cần thiết và đã được chứng minh bởi Lagarias. Giả thuyết Keller vẫn còn là vấn đề mở với 7n = . Sau nhiều năm, các tranh luận về giả thuyết Keller vẫn chưa kết thúc. Qua đó, nhiều lớp đồ thị đối với bài toán clique lớn nhất cũng được phát sinh. Corradi và Szabo [6] đã xây dựng đồ thị gọi là đồ thị Keller nΓ với n +∈
. Tập đỉnh của nΓ là các véc tơ với độ dài n , với giá trị 0, 1, 2 hoặc 3. Hai đỉnh bất kỳ có kết nối cạnh khi và chỉ khi trong n toạ độ, có đúng hai toạ độ khác nhau. Đồ thị Keller là đồ thị dày đặc với kích thước clique bị chặn bởi 2n . Corradi và Szabo đã chứng minh rằng, tồn tại phản ví dụ về giả thuyết Keller khi và chỉ khi nΓ có clique kích thước bằng 2n . Với sự giúp đỡ của những kết quả này, Lagarias và Shor đã chỉ được phản ví dụ cho trường hợp số chiều 10n = . Tương tự, Mackey đã xây dựng được clique với số chiều bằng 8, và chứng minh giả thuyết Keller không đúng khi 8n ≥ . Tuy nhiên trong trường hợp 7n = vẫn là vấn đề mở, và có thách thức sau: Thách thức 4 ( Bài toán mở [6]) Với đồ thị Keller 7Γ , tìm clique lớn nhất có kích thước bằng 128 hoặc chứng minh không tồn tại clique như thế. KẾT LUẬN Chúng tôi đã hệ thống các ứng dụng dẫn tới các bài toán cliques, tựa clique, phân vùng clique trên các đồ thị lớn. Cấu trúc và tính chất của các đồ thị này có những điểm khác nhau. Nhưng nói chung kích thước và mật độ của chúng đều lớn. Điều này gây khó khăn cho việc thiết kế các thuật toán phù hợp với mỗi bài toán để có thể giải quyết chúng hiệu quả. TÀI LIỆU THAM KHẢO [1]. Hayes, B.: Graph Theory in Practice: PartI. American Scientist 88(1), 9(2000) [2]. Nanavati et all: Analyzing the Structure and Evolution of Massive Telecom Graphs. IEEE Trans actions on Knowledge and Data Engineering 20(5),703– 718(2008) [3]. Abello, Pardalos, Resende: On Maximum Clique Problems in Very Lagre Graphs. External Memory Algorithms .DIMACS Series, pp.119– 130, (1999) [4]. vanPul, et all: New lower bounds for constatn weight codes. IEEE Trans. Inform. Theory 35, 1324–1329 (1989) [5]. Mitchell et all : Use of techniques derived from Graph theory to compare secondary structure motifs in proteins. J.Mol.Biol.212, 151 (1990) [6]. Corradi and Szabo : A Combinatorial Approach for Keller’s Conjecture. Periodica Math. Hung. 21(2), 95–100 (1990) [7]. Butenko, S.,Wilhelm, W.: Clique-detection models in computational biochemistry and genomics. Euorpean Journal of Operational Research 173,1–17 (2006) Đàm Thanh Phương và Đtg Tạp chí KHOA HỌC & CÔNG NGHỆ 102(02): 9 - 13 13 SUMMARY THE MAXIMUM CLIQUE PROBLEM – APPLICATIONS AND COMPUTATIONAL CHALLENGES Dam Thanh Phuong*, Ngo Manh Tuong, Khoa Thu Hoai College of Information and Communication Technology - TNU Maximum clique is a classical problem of graph theory and have many applications. Many problems in social, biology and finance networks resolved through finding cliques. Clique partitions and clique have also been used as a clustering or data classification tools. However, the actual problem is often modeled by a very large graph and requires large data storage memory for implementation of algorithms. In this paper, we discuss four applications and identify computational challenges which are both of theoretical and practical. Keywords: Cliques, quasi – cliques, clique partitions, independent set, maximum clique problem, maximum independent set. Ngày nhận bài:8/11/2012, ngày phản biện:19/12/2012, ngày duyệt đăng:26/3/2013 * Tel: 0912 998749, Email: dtphuong@ictu.edu.vn