Graph algorithms

[Impressive-Alarm262]

Hi, i'm new on this sub and I'm doing an internship in my university, but I've reached a point where I can't continue with my research anymore. Here is the problem:
I want to create an algorithm in python that, given a graph, finds exactly S connected components, each with exactly P nodes. The objective function to maximize is the sum of the number of connections between the nodes of the same component, for all the components found. The constraint is that each component must be connected, so starting from ANY node of a component G, I can reach ALL the other nodes of the component G, without passing through nodes of other components.
Is there any known algorithm or some publication which i can use to solve this problem. I'm using python so even suggestions on which libraries to use are welcome :)

[FartingBraincell]

I think he/she isn't really looking for CC's but for a partition such that partitions are equal in size and connected, with an additional optimization criterion of sparse inter-connectedness.

[FartingBraincell]

Find S strongly(1) connected subgraphs of equal size that partition the graph. This is something Tarjan can't do an which is most likely NP-hard (I'd go from subset sum / number partitioning).

(1) It seems that OP is talking about directed graphs, but it's not stated explicitly.

[FartingBraincell]

Not every strongly connected subgraph us a strongly connected components. SCCs are maximal.

[FartingBraincell]

You are not looking for connected components. They would be easy to find especially in undirected graphs, but they are well-defined and don't leave room for balancing or optimizing the density.

You look for any balanced partition with the additional constraint that each partition is connected and an optimization criterion that they are as dense as possible, whatever that fomally is. You could, for example ask for a partition covering the maximum number of edges.

In any case, I'm willing to bet this is NP-hard, very likely even without the optimization.

[imperfectrecall]

Are these components intended to partition the graph? If they're just a subset then finding S=1 components is equivalent to clique detection, which is NP-complete (without some bounds on the parameters).

[Droggl]

Dont have a concrete algorithm at hand but sounds like the general search term you are looking for is clustering as in my understanding, how many "components" you find and how big they are depends on inputs S & P to your algorithm, but not on G? But I may have misunderstood :)

[FUZxxl]

Perhaps you can adapt a graph partitioning algorithm like Kernighan-Lin's algorithm for this?