So the problem starts with a graph in which every node is connected with every node by a weighted edge. The goal is to find a weight treshold W, so that every edge that has a weight lower than or equal to W gets removed, which results in the maximum amount of connected components. A connected component is defined as at least two connected nodes.
I've thought about sorting all the weights of the edges from high to low, then iterating through that list and setting the treshold equal to the current weight and check if the current amount of components is the highest amount we've had thus far.
Would this be an efficient algorithm? Also, the graph is undirected.
Added: If two tresholds W1 and W2 produce the same maximum amount of components, then the treshold for which the least amount of nodes are in a connected component is chosen. In other words, the treshold for which there are the most amount of free nodes.
Clarifications: The application is a graph for plagiarism detection. Each pair of nodes has a weighted edge connecting them, where the weight represents the probability of plagiarism between the two. A "free node" is defined as a node that is not connected with any other node.
Let's say the treshold is a weight of 80. When a node (which represents some submission) doesn't have an edge with weight higher than 80 to any other node, it's a free node.