Analysis of a parallel MCMC algorithm for graph coloring with nearly uniform balancing
Autor: | Donatello Conte, Giuliano Grossi, Alessandro Petrini, Raffaella Lanzarotti, Jianyi Lin |
---|---|
Přispěvatelé: | Laboratoire d'Informatique Fondamentale et Appliquée de Tours (LIFAT), Université de Tours-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS), Université de Tours (UT)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL) |
Jazyk: | angličtina |
Rok vydání: | 2021 |
Předmět: |
Computer science
Parallel algorithms [SCCO.COMP]Cognitive science/Computer science 02 engineering and technology 01 natural sciences Settore INF/01 - INFORMATICA Color balancing [INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing Artificial Intelligence 0103 physical sciences Convergence (routing) 0202 electrical engineering electronic engineering information engineering Graph coloring 010306 general physics Statistical hypothesis testing Markov chain Node (networking) [INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV] Sampling (statistics) Settore ING-INF/05 - SISTEMI DI ELABORAZIONE DELLE INFORMAZIONI Character (mathematics) Markov chain Monte Carlo method [INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV] Signal Processing Scalability 020201 artificial intelligence & image processing Computer Vision and Pattern Recognition Algorithm Software |
Zdroj: | Pattern Recognition Letters Pattern Recognition Letters, Elsevier, 2021, 149, pp.30-36. ⟨10.1016/j.patrec.2021.05.014⟩ |
ISSN: | 0167-8655 |
Popis: | International audience; 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. |
Databáze: | OpenAIRE |
Externí odkaz: |