Бидний тухай
Багш ажилтан
Node ranking in graphs is a critical task in many applications such as social network analysis, recommendation systems, and infrastructure networks. Among various centrality measures, betweenness centrality is particularly important as it identifies the most influential nodes in terms of their control over information flow. Traditional algorithms for computing betweenness centrality often suffer from high computational complexity, especially in large-scale networks. In this paper, we investigate the impact of a simplified graph neural network model on node ranking based on betweenness centrality. Our results demonstrate that the proposed models offer a promising alternative to traditional methods and GNN-Bet model from Maurya et al [8], significantly improving computational efficiency while maintaining a competitive accuracy in node ranking.
We propose a novel Growing Stochastic Block Model (GSBM) that integrates explicit community structure with a preferential attachment (PA) mechanism, effectively capturing the modular organization and heavy-tailed degree distributions frequently observed in large-scale social and information networks. Unlike classical Stochastic Block Models (SBMs), which assume a fixed node set and static probabilistic edge formation rules, our GSBM introduces a dynamic growth process. New nodes sequentially join communities according to block-size probabilities sampled from a power-law distribution, forming connections based on block-aware preferential attachment that favors higher-degree nodes both within and across communities. This hybrid approach preserves the distinctive community characteristics of SBMs—dense intra-block and sparse inter-block connectivity—while naturally generating influential hub nodes typical of PA-based models, resulting in realistic power-law degree distributions and short average path lengths. We formally define the generative process, analyze its expected structural properties (including degree distribution and community modularity), and validate through simulations that the GSBM significantly outperforms traditional SBMs in replicating critical real-world network phenomena, such as disassortative mixing patterns and high-degree hubs bridging distinct communities. Our findings underscore the utility of the GSBM as a robust and realistic framework for evaluating community detection algorithms, studying diffusion dynamics, and analyzing network robustness in complex, evolving networks. Key Words: Network generation, Preferential attachment, Social Networks, Stochastic Block Model
Сүлжээнээс бүлэг илрүүлэхэд (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.
