Agrégats de mots sémantiquement cohérents issus d'un grand graphe de terrain

Chapitre 2. Les algorithmes de création de communautés

2.5 Synthèse

Cette synthèse liste en deux tableaux les méthodes présentées dans ce chapitre (cf. tableau 2.1 et tableau 2.2).

2.5.1 Caractéristiques importantes

Pour chaque méthode nous précisons si elle est applicable sur des graphes pondérés et orientés ou non et si le nombre de communautés doit être fixé à priori. Ces trois propriétés nous semblent primordiales, nous allons ici en justifier le choix par des exemples appliqués à un graphe de terrain bien connu, la ville de Kaliningrad. Nos communautés seront des arrondissements de la ville. Le but premier de ce découpage est que la circulation des personnes soit la plus simple possible au sein de chaque arrondissement. Pour des raisons de coût la mairie actuelle ne souhaite pas créer plus de deux arrondissements.

Après une étude, la mairie décide que le premier arrondissement sera constitué par la rive A et l'île B (cf. figure 2.17). Parfaitement connectés par deux ponts il semble que ces points de terre ferme puissent être rattachés. Le deuxième arrondissement est lui aussi parfaitement connecté, il semble simple de se déplacer entre la rive D à l'île C.

Le plan

^rive A

^Pont

La proposition

^Rivière

^Terre ferme

^rive

^île B

^île C

^île

^rive ^A

^Pont

^B

^île C

^Premier ^Deuxième

ⁿ

^Rivière

^{rive D}

Figure 2.17 : Proposition pour créer deux arrondissements dans la ville.

Graphe Orienté

Kaliningrad a changé. Certains ponts sont maintenant à sens unique (cf. figure 2.18).

2.5. Synthèse 80

Chapitre 2. Les algorithmes de création de communautés

Le plan

^île

La proposition

^île

^rive A

^B ^île C

^Pont

^Rivière

^{Terre ferme}

^{rive D}

^rive A

^Pont

^Rivière

^{rive D}

Figure 2.18 : Proposition pour créer trois arrondissements dans la ville en tenant compte des sens interdits.

^Premier

^B

^{île C}

^Deuxième Il est impossible, à cause des sens interdits, de rejoindre en voiture la rive A depuis l'île B et depuis l'île C de rejoindre directement la rive D. Utiliser un graphe orienté permettra de mettre en évidence cette caractéristique et le découpage en arrondissement proposé dans la figure 2.17 n'est plus adapté.

Comme nous le voyons ici prendre en compte l'orientation des liaisons permet d'obtenir des communautés ou arrondissements plus adaptés.

Graphe pondéré et nombre de communautés préétabli

Le problème posé est maintenant identique au problème précédent, mais certains ponts très anciens sont réservés, à un nombre de véhicules restreint (véhicules de moins de 1.5 tonnes et de moins de 1m70 de haut, ce qui correspond à environ 50% du trafic) (cf figure 2.19). De plus, ces ponts sont fermés la nuit ce qui correspond à une perte supplémentaire de trafic. Globalement ces ponts ont un trafic automobile inférieur de 60% à ceux qui ne sont pas soumis à ces restrictions. De plus, pour des raisons de sécurité certains ponts sont aussi interdits aux piétons car les trottoirs sont trop étroits.

2.5. Synthèse 81

Chapitre 2. Les algorithmes de création de communautés

Le plan

^Rivière

La proposition

^rive A

^île B

^île C

^Pont à trafic

^Pont

^Rivière

^{Terre ferme}

^réduit

^rive D

^rive A

Pont

Troisième

^réduit

^{rive D}

Figure 2.19 : Proposition pour créer trois arrondissements dans la ville en tenant compte des sens interdits et de la pondération des ponts par rapport au trafic automobile et piéton.

^Premier

^{île B}

^île C

Deuxième ^{Pont à trafic} La prise en compte des différentes pondérations pour le trafic des automobiles et des piétons sur les ponts de ville, nous conduit à proposer une autre alternative. En effet, la priorité première étant de limiter le trafic inter-arrondissement, la création de deux arrondissements ne peut se faire sans une obligation de déplacement complexe. La création de trois arrondissements permet au contraire de profiter pleinement de la liaison bidirectionnelle, non limitée et ouverte aux piétons que constitue le pont entre les deux îles.

Cet exemple illustre l'importance que peuvent avoir les pondérations de liens, ainsi que la limitation de qualité qui peut être apportée par un nombre de communautés préétabli.

2.5. Synthèse 82

Chapitre 2. Les algorithmes de création de communautés