Large-scale　graphs　have　become　prevalent　with　the　advent　of　the　big　data　era.　Distributed　graph　computing　systems　are　commonly　used　for　processing　and　analyzing　large-scale　graphs,　with　graph　partitioning　being　a　key　prerequisite　for　their　efficient　computation.　Graph　partitioning　aims　to　balance　the　load　across　partitions　while　minimizing　the　number　of　cut-edges.　Moreover,　it　should　achieve　high　efficiency　and　scalability.　However,　the　existing　popular　graph　partitioning　algorithms　do　not　fully　take　into　account　the　internal　topology　of　real-world　graphs,　which　affects　the　final　partition　quality　and　convergence.　Meanwhile,　they　easily　fall　into　the　local　optimum　due　to　partition　load　constraints.　This　paper　introduces　a　Novel　Optimized　Balanced　Graph　Partitioning　algorithm　(NOBGP).　First,　we　propose　an　initialization　strategy　based　on　label　propagation　of　core　vertices　to　achieve　initial　partitions　with　good　locality　and　accelerate　convergence.　Second,　we　optimize　the　label　propagation　process　to　ensure　balanced　partitions　and　propose　a　probability-based　disruption　strategy　to　avoid　the　local　optimum.　We　implement　NOBGP　on　the　distributed　graph　computing　framework　GraphX.　Extensive　experimental　results　on　real-world　graphs　show　that　the　proposed　algorithm　is　scalable　and　performs　better　than　the　existing　algorithms.　We　also　run　PageRank　and　Louvain　applications　using　the　graph　partitioning　results　to　demonstrate　the　efficiency　of　our　algorithm.　©　The　Author(s),　under　exclusive　license　to　Springer　Nature　Singapore　Pte　Ltd.　2025.