TY - JOUR

T1 - Analysis of a parallel MCMC algorithm for graph coloring with nearly uniform balancing

AU - Lin, Jianyi

AU - Conte, Donatello

AU - Grossi, Giuliano

AU - Lanzarotti, Raffaella

AU - Petrini, Alessandro

PY - 2021

Y1 - 2021

N2 - We propose the analysis of a scalable parallel MCMC algorithm for graph coloring aimed at balancing the color class sizes, provided that a suitable number of colors is made available. Firstly, it is shown that the Markov chain converges to the target distribution by repeatedly sampling from suitable proposed distributions over the neighboring colors of each node, independently and hence in parallel manner. We prove that the number of conflicts in the improper colorings genereted thoughout the iterations of the algorithm rapidly converges in probability to 0. As for the balancing, given to the complexity of the distributions involved, we propose a qualitative analysis about the balancing level achieved. Based on a collection of multinoulli distributions arising from the color occurrences within every node neighborhood, we provide some evidence about the character of the final color balancing, which results to be nearly uniform over the color classes. Some numerical simulations on big social graphs confirm the fast convergence and the balancing trend, which is validated through a statistical hypothesis test eventually.

AB - We propose the analysis of a scalable parallel MCMC algorithm for graph coloring aimed at balancing the color class sizes, provided that a suitable number of colors is made available. Firstly, it is shown that the Markov chain converges to the target distribution by repeatedly sampling from suitable proposed distributions over the neighboring colors of each node, independently and hence in parallel manner. We prove that the number of conflicts in the improper colorings genereted thoughout the iterations of the algorithm rapidly converges in probability to 0. As for the balancing, given to the complexity of the distributions involved, we propose a qualitative analysis about the balancing level achieved. Based on a collection of multinoulli distributions arising from the color occurrences within every node neighborhood, we provide some evidence about the character of the final color balancing, which results to be nearly uniform over the color classes. Some numerical simulations on big social graphs confirm the fast convergence and the balancing trend, which is validated through a statistical hypothesis test eventually.

KW - Color balancing

KW - Graph coloring

KW - Markov chain Monte Carlo method

KW - Parallel algorithms

KW - Color balancing

KW - Graph coloring

KW - Markov chain Monte Carlo method

KW - Parallel algorithms

UR - http://hdl.handle.net/10807/183902

U2 - 10.1016/j.patrec.2021.05.014

DO - 10.1016/j.patrec.2021.05.014

M3 - Article

VL - 149

SP - 30

EP - 36

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

SN - 0167-8655

ER -