Jean-Stéphane Ulmer
email: jeanstephane.ulmer@ensiacet.fr

Jean-Pierre Belaud
email: jeanpierre.belaud@ensiacet.fr

Jean-Marc Le Lann
email: jeanmarc.lelann@ensiacet.fr

Approche pour un meilleur alignement des processus métiers De la modélisation à l'implémentation

Keywords: ingénierie de systèmes d'information, ingénierie dirigée par les modèles, alignement de modèles, ingénierie des processus métiers, métamodèles, transformation information system engineering, model-driven engineering, model alignment, business process management, metamodels, transformation

Une entreprise doit être capable de décrire et de demeurer réactive face à un évènement endogène ou exogène. Une telle flexibilité peut s'obtenir par la gestion des processus d'entreprise. Lors d'une telle démarche, différentes transformations interviennent sur les modèles de processus développés par l'analyste métier et l'expert en technologies de l'information (TI). Un non-alignement se crée entre ces modèles hétérogènes lors de leurs manipulations : il s'agit du « fossé métier-TI » tel que décrit dans la littérature. L'objectif de notre travail est de proposer un cadre méthodologique permettant un meilleur pilotage des processus métiers, afin de tendre vers un alignement systématique de leur modélisation à leur implémentation au sein du système cible. En permettant la restitution intégrale d'un modèle transformé au sens de l'ingénierie inverse, notre plateforme permet une synchronisation entre modèle d'analyse et modèle d'implémentation.

ABSTRACT. A company must be able to describe and remain reactive against endogenous or exogenous event. Such flexibility can be achieved through the Business Process Management. In this approach, different transformations intervene on process models developed by the business analyst or the IT expert. A non-alignment is created between these heterogeneous domains during model manipulations: this is the "business-IT gap" as described in the literature. The aim of our works is to propose a methodological framework enhancing business process control, in order to obtain a systematic alignment from modelling to its implementation within the target system. By allowing a full restitution of a transformed model, our platform enables synchronization between analysis and implementation models.

Introduction

Pour que les organisations demeurent compétitives dans un environnement socioéconomique dynamique, elles doivent être en mesure de saisir de nouvelles opportunités, de réagir efficacement face à de nouvelles demandes. Dans cette optique, dès les années 1960, les systèmes d'information et les technologies d'information associées (SITI) furent mis en oeuvre afin de supporter la création de valeur au sein d'une entreprise. Rapidement, ces SITI ont pris une place de plus en plus importante au sein des organisations. En effet, posséder un système d'information efficace et efficient supportant les stratégies métiers et les processus qui y sont rattachés est devenu un facteur-clé de succès [START_REF] Luftman | Key issues for IT executives[END_REF]. Les SITI contribuent à la création de valeur, et ce, d'une manière reconnue : l'alignement entre la stratégie d'entreprise et les choix de déploiement des SITI est devenu un élément important de préoccupation pour les organisations [START_REF] Silvius | Business & IT Alignment in theory and practice[END_REF].

Selon [START_REF] Henderson | Strategic alignment: Leveraging information technology for transforming organizations[END_REF][START_REF] Cifuentes | Contribution à l'alignement complet des systèmes d'information techniques[END_REF] cet alignement peut être un ajustement stratégique dont la finalité est d'accroître la performance organisationnelle de l'entreprise. L'alignement peut également être d'ordre opérationnel (figure 1). Egalement désigné comme l'intégration fonctionnelle de l'entreprise, il en améliore la flexibilité métier. Cette amélioration se traduit par une réponse plus rapide aux nouveaux besoins client. [START_REF] Henderson | Strategic alignment: Leveraging information technology for transforming organizations[END_REF] Cette flexibilité se traduit par l'utilisation de processus d'entreprise supportés efficacement par les systèmes d'information (SI). Ils permettent notamment de mettre en oeuvre la stratégie concurrentielle de l'entreprise (Business strategy). Cette stratégie résulte de l'ajustement entre la stratégie de l'entreprise et de ses processus métiers ainsi que de l'intégration fonctionnelle de ces derniers avec les processus SITI.

Si l'intérêt de réaliser un tel alignement est reconnu, sa mise en oeuvre reste trop souvent limitée, en particulier pour l'intégration fonctionnelle. Il n'est pas rare que les acteurs de l'organisation ignorent les notions propres à cet alignement, de même qu'il existe une absence de communication entre domaine métier et domaine SITI [START_REF] Etien | Business process/information system co-evolution[END_REF]. Une discontinuité franche entre le domaine métier et le domaine SITI se crée. Au lieu de permettre et d'accompagner le changement des processus, les SI peuvent brider ou ralentir la mise en place de telles évolutions.

Problématique et objectifs

Nos travaux sont motivés par la réalisation d'une intégration fonctionnelle réversible au sens de la rétro-ingénierie, que nous qualifierons d'alignement opérationnel, entre domaine métier et domaine SITI selon une approche orientée processus. Néanmoins plusieurs difficultés inhérentes à l'utilisation d'une telle approche subsistent. Tout d'abord, une définition appropriée de l'alignement opérationnel et de ses propriétés est requise. Ces différentes propriétés doivent être respectées par notre approche solution.

Nous examinons les différentes représentations que revêt un processus au cours de son cycle de vie. Considérons ainsi la manipulation de modèles de processus schématisée au sein de la figure 2.

Typiquement, après sa conception, un modèle « papier » abstrait et décrivant un processus et son objectif stratégique, est transformé en un modèle métier. Ce modèle, plus ou moins formel, est fréquemment utilisé dans un but de documentation ou de communication. Il subit à son tour une transformation afin d'être utilisé par un SI. Cependant des modifications et ajustements sont souvent nécessaires afin de rendre le modèle SITI obtenu pleinement exploitable. Ces modifications contribuent à l'obtention d'un modèle SITI raffiné.

Il faut garder à l'esprit que ces diverses transformations s'effectuent essentiellement manuellement et de manière ad hoc, ponctuelle. Dès lors, pouvonsnous considérer ces différents modèles comme étant cohérents entre eux, représentent-ils le même processus ?

De plus ces modèles sont également amenés à évoluer. Le modèle métier peut décrire de nouveaux buts à atteindre, le modèle SITI devra s'adapter à de nouvelles technologies. Ces cycles de vie asynchrones entre modèles d'abstraction et de domaines différents entraînent une discontinuité entre le processus souhaité et le processus implémenté par le SI. Dès lors, des efforts de synchronisation et de cohérence entre modèles s'avèrent nécessaires.

Afin de répondre à ces problématiques, le reste de l'article est organisé de la manière suivante. Tout d'abord nous présentons les principaux concepts rattachés aux notions de processus et d'ingénierie des processus dans la section 3. Nous cherchons ainsi à mettre en évidence l'hétérogénéité des modèles manipulés au sein d'une approche orientée processus. La section 4 se concentre sur la notion d'alignement opérationnel qui devient dès lors nécessaire. Nous proposons des propriétés le définissant et que notre approche doit prendre en compte. A ces propriétés s'ajoutent celles présentées section 5 dont la motivation est d'améliorer l'agilité d'entreprise. La section 6 caractérise l'approche et la section 7 présente la plateforme associée que nous avons développée. Cette plateforme est ensuite éprouvée à travers un scénario-test défini dans la section 8. Enfin la section 9 clôture cet article en énonçant les conclusions et perspectives relatives à nos travaux de recherche. Les différentes étapes parcourant le cycle de vie d'un processus métier sont représentées sur la figure 3, inspirée de [START_REF] Muehlen | Workflow-based Process ControllingFoundation, Design, and Application of Workflow-driven Process Information Systems[END_REF]. L'ingénierie des processus métiers ou Business Process Management (BPM) considère ce cycle de vie en en regroupant les étapes selon trois grandes phases [START_REF] Debauche | BPM Business Process Management : Pilotage métier de l'entreprise[END_REF].

Un processus peut être considéré selon deux domaines bien distincts. Le domaine métier regroupe les étapes relatives à l'analyse, la conception (qu'il s'agisse de la modélisation ou de l'optimisation), l'évaluation et la simulation du processus. Le domaine SITI possède les étapes ayant un objectif d'automatisation du processus : son implémentation, son exécution, et le prélèvement de données relatives à cette exécution.

Figure 3. Cycle de vie du processus

Nous observons également que chaque domaine est régi par un acteur spécifique. L'analyste métier cherche de nouvelles façons d'améliorer l'efficacité « métier » de son entreprise, notamment en modifiant les processus [START_REF] Various | A Guide to the Business Analysis Body of Knowledge (BABOK)[END_REF]. Une des caractéristiques importantes d'une démarche d'ingénierie des processus métier est la possibilité pour un analyste métier de définir les processus métiers sans aucune compétence technique. Ainsi un modèle source doit être réalisé indépendamment des considérations de l'environnement cible. Cette première phase regroupant les étapes d'analyse et de conception du processus est la phase d'analyse ou Business Process Analysis (BPA). Suite à la phase d'analyse, nous obtenons un modèle d'analyse, conceptuel, peu ou pas formel, reposant sur un langage graphique et créé dans un but de documentation. les modèles sont-ils synchronisés ? s'agit-il de modèles sémantiquement équivalents ? au final, ces modèles sont-ils cohérents entre eux ? Afin de demeurer le plus formel possible, nous proposons une définition de chacun de ces différents termes, ainsi que leurs répercussions sur l'approche solution proposée.

Nous considérons que deux modèles, i et j, sont dits synchronisés si et seulement si des changements significatifs effectués sur le modèle i peuvent être répercutés sur le modèle j (est considéré comme significatif tout changement modifiant la structure et/ou le comportement d'un modèle). La solution envisagée doit assurer la propagation des modifications significatives d'un modèle à un autre afin de maintenir ces modèles synchronisés. Dans ce contexte, nous considérons comme significatif tout changement modifiant la structure et/ou le comportement d'un modèle.

Nous définissons deux modèles i et j comme sémantiquement équivalents si pour chaque élément appartenant à E i , un élément (ou un ensemble d'éléments) appartenant à E j peut lui être associé. Chacun de ces éléments associés doit suivre la même orchestration. Notre approche doit être en mesure de déterminer les relations sémantiques existantes entre éléments de modèles différents.

Enfin, nous établissons qu'il existe une cohérence dite « intermodèle » entre deux modèles si nous observons une équivalence sémantique et s'ils sont synchronisés entre eux. Cette cohérence intermodèle est considérée comme une condition nécessaire et suffisante d'un alignement opérationnel. En respectant les différents points présentés ici, l'approche proposée permet d'obtenir un alignement opérationnel entre domaine métier et domaine SITI.

Principes de modélisation considérés

A l'aide des propriétés énoncées précédemment, l'approche proposée doit être en mesure de réduire l'écart métier-SITI. Pour cela notre approche s'appuie sur une plateforme permettant la transformation des modèles d'analyse vers les modèles d'implémentation et garantissant la cohérence intermodèle. Afin de faciliter et de formaliser ces transformations, nous définissons un couplage faible entre modèles ainsi que l'utilisation systématique de métamodèles.

La principale limite rencontrée au sein d'un cycle d'ingénierie des processus réside dans la « discontinuité » entre le domaine métier et le domaine SITI. Cette discontinuité intervient notamment lors du passage d'un modèle d'analyse vers un modèle d'implémentation. Majoritairement, la solution logicielle choisie pour supporter ces transformations est un BPMS (BPM Suite). Il convient de garder à l'esprit que les modèles sont amenés à être modifiés, les processus représentés et les technologies de l'information utilisées pouvant évoluer. Des efforts de synchronisation, de mises à jour et de cohérence entre modèles s'avèrent nécessaires. L'entreprise et la nature de ses modèles étant en perpétuelle évolution, elles doivent pouvoir s'adapter à différents éditeurs ou à de nouvelles technologies. Cependant l'approche intégrée de modélisation basée sur un atelier logiciel unique comme le BPMS, se traduit par une dépendance forte à l'éditeur. L'entreprise ne possède plus la possibilité de modifier l'outil de modélisation voire la plateforme d'intégration, indépendamment l'un de l'autre. De ce fait l'entreprise n'est plus pleinement en mesure de modifier son outil de modélisation, son moteur d'exécution ou de s'adapter à de nouvelles technologies.

A l'inverse d'une approche fortement intégrée préconisant l'utilisation d'un éditeur logiciel unique, nous cherchons à obtenir un couplage faible entre les modèles d'analyse et les modèles d'implémentation. Ici la notion de couplage faible signifie que bien qu'il existe une interaction forte entre modèles, ceux-ci demeurent indépendants (l'analyste métier peut modifier le modèle d'analyse sans se soucier des répercussions sur le modèle technique, et inversement) et les environnements associés restent modifiables. Nous désirons également délimiter une stricte séparation entre ce que nous appellerons l'environnement de modélisation et l'environnement d'implémentation.

Approche orientée pivot

Respectant « l'approche pivot » exploitée dans l'interopérabilité système [START_REF] Meinadier | Le métier d'intégration de systèmes[END_REF], le rôle du pivot est d'assurer une équivalence sémantique entre un modèle conceptuel et le modèle d'implémentation lui correspondant.

A travers nos différents travaux (Ulmer et al., 2009 ;2010a), nous proposons une méthode centrée pivot afin d'améliorer l'alignement des différents modèles issus des phases d'analyse (BPA) et d'implémentation (BPI). L'alignement parfait tel que défini par [START_REF] Etien | Ingénierie de l'alignement: Concepts, Modèles et Processus -La méthode ACEM pour l'alignement d'un système d'information aux processus d'entreprise[END_REF] A un niveau d'abstraction inférieur, nous pouvons considérer, par exemple, les systèmes de gestion de bases de données (SGBD) notamment pour les bases de données relationnelles et la méthode MERISE [START_REF] Baptiste | Merise -Guide Pratique -Modélisation des données et des traitements, langage SQL[END_REF]. L'utilisation de modèles différents dans les bases de données composantes pose des problèmes d'hétérogénéité syntaxique. Une solution possible est de traduire tous ces schémas en un modèle commun, le modèle pivot, nommé le modèle logique de données.

Le concept de pivot n'est pas non plus inconnu au sein du domaine métier du Process Systems Engineering (PSE). Le rapide développement d'outils d'ingénierie des procédés assistée par ordinateur a entraîné le développement du standard CAPE-OPEN [START_REF] Belaud | Architectures et technologies des systèmes logiciels ouverts -Cape-Open, un standard pour l'intéropérabilité et l'intégration des composants logiciels de l'ingénierie des procédés[END_REF]. CAPE-OPEN a pour rôle d'accroître l'interopérabilité entre outils logiciels PSE. Tel un pivot de bas niveau, CAPE-OPEN permet, via son middleware, à des logiciels hétérogènes d'éditeurs différents d'interopérer, indépendamment de leurs langages de programmation et de leur système opérant. devient alors nécessaire pour stocker et échanger les informations des modèles entre les environnements de modélisation et d'implémentation.

Dans les sections suivantes, nous établissons la couverture de notre approche et les acteurs nécessaires à sa réalisation.

Vues

Nous cherchons à représenter la plupart des modèles de processus. Pour cela, nous devons considérer les différentes vues d'une entreprise. En effet un processus est représenté selon de nombreuses vues afin de rester compréhensible. Chacune de ces vues permet de décrire un aspect important du modèle de processus [START_REF] Touzi | Aide à la conception de Système d'Information Collaboratif, support de l'interopérabilité des entreprises[END_REF]ISO, 2005). La vue fonctionnelle décrit les processus et leurs structures. La vue informationnelle décrit les données et les documents qu'un processus utilise ou produit. La vue organisationnelle définit les acteurs et les rôles qui sont responsables de l'exécution d'un processus donné. La vue des ressources définit les outils et les systèmes qui supportent l'exécution du processus. Enfin, la vue comportementale décrit l'ordre dans lequel les processus sont exécutés. La figure 6 met en évidence les liens existants avec ces vues. Considérons par exemple BPMN 2 , un langage standard de modélisation de processus d'entreprise, il est centré sur la vue fonctionnelle, mais il permet de représenter les documents émis ou reçus (vue informationnelle) et de définir des actions intervenant au sein des réseaux de circulation des produits/informations (vue des ressources). L'opération inverse (depuis un modèle d'implémentation vers un modèle d'analyse) se réalise de la même manière et nécessite une même prise en charge par l'architecte de processus.

Acteurs et données

Nous avons vu le champ d'application de l'approche, ses acteurs et le type de données manipulées. Dans la suite de cette section, nous exposons les efforts de conception qui ont accompagné la définition de notre approche. L'ensemble de cette section relative à la conception de notre approche est explicité plus en détail dans (Ulmer et al., 2010b). Les différents points de conception abordés dans cet article sont illustrés au sein du projet de développement logiciel décrit dans la section suivante. Les différents mappings sont réalisés à l'aide de Kermeta. Kermeta peut être utilisé comme un tisseur d'aspect adapté aux métamodèles Ecore, capable de les manipuler sans les modifier. Pour cela, nous utilisons Kermeta avec le pattern de conception Visiteur [START_REF] Gamma | Design patterns. Catalogue des modèles de conception réutilisables[END_REF].

Plateforme SCALP

Mise en oeuvre

Le processus métier que nous manipulons afin d'étayer nos propos est un processus de réintégration de produits ayant subi un contrôle qualité. Ce processus a été récemment mis en place par un grand groupe de cosmétique pour ses unités de production de parfum. Le but de ce processus est de réinjecter dans le flux de production le lot prélevé et contrôlé par le département Qualité, de manière à réduire les pertes financières. Il est utilisé comme un exemple de référence pour valider notre plateforme et démontrer notre approche. Pour cet article, nous utilisons ce modèle de processus à travers un scénario à deux phases. Durant la première phase, nous effectuons une transformation depuis le diagramme Intalio de processus vers un module OpenERP. Puis à travers la deuxième phase nous réalisons la transformation inverse, depuis le module OpenERP vers le diagramme Intalio. Au préalable, nous effectuons des modifications fonctionnelles et structurelles au module OpenERP créé (figure 12). Ces modifications sont décrites section 8.2.

Figure 12. Scénario de démonstration

Ce scénario implique l'ensemble des acteurs décrits dans la section 3.1. Il permet de mettre en évidence les différents mécanismes et interactions intervenant lors d'une transformation « simple » depuis un modèle d'analyse vers un modèle d'implémentation. Le scénario met également en exergue l'utilité de notre plateforme et notamment les efforts de synchronisation, d'équivalence sémantique et donc de cohérence entre modèles lors de la transformation inverse.

Première phase : du diagramme de processus Intalio Designer au module OpenERP

Nous considérons que les métamodèles d'analyse, d'implémentation et pivot, soit respectivement MM BPA , MM BPI et MM Pivot , existent et sont bien définis. La première phase consiste à transformer un diagramme de processus respectant une charte graphique en un module exécutable sous un ERP.

Du diagramme de processus Intalio vers un modèle d'analyse m BPA

Nous importons les fichiers XML obtenus à partir d'Intalio Designer au sein de notre plateforme SCALP : le premier fichier décrit les informations graphiques, le second considère la logique exprimée par le processus. La transformation t1 est un programme java utilisant le parseur XML JDOM 7 . Cette transformation crée le modèle m BPA à partir des deux fichiers cités précédemment (figure 13). A titre d'illustration d'utilisation du modèle pivot, considérons le mapping m1 de l'élément Activity. Le tableau 3 définit les correspondances existantes entre les différents attributs selon qu'il s'agisse d'une activité définie par le MM BPA ou par le MM Pivot . Nous pouvons constater que de manière générale, la définition des éléments du MM Pivot englobe celles des éléments du MM BPA . Il en va logiquement de même entre MM Pivot et MM BPI . Les informations concernant l'aspect graphique de l'élément Activity sont contenues dans l'élément BPElement du métamodèle pivot. Cet élément permet de prendre en considération des informations n'influençant pas le modèle BPA et/ou le modèle BPI mais jugées nécessaires dans un but de rétroingénierie des processus (figure 14).

Du modèle d'implémentation vers le module OpenERP

A partir du mBPI obtenu, nous constituons le module OpenERP, il s'agit de la transformation t4 représentée figure 16. Ces différents types de fichier sont représentés et détaillés dans (Ulmer et al., 2010a).

Deuxième phase : du module ERP au diagramme de processus

Le module OpenERP obtenu à l'étape précédente n'est pas intégralement utilisable en l'état. Ainsi les fichiers nomModule.py et nomModuleView.xml demandent un apport d'information afin d'être utilisables. A cet effet, ces fichiers sont amenés à être modifiés par l'expert SITI : des fonctionnalités liées à l'interface OpenERP ou à l'affichage du module doivent être implémentées. En effet, à ce stade de développement, la génération de l'interface du module OpenERP reste très générique. L'ergonomie est à retravailler au cas par cas, de même que le choix des informations à afficher.

Conformément au scénario décrit en début de section 8, nous effectuons des modifications d'ordre technique sur le module OpenERP. Le fichier nomModule.py décrit la vue fonctionnelle de notre processus, des fonctions logiques exprimées en langage python sont ajoutées. Ces fonctions représentent les actions réalisées par les différentes activités du processus de réintégration. Par exemple, nous désirons ajouter une fonctionnalité évaluant le temps effectif passé sur un lot ciblé. Nous effectuons également des modifications de type structurel, nous simulons l'ajout d'une activité permettant de mettre à jour la liste des lots de produits semi-finis utilisés dans le processus de réintégration, il s'agit de l'activité « Mettre la liste à jour ». Cet ajout se traduit par une modification du control-flow. En effet l'ajout de l'activité provoque des changements au niveau du séquencement : il s'agit d'une modification significative. Les fichiers nomModule.py et nomModule_workflow.xml sont modifiés en conséquence à l'aide de l'éditeur d'OpenERP. REMARQUE. -Si lors de cette deuxième phase, les modifications apportées ne concernaient que les fonctionnalités des activités du processus (autrement dit leur exécution sous OpenERP) et l'apparence du module OpenERP, le diagramme de processus obtenu est identique à celui utilisé lors de la première phase.

Du module OpenERP vers le modèle d'implémentation

En résumé

Lors de la première phase, nous avons réalisé la transformation d'un modèle conceptuel, un diagramme de processus, en un modèle technique, un module ERP. A chaque étape de cette transformation, la conformité entre le modèle xmi obtenu et son métamodèle est validée à l'aide d'Ecore. Durant cette phase, nous avons pu montrer comment nous préservions les données non utilisables par le modèle technique, à l'aide du modèle pivot. Ces données sont restituées lors de la seconde phase, nous permettant d'obtenir un modèle conceptuel complet.

A travers les différentes transformations, nous générons un modèle de sortie prenant directement en compte les modifications subies par le modèle d'entrée (par exemple la création d'une activité) ou indirectement (modifications des instructions python associées à une activité). Les modifications étant propagées lors de ces transformations et l'intégrité des informations étant assurée, notre approche permet une synchronisation et une équivalence sémantique des modèles. Nous obtenons alors une cohérence intermodèle et donc un alignement opérationnel.

Les contributions apportées ainsi que nos travaux futurs sont décrits dans la section suivante. Afin de supporter cette approche, une solution logicielle a été développée, la plateforme SCALP dont une démonstration a été réalisée à l'aide d'un processus issu de l'industrie cosmétique. Son utilisation améliore l'alignement opérationnel entre d'une part, les infrastructures et les processus d'entreprise et, d'autre part, les infrastructures et les processus techniques. Et en permettant un couplage faible entre modèles ainsi qu'une formalisation des transformations à l'aide de métamodèles, notre approche et la plateforme qui lui est associée améliorent l'agilité d'entreprise.

Conclusions et perspectives

Diverses perspectives sont envisagées suite à nos travaux. Il s'agira tout d'abord d'éprouver notre plateforme en utilisant des processus plus spécifiques et/ou détaillés issus de PME/PMI. Cela nous permettra d'évaluer si l'expressivité du métamodèle pivot est suffisante.

Nous chercherons également à étayer l'aspect « couplage faible » de notre plateforme. Pour cela, son utilisation avec de nouveaux outils est envisagée (avec par exemple Bizagi Process Modeler en amont et des outils de suites bureautiques type Microsoft Excel en aval).

L'approche que nous proposons a été développée dans une optique de génération de code. Prendre en considération une optique d'orchestration de services préexistants pourrait la compléter. Pour cela, les mécanismes manipulant la partie pivot de notre approche devront être modifiés et fournir des méthodes de décomposition ou détection des éléments du processus en services déclarés préalablement. La plateforme cible serait des SI à base de composants ou packages standard de services.

A l'aide de notre approche, nous avons cherché à définir les liens existant entre les SI (infrastructures et processus techniques) et les unités métiers (infrastructures et processus d'entreprise), et ainsi apporter notre contribution à la littérature. Nous avons réduit nos travaux au domaine interne en nous préoccupant essentiellement de ces infrastructures SITI et des processus d'entreprise. Des travaux futurs pourront être menés sur la relation entre domaine interne et les stratégies employées par l'entreprise. L'étude de cet ajustement stratégique, menée notamment par [START_REF] Thevenet | Alignement de la stratégie et du système d'information[END_REF][START_REF] Cifuentes | Contribution à l'alignement complet des systèmes d'information techniques[END_REF] Le processus considéré est un processus de réintégration de produits ayant subi un contrôle qualité. Ce processus a été récemment mis en place par un grand groupe de cosmétique pour ses unités de production de parfum. Nous l'utilisons ici comme un exemple de référence pour valider notre plateforme et démontrer notre approche. Durant le conditionnement des produits, un pourcentage de la production est prélevé afin d'être contrôlé par le département Qualité. Le lot prélevé doit ensuite être réinjecté dans le flux de production afin d'éviter des pertes financières importantes. Cependant, les produits testés constituant ce lot sont ouverts durant ce contrôle. La réintégration concerne un flux de 300 000 produits par an, selon 94 formats de produits différents. Ceci implique de reconstruire l'emballage du produit avec un film cellophane sur une ligne de fabrication adéquate et de l'encrypter contre le détournement de produits. Un processus de réintégration de parfums est alors défini afin de rendre la majorité du lot réutilisable. Il est mis en place au sein de l'organisation Le processus commence lors du prélèvement d'un lot de produits sur une ligne de production. Le lot est contrôlé par le laboratoire de Qualité. Les produits du lot prélevé à un instant t peuvent être de trois types différents (figure 22 -a). ( 1) Les produits destinés à la vente nécessitent une étape de cellophanage avant d'être envoyés à une centrale de distribution. (2) Les produits testeurs ne nécessitent pas de cellophanage avant leur envoi en centrale de distribution. (3) Les produits semi-finis ne nécessitent pas non plus une étape de cellophanage mais requièrent un traitement interne pour une éventuelle utilisation future. Il faut également considérer que l'étape de cellophanage ne s'effectue que sur une ligne de production vide afin d'éviter des mélanges de numéro de lot (figure 22 -b). Avant leur envoi en centrale, les lots constitués de produits de type 1 ou 2 suivent une étape de remise en conformité puis une étape de constitution de palette (figure 22 -c).

Figure 1 .

 1 Figure 1. Modèle d'alignement stratégique selon[START_REF] Henderson | Strategic alignment: Leveraging information technology for transforming organizations[END_REF]

Figure 2 .

 2 Figure 2. Processus de transformation depuis un modèle métier vers un modèle SITI

A

  travers la phase d'implémentation, ou Business Process Implementation (BPI), l'expert SITI prend en charge ces besoins métiers et les transforme selon des considérations techniques afin de les rendre exploitables par un SI. Pour cela, il ajoute des informations techniques : le format des messages échangés, les protocoles de transport utilisés, les transformations de données effectuées, etc. Une fois modifié, nous obtenons un modèle d'implémentation, technique et formel, adoptant un langage textuel. La finalité du modèle est d'être implémentée par un moteur d'exécution de processus. Une phase de supervision des processus ou Business Activity Monitoring (BAM) conclut ce cycle. Elle fournit un ensemble d'outils assurant le pilotage de l'entreprise par un ensemble d'indicateurs d'analyse de performance, métriques calculées sur la base des mesures obtenues lors de la phase d'implémentation. Nous disposons ainsi des mesures nécessaires à l'évaluation et l'optimisation des processus. Dans le cadre de nos travaux, nous nous sommes plus particulièrement intéressés aux phases d'analyse et d'implémentation. La section suivante décrit plus en détail leur interaction. 4. Alignement opérationnel L'alignement opérationnel intervient lors de l'interaction entre modèles hétérogènes et de domaines différents. Typiquement, le modèle conceptuel issu de la phase d'analyse est transformé en un modèle technique, le modèle d'implémentation. Or la représentation d'un processus selon des critères métiers peut être imprécise, ambigüe et sujette à interprétations d'un point de vue informatique. Dès lors les experts SITI peuvent considérer que le modèle d'implémentation obtenu présente des irrégularités et nécessite des ajustements afin d'être pleinement exploitable (figure 4).

Figure 4 .

 4 Figure 4. Du modèle d'analyse au modèle d'implémentation, et inversement

  Qu'un modèle soit défini selon l'environnement d'analyse ou bien celui d'implémentation, il obéit à un langage d'expression et des règles structurelles. Ce langage et ces règles peuvent être formalisés sous la forme d'un métamodèle. Ainsi, les environnements de modélisation et d'implémentation possèdent chacun un métamodèle. Sans métamodèles, les règles de transformation entre modèles d'analyse et d'implémentation sont peu flexibles car définies au cas par cas. Conformément aux principes de l'ingénierie dirigée par les modèles (IDM) (Combemale, 2008), nous utilisons des métamodèles afin de systématiser et de formaliser ces transformations. Les différentes relations entre ces métamodèles et modèles sont représentées figure 5. L'émergence d'un élément central, support de la transformation, est détaillée plus en détail dans la section suivante : l'environnement pivot.

Figure 5 .

 5 Figure 5. Métamodèles et modèles

  peut être obtenu par l'utilisation d'un pivot. Le concept de pivot a déjà été utilisé selon divers niveaux d'abstraction. Pour l'implémentation des transformations de ses modèles, le projet FAROS 1 (Blay-Fornarino et al., 2008) utilise cette notion de pivot. Il s'agit ici de transposer des éléments métiers, des contrats, au sein de plateformes techniques. L'utilisation d'un modèle et d'un métamodèle pivot permet de formaliser ces transformations depuis la maîtrise d'ouvrage vers la maîtrise d'oeuvre et de les rendre reproductibles. Nous pouvons également citer les travaux de (Thevenet, 2010) et la méthode INSTAL (« INstal Strategic ALignment »). Cette méthode s'intéresse aux intentions d'alignement partagées par les deux niveaux à aligner (stratégique et opérationnel) et qui représentent ici l'alignement stratégique.

Figure 6 .

 6 Figure 6. Vues de modélisation d'une entreprise

  Nous avons précédemment décrit que deux acteurs sont considérés lors d'une approche orientée processus classique : l'analyste métier et l'expert SITI. Lors d'une transformation de modèles depuis un environnement vers un autre, trois types de données sont échangées entre ces acteurs : -(a) des données utilisables d'un modèle d'analyse lors de sa transformation vers un modèle d'implémentation. Il s'agit typiquement de données génériques et qui peuvent être réutilisées en modifiant l'environnement d'analyse ou encore celui d'implémentation ; -(b) des données non prises en compte, car jugées inutiles, par exemple des données d'ordre graphique, des annotations sur le modèle ; -(c) des données apportées de manière interne, indépendamment de l'autre acteur ici l'analyste métier. Il s'agit par exemple de données permettant de rendre le modèle SITI exploitable. Ces différents acteurs et les données échangées sont représentés sur la figure 7.

Figure 7 .

 7 Figure 7. Différents acteurs, différents types de données

Figure 8 .

 8 Figure 8. Trois environnements, trois acteurs

Figure 9 .

 9 Figure 9. Modèles, métamodèles, métamodèle pivot

Figure 10

 10 Figure 10. Plateforme SCALP

  Figure 11. Architecture de SCALP

Figure 13 .

 13 Figure 13. Transformation t1 : du diagramme de processus au m BPA

Figure 14 .

 14 Figure 14. Exemple d'utilisation de l'élément BPElement

Figure 15 .

 15 Figure 15. Extrait du m BPI obtenu

Figure 16 .

 16 Figure 16. Transformation t4 : du m BPI au module OpenERP

Figure 17 .

 17 Figure 17. Transformation t4' : du module OpenERP au m BPI

Figure 18 .

 18 Figure 18. Transformation t5 : du mBPI au mPivot 2

  Dans cet exemple les modifications portant sur l'orchestration des activités effectuées par l'expert SITI sont correctement répercutées sur le diagramme Intalio. L'ajout de l'activité « Mettre la liste à jour », activité suivant l'activité « Traiter les produits semi-finis » et précédant l'activité « Traiter en interne » est bien représenté comme le montre la figure 20. Lors de la génération du modèle pivot, les attributs graphiques de cet élément ont une valeur par défaut définie par l'architecte des processus (« 0 », « null » ou « empty » selon les cas), d'où sa présence à l'origine du diagramme (avec ses coordonnées x = 0 et y = 0).

Figure 19 .

 19 Figure 19. Transformation t1' : du mBPA 2 au diagramme Intalio

  Nos principales contributions furent de définir l'alignement opérationnel et sa réalisation au sein d'une entreprise. Pour cela nous préconisons l'utilisation d'une approche orientée pivot permettant une cohérence intermodèle entre modèles hétérogènes et un couplage faible entre environnements d'analyse et d'implémentation. L'obtention systématique d'une synchronisation, d'une équivalence sémantique et finalement d'une cohérence intermodèle permettent de réduire l'écart existant entre le domaine métier et le domaine SITI.

  permettrait d'élargir les possibilités de notre approche. Nous serions en mesure de conceptualiser l'ensemble des séquences d'alignement telles que définies par le Strategic Alignment Model (SAM). Une autre perspective possible à prendre en compte est la possibilité d'inclure un environnement dédié à la supervision des processus métiers, le BAM. Son rôle serait de fournir les outils nécessaires permettant d'obtenir un retour d'informations sur l'utilisation et l'exécution des processus issus de l'environnement SITI. Les informations devront ensuite être transmises à l'environnement métier sous forme d'indicateurs de performance significatifs. Annexes Annexe A. Diagramme des cas d'utilisation de la plateforme SCALP Le système considéré (« System » sur la figure suivante) est la plateforme SCALP.

Figure 21 .

 21 Figure 21. Diagramme des cas d'utilisation de la plateforme SCALP

  La plateforme SCALP et les environnements considérés sont représentés figure 10. Les différents outils et technologies impliqués sont répertoriés au sein du tableau 1. Si le prototype obtenu repose sur des outils spécifiques, l'approche mise en oeuvre reste indépendante des outils technologiques utilisés. Un diagramme des cas d'utilisation est présent en annexe 1 (figure 21). Abordons plus en détail l'architecture de cette plateforme logicielle. Tout d'abord, les différents métamodèles sont définis : le langage de représentation (MM_Rep) est décrit à l'aide d'Ecore et l'ensemble des règles (RefMet) grâce à Kermeta. Ulmer (2011) décrit en détail cette conception. Le contenu du RefMet est très dissemblable selon qu'il exprime les règles relatives à l'analyse, l'implémentation ou encore au pivot. Le RefMet du métamodèle d'analyse décrit les règles métiers portant sur le comportement. Le RefMet du métamodèle d'implémentation désigne l'ensemble des règles et contraintes que nous avons rencontrées lors de la réalisation de l'environnement d'implémentation. Le RefMet pivot assimile les deux RefMet précédemment cités afin de fournir des règles de contrôle et des valeurs par défaut des différents éléments du métamodèle pivot lors de leur instanciation.

	est réalisée à l'aide d'Ecore 0.7.0 et est appuyée par le langage Kermeta 6 1.3.0
	(« Kernel Metamodeling »). Tableau 1. Technologies et applications impliquées
	Niveau	Outil de modélisation	Environnement d'analyse	Environnement pivot	Environnement d'implémentation	Progiciel de gestion
	Applica-tions, applicatifs	Intalio Designer 6.0.2	Ecore 0.7.0, EMF 1.4.0, XML JDom	Ecore 0.7.0, EMF 1.4.0, XML JDom, Kermeta 1.3.0	Ecore 0.7.0, EMF 1.4.0, XML JDom	OpenERP 5.0.14, PGAdmin III
	Techno-logies, langages	BPMN, XML	XML, XMI, Java	XML, XMI, Java	XML, XMI, Java	Python, PostgreSQL, XML
	Format des fichiers	.bpmn, .bpmn_dia-gram	.xmi, .ecore, .java	.xmi, .ecore, .java, .kmt	.xmi, .ecore, .java	.xml, .py
	La figure 11 illustre les opérations nécessaires au passage d'un modèle
	conceptuel issu de l'outil de modélisation Intalio Designer vers un modèle technique
	et son module OpenERP correspondant. Préalablement à ces transformations, les
	mappings (m1, m2, m3, m4) entre métamodèles et métamodèle Pivot doivent être
	réalisés.
		intalio.com/bpms/designer
	4. http://www.openerp.com/
	5. http://www.eclipse.org/

  La transformation t2 permettant d'obtenir un modèle pivot m Pivot à partir de m BPA est un programme Kermeta. La transformation t2 est effectuée en reprenant le paradigme du pattern visiteur. Un programme Visiteur détermine les éléments (et leurs attributs) appartenant à MM BPA . Puis un programme Transformation les associe aux éléments et attributs constituant le MM Pivot . Avant la réalisation de la transformation t2, les mappings m1 (MM BPA MM Pivot ) et m2 (MM Pivot MM BPA ) doivent être effectués. Le tableau 2 reprend ces mappings.

	phases du scénario de validation doit être conforme à son métamodèle MM i associé
	afin d'être manipulable par Kermeta. Cette conformité est vérifiée à l'aide du menu
	contextuel proposé par Ecore (clic-droit  « Validate »). A partir de ce modèle m BPA ,
	nous effectuons la transformation t2 afin d'obtenir notre modèle m Pivot .
	8.1.2. Du modèle d'analyse vers le modèle d'implémentation
	Tableau 2. Mappings m1 et m2 : correspondance sémantique
		entre MM BPA et MM Pivot
	Elément MMBPA (A)	Correspondance sémantique	Elément MMPivot (B)
	BpmnDiagram	A B	Process
	Pool	A B	Pool
	Lane	A B	Lane
	Activity	A B	Activity
	SubProcess	A B	SubProcess
	SequenceEdge	A B	Edge
	Detail	A B	BPElement
		Transformation t1
		(intalio2mBPA.java)

A travers l'approche proposée dans cet article, nous considérons que le système pivot doit être en mesure de faciliter la transformation entre des modèles de perspectives et d'abstractions différentes. Pour cela, il doit s'appuyer sur leurs métamodèles respectifs. Il doit pouvoir ajouter les informations nécessaires, préserver l'intégrité de ces informations et leur cohérence. L'utilisation d'un environnement pivot doit atténuer la dépendance existant entre l'environnement de modélisation et l'environnement d'implémentation. Cette indépendance assure un couplage faible entre modèles issus de ces environnements. Ce format intermédiaire 1. Projet ANR RNTL FAROS (composition de contrats pour la Fiabilité d'Architectures Orientées Services) : http://www.lifl.fr/faros


CNRS, CLLE, ISCPIF Bruno Gaume
email: gaume@univ-tlse2.fr

Alexandre Delanoe
email: alexandre.delanoe@iscpif.fr

Alp Mestanogullari

Alexandre Delanoë

Introducing a mesoscopic scale with Conf luence in Modularity, to improve graph clustering resolution

Keywords: 4, 1 Implémentation: Alp et Alexandre

Given a graph G = (V, E) and two vertices i, j ∈ V , we introduce Conf luence(G, i, j), a vertex mesoscopic closeness measure which brings together vertices from the same link-dense region of the graph G, and separates vertices coming from two distinct dense regions.

Conf luence becomes a useful tool to avoid the resolution problems of the standard M odularity(G, Γ) measure for a given clustering Γ, as evidenced by our comparative study between these two measures on toy graphs. We additionally present a heuristic to nd a partitional clustering of a graph that tentatively optimizes a clustering quality function derived from Conf luence, comparing the new heuristic's behaviour to the state of the art Louvain and Inf omap methods on real terrain networks, while introducing a way to control the size of the resulting clusters along the way. 1 Contents 1 Introduction 2 Modularity 2.1 Limits of Modularity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 Avoiding M odularity limits by introducing a mesoscopic scale 3.1 Conuence, a vertices mesoscopic closeness measure . . . .

Introduction

Terrain networks are real world networks that model data gathered by eld work, in diverse elds such as sociology, linguistics, biology, or graphs from the internet.

Most terrain networks contrast with articial graphs (deterministic or random) and share four similar

properties [START_REF] Watts | Collective Dynamics of Small-World Networks[END_REF], Albert and Barabasi, 2002, Newman, 2003]. They exhibit:

p 1 : A low density (not many edges);

p 2 : Short paths (the average number of edges L on the shortest path between two vertices is low); p 3 : A high clustering rate C = 3 × number of triangles number of connected triplets (locally densely connected subgraphs can be found whereas the whole graph is globally sparse); p 4 : A heavy-tailed degree distribution (the distribution of the degrees of the vertices of the graph can be approximated by a power law).

Clustering a terrain network consists in grouping together in modules vertices that belong to the same densely connected region of the graph (property p 3 ), while keeping separate vertices that do not (property p 1 ). The dierence with a classication task is that the number of groups is not known in advance.

Let G = (V, E) be a graph:

-Module: A module γ of G is a non-empty subset of the graph's vertices: γ = ∅ and γ ⊂ V ; -Clustering: A clustering Γ of G is a set of modules of G such that γ∈Γ γ = V ; -Partitional clustering: If ∀γ i , γ j ∈ Γ, (i = j) ⇒ (γ i ∩ γ j = ∅), then Γ is a partitional clustering of G, where modules of G are not allowed to overlap. Given such a Γ we can dene an equivalence relation Γ ∼ on the set of vertices: ∀u, v ∈ V, (u

Γ ∼ v) ⇔ (∃γ ∈ Γ such that u ∈ γ and v ∈ γ);
-Clustering quality function: A clustering quality function Q(G, Γ) is an R-valued function whose goal is to measure the adequacy of the modules with the densely connected regions of terrain networks (property p 3 ).

In order to establish a good partitional clustering for a graph G = (V, E), given a clustering quality function Q, it would in theory be sucient to build all the possible partitionings of the set of vertices V , and to pick a partitioning Γ such that Q(G, Γ) is optimal. This method is however obviously impractical, since the number of partionings of a set of size n = |V | is equal to the n th Bell number, a sequence known to grow exponentially [Knuth, 1968].

Many graph clustering methods therefore consist in dening a heuristic that can nd in a reasonable amount of time a clustering Γ that tentatively optimises Q(G, Γ) for a given clustering quality function Q. Several partitional clustering methods, such as Louvain [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF], use the M odularity quality function suggested in 2004 by Newman and Girvan [START_REF] Newman | Finding and evaluating community structure in networks[END_REF].

In section 2 we present the M odularity quality function, describing its limits in section 2.1. To avoid these limits, section 3 revisits the denition of M odularity to introduce a mesoscopic scale, with a vertices mesoscopic closeness measure Conf luence, that we dene in section 3.1. We then compare the clusterings which maximize this new quality function with the ones that maximize M odularity, on a few small toy graphs, in section 3.3.

We then describe, in section 4, a new heuristic to optimize this new quality function on bigger graphs, comparing in section 4.2 the results with those obtained using two of the most used state of the art heuristics: Louvain [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] which tries to maximize M odularity, and Inf omap, among the most elegant and ecient heuritics, which tries to maximize the quality function described in 2008 by [START_REF] Rosvall | Maps of random walks on complex networks reveal community structure[END_REF].

Finally, in section 5, we describe a way to control the size of the modules and conclude in section 6.

Modularity

The modularity of a partitional clustering for a graph G = (V, E) with m = |E| edges is equal to the dierence between the proportion of links internal to modules of the clustering, and the same quantity in a null model, where no community structure is expected. The null model is a random graph G N ull with the same number of vertices and edges, as well as the same distribution of degrees as G, where the probability of having an edge between two vertices x and y is equal to

d G (x).d G (y) 2m , with d G (i) = |{v ∈ V /{i, v} ∈ E}| is the degree of vertex i in G.
Let G = (V, E) be a graph with m edges and Γ a partitioning of V . The modularity of Γ can be dened as follows.

M odularity(G, Γ) = 1 2m γ∈Γ i,j∈γ P edge(G, i, j) -P edge(G N ull , i, j)

(1)

Where P edge(G, x, y) is a symmetrical vertex closeness measure equal to the probability of {x, y} being an edge of G, that is:

P edge(G, i, j) = 1 if {i, j} ∈ E, 0 otberwise.
(2)

P edge(G N ull , i, j) = d G (i).d G (j) 2m (3)
In equation 1, the rst term 1 2m is purely conventional, so that modularity values all live in the [-1, 1] interval, but plays no role when maximizing modularity, since it is constant for a given graph G.

We then dene Q P edge as Newman and Girvan's quality function, to be maximized:

Q P edge (G, Γ) = γ∈Γ i,j∈γ P edge(G, i, j) -P edge(G N ull , i, j) = γ∈Γ i,j∈γ 1 -d G (i).d G (j) 2m if {i, j} ∈ E, -d G (i).d G (j) 2m otherwise. (4)
A good partitional clustering Γ as per 4 is one that groups in the same module vertices that are linked (especially ones with low degrees, but also to a lesser extent ones with high degrees), while avoiding as much as possible the grouping of non-linked vertices (especially ones with high degrees, but to a lesser extent ones with low degrees).

Limits of Modularity

Several authors [Fortunato andBarthelemy, 2006, Kumpula et al., 2007] showed that optimizing M odularity leads to merging small modules into larger ones, even when those small modules are well dened and weakly connected to one another. To address this problem, some authors [Reichardt andBornholdt, 2006, Arenas et al., 2008] dened multiresolution variants of M odularity, adding a resolution parameter to control module sizes.

For instance [START_REF] Reichardt | Statistical mechanics of community detection[END_REF]] introduces a parameter λ ∈ R in equation 4:

Q λ = γ∈Γ i,j∈γ 1 -λ. d G (i).d G (j) 2m if {i, j} ∈ E, -λ. d G (i).d G (j) 2m otherwise. ( 5
)
where λ is a resolution parameter: the higher λ is, the smaller the modules get (high resolution).

However, in [START_REF] Lancichinetti | Limits of modularity maximization in community detection[END_REF], the authors show that ... multiresolution Modularity suers from two opposite coexisting problems: the tendency to merge small subgraphs, which dominates when the resolution is low; the tendency to split large subgraphs, which dominates when the resolution is high. In benchmark networks with heterogeneous distributions of cluster sizes, the simultaneous elimination of both biases is not possible and multiresolution Modularity is not capable to recover the planted community structure, not even when it is pronounced and easily detectable by other methods, for any value of the resolution parameter. This holds for other multiresolution techniques and it is likely to be a general problem of methods based on global optimization.

... real networks are characterized by the coexistence of clusters of very dierent sizes, whose distributions are quite well described by power laws [START_REF] Clauset | Finding community structure in very large networks[END_REF], Radicchi et al., 2004].

Therefore there is no characteristic cluster size and tuning a resolution parameter may not help.

3 Avoiding M odularity limits by introducing a mesoscopic scale In equation 4, with regards to a graph G:

P edge(G, i, j) = 1 if {i, j} ∈ E, 0 otherwise.
is a local (microscopic) vertices closeness measure relative to G;

P edge(G N ull , i, j) = d G (i).d G (j)
2m is a global (macroscopic) vertices closeness measure relative to G.

To avoid limits described in section 2.1, we introduce in equation 4 an intermediate mesoscopic 1 vertices closeness measure relative to G: Conf luence(G, i, j) that we dene below.

Conuence, a vertices mesoscopic closeness measure

If G = (V, E) is a reexive 2 and undirected graph, let us imagine a walker wandering on the graph G: at time t ∈ N, the walker is on one vertex i ∈ V ; at time t + 1, the walker can reach any neighbouring vertex of i, with uniform probability. This process is called a simple random walk [Bollobas, 2002]. It can be dened by a Markov chain on V with an 1 A mesoscopic scale is an intermediate scale between a local microscopic scale and a global macroscopic scale. 2 i.e. each vertex is connected to itself. If such self-loops do not exist in the data, they may be added without loss of information.

n × n transition matrix [G]: [G] = (g i,j ) i,j∈V with g i,j =    1 d G (i) if {i, j} ∈ E, 0 otherwise. ( 6
)
Since G is reexive, each vertex has at least one neighbour (itself ) and [G] is therefore well dened. Furthermore, by construction, [G] is a stochastic matrix: ∀i ∈ V, j∈V g i,j = 1. The probability P t G (i j) of a walker starting on vertex i and reaching vertex j after t steps is:

P t G (i j) = ([G] t ) i,j (7)
Propsition 1 Let G = (V, E) be a reexive graph with m edges, and G null = (V, E null ) its null model such that the probability of the existence of a link between two vertices i and j

is e i,j = d G (i).d G (j) 2m . ∀t ∈ N * , ∀i, j ∈ V, P t G null (i j) = d G (j) 2m (8)
Proof by induction on t : (a) True for t = 1:

∀i, j ∈ V, P 1 G null (i j) = e i,j . 1 d G (i) = d G (i).d G (j) 2m . 1 d G (i) = d G (j) 2m
(b) If true for t then true for t + 1:

∀i, j ∈ V, P t+1 G null (i j) = k∈V P t G null (i k).P 1 G null (k j) = k∈V P t G null (i k). d G (j) 2m = d G (j) 2m . k∈V P t G null (i k) = d G (j) 2m . k∈V d G (k) 2m = d G (j) 2m (a) & (b) ⇒ 8
On a graph G = (V, E) the trajectory of a random walker is completely governed by the topology of the graph in the vicinity of the starting node: after t steps, any vertex j located at a distance of t links or less can be reached. The probability of this event depends on the number of paths between i and j, and on the structure of the graph around the intermediary vertices along those paths. The more short paths exist between vertices i and j, the higher the probability P t G (i j) of reaching j from i.

On the graph G null the trajectory of a random walker is only governed by the degrees of the vertices, and no longer at all by the topology of the graph in the vicinity of the starting node.

We want to consider as close each pair of vertices {i, j} having a probability of reaching j from i after a short random walk in G, greater than the probability of reaching j from i in G null . We therefore dene the t-conuence Conf t (G, i, j) between two vertices i, j on a graph G as follows:

Conf t (G, i, j) =    0 if i = j, P t G (i j)-P t G null (i j) P t G (i j)+P t G null (i j) = P t G (i j)- d G (j) 2m P t G (i j)+ d G (j) 2m otherwise. ( 9
)
Propsition 2 Let G = (V, E) be a reexive graph with m edges, and G null its null model such that the probability of the existence of a link between two vertices i and j is e i,j =

d G (i).d G (j) 2m . ∀t ∈ N * , ∀i, j ∈ V, Conf t (G N ull , i, j) = 0 (10)
Proof :

If i = j, the result follows directly from denition 9.

If i = j, Conf t (G N ull , i, j) = P t G N ull (i j)- d G N ull (j) 2m P t G N ull (i j)+ d G N ull (j) 2m
(by denition 9)

= P t G N ull (i j)- d G (j) 2m P t G N ull (i j)+ d G (j) 2m (by denition of G N ull ) = d G (j) 2m - d G (j) 2m d G (j) 2m + d G (j) 2m (by proposition 1) = 0 To prove that Conf t (G, • , • ) is symmetric, we rst need to prove proposition 3. Propsition 3 Let G = (V, E) be a reexive graph. ∀t ∈ N * , ∀i, j ∈ V, P t G (i j) = d G (j) d G (i) .P t G (j i) (11)
Proof by induction on t :

(a) True for t = 1:

∀i, j ∈ V, if {i, j} / ∈ E, then P 1 G (i j) = 0 and P 1 G (j i) = 0, therefore P 1 G (i j) = d G (j) d G (i) .P 1 G (j i) = 0 otherwise P 1 G (i j) = 1 d G (i) = d G (j) d G (i) . 1 d G (j) = d G (j) d G (i) .P 1 G (j i) (b) If true for t then true for t + 1: ∀i, j ∈ V, P t+1 G (i j) = k∈V P t G (i k).P 1 G (k j) = k∈V P t G (k i). d G (k) d G (i) .P 1 G (k j) = k∈V P t G (k i). d G (k) d G (i) .P 1 G (j k). d G (j) d G (k) = k∈V P t G (k i).P 1 G (j k). d G (j) d G (i) = d G (j) d G (i) k∈V P 1 G (j k).P t G (k i) = d G (j) d G (i) .P t+1 G (j i) (a) & (b) ⇒ 11 Propsition 4 Let G = (V, E) be a reexive graph. ∀t ∈ N * , ∀i, j ∈ V, Conf t (G, i, j) = Conf t (G, j, i) (12)
Proof :

If i=j : it follows directly from denition 9.

If i = j : Conf t (G, i, j) = P t G (i j)-P t G null (i j) P t G (i j)+P t G null (i j) = P t G (i j)- d G (j) 2m P t G (i j)+ d G (j) 2m = d G (j) d G (i) .P t G (j i)- d G (j) 2m d G (j) d G (i) .P t G (j i)+ d G (j) 2m = ( d G (j) d G (i) .P t G (j i)- d G (j) 2m ). d G (i) d G (j) ( d G (j) d G (i) .P t G (j i)+ d G (j) 2m ). d G (i) d G (j) = P t G (j i)- d G (i) 2m P t G (j i)+ d G (i) 2m = P t G (j i)-P t G null (j i) P t G (j i)+P t G null (j i) = Conf t (G, j, i)
Conf luence actually denes an innity of symmetrical vertex closeness measures, one for each random walk length t. For clarity, in the rest of this paper, we set t = 3 and dene Conf (G, i, j) = Conf 3 (G, i, j).

Most terrain networks exhibit the properties p 2 (short paths) and p 3 (high clustering rate). With a classic distance such as the shortest path between two vertices, all vertices would be close to each other in a terrain network (because of property p 2 ). On the contrary, Conf luence allows us to identify vertices living in the same higher density zones of G (property p 3 ):

If i, j are in the same high local density region:

P 3 G (i j) > P 3 G null (i j), thus Conf (G, i, j) > 0 (13)
If i, j are in two distinct high local density regions:

P 3 G (i j) < P 3 G null (i j), thus Conf (G, i, j) < 0 (14)

Introducing a mesoscopic scale in Modularity

To avoid the limits of M odularity described in section 2.1, we propose Q Conf , a new clustering quality function, which introduces a mesoscopic scale into M odularity through Conf luence:

Q Conf (G, Γ) = γ∈Γ i =j∈γ Conf (G, i, j) + P edge(G, i, j) -P edge(G null , i, j)
By the denitions of Conf (equation 9) and P edge (equations 2 and 3) :

Q Conf (G, Γ) = γ∈Γ i =j∈γ P 3 G (i j)- d G (j) 2m P 3 G (i j)+ d G (j) 2m + 1 -d G (i).d G (j) 2m if {i, j} ∈ E, -d G (i).d G (j) 2m otherwise.
Leading us to the following denition of Q Conf :

Q Conf (G, Γ) = γ∈Γ i =j∈γ          P 3 G (i j)- d G (j) 2m P 3 G (i j)+ d G (j) 2m + 1 -d G (i).d G (j) 2m if {i, j} ∈ E, P 3 G (i j)- d G (j) 2m P 3 G (i j)+ d G (j) 2m -d G (i).d G (j) 2m otherwise. (15)
To make it easier to interpret Q Conf , we dene the GooDness of a clustering Γ for a graph G = (V, E):

GooDness(G, Γ) = 1 2|E| .Q Conf (G, Γ) (16)
and the ConF ness of a set of vertices γ ∈ Γ for a graph G = (V, E): [START_REF] Brandes | On modularity clustering[END_REF], and the same holds for computing a clustering that maximizes Q Conf .

ConF ness(G, γ) = 1 |γ|.(|γ| -1) i =j∈γ Conf luence(G, i, j) (17) 3.3 Optimality for Q Pedge versus optimality for Q Conf A partitional clustering ∆ is optimal for a quality function Q i: For all partitioning Γ of V , Q G, ∆) Q G, Γ) . Computing a ∆ that maximizes Q P edge (G, ∆) is N P -complete [
However, when the number of vertices of a graph G = (V, E) is small, the problem of maximizing the modularity can be turned into a reasonably tractable Integer Linear Program (see [START_REF] Brandes | On modularity clustering[END_REF]): We dene n 2 decision variables X ij ∈ {0, 1}, one for each pair of vertices {i, j} ∈ V . The key idea is that we can build an equivalence relation on V (i ∼ j i X ij = 1) and therefore a partitioning of V . To guarantee that the decision variables give rise to an equivalence relation, they must satisfy the following constraints:

Reexivity: ∀i ∈ V, X ii = 1; Symmetry: ∀i, j ∈ V : X ij = X ji ; Transitivity: ∀i, j, k ∈ V :    ∀i, j, k ∈ V : X ij + X jk -2.X ik ≤ 1; ∀i, j, k ∈ V : X ik + X ij -2.X jk ≤ 1; ∀i, j, k ∈ V : X jk + X ik -2.X ij ≤ 1.
With the following objective functions to maximize:

For Q Pedge : i,j∈V X ij . P edge(G, i, j) -P edge(G N ull , i, j) For Q Conf : i =j∈V X ij . Conf (G, i, j) + P edge(G, i, j) -P edge(G null , i, j) (18)
On four small aticial graphs, G 1 toy , ... G 4 toy , we compare optimal clusterings ∆ G P edge and ∆ G Conf respectively computed for Q P edge and Q Conf , with results illustrated in Figure 1.

The optimal clusterings for Q Conf do not necessarily have a higher resolution than with Q P edge , they can even have a lower resolution3 :

• Fig. 6 • ∆

P edge = δ 2 Conf ∪ δ 3 Conf : • ∆ G 1 toy Conf = δ 1 Conf ={0, 4, 5, 6} 0.10 , δ 2 Conf ={1, 2, 3} 0.18 , δ 3 Conf ={7, 8} 0.18 ; • ∆ G 1 toy P edge = δ 1 P edge ={1, 2,
∆ G 3 toy Conf is dierent from ∆ G 3 toy Pedge , with δ 1 Conf = δ 2 P edge ∪ δ 3 P edge and δ 1 P edge = δ 2 Conf ∪ δ 3 Conf : • ∆ G 3 toy Conf = δ 1 Conf ={0, 1, 2, 3, 4,
G 4 toy Conf = ∆ G 4 toy P edge = δ 1 ={0,

A heuristic by edges conuence

We describe in this section a heuristic for tentatively maximizing Q Conf . To this end, we start with a variant on Conf , named Conf r, where the conuence between two adjacent vertices is computed by removing the edge between them 4 :

Conf r(G, i, j) = Conf (G, i, j) if {i, j} / ∈ E, Conf (G = (V, E -{i, j}), i, j) otherwise. ( 19
)
Conf r gives us an ordering on the edges {i, j} ∈ E of the graph. In particular, sorting the edges by decreasing Conf r(G, i, j) forms the basis of a new strategy for constructing the cluster's modules, Hbec (Heuristic by edges conf luence), described 5 in algorithm 1. On G 5 toy , the graph depicted in Figure 2, Hbec yields the following clusters: Hbec(G 5 toys ) = {0, 1, 3, 4, 5}, {6, 7, 8, 9, 10}, {2} . It is interesting to note how vertex 2 is left isolated in its own cluster by Hbec, whereas it joins the {6, 7, 8, 9, 10} module in the optimal clustering for Q Conf : ∆ G 5 toy Conf = {0, 1, 3, 4, 5}, {2, 6, 7, 8, 9, 10} . 4 A comparative study of Conf r with over 80 similarity measures between vertices of a graph has been done by Emmanuel Navarro in his thesis, looking into the sensitivity of various methods to the density of graphs, paths of length 1 and the degrees of vertices, among other aspects. This thesis is available at https://oatao.univ-toulouse.fr/12024/1/navarro.pdf. The study shows that, among the 80 similarity measures considered, Conf r(G, i, j) is the only one that, even though it does not systematically regroup pairs of vertices {i, j} ∈ E, is correlated to the local edge density around vertices i and j, while being independent of the global density of the graphs.

5 Dierent edges might happen to have the exact same Conf r value, making the process non-deterministic in general, because of its sensitivity on the order in which the edges with identical Conf r values are processed. A simple solution to this problem is to sort edges by rst comparing their Conf r values and then using the lexicographic order on (i, j) when Conf r values are strictly identical. Indeed, when a vertex is linked to two or more distinct dense regions of a graph, Hbec tends to leave that vertex isolated due to its Conf r-centered strategy, which does not push the said vertex towards one of those regions over the other. It is therefore desirable to add one last step to the process, to get even closer to the optimal clustering by trying to merge more modules with a greedy algorithm:

FastGreedy(Hbec(G)) : we iteratively merge pairs of modules resulting from Hbec(G) when the union of modules is locally optimal with respect to Q Conf , stopping when merging any pair of the remaining modules would not result in an increase of Q Conf .

We call Kodex(G) the complete algorithm, including the nal FastGreedy step. We

Implementation

Our implementation of Kodex reects the high-level description from the previous sections and is therefore split into three main parts: pre-computing the conuence of all the edges of the graph (and sorting the said list of edges in decreasing conuence order), doing a rst clustering pass (H bec), and the nal greedy step. Let G = (V, E), and n = |V |.

Edges conuence:

First, construct the reexive sparse adjacency matrix of the input graph, Adj(G) ∈ M n (R), represented using the Compressed Sparse Column format, supported by the vast majority of sparse linear algebra libraries, by supplying the appropriate routine with all the (i, j, 1) triplets, where {i, j}

∈ E or i = j. That is, Adj(G) i,j = 1 if i, j ∈ E or i = j, 0 otherwise .
Then compute the corresponding transition matrix, T (G), assuming a uniform probability of reaching any neighbor from a given vertex. This amounts to setting all nonzero values of a column j to 1

deg G j . That is, T (G) i,j = 1 deg G (j) if i, j ∈ E, 0 otherwise .
Algorithm 1 Hbec(G) Heuristic by edges conuence for optimizing

Q Conf Input: G = (V, E) an undirected graph Output: C a partitional clustering of G for i ∈ V do mod i {i} v i i q 0 Υ ∅ While Υ = E do {i, j} arg max {x,y}∈E-Υ Conf r(G, x, y) (a) Υ Υ ∪ {{i, j}} if v i = v j then
i and j are not in the same module

q candidate q + 2. x∈mi y∈mj Conf (G, x, y) + P edge(G, x, y) -P edge(G null , x, y) (b)
if q q candidate then q q candidate mod i mod i ∪ mod j for y ∈ mod j do

v y v i m j ∅ C ∅ for i ∈ V do if mod i = ∅ C C ∪ {mod i } return C
Then compute the proxemy matrix, P (G) = T (G) 3 .

Next, we iterate over the list of edges {a, b} ∈ E, constructing another list:

Dene T (G -{a, b}) to be the same as T (G) except for the entries at (a, b)

and (b, a) that should be set to 0, to emulate the removal of the link between vertices a and b, and an update to the other entries of the two relevant columns to reect a decrease by 1 in the degree of vertices a and b, to account for the freshly removed link.

That is,

T (G -{a, b}) i,j =    0 if {i, j} = {a, b} 1 deg G (j) if j = a or j = b but i / ∈ {a, b} T (G) i,j otherwise Dene e b ∈ R n as (e b ) i = 1 if i = b, 0 otherwise , ideally using a sparse repre- sentation.
Multiply T (G -{a, b}) and e b , and multiply the result by T (G -{a, b}), and again, as many times as the length of the random walk is, which has been 3 in most of this paper. That is, for t = 3, we compute: T (G -{a, b})T (G -{a, b})T (G -{a, b})e b . We call the resulting vector w

∈ R n Finally, compute conf a,b = wa- deg G (a)-1 nnz(Adj(G))-2 wa+ deg G (a)-1 nnz(Adj(G))-2
where nnz is a function returning the number of non-zero entries in a sparse matrix, typically provided by sparse linear algebra libraries. Return (a, b, conf a,b ).

Sort the list of (a, b, conf a,b ) according to conf a,b , in decreasing order, breaking equalities by discriminating on the lexicographic ordering on a and then b.

Hbec

We create a clustering with all vertices isolated in their own 1-point cluster. Clusters are represented with associative maps from cluster identiers to sets of vertex identiers, i.e clust[i] = {a, b, c} means that vertices a, b, c are in cluster number i, while maintaining another associative map from vertex identiers to cluster identier, i.e index[i] = c means that vertex i belongs to cluster c. We additionally maintain a mapping from cluster identiers to scores, score[i], to avoid save some computations that we will keep reusing, instead of performing them from scratch every time.

We set the score of our clustering, clust s core to 0 initially. We iterate over the sorted list of edges from the previous phase. When processing entry (a, b, conf a,b ):

We compute the clustering quality improvement we would get by merging clusters index[a] and index[b]:

score(index[a] and index[b]) = i∈clust[index[a]],j∈clust[index[b]] f (i, j) (20)
where f is dened as:

f (i, j) = P (G) i,j -deg G (i) nnz(Adj(G) P (G) i,j + deg G (i) nnz(Adj(G) + Adj(G) i,j - (deg G (i) -1)(deg G (j) -1) nnz(Adj(G)) -n If score(index[a] and index[b])-score[index[a]]-score[index[b]] > 0, we merge index[b] into index[a]: * clust s core := clust s core + score(index[a] and index[b]) -score[index[a]] - score[index[b]] * clust[index[a]] := clust[index[a]] ∪ clust[index[b]] * score[index[a]] := score(index[a] and index[b]) * For all i ∈ clust[index[b]], we set index[i] := index[a].
Otherwise, we move on to the next edge.

Once all the edges have been processed, clust describes a partitional clustering of G.

Final greedy step

For all pairs of non-empty clusters resulting from Hbec, compute the sum described in equation 20, using an associative container of some sort to record the mapping between the pair of cluster identiers and the resulting score.

If there is a pair of clusters for which the sum yields a strictly positive number (i.e a pair that would improve the quality of the clustering, if merged), merge them, updating the scores computed in the rst step to account for the merge, wherever one of those clusters is involved.

Repeat until no such pair of clusters exists anymore.

Tests

We compare three heuristics for computing a partitional clustering:

Louvain : The Louvain method [START_REF] Blondel | Fast unfolding of communities in large networks[END_REF] is the state of the art heuristic that tentatively maximizes M odularity;

Infomap : The Inf omap method is a heuristic for tentatively maximizing the quality function described in 2008 by [START_REF] Rosvall | Maps of random walks on complex networks reveal community structure[END_REF]. This quality function is based on the minimum description length principle [Grünwald, 2007].

It consists in measuring the compression ratio that a given partitioning Γ provides for describing the trajectory of a random walk on a graph. The trajectory description happens on two levels. When the walker enters a module, we write down its name. We then write the vertices that the walker visits, with a notation local to the module, so that an identical short name may be used for dierent vertices from dierent modules. A concise description of the trajectory, with a good compression ratio, is therefore possible when the modules of Γ are such that the walker tends to stay in them, which corresponds to the idea that the walker is captured when it enters a good module, which is supposed to be a densely linked region that is only weakly connected to other modules. The quality 6 of a partitional clustering is the compression ratio that Γ provides for describing the trajectory of a random walker on G; Kodex : The heuristic described in section 4 that tentatively maximizes Q Conf .

Louvain, Infomap and Kodex on four G toys graphs

We start by testing Louvain, Inf omap and Kodex on the four G toys graphs of section 3.3.

The results are summarized in Figure 3.

On these four G toys graphs, Louvain nds the optimal modules with respect to Q P edge while Kodex nds the optimal modules with respect to Q Conf . On G 2 toy and G 3 toy , Inf omap and Kodex agree on the clustering, both nding the optimal modules with respect to Q Conf . However, on G 1 toy and G 4 toy , Inf omap collects all the vertices into a single module, because there is no way to compress the description of the path of a random walker on either of those graphs.

Indeed, G 4 toy has been articially constructed as follow: G 4 toy = (V, E) where V is the union of 3 sets of 8 vertices, γ 1 = {0, ..., 7}, γ 2 = {8, ..., 15}, γ 3 = {16, ..., 23}, and edges are randomly drawn using two dierent probabilities: we use a probability of 0.5 for drawing an edge between two vertices from the same γ i , and a probability of 0.25 when the two vertices come from dierent sets. Vertices from a given γ i are expected to have as many internal links (within γ i ) as they have links to vertices from the two other sets. At every single step, the random walker is equally likely to leave a γ i or stay within it, which eectively prevents any path compression to take place in G 4 toy . G FrSynV : The Dicosyn resource comes from a collaboration between IBM and the CNRS laboratory ATILF http://www.atilf.fr/. Starting with seven classical French dictionaries (Bailly, Benac, Du Chazaud, Guizot, Lafaye, Larousse and Robert), they extracted synonymic relationships, and the resulting graph G F rSyn was then symmetrized and split by P oS into three graphs: G F rSynV for verbs, G F rSyn.N for nouns and G F rSyn.A for adjectives.

G Actors : The well known network of actors [START_REF] Watts | Collective Dynamics of Small-World Networks[END_REF]] has been built from the Internet Movie Database (April 1997) http://us.imdb.com; nodes are actors, and two actors are linked if they have played in a lm together [START_REF] Rossi | The network data repository with interactive graph analytics and visualization[END_REF] https://networkrepository.com/actor-collaboration.php.

G DBLP : The DBLP computer science bibliography provides a comprehensive list of research papers in computer science [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF].

Two authors are connected if they have published at least one paper together https://snap. stanford.edu/data/com-DBLP.html.

G Amazon : A network was collected by crawling the Amazon website. It is based on the Customers Who Bought This Item Also Bought feature of the Amazon website [START_REF] Leskovec | SNAP Datasets: Stanford large network dataset collection[END_REF]. If a product i is frequently co-purchased with product j, the graph contains an undirected edge from i to j https://snap.stanford. edu/data/com-Amazon.html. The power law estimation we give, λ(r 2 ) is not very accurate (see for instance [Newman, 2005]). However, giving a correct estimation of the odds that a given discrete distribution is heavy-tailed is a dicult issue ( [START_REF] Goldstein | Problems with tting to the power-law distribution[END_REF], Clauset et al., 2009]), and rening the power-law estimates is beyond the scope of this paper. In order to gain some control over the size of modules, we introduce a β parameter into Q Conf , resulting in the following Q β Conf (G, Γ) quality function:

Q β Conf (G, Γ) = γ∈Γ i =j∈γ    Conf (G, i, j) + 1 -d G (i).d G (j) 2m if {i, j} ∈ E, Conf (G, i, j) -d G (i).d G (j) 2m -β * 1 -Conf (G, i, j) otherwise. = γ∈Γ i =j∈γ          P 3 G (i j)- d G (j) 2m P 3 G (i j)+ d G (j) 2m + 1 -d G (i).d G (j) 2m if {i, j} ∈ E, P 3 G (i j)- d G (j) 2m P 3 G (i j)+ d G (j) 2m -d G (i).d G (j) 2m -β * 1 - P 3 G (i j)- d G (j) 2m P 3 G (i j)+ d G (j) 2m
otherwise.

(

) Since P 3 G (i j) ∈ [0, 1], it follows that P 3 G (i j)- d G (j) 2m P 3 G (i j)+ d G (j) 2m 21
∈ [-1, 1], and therefore:

if β > 0, then -β * 1 - P 3 G (i j)- d G (j) 2m P 3 G (i j)+ d G (j) 2m
0. That is, with β > 0:

If {i, j} ∈ E, then noting changes ;

If {i, j} / ∈ E and i, j are in the same high density region, then we slightly penalize the {i, j} pair (by 13);

If {i, j} / ∈ E and i, j are in two distinct high density regions, then we strongly penalize the {i, j} pair (by 14).

Because we must avoid as much as possible that the modules contain pairs {i, j} / ∈ E (with increasing eciency as β grows), this forces modules to be smaller, as illustrated by Figure 4 on graph G 3 toy . Increasing β does not simply split modules (resulting in a hierarchical approach). This can be observed when going from β = 0.5 to β = 1.0, noticing that there

is no δ ∈ ∆ G 3 toy Q 0.5 Conf such that δ 2 Q 1.0 Conf = {0, 2, 4} ⊂ δ.
Revisiting the previous algorithm to account for the β parameter, yielding Kodex(G, β), simply amounts to replacing line (b) in algorithm 1 by: q candidate q+2.

x∈mi y∈mj

Conf (G, x, y) + P edge(G, x, y) -P edge(G null , x, y) if {x, y} ∈ E,

(1 + β).Conf (G, x, y) + P edge(G, x, y) -P edge(G null , x, y) -β otherwise. Conf ={13,14,15} 0.66 .

Table 3 shows the results for Kodex(G, β) with β = 0.0, β = 0.5, β = 1.0 on four real terrain graphs. To compare two clusterings Γ 1 and Γ 2 , of a graph G = (V, E) we dene:

P recision(Γ 1 , Γ 2 ) = γ∈Γ 1 {x, y} ∈ γ × γ γ∈Γ 2 {x, y} ∈ γ × γ γ∈Γ 1 {x, y} ∈ γ × γ Recall(Γ 1 , Γ 2 ) = γ∈Γ 1 {x, y} ∈ γ × γ γ∈Γ 2 {x, y} ∈ γ × γ γ∈Γ 2 {x, y} ∈ γ × γ F score(Γ 1 , Γ 2 ) = 2.
P recision(Γ 1 , Γ 2 ).Recall(Γ 1 , Γ 2 ) P recision(Γ 1 , Γ 2 ) + Recall(Γ 1 , Γ 2 )

Figure 5 shows F score(Γ 1 , Γ 2 ) between clusterings Kodex(G, 0.0), Kodex(G, 0.5), Kodex(G, 1.0), Louvain(G) et Inf omap(G) on the graphs G F rSynV , G Actors , G DBLP and G Amazon . (TODO: Commenter les resultats de la table 3 et de la gure 5: Bruno)

6 Conclusions and perspectives

In this paper, we dened Conf luence, a mesoscopic vertex closeness measure based on short random walks, that we introduced into M odularity to dene Q Conf , a new clustering quality function. With four small toy graphs, we showed that optimal clusterings for Q Conf improve the resolution of optimal clusterings for M odularity.

We then introduced Kodex(G), a heuristic based on the Conf luence of edges to optimize Q Conf on a graph G. On the same four little toy graphs, we showed that Kodex nds an optimal clustering for Q Conf and that for two of those toy graphs, Kodex(G) = Inf omap(G), while on the other two, Kodex(G) identies the modules we expected while Inf omap(G) regroups all vertices into a single module.

We showed that Kodex avoids the resolution problem of Louvain on four real terrain graphs, and that the modules computed by Inf omap are closer to those computed by

Figure 1 :

 1 Figure1: Optimality with respect to Q Pedge versus optimality with respect to Q Conf . Shapes describe an optimal clustering for Q Conf (if two vertices have same shape, then they are in a same module for Q Conf ). Colors describe an optimal clustering for Q P edge (if two vertices have same color, then they are in a same module for Q P edge ).

Figure

  Figure 2: G 5 toys

Figure 3 :

 3 Figure 3: Clusterings with Louvain, Infomap and Kodex: shapes describe Kodex(G), colors describe Louvain(G), and blocks describe Inf omap(G).

  , Inf omap(G 1 toy ) = {V }, Kodex(G 1 toy ) Louvain, Infomap and Kodex on terrain graphs We now compare Louvain, Inf omap and Kodex on four state-of-the-art terrain graphs.

(a) G 3 toyFigure 4 :

 34 Figure 4: Optimal clusterings of G 3 toy for Q β=0.0 Conf , Q β=0.5 Conf , Q β=1.0 Conf : In Fig. 4(a),

Table 3 :

 3 Kodex clusterings of four terrain graphs with β = 0.0, β = 0.5, β = 1.0 -;for Number of modules ; Length of the biggest modules

Figure 5 :

 5 Figure 5: Fscore(Γ 1 , Γ 2 ): Comparison of clusterings Kodex(G, 0.0), Kodex(G, 0.5), Kodex(G, 1.0), Louvain(G) and Inf omap(G) on G F rSynV , G Actors , G DBLP et G Amazon .

Table 1 :

 1 Table1illustrates the pedigrees 7 of these terrain graphs, and Table2illustrates the execu- tion times, number of modules, and the length of the biggest module found by the dierent methods.. Pedigrees: n and m are the number of vertices and edges, k is the mean degree of vertices, C is the clustering coecient of the graph, L lcc is the average shortest path length between any two nodes of the largest connected component (largest subgraph in which there exist at least one path between any two nodes) and n lcc the number of vertices of this component, λ is the coecient of the best tting power law of the degree distribution and r 2 is the correlation coecient of the t, measuring how well the data is modelled by the power law.

	Graph	n	m	k	C	L lcc (n lcc )	λ(r 2 )
	G FrSynV	9,147	51,423	11.24	0.14	4.20(8,993)	-1.88(0.91)
	G Actors	68,684	3,007,298	87.57	0.20	3.51(68,019)	-1.49(0.90)
	G DBLP	317,080	1,049,866	6.62	0.31	6.79(317,080)	-2.71(0.95)
	G Amazon 334,863 925,872	5.53	0.21	11.95(334,863)	-2.81(0.93)
	(TODO: Commenter les resultats de la table 2: Bruno)
	7

Table 2 :

 2 Clusterings of four Terrain Graphs with Louvain, Kodex, Infomap: (T) Time computation in seconds (Louvain and Infomap in C++, Kodex in Haskell (see section 4.1), (N) Number of modules, (M) Length of the biggest module and -; -;for Louvain ; Kodex ; Inf omapIn many domains such as linguistics, sociology or biology, it can be useful to look into sets of objects (documents, sentences, words, individuals, cells, ...) at dierent levels of granularity.

		G FrSynV	G Actors	G DBLP	G Amazon
	(T)	0 ; ?? ; 13	?? ; ?? ; ??	11 ; 9, 639 ; 1, 933	6 ; 7, 830 ; 1, 795
	(N)	90 ; 671 ; 575	?? ; ?? ; ??	238 ; 17, 437 ; 16, 960	234 ; 20, 703 ; 17, 292
	(M) 1, 189 ; 155 ; 173	???? ; ??? ; ???	25, 893 ; 249 ; 599	12, 783 ; 535 ; 347

Where _ , _ for the M odularity, GooDness of the clustering, and _ for the ConF ness of the modules

Note that this quality function cannot be expressed as γ∈Γ i,j∈γ sim(G, i, j), with sim(G, ., .) an R-valued symmetric similarity measure between vertices of G. We therefore left out this quality function in our study of optimality in section 3.3, not having the ability to dene the corresponding objective function to maximize in a similar fashion to what was done for Q P edge and Q Conf with the formulas 18.

Kodex than the ones produced by Louvain.

Finally, to get a handle on the size of modules, we introduced the β ∈ R parameter, resulting in the Q β Conf quality function and the Kodex(G, β) variant of the algorithm. We then showed that this approach is not hierarchical 8 . Length of Random Walks:

For clarity and simplicity, we restricted the random walks of P t G (i j) to a length of t = 3. A rst study of the impact of the length of those random walks was done in [START_REF] Gaume | Building Real-World Complex Networks by Wandering on Random Graphs[END_REF], but a deeper one should be carried to understand how the length inuences the mesoscopicity of Conf luence and its eect on Q Conf and Kodex. Indeed, if G is connected and i = j:

Conf luence is independent of the intermediate structures between the two vertices i and j ;

, Conf luence is dependent of the t-intermediate structures (t-mesoscopicity) between the two vertices i and j (see13 and 14); When t → ∞: lim t→∞ Conf t (G, i, j) = 0, Conf luence is constant 9 . For example we can build the graph G 1 toy from G 1 toy by inserting a new vertex in the middle of each edge. Figure 6 illustrates the optimal clusterings on G 1 toy and on G 1 self.memory toy for Q 0.0 Conf with t = 3 and with t = 6, allowing us to see that:

G 1 toy with t = 6: we get the modules ∆

Conf = {0, 4, 5, 6} ⊂ {0, 4, 5, 6, cut(0/4), cut(0/5), cut(0/6), cut(4/5), cut(4/6), cut(5/6)};

Conf are not necessarily subsets of the optimal modules for

Conf . 9 We can prove with the Perron-Frobenius theorem [Stewart, 1994] that if G is connected, then

2m and so by proposition 1:

δ 3 Conf = {7, 8} ⊂ {7, 8, cut(7/8), cut(3/7), cut(4/7), cut(2/8), cut(5/8)}.

On G 1 toy with t = 3: we do not get the modules of ∆

Directed graphs:

If G is a positively weighted graph by W = {w i,j such {i, j} ∈ E}, then we can apply Q Conf and Kodex by replacing equations 6 and 9 by 22 and 23 respectively:

[G] = (g i,j ) i,j∈V with g i,j =

If G is a directed graph, one can also consider using a variant of page rank [START_REF] Gaume | Pagerank induced topology for real-world networks[END_REF] in place of equation 7.

Overlaps:

In order to dene a heuristic for computing clusters with potential overlaps between modules, one could consider using Hbec to isolate vertices between several dense regions of the graph (see section 4) and allowing them to belong to the modules corresponding to those dense regions, identied with the help of ConF ness (see 17).