Бидний тухай
Багш ажилтан
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) ашиглах хувьслын алгоритмыг зохиомжлов. ЧОБ-д өргөн ашиглагддаг зургаан бодит сүлжээн дээр алгоритмын ажиллагааг туршиж, гурван аргатай харьцуулан, гүйцэтгэлийг үнэллээ. Дэвшүүлж буй алгоритм богино хугацаанд сайн шийд гаргаж байгааг туршилтын үр дүн харуулав.
Сүлжээний нийт ирмэгийн квадрат язгууртай тэнцүү тоогоор устгах “Girvan-Newman” алгоритмын өөрчилсөн хувилбарыг (цаашид GN-M гэж нэрлэсэн) үндсэн алгоритмтай нь харьцуулж, үр дүнг танилцуулна. “Girvan-Newman” алгоритм нь сүлжээнээс бүлэг илрүүлэхдээ сүлжээний бүх ирмэгийн хоорондын төв (betweenness centrality)-ийн эрэмбийг бодож хамгийн өндөр эрэмбэтэй ирмэгийг устгана. Эхний ирмэгийг устгасны дараа үүссэн сүлжээний ирмэгүүдийн хоорондын төвийн эрэмбийг дахин бодож хамгийн өндөр хоорондын төвийн эрэмбэтэй ирмэгийг устгана. Энэ үйлдлийг өгөгдсөн тооны бүлэг илрүүлэх хүртэл давтах байдлаар ажиллана. “Girvan-Newman” алгоритм нь ирмэг устгах бүрдээ хоорондын төвийн эрэмбийг бодсоноор хугацаа их зарцуулдаг (О (m2n)) учир олон ирмэгтэй том сүлжээнд ашиглахад хүндрэлтэй юм. Алгоритмын хурдыг сайжруулах зорилгоор нэг удаа бодсон хоорондын төвийн эрэмбийг ашиглан нийт ирмэгийн тооноос хамааруулж тодорхой тоогоор устгана. Өргөн хэрэглэгддэг таван нийгмийн сүлжээний (well-known social networks) өгөгдлийг ашиглан GN-M алгоритмаа тестэлж, “Girvan-Newman” алгоритмтай харьцуулан гүйцэтгэлийг үнэллээ. “Girvan-Newman” алгоритмтай харьцуулахад сүлжээний хэмжээнээс хамаарч хурдыг 2-5 дахин багасгасан үр дүн харуулж байна.
In this work, we tested the global thresholding method, the well-known image segmentation method for separating objects and background from the image on its refined histogram using the distinction neighborhood metric. If the original histogram of image has some large bins which occupy the most density of whole intensity distribution, it is a problem for global methods such as segmentation and contrast enhancement. We refined the histogram to overcome the big bin problem in which sub-bins are created from big-bins based on distinction metric. Median and Otsu thresholding methods are used in our work, and experimental results show that they work more effectively on the refined histograms.
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-н сүлжээний өгөгдлийг ашиглан тестлэв. Туршилтын үр дүнгээс харахад дэвшүүлсэн арга ихэнх сүлжээний хувьд бусад аргаас давуу үр дүн үзүүллээ.
The critical node problem (CNP) removes a limited number of nodes from a network in order to achieve the minimum pair-wise connectivity in the remaining network. In this paper, we present a heuristic algorithm for solving the CNP on planar networks. We propose an efficient method to evaluate the quality of solutions by using special properties of planar networks. This enables us to develop a computationally efficient heuristic algorithm for solving the CNP. The proposed algorithm is tested on randomly generated planar networks. The computational experiments show the superiority of this algorithm compared with other algorithms. Furthermore, we examine how the proposed algorithm can be used for a variant of the CNP, called the cardinality-constrained critical node problem.
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 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 deals a problem with detecting the critical nodes in order to achieve minimum pair-wise connectivity in the residual graph after removing a limited number of nodes from the graph. It is called the critical node detection problem (CNDP). In this paper, we propose a new hybridization scheme of greedy randomized adaptive search procedure (GRASP) with exterior path-relinking. Exterior path-relinking, a recently proposed metaheuristic method, creates paths of successive solutions starting from two highquality solutions to other high quality solutions. A randomly selected solution from the elite solution pool collecting throughout GRASP iterations and the resulting solution from each GRASP iteration are relinked by exterior path-relinking for finding better solutions. The proposed algorithm is assisted on test instances from the literature. Computational experiments demonstrate that the proposed method outperforms other existing algorithms in the area of CNDP.
As the number of objectives increases,the performance of the Pareto dominance-based Evolutionary Multi-objective Optimization( EMO) algorithms such as NSGA-II,SPEA2 severely deteriorates due to the drastic increase in the Pareto-incomparable solutions. We propose a sorting method which classifies these incomparable solutions into several ordered classes by using the decision maker's( DM) preference information.This is accomplished by designing an interactive evolutionary algorithm and constructing convex cones. This method allows the DMs to drive the search process toward a preferred region of the Pareto optimal front. The performance of the proposed algorithm is assessed for two,three,and four-objective knapsack problems. The results demonstrate the algorithm ' s ability to converge to the most preferred point. The evaluation and comparison of the results indicate that the proposed approach gives better solutions than that of NSGA-II. In addition, the approach is more efficient compared to NSGA-II in terms of the number of generations required to reach the preferred point.
