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

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@cit.ctu.edu.vn, dkaki@irit.fr 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 trúc đồ thị có thể mô hình hóa các loại dữ liệu thể hiện dưới dạng tập các đối tượng và quan hệ giữa các đối tượng đó. Rất nhiều chiến lược được đề xuất cho việc vẽ đồ thị tự động. Các giải thuật phổ biến nhất đều dựa trên giải pháp tương đối đơn giản đó là mô hình lực có hướng (forced-directed model) [5, 6] và cho kết quả tốt (ít sự giao cắt giữa các cung, cấu trúc cân đối) đối với các đồ thị có kích thước nhỏ (vài trăm đỉnh). Một số giải thuật khác [7, 8] dựa trên quá trình tính toán nhiều pha đã chứng tỏ khả năng thích ứng với các đồ thị có kích thước lớn (vài nghìn đỉnh). Các giải thuật này khá thành công trong việc hiển thị cấu trúc nhóm của đồ thị khi mà các nhóm này được sinh ra một cách “tự nhiên” dựa trên cấu trúc nội tại của đồ thị. Tuy nhiên các giải thuật được xây dựng dựa trên các giải pháp vừa nêu “luôn không thành công” trong việc hiển thị cấu trúc nhóm được xây dựng dựa trên thuộc tính siêu dữ liệu của các đỉnh. Một yếu tố quan trọng trong việc hiển thị một đồ thị phân nhóm (clustered graph) đó là các đỉnh của cùng một nhóm phải gần nhau và tách biệt với các đỉnh thuộc vào các lớp khác. Vùng bao phủ bởi các nhóm phải không trùng nhau và là các vùng bao lồi (convex hull). Chúng ta có thể tách biệt hai trường hợp: vùng bao phủ của mỗi nhóm được định nghĩa sẵn, vùng bao phủ của mỗi nhóm được tính toán bởi giải thuật. Thật vậy, trong đa phần các trường hợp, vùng bao phủ của mỗi nhóm đã được định nghĩa trước. Ví dụ như trong lĩnh vực thiết kế mạch điện, số lượng lớn các linh kiện thuộc về một board mạch sẽ phải được bố trí trong một vùng không gian giới hạn. Trong bài báo này, chúng tôi đề xuất một mô hình lực cho phép vẽ đồ thị phân nhóm đảm bảo các điều kiện rằng mỗi nhóm sẽ được hiển thị bên trong một vùng bao lồi phân biệt với vùng hiển thị của các nhóm khác cũng như tối ưu hóa hình thức hiển thị của từng nhóm. Trong phạm vi nghiên cứu này, chúng tôi giả sử rằng các nhóm đã được tính toán và biết trước, có thể là được tính toán bởi một giải thuật phân nhóm đồ thị nào đó (dựa theo cấu trúc liên kết giữa các đỉnh) hoặc tính toán dựa trên dữ liệu thuộc tính gắn kết với các đỉnh của đồ thị. Mô hình chúng tôi đề xuất cũng phải cho kết quả tốt trong cả hai trường hợp: có ràng buộc hoặc không có ràng buộc về vùng hiển thị cho mỗi nhóm. Mô hình mà chúng tôi đề xuất sẽ phải tạo ra được một “bức vẽ” sao cho người dùng có thể sử dụng nó để xem xét và khám phá các yếu tố tiềm ẩn bên trong dữ liệu thông qua việc nhận rõ được các liên kết liên nhóm và các liên kết nội tại trong mỗi nhóm. Mô hình chúng tôi đề xuất là một sự điều chỉnh của mô hình được đề xuất bởi [5] và tiếp nối công trình nghiên cứu được giới thiệu trong [9]. Một trong số những ưu điểm nổi bật của mô hình do chúng tôi đề xuất so với những mô hình khác đó là sự thành công trong việc “tách rời” các nhóm ngay cả trong trường hợp số lượng cung gắn kết các đỉnh trong một nhóm là rất thấp. Phần còn lại của bài báo được tổ chức như trình bày sau đây. Trong phần II chúng tôi sẽ nêu định nghĩa về cấu trúc đồ thị phân nhóm và tổng quan các vấn đề về vẽ đồ thị tự động. Mô hình lực cho biểu diễn đồ thị phân nhóm được trình bày trong phần III. Phần IV sẽ mô tả kết quả đạt được của mô hình đề xuất thông qua 3 ví dụ áp dụng. Trong trường hợp có ràng buộc về vùng hiển thị của mỗi nhóm, trước tiên chúng tôi sử dụng dữ liệu về mạng trích dẫn (citation network) rút trích từ [10], thực hiện phân tích Hub và Authority và dùng giá trị Authority của mỗi đỉnh để vẽ đồ thị theo kiến trúc phân tầng. Tiếp theo chúng tôi sử dụng dữ liệu liên quan đến khoảng 1000 hợp đồng [11] mua bán ruộng đất giữa nông dân và các lãnh chúa trong vùng Lot, một vùng nhỏ ở miền Tây Nam nước Pháp và hiển thị chúng 3 tr lu A p P v B l n s m th l c n d m k b m n c k đ n v tr c c đ n p “ c c c 50 ên bản đồ Ko ận một số ưu . Cấu trúc đ Đồ thị hân nhóm CG là phân nhóm ới số nhóm là . Các công t Vẽ đồ t ại đây đã có n hư: giải pháp ố chỉ phù hợp Eades [ ô hình lực. M ép và các cu ò xo và vị trí hiến lược này hiều nhất tron ài đường đi n ỗi đỉnh cho p hái niệm “co ố trí các đỉnh Các giả à ở giai đoạn hiều pha dựa hỉ bao gồm b hởi tạo vị trí ược tính ổn đ Trong n ày có thể đượ ẽ đồ thị phân ong không gi ủa mỗi nhóm ác đỉnh khác ược áp dụng hóm giải phá hân nhóm củ khám phá” cấ Giải ph ạnh: cách thứ ác công trình ác cung kết n honen. Cả 2 nhược điểm ồ thị phân nh G là cặp (V, E là một bộ ba xác lập trên 3. rình có liên q hị tự động là hiều công trì vẽ trực giao ( với cấu trúc 15] phát triển ô hình này x ng được xem của các đỉnh , Kamada và g cộng đồng gắn nhất) giữ hép hai đỉnh oling tempera ở lần lặp sau i pháp trên, t khởi tạo vị t trên phép ph a phần tử. Ở và dịch chuy ịnh của giải th gữ cảnh đồ t c xếp vào ba nhóm trong an hai chiều v . Chuang [18] trong nhóm đ cho trường h p vừa trình b a đồ thị (có th u trúc bên tro áp cho bài toá c định nghĩa c nêu trên định ối đến các đỉn ví dụ trên đề của mô hình đ óm ), trong đó V (V, E, P), tro V. Số phần t uan vấn đề nghiên nh nghiên cứu orthogonal dr đặc biệt như c một trong số em đồ thị như như các lò xo tại trạng thái Kawai [6] cũ . Kamada và a hai đỉnh. Tr sẽ đẩy nhau t ture” nhằm g đã tốt hơn các uy nhiên, khô rí của các đỉn ân tích tập co mỗi pha chỉ c ển. Chính ch uật khi mà ch hị phân nhóm nhóm tiếp cậ không gian b à biểu diễn b đề xuất giải ể thực hiện v ợp vùng bao ày, Balzer [19 ể là cấu trúc ng của nhóm n vẽ đồ thị ph ác nhóm cũn nghĩa nhóm h ngoài nhóm C1 u cho thấy tín ề xuất cùng đ II. T là tập hữu h ng đó V là tậ ử của P chính Hình 1. Min cứu của cả l được tiến h awing) [12], ấu trúc cây [1 các chiến lượ là một cấu tr kết nối các v cân bằng (có ng như Fruc Kawai đề xuấ ong khi đó Fr hay vì chỉ hú iảm khoảng c h bố trí ở lần ng có được s h được khởi n độc lập lớn ó các đỉnh kh iến lược này ỉ có ba đỉnh ( , không có q n đặc trưng đư a chiều dựa t a chiều của đồ pháp bổ sung iệc “níu giữ” hiển thị của ] đề xuất các phân cấp - câ tương ứng đư ân nhóm mà g như cách th là tập hợp cá . Tuy nhiên đ h hiệu quả c ịnh hướng ng ỔNG QUAN ạn các đỉnh (n p hữu hạn các là số nhóm c h họa đồ thị ph ĩnh vực toán h ành. Một vài giải pháp vẽ t 4]. c vẽ đồ thị đư úc cơ học tron iên bi. Các đ mức năng lượ hterman and R t lực hút của uchterman an t nhau khi có ách dịch chuy lặp trước. ự ổn định tron tạo một cách nhất (maxim ông thuộc tập đã đẩy nhanh pha đầu tiên) uá nhiều công ợc đề xuất b rên hướng tiế thị phân nhó một đỉnh giả các đỉnh thu mỗi nhóm đư h tiếp cận ph y) sẽ được biể ợc chọn. chúng tôi đề x ức tác động củ c đỉnh với rấ iều này khôn C2 P ủa mô hình m hiên cứu tron út) và E ⊆ V đỉnh (nút), E ủa G. Hình 1 ân nhóm ọc và khoa h trong số đó p heo đường trò ợc sử dụng n g đó các đỉnh ỉnh sẽ di chuy ng nhỏ nhất) eingold [5] các lò xo sẽ p d Reingold bổ cung nối. Bên ển tối đa sau g việc tạo ra ngẫu nhiên. G al independen các đỉnh đã tốc độ thực được khởi tạo trình nghiên ởi [17], [18] v p cận chia để m sẽ là sự tổ cho mỗi nhóm ộc cùng một ợc người dù ân cấp cho v u diễn. Tại m uất phân biệt a lực lên sự d t nhiều cung g phải lúc nà C3 Trươn à chúng tôi đ g tương lai. x V là tập hữ ⊆ V x V là t minh họa cấ ọc máy tính. hù hợp với cấ n (circular lay hiều nhất tron của đồ thị đư ển theo lực h chính là hình đã đề xuất 2 hải tỷ lệ với sung khái ni cạnh đó nhó mỗi lần lặp d các hình vẽ ajer [16] đề t set filtration xác định vị t thi của giải t vị trí ngẫu n cứu được th à [19]. Ho [1 trị. Mỗi nhó hợp các hình cùng lực hú nhóm ở gần n ng định nghĩ ấn đề vẽ đồ t ỗi thời điểm với các giải p ịch chuyển c kết nối các đỉ o cũng đúng t g Quốc Định, Ta ề xuất. Phần u hạn các cu ập hữu hạn c u trúc đồ thị p Trong gần 2 t u trúc chung out) [13] tro g cộng đồng ợc xem như út/đẩy phát si vẽ của đồ th giải pháp đượ khoảng cách ệm năng lượn m tác giả cũn ựa trên giả t của cùng một xuất giải phá ) trong đó tậ rí ở pha liền t huật cũng như hiên ban đầu. ực hiện. Các 7] đề xuất ph m sẽ được vẽ vẽ không gian t mạnh từ đỉn hau. Giải ph a trước. Khôn hị phân nhóm người dùng c háp trước đó ủa các đỉnh. T nh trong nhó rong thực tế v oufiq Dkaki V sẽ thảo ng. Đồ thị ác cung và hân nhóm hập kỷ trở của đồ thị ng khi một với tên gọi các viên bi nh bởi các ị. Dựa trên c sử dụng đồ thị (độ g điện vào g bổ sung huyết cách đồ thị khi p bao gồm p nhỏ nhất rước được đảm bảo công trình ương pháp riêng biệt hai chiều h này đến áp đề xuất g như hai . Cấu trúc ó thể chọn ở hai khía ác giả của m và rất ít ì các đỉnh MÔ HÌNH LỰC CHO BIỂU DIỄN ĐỒ THỊ PHÂN NHÓM 351 có thể được nhóm lại theo một ràng buộc bất kỳ nào đó chứ không phải chỉ dựa trên bản chất mối liên hệ giữa các đỉnh. Ví dụ như đối với mạng trích dẫn (citation network), các nhóm có thể được xây dựng dựa trên sự tương đồng về mặt địa lý giữa các đỉnh (tác giả của các bài báo thuộc cùng một trường, một quốc gia ). Và trong trường hợp như thế thì các giải pháp đề xuất ở trên không cho kết quả mỹ mãn. Chúng tôi cũng tin rằng, một bản vẽ “đẹp” cho đồ thị phân nhóm cần đáp ứng các yêu cầu sau: • Mỗi một nhóm phải được bố trí trong một vùng bao lồi • Vùng bao lồi của các nhóm không bao phủ nhau • Giảm đến mức tối thiểu sự giao cắt giữa các cung kết nối các đỉnh trong cùng một nhóm • Giảm thiểu sự trùng lặp về vị trí giữa các đỉnh III. MÔ HÌNH ĐỀ XUẤT Mô hình mà chúng tôi đề xuất là sự điều chỉnh của mô hình lực đề xuất bởi [5] và cũng bao gồm nhiều lần lặp với hai bước chính ở mỗi lần lặp: tính toán lực hút và lực đẩy cho mỗi cặp đỉnh, tính khoảng cách và hướng dịch chuyển của mỗi đỉnh dựa trên khoảng cách dịch chuyển tối đa. Chúng tôi cũng sử dụng khái niệm “cooling temperature” đã trình bày trong [5] để giảm khoảng cách dịch chuyển tối đa qua mỗi lần lặp. Ý tưởng của việc giảm giá trị khoảng cách dịch chuyển này đó là “bản vẽ” sẽ tốt hơn sau mỗi lần lặp vì thế việc dịch chuyển sẽ phải nhỏ dần sau mỗi lần lặp. Điểm điều chỉnh quan trọng so với [5] đó là chúng tôi phân biệt 2 loại lực: lực tác động bởi đỉnh thuộc cùng một nhóm và lực tác động bởi đỉnh khác nhóm đồng thời bổ sung lực hút giữa các đỉnh không có cung nối của cùng một nhóm (cung giả). • Nội lực: lực hút/đẩy giữa các đỉnh thuộc cùng một nhóm • Ngoại lực: lực hút/đẩy giữa các đỉnh khác nhóm • Lực giả: lực hút giữa các đỉnh không có cung nối thuộc cùng một nhóm. Các lực được định nghĩa thông qua khái niệm khoảng cách tối ưu. Khoảng cách tối ưu là khoảng cách giữa các đỉnh không có cung nối và được định nghĩa như sau ݋݌ݐܦ݅ݏݐ ൌ ඨkích thước vùng hiển thị số đỉnh của đồ thị Nếu gọi fa, fr lần lượt là lực hút và lực đẩy và d là khoảng cách euclide giữa hai đỉnh, khi đó fa và fr có thể định nghĩa như sau: fa(d) = d2/optDist fr(d) = -optDist2/d Trong mô hình chúng tôi đề xuất 2 loại lực (nội lực và ngoại lực) vì thế cần định nghĩa 2 loại khoảng cách tối ưu: optDist – khoảng cách tối ưu giữa các đỉnh không thuộc cùng nhóm và optDistCluster – khoảng cách tối ưu giữa các đỉnh thuộc cùng một nhóm. Và chúng tôi cũng tin rằng khoảng cách giữa các đỉnh thuộc cùng nhóm phải nhỏ hơn khoảng cách giữa các đỉnh thuộc các nhóm khác nhau (optDist = a * optDistCluster với a > 1) vì kích thước vùng hiển thị của mỗi nhóm sẽ nhỏ hơn kích thước vùng hiển thị toàn bộ đồ thị. Khi chọn optDist < optDistCluster chúng tôi giả thuyết rằng các đỉnh bên ngoài nhóm sẽ ít có tác động đến sự dịch chuyển của một đỉnh hơn là các đỉnh thuộc cùng nhóm. Một vấn đề nữa cũng cần được quan tâm đó là các lực giả (lực hút) sẽ phải có cường độ nhỏ hơn lực hút nội lực. A. Vùng hiển thị cho nhóm không được định nghĩa trước Như đã đề cập ở phần trên, trong trường hợp này chúng tôi bổ sung thêm các cung giả gắn kết các đỉnh thuộc cùng một nhóm nhưng không có cung kết nối. Việc bổ sung các cung giả này cho phép níu giữ các đỉnh thuộc cùng một nhóm ở gần nhau. Tuy nhiên, bên cạnh việc thể hiện được cấu trúc phân nhóm của đồ thị thì cấu trúc nội tại của mỗi nhóm cũng phải được quan tâm. Thật vậy cách biểu diễn mỗi nhóm trong đồ thị phân nhóm sẽ là tối ưu nếu như nó được biểu diễn như là một đồ thị riêng lẻ. Để đảm bảo được điều này thì các lực giả cần có trọng số thấp hơn so với các lực thật. Nói một cách khác, việc bổ sung các cung giả sẽ phải không gây quá nhiều tác động đến cấu trúc thật của nhóm. Trong mô hình của chúng tôi, cường độ của các lực giả sẽ được tính toán dựa trên tỷ lệ cung giả so với cung thật của đồ thị. Hình 2 mô tả các loại lực sẽ được tính toán trong quá trình dịch chuyển các đỉnh. Phần trên của hình minh họa đồ thị cần được vẽ với 2 nhóm và các cung nối như hình. Phần hình bên dưới minh họa cho các loại lực hút sẽ tác động lên từng đỉnh khi áp dụng mô hình mà chúng tôi đề xuất. Giữa 2 đỉnh luôn tồn tại lực đẩy cho dù là có hay là không có cung nối, để đơn giản các lực này sẽ không minh họa trong hình 2. 3 B h s c ứ đ v th đ C 52 . Vùng hiển Trong t ợp ứng dụng ung các cung òn cần thiết. ng. Lực đẩy iểm, do có nh ùng hiển thị. iểu (khoảng ường biên và • = ∞ n • = optD Hình 3 . Giải thuật Tham s Đ V n Kết qu Giải th → trườ Khởi tạ → trườ Khởi tạ while te for v → trư thị được định rường hợp nà mà hầu như giả nhằm tạo Thay vào đó này sẽ mạnh iều lực đồng Để tránh trườ cách dịch chu d là khoảng c ếu d < optDis istCluster/k3 minh họa việc ố đầu vào ồ thị phân n ùng hiển th hóm (tùy chọ ả Hình vẽ củ uật ng hợp vùng h o ngẫu nhiên ng hợp vùng h o vị trí các đỉn mperature > ∈ V do begin ờng hợp vùng Hình 2. M nghĩa trước y thì vùng hiể chưa có công nên các lực h sẽ có các lực khi khoảng cá thời tác động ng hợp này, yển tối đa tại ách từ đỉnh đ tCluster bổ sung các Hìn hóm CG trong ị (vùng hình n). a đồ thị (tạo iển thị không vị trí của các iển thị được h bên trong v 1 begin hiển thị đượ ô hình lực cho n thị (vùng b trình nghiên út giả cho cá đẩy giữa đư ch từ đỉnh đế lên trên một khi khoảng cá mỗi bước lặp ến đường biên lực đẩy từ biê h 3. Minh họa t đó các đỉnh chữ nhật xác độ x, y của m được định ng đỉnh định nghĩa ùng hiển thị c định nghĩa vùng hiển thị k ao lồi) của m cứu nào trướ c đỉnh thuộc c ờng biên của n đường biên đỉnh nên sẽ d ch từ đỉnh đế ) thì lực đẩy thì ff được đ n ác dụng lực đẩ của đồ thị đã định bởi đỉn ỗi đỉnh của đồ hĩa của lớp tương lực đẩy từ nội lực ngo lực nội hông được địn ỗi nhóm được c đây đề cập ùng một nhóm vùng hiển thị là nhỏ và ng ẫn đến trườn n đường biên sẽ được nâng ịnh nghĩa như y với đường biê được phân thà h trên bên trá thị) ứng biên ại lực giả lực Trươn h nghĩa định nghĩa tr đến. Với trườ nhưng khôn với các đỉnh ược lại. Tuy g hợp lực đủ bằng hoặc n lên cực đại. N sau: n nh các nhóm i và chiều d g Quốc Định, Ta ước. Đây là m ng hợp này t g có cung nố bên trong nh nhiên tại cùn lớn để đẩy đỉ hỏ hơn khoản ếu gọi ff là lự khác nhau (b ài, chiều rộng oufiq Dkaki ột trường hì việc bổ i là không óm tương g một thời nh ra khỏi g cách tối c đẩy của ắt buộc). ) của mỗi Mt đ b k n h m o th A m n n c Ô HÌNH LỰC C end for (u end → trư for (u end for v end giảm end Cũng g ôi tính toán tá ỉnh theo hàm an đầu khoản hoảng cách d Quá trìn hóm không xá iển thị của mỗ ỗi nhóm. Ở b ptDistCluster, Trong p i của mô hìn . Ví dụ 1 - M Ví dụ đ ỗi đỉnh biểu hóm như trên hư hình 4. Ch ấu trúc phân n HO BIỂU DIỄN Tính lực đ for u ≠ v i tí end , v) ∈ E do b tính lực hú ờng hợp vùng , v) ∉ E và u, tính lực hú ∈ V do begin tổng hợp c dịch chuy giá trị temper iống như mô c động của to cooling temp g cách tối đa ịch chuyển tố h dịch chuyển c định thì các i nhóm được ước tính toán nếu là trường hần này, chún h mà chúng tô ạng cộng tác ầu tiên chúng diễn cho một không phải úng ta có thể hóm của đồ t ĐỒ THỊ PHÂN ẩy từ biên lên n V do begin nh lực đẩy tá egin t tác dụng lên hiển thị khô v thuộc cùng t giả tác dụng ác lực lên v ển v dựa trên ature hình gốc, mô àn bộ các lự erature. Hàm này có thể đư i đa có thể giả khởi nguồn từ đỉnh được khở định nghĩa trư lực tác động hợp thuộc hai g tôi giới thi i đề xuất. tôi sử dụng đ người cụ thể là vấn đề chín dễ dàng nhận hị. Hìn NHÓM đỉnh v c dụng trên v u và v ng được định nhóm do beg lên u và v hàm cooling t hình chúng tô c lên trên mỗ cooling temp ợc xác lập giá m đi 1. Giá tr cấu hình khở i tạo vị trí ng ớc thì các đỉn lên mỗi đỉnh, nhóm khác nh IV. KẾT Q ệu và thảo luậ ó là một mạn (nghiên cứu v h. Trước tiên thấy kết quả h 4. Hình vẽ sử và u nghĩa in emperature i đề xuất là m i đỉnh. Tiếp th eratue xác địn trị bằng với k ị temperature i tạo ngẫu nhi ẫu nhiên trong h phải được k nếu là đỉnh th au thì sử dụng UẢ VÀ ĐÁN n kết quả thôn g cộng tác ba iên). Ở ví dụ , chúng tôi á khi áp dụng m dụng mô hình ột quá trình l eo là tính to h khoảng các hoảng cách t đơn giản có t ên lúc đầu. Đố phạm vi khun hởi tạo vị trí b uộc cùng một khoảng cách H GIÁ g qua ba ví d o gồm 32 đỉn này việc bằng p dụng mô hì ô hình [5] là đề xuất bởi [5 ặp bao gồm 2 án khoảng cá h dịch chuyể ối ưu giữa các hể là số lần lặ i với trường h g vẽ. Ngược l ên trong vùn nhóm thì sử tối ưu optD