Бидний тухай
Багш ажилтан
Betweenness centrality (BC) can be an useful tool to analyze big data given that it's represented as a graph. One of the special betweenness centrality, k-betweenness centrality (k-BC), assumes that the identities distanced further than k hops are not likely to exchange information with each other. There are not many works done for k-BC in literature. We designed estimated k-BC algorithm by combining k-BC with other approximate betweenness centrality algorithms to scale the algorithm even further. The complexity of estimated k-BC algorithm is O(s * d^k) where s, d and k are the sample size, average degree and branching factor respectively. We experimented on six widely used dataset and measured both the quality of the node ranking and running time. The result shows that estimated k-BC is highly correlated with BC and 1000 fold faster.
Энэхүү ажлаар сүлжээ (граф)-ний чухал оройн бодлого (ЧОБ)-ыг хувьслын алгоритм (evolutionary algorithm (EA))-аар бодох аргыг судална. ЧОБ нь сүлжээнээс хамгийн цөөн тооны оройг устган, үлдэгдэл сүлжээний хамгийн том холбоост бүрдлийн хэмжээг өгөгдсөн L параметрээс бага байлгах бодлого юм. Сүүлийн жилүүдэд хийгдэж буй өгөгдөлд суурилсан судалгаагаар байгаль, нийгэм дэх сүлжээ (систем) нь бүлэг бүтэц (community structure)-тэй гэдгийг тогтоогоод байна. Энэ ажилд сүлжээний бүлэг бүтцийн мэдээллийг ЧОБ-д ашиглах шинэ аргыг танилцууллаа. Тодруулбал, бүлэг бүтцийн мэдээллийг генийн дүрслэлээр (representation) ашиглах хувьслын алгоритмыг зохиомжлов. ЧОБ-д өргөн ашиглагддаг зургаан бодит сүлжээн дээр алгоритмын ажиллагааг туршиж, гурван аргатай харьцуулан, гүйцэтгэлийг үнэллээ. Дэвшүүлж буй алгоритм богино хугацаанд сайн шийд гаргаж байгааг туршилтын үр дүн харуулав.
Сүлжээнээс бүлэг илрүүлэхэд (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 үед) байгаа нь туршилтын үр дүнгээс харагдав.
Энэхүү ажлаар сүлжээ (граф) -ний чухал оройн бодлого (ЧОБ) -ыг хувьслын алгоритм (evolutionary algorithm (EA)) -аар бодох аргыг судална. ЧОБ нь сүлжээнээс хамгийн цөөн тооны оройг устган, үлдэгдэл сүлжээний хамгийн том холбоост бүрдлийн хэмжээг өгөгдсөн L параметрээс бага байлгах бодлого юм. Сүүлийн жилүүдэд хийгдэж буй өгөгдөлд суурилсан судалгаагаар байгаль, нийгэм дэх сүлжээ (систем) нь бүлэг бүтэц (community structure)-тэй гэдгийг тогтоогоод байна. Энэ ажилд сүлжээний бүлэг бүтцийн мэдээллийг ЧОБ-д ашиглах шинэ аргыг танилцууллаа. Тодруулбал, бүлэг бүтцийн мэдээллийг генийн дүрслэлээр (representation) ашиглах хувьслын алгоритмыг зохиомжлов. ЧОБ-д өргөн ашиглагддаг зургаан бодит сүлжээн дээр алгоритмын ажиллагааг туршиж, гурван аргатай харьцуулан, гүйцэтгэлийг үнэллээ. Дэвшүүлж буй алгоритм богино хугацаанд сайн шийд гаргаж байгааг туршилтын үр дүн харуулав.
The shortest path betweenness value of a node quantifies the amount of information passing through the node when all the pairs of nodes in the network exchange information in full capacity measured by the number of the shortest paths between the pairs assuming that the information travels in the shortest paths. It is calculated as the cumulative of the fractions of the number of shortest paths between the node pairs over how many of them actually pass through the node of interest. It’s possible for a node to have zero or underrated betweenness value while sitting just next to the giant flow of information. These nodes may have a significant influence on the network when the normal flow of information is disrupted. We propose a betweenness centrality measure called collective betweenness that takes into account the surroundings of a node. We will compare our measure with other centrality metrics and show some applications of it.
Энэ ажлаар хоорондын төвийн аргаар өндөр эрэмбэ оногдох оройн дэд олонлогийн сүлжээн дэх нөлөөллийг судална. Оройн дэд олонлогийг устгасны дараа үлдэх сүлжээний бүтэц дэх өөрчлөлтөөр дэд олонлогийн нөлөөг үнэлнэ. Устгах дэд олонлогийг илрүүлэх дөрвөн алгоритмыг тодорхойлж, тэдгээрийн үр дүнг харьцуулан шинжлэв. Хоорондын төвийн аргаар өндөр эрэмбэ оногдсон к оройг нэгэн зэрэг устгах алгоритмыг сүлжээг задлахад үр дүнтэйгээр ашиглах боломжтойг туршилтын үр дүн харуулав.
Сүлжээг Задлах Бодлого нь олонлогт орсон оройнуудыг устгахад сүлжээг жижиг хэмжээтэй, холбоост бүрдлүүд болгон задлах, хамгийн бага хэмжээтэй оройн олонлогийг олдог. Уг бодлого нь нийгэм, биологи, технологийн сүлжээнүүдийн бат бөх чанарыг судлахаас гадна, дутагдалтай бүтцийг судлахад ач холбогдолтой. Сүүлийн жилүүдэд дахин оруулах аргыг сүлжээг задлах бодлогод ашиглах судалгаа хийгдэж эхлээд байна. Гэхдээ дахин оруулах аргын судалгаа дутмаг байна. Энэхүү ажлаар бид нэгэн шинэ дахин оруулах аргыг танилцууллаа. Дэвшүүлсэн аргаа нийгэм, биологи, технологийн төрлийн 13-н сүлжээний өгөгдлийг ашиглан тестлэв. Туршилтын үр дүнгээс харахад дэвшүүлсэн арга ихэнх сүлжээний хувьд бусад аргаас давуу үр дүн үзүүллээ.
Рубикын шооны оптимал алгоритмуудын нэг болох Тистлетвэйтийн 52 үйлдэлт алгоритм нь хайлтын огторгуйг багасгахын тулд Математикийн бүлэг ашигладаг. Энэхүү алгоритм нь урьдаас тооцоолон гаргасан хүснэгтийн тусламжтайгаар шоог эвлүүлдэг бөгөөд зохиогчийн хүснэгт товчхон, ойлгоход хүндрэлтэй байсан ба хүснэгтийн зарим хэсгийг зохиогч зориудаар илэрхий хэмээн үзэж орхисон байсан. Энэхүү ажлын гол зорилго нь уг алгоритмыг хэрэгжүүлэхийн тулд зохиогчийн хүснэгтийг ашиглахгүйгээр төвшний нэвтрэлтээр хэрхэн өөрийн хүснэгтийг үүсгэж болохыг харуулах болно.
Рубикын шооны оптимал алгоритмуудын нэг болох Тистлетвэйтийн 52 үйлдэлт алгоритм нь хайлтын огторгуйг багасгахын тулд Математикийн бүлэг ашигладаг. Энэхүү алгоритм нь урьдаас тооцоолон гаргасан хүснэгтийн тусламжтайгаар шоог эвлүүлдэг бөгөөд зохиогчийн хүснэгт товчхон, ойлгоход хүндрэлтэй байсан ба хүснэгтийн зарим хэсгийг зохиогч зориудаар илэрхий хэмээн үзэж орхисон байсан. Энэхүү ажлын гол зорилго нь уг алгоритмыг хэрэгжүүлэхийн тулд зохиогчийн хүснэгтийг ашиглахгүйгээр төвшний нэвтрэлтээр хэрхэн өөрийн хүснэгтийг үүсгэж болохыг харуулах болно.
