Suppose a graph G is partitioned across k machines using partitioner like METIS.
Consider two vertices v1 & v2 in the graph having shortest path of length 'd' between them.
After partitioning how many of these 'd' edges are likely to be span across the partitions? I am mainly concerned with longest shortest path i.e.(diameter). How many of the edge are likely to be cross partition edges?
Is there any existing literature on effect of METIS partitioning on number of hops to traverse for shortest path between two vertices?
For example in the attached figure, vertices A & D have shortest path A->E->D,on partition, E gets mapped to host 2, so both edges of the path became cross partition edges.
So I don't know of any literature, but the goal of METIS is to find the best separator, namely the fewest amount of edges to remove to partition the graph. I use it for making artificial simulations for redistricting plans in each of the United States. In general, that will usually keep the path lengths as short as possible, but there will of course be circumstances where that will not be efficient in that context, producing longer paths in ring-like structures. It ultimately should have a lot to do with the degrees of those vertices and the local edges.
Hi Matthew,
thanks for your reply. You briefly hinted at factors like degree of vertices and edges in the partition. It would be very great, if you can elaborate more on that. I understand that there is probably no deterministic answer to this question, but I wanted to understand intuition behind your reasoning.
Thanks
Ravikant
So here is my rationale:
The only edges that are "removed" by METIS are ones that connect vertices in different partition groups.
That being said, any vertices that are in different partition groups will have their shortest path become non-existent.
For those who are in the same partition group (which is what you are asking about), the question is whether or not a shortest path is made of edges that connect only vertices in that partition group. In other words, you are looking for partitions that are distance hereditary subgraphs ideally (Howorka, 1977). To be distance hereditary implies that the subgraph maintains the length of the shortest path. It also would work if each partition was a convex subgraph (one that maintains all shortest paths between all of the vertices (Artigas et al., 2007)).
Howorka, E. (1977). A characterization of distance-hereditary graphs. The quarterly journal of mathematics, 28(4), 417-420.
Artigas, D., Dourado, M. C., & Szwarcfiter, J. L. (2007). Convex partitions of graphs. Electronic Notes in Discrete Mathematics, 29, 147-151.
METIS would alter the shortest path in situations where all of the shortest paths connect vertices that are outside of the partition group. So what is happening in that case is you are removing part of a loop to partition the graph (which just happens to be the smallest part of the loop).
Hopefully that clears things up. The more edges that a fringe vertex (one that is on the edge of the partition) has to vertices in its partition group rather than those outside, the higher the likelihood that the shortest path is not being removed. Again, that is not a guarantee.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs