Intelligences Journal revue en intelligence économique
[English version]

Structuration unilatéralement-connexe prétopologique : une extension de la librairie PretopoLIB

Coralie Petermann, Vincent Levorato et Marc Bui

Résumé

Dans ce papier, nous traitons la question de la connexité unilatérale utilisée dans le cadre de la structuration par composantes des graphes et réseaux orientés. Pour cela, nous avons défini un algorithme permettant de détecter les composantes unilatéralement connexes dans le cadre de la prétopologie, et nous l'avons intégré à la librairie JAVA PretopoLIB.

Abstract

In this paper, we solve the issue of unilateral connectedness used in structuring components of directed graphs and networks. To achieve this, we define an algorithm to detect the components unilaterally related using pretopology, and we integrate this algorithm in the Java library PretopoLIB.

Mots-clés

structuration, théorie des graphes, prétopologie, classification, pretopoLIB, graph theory, pretopology, pretopoLIB

Texte intégral

Introduction

Les réseaux biologiques, sociaux, technologiques, et d'information sont souvent étudiés à l'aide de graphes (Newman, 2003) et l'analyse de graphes est essentielle pour comprendre les caractéristiques de ces systèmes.

Une des caractéristiques les plus pertinentes des graphes représentant des systèmes réels est la structure des communautés. Ce problème n'est pas encore résolu de façon satisfaisante, en dépit du grand nombre d'algorithmes proposés (Lancichinetti & Fortunato, 2009).

Dans ce cadre, nous avons déjà présenté l'algorithme LP11 de classification des réseaux orientés par les composantes fortement connexes de diamètre maximal p qui avait obtenu des résultats très satisfaisants (Levorato & Peterman, 2011). Nous présentons la suite de ce travail, car nous nous concentrons désormais sur les autres types de connexités, plus spécifiquement la connexité unilatérale issue de la prétopologie. En effet, nous proposons de conserver et utiliser toutes les informations des réseaux complexes, en les représentant dans un espace prétopologique à l'aide de relations prétopologiques orientées.

Dans cet article, nous nous attelons à présenter l'algorithme de détection des composantes unilatéralement connexes, et l'extension de la librairie logicielle PretopoLib que nous avons fait pour l'y intégrer. Dans une première partie nous présentons la prétopologie, la théorie mathématique à la base de notre travail, puis nous aborderons les notions de χ-connexité parmi lesquelles figure la connexité unilatérale. Ensuite, nous présenterons notre algorithme de détection des composantes unilatéralement connexes, et enfin, nous conclurons par la présentation de la PretopoLIB et quelques démonstrations.

Prétopologie

La prétopologie est une théorie mathématique ayant une axiomatique plus faible que la topologie classique, et qui permet d'exprimer les transformations structurelles d'ensembles composés d'éléments en interaction tels que la constitution de coalitions parmi une population, les phénomènes d'alliance, les processus de tolérance, d'acceptabilité et l'émergence de comportements collectifs (Belmandt, 2011), (Levorato &Ahat, 2008).

Nous appelons adhérence définie sur E, toute fonction a(.) de P(E) dans P(E) telle que :

  • a() =

  • AE,Aa(A)

Agrandir Image1

Figure 1 : adhérence de A

Nous appelons intérieur défini sur E, toute fonction i(.) de P(E) dans P(E) telle que :

  • i(E) =E

  • AE, i(A)A

Image2

Figure 2 : intérieur de A

Etant donné, un ensemble E, a(.) et i(.), le couple s = (a(.), i(.)) est appelé une structure prétopologique sur E et le 3-uple (E,a(.),i(.)) est appelé espace prétopologique. En prétopologie, un réseau complexe est vu comme une famille de prétopologies sur un ensemble donné E (Levorato, 2011).

Agrandir Image3

Figure 3 : une famille prétopologique composée de 3 espaces

L’avantage de la prétopologie est de pouvoir séparer chaque critère dans un espace prétopologique propre afin de simplifier la modélisation. De cette manière, une modification d’un critère est instantanée.

χ-connexités

La connectivité est un concept intéressant pour les problèmes de modélisation liés à l’homogénéité, ou à la structuration des éléments. Cependant les axiomes de la topologie classique sont souvent en contradiction avec les conditions réelles de terrain, en particulier dans les sciences sociales (Belmandt, 2011).

La prétopologie définit différents types de connexités. Dans cette section, nous considérons un ensemble E, défini par une structure prétopologique s = (i(.),a(.)) de type V. Nous notons σ = (O(.),F(.)) les opérations d’ouverture et de fermeture de E. Il existe différents types de connexité, que l’on nomme les χ-connexités avec χ correspondant à :

  • SC : fortement connexe ;

  • UC : unilatéralement connexe ;

  • HC : hyperconnexe ;

  • AC : apo-connexe ;

  • C :connexe ;

Fortement connexe

Définition

A E,A ̸ = ,F(A) = E (le seul fermé non nul est E).

E est SC si et seulement si A P(E), B P(E), il existe un chemin de A vers B.

Unilatéralement connexe

Définition

E est unilatéralement connexe (UC) si et seulement si : A E, A ̸ = , F (A) = E sinon B E, B ̸ = , B E − F (A) A F (B) ;

Cela revient à dire que E est UC si et seulement si pour tout A P(E) et pour tout B P(E) il existe un chemin de A vers B ou de B vers A (les fermés sont emboités).

Hyperconnexe

Définition

AE, A̸ =, F(A) =E. Sinon B̸ =, BE−F(A), tel que AF(B).

E est HC si et seulement si A P(E),B P(E),il existe un chemin de A vers B ou il existe un chemin de B vers E -F (B), partie qui rencontre A (la fermeture de tout ouvert non vide vaut E).

Apo-connexe

Définition

A, B deux sous-ensembles non vides de E, on a toujours F (A) ∩ F (B) ̸ = .

E est AC si et seulement si A P(E),B P(E), M P(E) avec un chemin de M vers A et un de M vers B.

Connexe

E est C si et seulement si A P(E),B P(E), il existe un chemin de A vers B ou M P(E) avec un chemin de M vers B et un de M vers E-F(B), partie qui rencontre A.

On a alors :

  • E est SCE est UC

  • E est UCE est HC et E est AC

  • E est HCE est C

  • E est ACE est C

Image4

Figure 4 : X-connexités

Dans la partie suivante, nous décrivons précisément notre algorithme de détection des composantes unilatéralement connexes.

Notre algorithme

Notre méthode de recherche des composantes unilatéralement connexe est une approche bottom-up via un parcours en largeur BFS (Breadth First Search) du réseau. Nous parcourons un à un les nœuds d’un même niveau pour tenter de les agréger.

Image5

Figure 5 : parcours BFS

Algorithme

Agrandir Image6

PretopoLIB

PretopoLib est une librairie JAVA implémentant les concepts de la prétopologie (Levorato & Ben Amor, 2010). Son intérêt réside dans la représentation de structures de données permettant la manipulation des données par des opérations ensemblistes. Même si des librairies implémentant la théorie des graphes existent, pretopoLIB est la seule librairie implémentant les concepts prétopologiques. Celle-ci offre un cadre de développement d’algorithmes efficaces pour la fouille de données, la structuration et la modélisation des systèmes complexes.

PretopoLib est écrite en JAVA par Vincent Levorato et Marc Bui (Levorato & Bui, 2008). L’objectif était de proposer un outil réutilisable et distribuable. Celle-ci contient deux principaux sous-modules, PretopoNotion qui implémente les concepts mathématiques et PretopoVisual qui est utilisé comme une surcouche pour la visualisation des données.

Dans la section suivante, nous présentons quelques illustrations de l’extension proposée pour la PretopoLIB.

Démonstrations

Le module de visualisation de la PretopoLIB est basée sur deux libraires externes, Prefuse et JUNG, initialement destinées à la représentation des graphes. Chacune permet de représenter différemment les espaces en fonction des besoins.

Pour tester et visualiser notre méthode, nous avons utilisé un générateur de graphes qui permet des générations complexes de graphes non orienté réaliste et orientés, qui peuvent être facilement utilisés en temps que structures prétopologiques ayant des relations binaires orientées. Nous avons choisi le générateur dit benchmark LFR proposé par Lancichinetti et Radicchi en 2008 (Lancichinetti, Fortunato & Radicchi, 2008) avec le paramétrage suivant :

  • n le nombre de nœuds du graphe (n =50)

  • kavg le degré moyen des nœuds (kavg = 5)

  • kmax le degré maximum des nœuds ( kmax = 10)

  • minc, maxc les tailles minimales et maximales des communautés ( minc = 2, maxc = 5)

  • μ, le paramètre de mixage des communautés i.e. pour chaque nœud, le ratio entre le nombre d’arêtes sortantes et le nombre d’arêtes entrantes de la communauté. (μ = 0.1)

Agrandir Image7

Figure 6 : Exemple d'espace prétopologique mixte (à gauche) et d'une visualisation (à droite).

Image8

Figure 7 : espace prétopologique constitué de 50 nœuds et de relations binaires orientées.

Image9

Figure 8 : PretopoLIB avec surcouche JUNG, structuration par les composantes unilatéralement connexes (7 composantes)

Image10

Figure 9 : PreotpoLIB avec surcouche JUNG, structuration par les composantes fortement connexes (13 composantes)

Comme le montrent les figures précédentes, nous obtenons une structuration des composantes connexes différente de celle par les composantes unilatéralement connexes. Notre algorithme permet donc de structurer différemment certains espaces prétopologiques.

Conclusion

Dans cet article, nous nous sommes concentrés sur la détection de composantes unilatéralement connexes. Notre principale contribution est l’extension de la librairie JAVA PretopoLIB, à travers l’ajout d’un algorithme de détection de ces composantes.

Nous avons encore des travaux d’optimisation de cet algorithme à effectuer, afin d’obtenir une meilleure complexité. La finesse des résultats obtenus est intéressante dans le cadre de grands réseaux fortement connectés. Il serait donc intéressant d’accélérer les temps de traitement encore longs pour effectuer des séries de tests sur des réseaux ayant un degré moyen et un nombre de nœuds élevés.

Par la suite, nous souhaiterions poursuivre nos travaux de structuration par les communautés, et étendre notre algorithme de classification précédent à la structuration par composantes UC (Levorato & Petermann, 2011).

Bibliographie

[1] Berge, C. (1970). Graphes et Hypergraphes. Dunod, Paris.

[2] Vincent Levorato, Coralie Petermann. Detection of Communities in Directed Networks based on Strongly p-Connected Components 3rd IEEE International Conference on Computational Aspects of Social Networks (CASoN’2011), Salamanca, Spain ; 2011.

[3] A. Lancichinetti and S. Fortunato, Community detection algorithms : A comparative analysis, Phys. Rev. E, vol. 80, p. 056117, 2009.

[4] A. Lancichinetti, S. Fortunato, and F. Radicchi, Benchmark graphs for testing community detection algorithms, Phys. Rev. E, vol. 78, no. 4, p. 046110, 2008.

[5] V.Levorato, S. Ben Amor, PretopoLib : la librairie JAVA de la Prétopologie, Extraction et Gestion des Connaissances (EGC), 2010.

[6] M. E. J. Newman. The Structure and Function of Complex Networks. SIAM Review, vol. 45, No. 2. (2003), pp. 167-256.

[7] ZT. Belmandt. Basics of pretopology. Hermann, 155 pages, ISBN : 978 27056 8077, 2011.

[8] Vincent Levorato and Murat Ahat. Modélisation de la dynamique des réseaux complexes as- sociée à la prétopologie. 9eme congrès de la Société Franc ̧aise de Recherche Opérationnelle et d’Aide a la Décision, ROADEF08, Clermont-Ferrand, France, February 2008.

[9] V. Levorato. Modeling Groups in Social Networks, In Proceedings of the 25th European Conference on Modelling and Simulation (ECMS’2011), pages 129-134, Krakow, Poland, 2011.

[10] V. Levorato. Contributions à la Modélisation des Réseaux Complexes : Prétopologie et Applications. PhD thesis, Université de Paris 8, 2008.

[11] V. Levorato, M. Bui (2008). Pretopolib. Dépôt de logiciel à l’Agence pour la Protection des Programmes. IDDN.FR.001.470004.000.R.P.2008.000.20600.

Pour citer ce document

Coralie Petermann, Vincent Levorato et Marc Bui, «Structuration unilatéralement-connexe prétopologique : une extension de la librairie PretopoLIB», Intelligences Journal [En ligne], Numéros en texte intégral , Numéro 2 , URL : http://lodel.irevues.inist.fr/isj/index.php?id=215

Auteurs

Coralie Petermann
Prism, Université de Versailles St-Quentin-en-Yvelines, FR-78035 Versailles
Vincent Levorato
CESI, 959 rue de la Bergeresse, F-45160 Olivet
Marc Bui
LaISC, 41 rue Gay-Lussac, F-75005 Paris