Бидний тухай
Багш ажилтан
Сүлжээнээс бүлэг илрүүлэхэд (community detection) өргөн хэрэглэгддэг, стандарт алгоритм болох GirvanNewman (цаашид GN гэж товчлох) алгоритм, түүний хурдыг сайжруулах боломжуудыг энэ өгүүлэлд авч үзнэ. GN алгоритм нь сүлжээний ирмэгүүдийн хоорондын төв (betweenness centrality)-ийг бодож хамгийн өндөр оноо авсан нэг ирмэгийг устгах, дахин хоорондын төв (цаашид ХТ гэж товчлох) бодож өндөр оноотой ирмэгийг устгах гэх мэтээр ирмэгүүдийг устгаж, бүлгүүдийг илрүүлдэг. GN алгоритмын ажиллах хугацаа нь O(n · m^2) (m-нийт ирмэгийн тоо, n-нийт оройн тоо) учир олон ирмэгтэй том сүлжээнд ашиглахад хүндрэлтэй юм. Алгоритмын хурдыг сайжруулах зорилгоор нэг удаа бодсон ХТ-ийн оноог ашиглан нэгэн зэрэг олон ирмэг устгах, ХТ оноог ойролцоогоор бодох гэсэн хоёр санааг ашиглан GN алгоритмын өргөтгөл дөрвөн хувилбарыг үүсгэв. Сүлжээний ирмэгүүдийг ХТ-ийн оноогоор эрэмбэлж эхний √m оройг нэгэн зэрэг устгах хоёр алгоритм (цаашид GN-2A, GN-2B гэж нэрлэсэн), GN-2A, GN-2B алгоритмуудыг ойролцоо ХТ-ийн оноог бодох аргатай хослуулсан (цаашид GN-3A, GN-3B гэж нэрлэсэн) мөн хоёр хувилбар зохиомжлов. Өргөн хэрэглэгддэг таван сүлжээний өгөгдлийг ашиглан GN-2A, GN-2B, GN-3A, GN-3B алгоритмыг тестэлж, GN алгоритмтай харьцуулан гүйцэтгэлийг үнэллээ. Том сүлжээний хувьд GN алгоритмтай харьцуулахад хурдыг 8-33 дахин сайжруулсан үр дүн харуулж байна.
Сүлжээний хоорондын төв (ХТ)-ийг тооцоолох зарим хувилбар ($k$ хоорондын төв, ойролцоо хоорондын төв)-уудыг харьцуулан, үнэлнэ. k хоорондын төв (k-ХТ) нь сүлжээний хол байрших тоглогчид хооронд мэдээлэл дамжих боломж багатай байдаг шинж чанарыг загварчлах зорилгоор ХТ-ийг тооцоолохдоо k -с хэтрэхгүй урттай замуудын мэдээллийг авч үздэг. Ойролцоо хоорондын төв (ойролцоо ХТ)-ийн судалгаа сүүлийн жилүүдэд эрчимтэй хийгдэж байгаа боловч k-ХТ-ийг ойролцоолох судалгаа дутмаг байна. Бид энэ өгүүллээр $k$-ХТ-ийг түүврийн аргатай хослуулан ойролцоо k хоорондын төв (ойролцоо $k$-ХТ) алгоритмыг зохиомжлов. Ойролцоо $k$-ХТ-ийн алгоритмын хугацааны үнэлгээ нь $O(log^3(n)*d^k)$ байна, энд $n$ оройн тоо, $d$ нь сүлжээний дундаж зэрэг, $k$ нь авч үзэх замын дээд уртыг илэрхийлнэ. Өргөн хэрэглэгддэг гурван сүлжээн дээр туршилтыг гүйцэтгэв. Ойролцоо $k$-ХТ-ийн алгоритмын ($k \ge$ 4 үед) үр дүн нь ХТ-ийн алгоритмын үр дүнтэй өндөр хувийн корреляци-тай бөгөөд дунджаар 1,000 дахин бага хугацаанд ажиллаж ($k$=4, 5 үед) байгаа нь туршилтын үр дүнгээс харагдав.
Энэ ажлаар хоорондын төвийн аргаар өндөр эрэмбэ оногдох оройн дэд олонлогийн сүлжээн дэх нөлөөллийг судална. Оройн дэд олонлогийг устгасны дараа үлдэх сүлжээний бүтэц дэх өөрчлөлтөөр дэд олонлогийн нөлөөг үнэлнэ. Устгах дэд олонлогийг илрүүлэх дөрвөн алгоритмыг тодорхойлж, тэдгээрийн үр дүнг харьцуулан шинжлэв. Хоорондын төвийн аргаар өндөр эрэмбэ оногдсон к оройг нэгэн зэрэг устгах алгоритмыг сүлжээг задлахад үр дүнтэйгээр ашиглах боломжтойг туршилтын үр дүн харуулав.
Өгүүллээр монгол хэлний "ижил үг" буюу бичлэг ижил ч утга нь өөр үгс өгүүлбэрт аль утгаараа орсныг графт суурилсан статистик аргаар тодорхойлохыг оролдлоо. Бид 1.6 сая орчим үгтэй гар тэмдэглэгээт хөмрөгөөс 440 мянга орчим оройтой утгын граф байгуулсан ба уг графаас туршилтын хөмрөгт орсон ижил үгсийн утгыг хайхад 55.4 хувь зөв тодорхойлсон. Энэ нь олон улсын жишигтэй харьцуулахуйц үр дүн юм.
Өгүүллээр монгол хэлний "ижил үг" буюу бичлэг ижил ч утга нь өөр үгс өгүүлбэрт аль утгаараа орсныг графт суурилсан статистик аргаар тодорхойлохыг оролдлоо. Бид 1.6 сая орчим үгтэй гар тэмдэглэгээт хөмрөгөөс 440 мянга орчим оройтой утгын граф байгуулсан ба уг графаас туршилтын хөмрөгт орсон ижил үгсийн утгыг хайхад 55.4 хувь зөв тодорхойлсон. Энэ нь олон улсын жишигтэй харьцуулахуйц үр дүн юм.
This paper presents a random walk based heuristic algorithm for detecting critical nodes in networks. There are a number of methods that are proposed for solving the problem. However, most of them are focused on sparse networks, and therefore studies on methods focusing on denser graphs are still needed. In this paper, we introduce two simple random walk based heuristic algorithms. The performance of the variants is conducted with extensive experiments on datasets from the literature. The result of experiments shows that the proposed algorithms can be competitive with the existing other methods.
This paper presents a graph-based word sense disambiguation(WSD) method for Mongolian and its results. WSD automatically identifying the meaning of ambiguous words in context, is an important stage of text processing. The results indicate that the right combination of similarity metrics algorithms can lead to a performance comparable with the state-of-the-art in unsupervised word sense disambiguation, as measured on hand annotated sentences.
