There is an undirected weighted graph. The weights are costs.

I would like to find all the k-nearest neighbour. (k or less than k, but more than a specified number)

When you found the most similar connected nodes, you need to "exclude" them from the graph, but taking care of not to lose the connectivity of other nodes relying on them, so maximize the number of k-nearest groups. I wouldn't like to see "n/group size" iteration.

The result must include cost and partition. (there can be unconnected graphs next to each other)

Undirected is especially bi-directed and undirected costs, however it will be summed together. The higher/lower the two numbers relatively are, the higher/lower the combined costs.

I tracked down some of the algorithms (MST /all Shortest paths/similarity/centrality), but none of them was matching my expectation.

This algorithm just one of my challenges, so reusing is more preferable (saving time).

Any idea, how to solve this problem?

Efficiency and parallelism do matter as it can be billions of nodes, but not the first priority as it can be clustered in different ways initially.