CNS graphe orienté fortement connexe

rebellin · January 2023

Bonjour

Je viens d'écrire un petit programme en Python pour simuler un réseau de pages Web reliées entre elles - en fait un graphe orienté. J'ai fait ce travail dans le cadre de mon cours de SNT (=informatique en seconde), dans le but de montrer une méthode de PageRank : les élèves choisissent les liens entre les pages, puis une balise parcourt le graphe aléatoirement. On compte ensuite le nombre de passages sur chaque sommet (=site Web), ce qui fournit un estimateur de sa pertinence.

Le problème, c'est qu'il faut que le graphe soit fortement connexe (par exemple, c'est un peu idiot si on tourne en rond entre deux pages). Voici donc ma question : y a-t-il une méthode, utilisant la matrice d'un graphe orienté et ses puissances successives, permettant de savoir si ce graphe est fortement connexe ou non (i.e. on peut relier n'importe quels sommets 2 à 2) ?

J'avais envie de dire que pour une matrice de taille n, il suffisait que $\min\left(M_{i,j},M^2_{i,j},\cdots,M^n_{i,j}\right)$ soit non nul. Mais je n'ai pas vraiment d'argument à avancer.

Merci de m'avoir lu !

Math Coss · January 2023

Ce serait idiot mais en quoi serait-ce un problème ? Si certaines pages n'ont aucun lien qui mènent vers elles, elles sont jugées non pertinentes et c'est tout.

Ce qu'on veut, c'est que tous les coefficients de $\mathrm{I}_n+M+M^2+\cdots$ soient strictement positifs. On peut pour le vérifier calculer $(\mathrm{I}_n-M)^{-1}$ (si cette matrice existe, ce qui revient à dire que $1$ n'est pas valeur propre, ce qui s'interprète mais j'ai du mal...). Numériquement, c'est impossible avec une matrice de la taille du web, d'où un renvoi au paragraphe précédent...

En fait, pour éviter ce phénomène et, me semble-t-il, pour des raisons de stabilité numérique, il me semble que l'algorithme PageRank offre la possibilité d'aller sur une page quelconque avec une probabilité faible, indépendamment des liens. Autrement dit, si $A$ est la matrice du graphe renormalisée de sorte que la somme des lignes vaille $1$ sur toute ligne (autrement dit, $a_{ij}=m_{ij}/\sum_{k=1}^na_{ik}$ pour tout $(i,j)$ -- cela pourrait être des colonnes si tu comptes les passages sur une ligne $L_p$ via $L_{p+1}=L_pM$ au lieu d'une colonne $C_p$ via $C_{p+1}=MC_p$) et $J$ la matrice dont tous les coefficients valent $1$, on utilise $\pi A+(1-\pi)J$ au lieu de $M$ ou $A$, où $\pi$ est un nombre proche de $1$.

samok · January 2023

Bonsoir rebellin,

$M$ étant la matrice d'adjacence d'un graphe orienté de $n$ sommets, $M_{i,j}^k$ est le nombre de chemins de $i$ à $j$ en parcourant $k$ arêtes.

Ta condition suffit et est nécessaire pour conclure que le graphe soit connexe.

J'ai pas survécu à la définition de "fortement connexe" de Wikipédia en français.

rebellin · January 2023

@Math Coss

Merci pour la réponse. C'est très élégant le coup de $I-M$ inversible. Je ne peux l'utiliser tel quel, parce que je ne veux installer aucun module Python, donc mes matrices sont des listes de listes et j'ai dû faire une fonction pour le produit et les puissances...

Je voulais quelque chose de simple, qui ne soit pas exactement le "vrai" PageRank - c'est pour une classe de 2de, et je n'ai qu'une heure pour traiter le sujet... La condition "fortement connexe" évite certains problèmes.

J'ai l'impression que ma condition est bien une CNS. D'abord, elle est clairement suffisante. Réciproquement, supposons qu'il existe $i,j$ tels que $M_{i,j}=M^2_{i,j}=\cdots=M^n_{i,j}=0~;$ supposons également qu'il existe un chemin qui amène de $i$ à $j.$ Notons $k$ la longueur minimale d'un tel chemin. D'abord $k>n.$ Ensuite, comme il y a $n$ sommets, le chemin passe deux fois au moins par un certain sommet. En enlevant la partie intermédiaire entre ces deux passages, on a encore un chemin qui relie $i$ à $j,$ mais sa longueur est strictement inférieure à $k.$ Contradiction.

rebellin · January 2023

Je crois qu'on peut se contenter de $M_{i,j}=M^2_{i,j}=\cdots=M^{n-1}_{i,j}=0.$

Calli · January 2023

Bonjour,
Je suis d'accord avec ta CNS rebellin.

À propos de la remarque de @Math Coss : Si le graphe possède un chemin orienté non trivial qui boucle, alors $\sum_{k\in \Bbb N} M^k$ possède des coefficients égaux à $+\infty $. En effet, le coefficient $(i, i) $ de cette matrice est le nombre de chemins de longueur quelconque de $i$ à $i$. Et on peut répéter autant de fois qu'on veut une boucle donnée. Donc $I-M$ n'est pas inversible dans ce cas.

Heuristique · January 2023

Bonjour,

Je suis aussi d'accord avec ta CNS (mais je crois que c'est un max et non un min).

En moins coûteux (ton algo est en $O(n^4)$...) : pour tout sommet $s$ de $G$, lance un parcours en profondeur et vérifie que tous les sommets sont bien atteints. Là, on fait du $O(nm)$. En plus, ça t'évite de coder le produit matriciel.

On peut faire encore plus rapide, en $O(m)$ avec l'algorithme de Tarjan, mais ça devient plus dur de l'expliquer aux élèves...

Après, si tes graphes sont petits, le produit matriciel marchera.

rebellin · January 2023

En fait il faut bien aller jusqu'à $n$, et c'est bien un max et non un min : $\max\left(M_{i,j},M^2_{i,j},\cdots ,M^{n}_{i,j}\right)\not=0.$

rebellin · January 2023

Merci à tous pour vos réponses. J'ai passé deux jours à coder le script (un peu plus de 200 lignes) et je commençais à fatiguer. Ce qui est bien avec Python et Tkinter, c'est qu'on peut tester le code "en vrai" !

Heuristique · January 2023

Euh non, $n-1$ suffit normalement. Dans un graphe de taille $n$, si tu fais un chemin de taille $n$, il traverse (en comptant le début et la fin) $n+1$ sommets donc, par le lemme des tiroirs, admet forcément un cycle que l'on peut alors supprimer du chemin.

rebellin · January 2023

Je déterre cet ancien sujet, je n'avais pas vu ta réponse @Heuristique : j'avais un graphe orienté, représenté par une matrice carrée $M$ de taille $n.$ J'ai écrit qu'une CNS pour que le graphe soit fortement connexe est $$\forall (i,j),\quad~\max\left(M_{i,j},M^2_{i,j},\cdots ,M^{n}_{i,j}\right)\not=0.$$

Je crois qu'il faut bel et bien aller jusqu'à $n$ (donc $n-1$ ne suffit pas). On le voit par exemple avec $n=2~:$ dans le cas où les deux sites sont liés, la matrice $M$ est égale à $\begin{pmatrix}0&1\\1&0\end{pmatrix}~;$ et $M^2=\begin{pmatrix}1&0\\0&1\end{pmatrix}.$ On a bien $\forall (i,j),~\max\left(M_{i,j},M^2_{i,j}\right)\not=0,$ tandis que $M_{1,1}=0.$

Heuristique · January 2023

Oui pardon, j'oubliais les chemins de longueurs nulles. Ma condition était plutôt $\forall (i,j),\ \max(M^0_{i,j},M^1_{i,j},\ldots,M^{n-1}_{i,j}) \neq 0$.

En effet, sur ton exemple, le chemin vide est un chemin de 1 à 1.

Mea culpa donc !

CNS graphe orienté fortement connexe

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 24