# Un nouvel estimateur des niveaux de densité utilisant les graphes et complexes simpliciaux. Application à la détection des clusters de galaxies

Louis Hauseux, Konstantin Avrachenkov, Josiane Zerubia

► To cite this version:

Louis Hauseux, Konstantin Avrachenkov, Josiane Zerubia. Un nouvel estimateur des niveaux de densité utilisant les graphes et complexes simpliciaux. Application à la détection des clusters de galaxies. XVIe Journées de géostatistiques (Fontainebleau, 7-8 septembre 2023) organisé par les Mines de Paris - PSL, Sep 2023, Fontainebleau, France. . hal-04222280

HAL Id: hal-0422280

https://inria.hal.science/hal-0422280v1

Submitted on 29 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons CC BY 4.0 - Attribution - International License
# Un nouvel estimateur des niveaux de densité utilisant les graphes et complexes simpliciaux
## Application à la détection des clusters de galaxies

Louis HAUSEUX

Konstantin AVRACHENKOV

Josiane ZERUBIA

Inria, Université Côte d'Azur, Sophia-Antipolis, France

Prénom.Nom@Inria.fr

## Présentation du problème

Les galaxies ne se répartissent pas uniformément au sein de l'univers mais se regroupent au sein de « structures à grandes échelles » :

1°) des super-amas de galaxies (petits volumes hyper-denses de $\mathbb{R}^3$);

2°) des feuillets ou « murs » de galaxies (surfaces);

3°) des « filaments » de galaxies (courbes).

Ces clusters délimitent de grandes régions quasiment vides de galaxies.

<figure><img src="image_2.png" /><figcaption>Figure 1. Nuage de points synthétique $\mathcal{X} \subset \mathbb{R}^2$ créé par les auteurs de l'article [4] et gracieusement fourni par R. Stoica, V. Martínez et E. Saar. Au milieu, le résultat de leur algorithme. À droite, le nôtre.</figcaption></figure>

→ Clusters hiérarchiques ⇒ il est naturel de recourir à un **estimateur de densité**. Estimateurs de densité classiques pour notre problème [2] :

**Delaunay** [3] & **K-Plus-Proches-Voisins** [1].

## Outils mathématiques

**Graphes géométriques.** Soit $\mathcal{X} = \{x_1, ..., x_n\} \subset \mathbb{R}^d$ un nuage de points, les $x_i$ ayant été tirés i.i.d. selon une mesure à densité $f$ par rapport à la mesure de Lebesgue. Soit $r > 0$ un rayon, le graphe géométrique $G(\mathcal{X}, r)$ est le graphe (non orienté) :

$$ \text{Sommets} := \mathcal{X}; $$

$$ \text{Arêtes} := \{\{x_i, x_j\} \mid |x_i - x_j| < r\}. $$

**Complexe simplicial** est un ensemble $\mathcal{K} \subset \mathcal{P}(\mathcal{X})$ constitué de parties $\sigma$ non vides d'un ensemble fini $\mathcal{X} (= \text{Sommets})$ vérifiant :

$$ \forall \sigma \in \mathcal{K}, \forall \tau \subseteq \sigma, \tau \neq \emptyset \Rightarrow \tau \in \mathcal{K}. $$

Un élément $\sigma \in \mathcal{K}$ est un *simplexe*. Ses sous-ensembles $\tau \subseteq \sigma$ en sont ses *faces*.

→ **permet de généraliser la notion de graphe ainsi que de composante connexe.**

**Percolation.** Soit $\mathcal{X} := \mathcal{H}_1 \cup \{0\} \subset \mathbb{R}^d$ un processus ponctuel de Poisson homogène sur $\mathbb{R}^d$ d'intensité $\lambda := 1$. Il existe un *rayon critique* $r_c$ tel que :

— $\forall r < r_c$, avec probabilité 1, $G(\mathcal{X}, r)$ n'a aucune composante connexe infinie;

— $\forall r > r_c$, avec probabilité 1, $G(\mathcal{X}, r)$ possède une composante connexe infinie.

*Percolation* = composante $\infty$ présente (contenant une proportion $p_\infty(r)$ des points).

→ **la percolation est un phénomène rapide** : $p_\infty(r)$ se rapproche très vite de 1. « Mesurons » cette vitesse. Soit $0 < \varepsilon < \frac{1}{2}$. Notons $r_{\min} := p_\infty^{-1}(\varepsilon)$ et $r_{\max} := p_\infty^{-1}(1 - \varepsilon)$. La **vitesse de percolation** se mesure grâce à : $\frac{r_{\max}}{r_{\min}}$.

<figure><img src="image_3.png" /><figcaption>Figure 2. Avec $\varepsilon \leftarrow 0, 0.5, r_{\min} = 1, 15$ et $r_{\max} = 1, 30$ soit $\frac{r_{\max}}{r_{\min}} \approx 1, 13$.</figcaption></figure>

→ **percolation rapide** ⇒ 2 clusters voisins de densités proches bien distingués.

→ Soit $G$ le graphe élagué des petites composantes (de taille $\leq \text{SeuilPerco} \leftarrow 50$).

**Niveaux de densité.** High-Density Clusters($h$) := $f^{-1}([h; +\infty])$ [5], [6]. Soit $P \in [0; 1]$, la hauteur $h_P$ de densité associée : $h_P := \inf \{h \mid \int_{f \ge h} f(x)dx \le P\}$.

Le **rayon** associé : $r_P = \inf \{r \mid \frac{|\text{Nœuds}(G(\mathcal{X}, r))|}{|\text{Nœuds}(G(\mathcal{X}, r))|} \ge P\}$.

La **carte des niveaux** : $\mathcal{P} : x \mapsto := \inf \{P \in [0; 1] \mid x \in \text{High-Density Clusters}(h_P)\}$.

La **carte empirique des niveaux** : $\hat{P}(x) := \inf \{P \in [0; 1] \mid x \in \Sigma_P\}$ ($\inf(\emptyset) = 0$).

Le **cluster de niveau** $\Sigma_P := \bigcup_{x \in \text{Nœuds}(G(r_P))} B(x, r_P)$.

**Précision/Rappel sur la bonne identification d'un cluster.** Soit $P \in [0; 1]$ et $C_P$ un cluster de niveau $P$. Soit $\hat{C}_P$ le cluster empirique associé.

$$ \text{Précision} := \frac{|C_P \cap \hat{C}_P|}{|\hat{C}_P|}, \quad \text{Rappel} := \frac{|C_P \cap \hat{C}_P|}{|C_P|}. $$

## Résultats

**Données** : densité $f$ imitant des filaments plus ou moins fins/denses par des rectangles à densité homogène.

<figure><img src="image_4.png" /><figcaption>Figure 3. À gauche : les niveaux de densité théoriques. À droite : un nuage $\mathcal{X}$ de 2000 points générés i.i.d. selon $f$. Un graphe géométrique $G(\mathcal{X}, r)$ est dessiné avec **arêtes** en rouge et le cluster associé $\Sigma_P$ en vert. *SeuilPercolation* $\leftarrow 50$.</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>Figure 4. Trois estimateurs des niveaux de densité sur $\mathcal{X}$ : notre **Graphe-Percol**; **Delaunay**; 10-Plus-Proches-Voisins.</figcaption></figure>

→ Visuellement, le nôtre est **plus homogène et moins sujet aux petites sur-détections**.

Quatre 'filaments' apparaissant successivement $\iff$ Quatre niveaux de clusters :

<table><thead><tr><th rowspan="2">Algorithme</th><th colspan="2">1 - P̂ > 0, 617</th><th colspan="2">1 - P̂ > 0, 280</th><th colspan="2">1 - P̂ > 0, 169</th><th colspan="2">1 - P̂ > 0, 140</th></tr><tr><th>Précision</th><th>Rappel</th><th>Précision</th><th>Rappel</th><th>Précision</th><th>Rappel</th><th>Précision</th><th>Rappel</th></tr></thead><tbody><tr><td>Graphe-Percol</td><td><strong>0,741</strong></td><td><strong>0,827</strong></td><td>0,881</td><td><strong>0,970</strong></td><td>0,814</td><td><strong>0,945</strong></td><td>0,783</td><td><strong>0,896</strong></td></tr><tr><td>Delaunay</td><td>0,573</td><td>0,315</td><td>0,857</td><td>0,799</td><td><strong>0,892</strong></td><td>0,899</td><td><strong>0,881</strong></td><td>0,886</td></tr><tr><td>K-Plus-Proches-Voisins</td><td>0,600</td><td>0,528</td><td><strong>0,899</strong></td><td>0,864</td><td>0,861</td><td><strong>0,945</strong></td><td>0,802</td><td>0,893</td></tr></tbody></table>

Notre estimateur l'emporte haut-la-main sur le premier niveau (le 'super-amas' à gauche).

→ **Percolation rapide** ⇒ recouvre bien le 'super-amas' avant de commencer sur le 'filament' médian.

<figure><img src="image_6.png" /><figcaption>Figure 5. Clusters $\hat{C}_P$ pour le seuil $1 - P = 0, 617$. De gauche à droite : **Graphe-Percol**; **Delaunay**; 10-Plus-Proches-Voisins.</figcaption></figure>

→ Graphes/complexes simpliciaux ⇒ extraction plus facile de filaments. **Cf. image de dr. Figure 1.**

### Algorithme d'extraction de filaments de galaxies

→ Partir d'une comp. connexe $G$ de $G$ et de son *Filament* (sous-gr.) déjà construit.

→ Décider d'un nombre de Centres à ajouter selon la taille de $G$.

→ Itérativement, un nouveau centre $x$ est choisi de façon à minimiser :

$$ D[x] = \sum_{y \in \text{Nœuds}(G)} d(y, \text{Filament} \cup \text{Branche}_x)^2 $$

(où $d$ est la distance induite sur le graphe et $\text{Branche}_x$ le chemin le plus court de $x$ à *Filament*).

*Filament* $\leftarrow$ *Filament* $\cup$ *Branche$_x*

→ Premier centre choisi : **moyenne de Fréchet** de $G$.

## Conclusion

→ Avoir un regard *persistant* (= variationnel) permet d'observer les différentes phases de percolation.

→ La percolation est un phénomène très rapide permettant de distinguer deux niveaux de densité proches.

→ Comparé aux estimateurs de densité conventionnels pour ce problème, les premiers résultats sont très encourageants. Notamment pour les hauts niveaux de densité.

## Perspectives

→ Considérer la masse (= luminosité) d'une galaxie. 🤷 Introduire des rayons non uniformes.

→ Revenir sur le choix de $\Sigma_P$. Il y a certainement des améliorations à trouver dans cette voie.

→ **Regarder ≠ types de connexités** possibles avec les complexes simpliciaux. Il y a encore plus à faire sur ce plan : nos premiers résultats montrent que l'on peut ainsi **augmenter la vitesse de percolation**.

## Bibliographie

[1] G. BIAU et L. DEVROYE, *Lectures on the Nearest Neighbor Method*. Springer, 2015, t. 246, ISBN : 978-3-319-25386-2. DOI : 10.1007/978-3-319-25388-6.

[2] B. DARVISH, B. MOBASHER, D. SOBRAL, N. SCOVILLE et M. ARAGON-CALVO, "A Comparative Study of Density Field Estimation for Galaxies," *The Astrophysical Journal*, t. 805, n° 2, p. 121, 2015. DOI : 10.1088/0004-637X/805/2/121.

[3] W. E. SCHAAP, "DTFE: the Delaunay Tessellation Field Estimator," thèse de doct., Proefschrift Rijksuniversiteit Groningen, 2007, p. 287.

[4] STOICA, R., MARTÍNEZ, V., MATEU, J. et SAAR, E., "Detection of cosmic filaments using the Candy model," *Astronomy & Astrophysics*, t. 434, n° 2, p. 423-432, 2005. DOI : 10.1051/0004-6361 : 20042409.

[5] M. PENROSE, *Random Geometric Graphs*. Oxford University Press, 2003, t. 5, ISBN : 9780198506263. DOI : 10.1093/acprof:oso/9780198506263.001.0001.

[6] J. A. HARTIGAN, *Clustering Algorithms*. John Wiley & Sons, Inc., 1975, ISBN : 9780471356455.