1 Enumération des cliques maximales dun graphe, des bicliques maximales dun graphe biparti LIMOS – Clermont-Ferrand Alain Gély, Lhouari Nourine, Bachir

1

Enumération des cliques maximales d’un graphe,

des bicliques maximales d’un graphe biparti

LIMOS – Clermont-Ferrand

Alain Gély, Lhouari Nourine, Bachir Sadi

10 Novembre 2006

Journées Graphes & Algorithmes, Novembre 2006, Orléans

2

1. Définitions

2. Problématique de l’énumération

Mesure de Complexité

Méthodes d’énumération

3. Enumération des Cliques Maximales

Existant

Graphe des transitions des cliques maximales

Propriétés du graphe de Transitions

4. Enumération des Bicliques Maximales

Propriétés du graphe de transition

5. Conclusion

3

1. Définitions





Existant





5. Conclusion

4G = ( V , E )

1

2 3

4

5

7

6

Clique Maximale

x,y C (x,y) E

Pour tout zC , C z n’est pas une clique

G = ( U, V , E )

DéfinitionsClique maximale, Biclique maximale

5G = ( V , E )

1

2 3

4

5

7

6

Clique Maximale

x,y C (x,y) E

Pour tout zC , C z n’est pas une clique

G = ( U, V , E )

1 23

45

67

Biclique Maximale

x,y B, x U, y V (x,y) E

Pour tout zB , B z n’est pas une biclique

DéfinitionsClique maximale, Biclique maximale

6

1. Définitions





Existant





5. Conclusion

7

Algorithme d’EnumérationDéfinition

Entrée : S une structure discrète, P une propriété

Sortie : Liste des configurations de S satisfaisant P

S = un graphe G(V,E)

P = être une clique maximale de G

Sortie : Liste des cliques maximales de G

Taille de l’entrée : n

Taille de la sortie : N ( # Configurations )

8

1. Définitions





Existant





5. Conclusion

9

Algorithme d’énumération

Polynomiale : O((n+N)k)

Complexité temporelle

Taille de l’entrée : n

Taille de la Sortie : N ( # configurations )

Polynomiale par objet : O(nk N)

A délai polynomial : O(nk N)

C1 C2 Ci Ci-1 CNDébut Fin

O(nk) O(nk) O(nk) O(nk)

Complexité Spatiale

Polynomiale : O(nk)

Exponentielle : O(nkN) ( stockage nécessaire au traitement)

10

1. Définitions





Existant





5. Conclusion

11


Enumération dans l’ordre lexicographique

(exemple : sous-ensembles de {1,2,3})

Trouver une première configuration C

Calculer Suivant(C)

Première configuration :

Suivant() : 1

Suivant(1) : 12

Suivant(12) : 123

Suivant(123) : 13

Suivant(13) : 2

Suivant(2) : 23

Suivant(23) : 3

12

Retour-Arrière

Choisir une propriété P

Enumérer les configurations qui vérifient P

Enumérer les configurations qui ne vérifient pas P

1, 12, 123 , 2, 23

Contenir 1 Ne pas contenir 1

Méthodes d’énumération(exemple : sous-ensembles de {1,2,3})

13

- Notion de proximité entre objets à générer

- Recherche d’un chemin Hamiltonien

1 2

12

3

13 23

123

Code de Gray (Gray 54)


- « construction » d’un graphe de proximité

14

Méthode de Recherche Locale Inverse (Avis Fukuda 96)

- Fonction de voisinage

- Optimisation d’un critère

1

2

123 13

23

123


- Inversion de la recherche

Ø

15

Dans tous les cas

Utilisation d’arbre / de graphe ayant pour sommet des objets à construire


1 2

12

3

13 23

123

Ø

2

12

3

13 23

123

Ø Ø

1

12

2

23123

1

Code de Gray13

3

2

12

3

13 23

123

Ø

1

Retour-arrière( )Ø 1 12 123 13 2

Suivant( )

23 3

16

1. Définitions





Existant





5. Conclusion

17

ExistantG = ( V , E )

{1,2,3}

{1,5}

{1,6}

{2,3,4}

{2,3,7}

{4,5}

{6,7}

C(G)

C(G) exponentielle

Algorithmes :

• Espace polynomial

• Délai polynomial

• Ordre lexicographique

Prochaine clique maximale lexicographique : NP-complet

1

2 3

4

5

7

6

[Tsukiyama & al 77][Johnson & al 88]

Enumération des cliques maximales

18

1. Définitions





Existant





5. Conclusion

19


G = ( U , V )

{1,2,3}

{1,5}

{1,6}

{2,3,4}

{2,3,7}

{4,5}

{6,7}

C0

C1

C2

C3

C4

C5

C6

?

C(G)

Intuition

Définir un graphe de proximité

C(G) , Ensemble de sommets

T(G) = (C(G) ,T)

Graphe des transitions des cliques max de G

Reste à déterminerL’ensemble des transitions

1

2 3

4

5

7

6

20

Cx Cyj

Transition utilisant un sommet j de V

j n’appartient pas à Cx

j appartient à Cy

ensembledes arcs

Soit Kj( ), un opérateur sur une clique maximale

Transition ssi Cy = Kj( Cx ),


21

Kj( ) ?

1 2 3 4 j n

Voisinage de J

i

Est une clique

j n

Complétion (gloutonne) pour obtenir une clique maximale C

C est une clique maximale de G … ou non


22

j Cx, Kj(Cx) Plus petite clique max. de

{ Cx { 1, … , j } v(j) } { j , … , n}

Préfixe de Cx

Voisinage de j dans le préfixe de Cx

Labels supérieur à j

Kj( )

1

2 3

4

5

7

6


23

1. { 1,2,3} { 1,…,4 } = {1,2,3}2. V(4) = {2,3,5}3. {1,2,3} {2,3,5} = {2,3}4. Plus petite clique maximale de {2,3} {4,…,7}

K3({1,2,3}) = {2,3,4} C(G)

K4({1,2,3}) ?

1

2 3

4

5

7

6

{1,2,3} {2,3,4}4

Transition

1

2 3

4

5

7

6


24

1. { 1,6} { 1,2,3 } = {1}2. V(3) = {1,2,4,7}3. {1} {1,2,4,7} = {1}4. Plus petite clique maximale de {1 } {3,…,10}

K3({1,6}) = {1,3} C(G)

K3({1,6}) ?

1

2 3

4

5

7

6

{1,6} ?3

Pas de transition de label 3

1

2 3

4

5

7

6


25

T(G) Graphe des transitions de G

67

237

123

234

45

15

16

5

6

1

1

7

4

7

2

4

2

14

4

65

6

27

2

6

1

4

1

2 3

4

5

7

6

G(V,E)

26

1. Définitions





Existant





5. Conclusion

27

Propriétés de T(G)

Idée de la preuve :

Soit C0 la plus petite clique maximale de G

• Il existe un chemin de C0 vers n’importe quelle Ci

• Il existe un chemin de Ci vers C0

C0 Ck ClCi Cj

T(G) est fortement connexe

28

T(G) Graphe de transitions de G

67

237

123

234

45

15

16

5

6

1

1

7

4

7

2

4

2

14

4

65

6

27

2

6

1

4

1

2 3

4

5

7

6

G(V,E)

29

1

12

123

123 234

123 15 234 45

123 16 15 16 234 6 45 6

123 237 16 67 15 7 16 7 234 237 45 7

1

2 3

4

5

7

6

1

2 3

4

5

7

6

1

2 3

4

5

7

6

1

2 3

4

5

6

7

1

2 3

4

5

6

7

1

2 3

4

5

6

7

1

2 3

4

5

7

6

T(G) : Chemin de C0 vers Ci

Induction structurelle

30

1

12

123

123 234

123 15 234 45

123 16 15 16 234 45

123 237 16 67 15 16 234 237 45

1

2 3

4

5

7

6

1

2 3

4

5

7

6

1

2 3

4

5

7

6

1

2 3

4

5

6

7

1

2 3

4

5

6

7

1

2 3

4

5

6

7

1

2 3

4

5

7

6

4

5

7

5

66

7 7

31

T(G)

67

237

123

234

45

15

16

5

6

1

1

7

4

7

2

4

2

14

4

65

6

27

2

6

1

4

1

2 3

4

5

7

6

G(V,E)

32

T(G)

67

237

123

234

45

15

16

5

6

1

1

7

4

7

2

4

2

14

4

65

6

27

2

6

1

4

1

2 3

4

5

7

6

G(V,E)

33

1

12

123

123 234

123 15 234 45

123 16 15 16 234 45

123 237 16 67 15 16 234 237 45

1

2 3

4

5

7

6

1

2 3

4

5

7

6

1

2 3

4

5

7

6

1

2 3

4

5

6

7

1

2 3

4

5

6

7

1

2 3

4

5

6

7

1

2 3

4

5

7

6

4

5

7

5

66

7 7

T(G) : plus de chemins de C0 vers Ci que de séquences de construction

34

Résultat :

T(G) possède plusieurs arbres couvrant

enracinés en C0

35

2 Etapes :

1. Choisir une arborescence T(G) (enracinée en C0)(plusieurs choix)

2. Parcourir l’arborescence recouvrante(plusieurs choix)

G(V,E) |V|=n, |E|=m

• Construction de C0 O(m)

• calcule des Transitions O(m)

• Tester la maximalité O(m)

• # transitions pour une clique max. O(n)

O(n.m)

1i

n

C0

T(G) Graphes de transitions de G – Algorithmes & Complexités

36

[ Tsukiyama & al. 77 ]

Graphe de transitions

Ordre quelconque – espace polynomial – Délai Polynomial

67

237

123

234

45

5

46

15 5

16

7

7

67237123 234 451516

Arbre couvrant :

• Chemins définis par des séquences de construction

• Choisir la plus petite séquence lexicographique

Parcours : En profondeur d’abord

37

[Johnson & al. 88]

Graphe de transitions

67

237

123

234

45

5

46

15 5

16

7

7

67237123 234 4515 16

Ordre lexicographique – espace exponentiel

Délai polynomial

Propriété de l’arbre couvrant de Tsukiyama :

• If Cx atteignable depuis Cy, alors Cy < Cx

Parcours : Stockage et reprise

123

15

16

234

237

67

45

38

1 2

3 4

5 6

7 8

1

3 5

827

46

Classes particulières - Graphes de Comparabilité

[Cai, Kong, 92]

Sommets numérotés selon une extension linéaire de l’ordre

Hypothèse

Ordre lexicographique – espace polynomial

Délai polynomial

39

1 2

3 4

5 6

7 8

1

3 5

827

46

La séquence des cliques maximales de G dans l’ordre lexicographique forment un

chemin Hamiltonien dans T(G)

Résultat

Classes particulières - Graphes de ComparabilitéOrdre lexicographique – espace polynomial

Délai polynomial

40

1. Définitions

2. Problématique de la génération


Méthodes de génération

3. Génération des Cliques Maximales

Existant



4. Génération des Bicliques Maximales


5. Conclusion

41

II. Enumération des bicliques maximales

G = (U,V,E)

2

3

1

5

6

7

8

42

1. Définitions





Existant





5. Conclusion

43

Enumération des bicliques d’un graphe Biparti

Hypothèse de numérotations

Si i U , j V alors i < j

G = (U,V,E)

1 2 n

n+1 n+1 m

44

1

12

123

T(G) : chemin de C0 vers Ci avec des labels dans V (exclusivement)

1234

Sommets de U : clique

i

j Cliques max.

atteignables par une séquence sur V

Propriété

45

1 2 3 4 j ni

Sommets de U Sommets de V

j

i Cyi Cx

j VTransition => Cx ∩ V Cy ∩ V

Propriété

Enumération des bicliques d’un graphe Biparti

46

Propriétés du graphe de transitions

(123,78)

(13,578)

(1,5678)

(1234,8 )

5 6 7 8

1 2 3 4U

V

(12,678)

6 57

56

65

Treillis de Galois sous graphe de T(G)

Propriétés

Utiliser la structure de treillis = utiliser un sous graphe de T(G)

Propriété

47

Connexion entre algorithmes connus

[Tsukiyama & al. 77]

équivalent à un génération dans l’ordre lectique

Bicliques énumérables à partir de V seulement

Next-Closure [Ganter 84] et [Tsukiyama & al 77] énumèrent les bicliques maximales selon la même

séquence

Remarque

67

237

123

234

45

5

4

615 5

16

7

7

48

1. Définitions





Existant





5. Conclusion

49

Conclusion

Mise en place d’un cadre général d’énumération

Comparaison d’algorithmes en utilisant T(G)

Adaptation à la génération des bicliques maximales

Algorithmes de génération des cliques et des bicliques

Propriétés supplémentaires de T(G) ?

Etudes de Classes de graphes particulières

Perspectives

50

Merci

Documents

1 Enumération des cliques maximales dun graphe, des bicliques maximales dun graphe biparti LIMOS – Clermont-Ferrand Alain Gély, Lhouari Nourine, Bachir