Ойролцоо k хоорондын төв

Abstract

Сүлжээний хоорондын төв (ХТ)-ийг тооцоолох зарим хувилбар (k хоорондын төв, ойролцоо хоорондын төв)-уудыг харьцуулан, үнэлнэ. k хоорондын төв (k-ХТ) нь сүлжээний хол байрших тоглогчид хооронд мэдээлэл дамжих боломж багатай байдаг шинж чанарыг загварчлах зорилгоор ХТ-ийг тооцоолохдоо k -с хэтрэхгүй урттай замуудын мэдээллийг авч үздэг. Ойролцоо хоорондын төв (ойролцоо ХТ)-ийн судалгаа сүүлийн жилүүдэд эрчимтэй хийгдэж байгаа боловч k-ХТ-ийг ойролцоолох судалгаа дутмаг байна. Бид энэ өгүүллээр k-ХТ-ийг түүврийн аргатай хослуулан ойролцоо k хоорондын төв (ойролцоо k-ХТ) алгоритмыг зохиомжлов. Ойролцоо k-ХТ-ийн алгоритмын хугацааны үнэлгээ нь O(log^3(n)*d^k) байна, энд n оройн тоо, d нь сүлжээний дундаж зэрэг, k нь авч үзэх замын дээд уртыг илэрхийлнэ. Өргөн хэрэглэгддэг гурван сүлжээн дээр туршилтыг гүйцэтгэв. Ойролцоо k-ХТ-ийн алгоритмын (k >=4 үед) үр дүн нь ХТ-ийн алгоритмын үр дүнтэй өндөр хувийн корреляцитай бөгөөд дунджаар 1,000 дахин бага хугацаанд ажиллаж (k∈{4, 5} үед) байгаа нь туршилтын үр дүнгээс харагдав.