It seems to me the problem you describe is known as the Correlation Clustering Problem. This information should help you find some implementations, such as:
Note some community detection algorithms have also been modified in order to process signed networks, e.g. Amelio'13, Sharma'12, Anchuri'12, etc. However, I couldn't find any publicly available implementationsimplementation.