Towards Graph Clustering for Distributed Computing Environments

Several algorithms and tools that operate on graphs can significantly benefit from distributed computing. For instance, consider a logistic transportation network represented as a temporal graph. Optimizing transportation routes and times is a well-known NP-hard problem. One typical approach is problem decomposition, which requires optimal partitioning of the network. In such problems, the goals include minimizing the number of cross-partition edges, balancing the sizes of partitions, and controlling the number of partitions to match the capabilities of the computing environment. In this paper, we propose a mathematical formulation of the graph clustering problem for distributed computing environments, along with a simple initial heuristic that can be used to obtain partitions.