4
$\begingroup$

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 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.

$\endgroup$
2
  • 1
    $\begingroup$ With the extra constrain, the connected components are not unique. I assume you want to get the minimum number of connected components (i.e. dont split the graph to too many small components)? Or what metrics, if any, you want to optimize? $\endgroup$ Feb 4, 2020 at 15:44
  • $\begingroup$ Yes that's right. I want to remove the smallest number of edges such that the constraint is met, or alternatively obtain the smallest possible number of new components such that the constraint is met. If there are still multiple equally 'good' solutions, I'm happy to pick one at random or come up with some other heuristic to choose between the options. $\endgroup$
    – Will
    Feb 4, 2020 at 15:50

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.