A graph-based clustering problem

Question

I have a graph in which each node is associated with a time stamp. I have around 15-20 nodes associated with each time stamp.

The edges are not weighted & there cannot be an edge between nodes which share a timestamp.

I'd like to find connected components of the graph but with the additional constraint that each discovered component can contain at most one node from each timestep.

I can easily find connected components using networkx in Python, but I'm not sure of the best way to enforce the constraint. Often the connected components contain multiple nodes with the same timestamp.

It feels like the best way to proceed is to treat each connected component as a subgraph and try to find an optimal way of removing edges to enforce the constraint. I want to remove the fewest possible edges such that the constraint is satisfied.

I'm not quite sure how to do that. Any help would be much appreciated.

EDIT:

Here is an example of the subgraph for the largest connected component

It's the edges in the middle that are causing the problem. I essentially want to find the edges to remove which optimally break off the branches, which each contain at most one node from each timestep.

EDIT 2:

I tried a greedy approach whereby I score each edge according to the total number of constraint violations if that edge is removed. I then remove the edge that leads to the greatest improvement. I do this until there are no constraint violations left. It doesn't even get close to the solution I'm looking for. I end up removing almost all of the edges.

Answer 1

I've found something satisfactory for this problem now. I was able to come up with a way of weighting the edges which improved things. No guarantees about its general applicability but it works fine given the specifics of my application.

I use a greedy partitioning of nodes.

• Find the connected components
• For each connected component, add a random node from the smallest timestamp to the partition.
• Move to the next timestamp and find the best connected node to the current partition, i.e. the one that maximally increases the total weight of the subgraph formed by all partitioned nodes.
• Add that node to the partition. Iteratively do this until all nodes have been assigned to a partition.

It's simple but its fast & it works OK for my problem. I'd still be interested in better methods for either the weighted or unweighted version of this problem, if they exist.