Analyse de graphes signés pour détecter la corruption dans les marchés publics Encadrants Rosa Figueiredo Vincent Labatut Lieu du stage Laboratoire Informatique d'Avignon (LIA), Avignon, France Descriptif du stage Contexte L'ouverture massive des données publiques recouvre une importance particulière dans le cadre des marchés publics, et la récente réforme de ces marchés introduit explicitement l'open data dans la commande publique. Ce sont donc dès aujourd'hui une masse importante, et à court terme l'intégralité des données relatives aux marchés publics qui peuvent faire l'objet d'analyses qui jusqu'à présent se heurtaient à l'inexistence ou à la partialité de jeux de données. Que ce soit par les montants en jeu (la commande publique correspond à presque 15% du PIB, 200 milliards d'euros par an pour les seuls marchés publics), ou par les bénéfices économiques et sociétaux escomptés derrière cet impératif de transparence, le traitement et l'analyse de ces données constituent un enjeu tant académique que sociétal majeur. Le travail motivant la présente offre de stage s'insère dans les deux axes transversaux du LIA : Systèmes Complexes et Société Numérique. À l'intersection de l'informatique, des sciences économiques et des sciences juridiques, il fait partie de DéCoMaP (Détection de la corruption dans les marchés publics) un projet à plus grande échelle financé par l'ANR et visant à collecter, traiter et analyser les données ouvertes relatives aux marchés publics français, afin d'élaborer un outil basé sur les méthodes de graphes signés pour la détection des risques de corruption qui peuvent exister entre acheteurs publics et entreprises. La prise en compte de la nature duale des liens unissant entreprises et donneurs d'ordres (relation contractuelle normale ou corruption) est fondamentale à la bonne modélisation du système étudié, et nécessite d'utiliser des réseaux signés. Il s'agit d'un type de réseau bien moins exploré que les réseaux non-signés classiques, et permettant d'inclure dans un même modèle des relations antagonistes. L'élaboration d'outils de détection automatique des risques de corruption dans les marchés publics ("red flagging") n'est en soit pas totalement nouvelle, et se développe depuis quelques années déjà [1], notamment à l'échelle européenne [2]. Outre qu'aucun outil n'a à ce jour été adapté au cadre juridique et aux données des marchés publics français, les méthodes appliquées présentent une limite importante. Les approches existantes se focalisent sur des données individuelles, caractérisant de façon indépendante clients et fournisseurs, et ignorent les informations relationnelles, correspondant aux interdépendances et interactions entre ces différents acteurs. De ce fait, les outils produits passent à côté d'un certain nombre de propriétés émergentes, i.e. présentes à une granularité plus élevée que l'acteur isolé. Travail demandé Le travail effectué avant ce stage a permis de collecter et structurer l'ensemble des données issues des marchés publics français, telles que proposées par le Bulletin Officiel des Annonces des Marchés Publics (BOAMP) (annonces et avis d'attribution). Il s'agit maintenant d'identifier les données a priori pertinentes, et de les enrichir à partir à la fois de l'état de l'art académique (analyse juridique, approche économique théorique et empirique) et de l'expertise d'un Professeur en économie, Pierre-Henri Morand (LBNC - AU), qui porte le projet DéCoMaP. En fonction du déroulement du projet, il est envisageable de compléter la BD existante en exploitant d'autres sources de données telles que TED (l'équivalent européen du BOAMP). Le stagiaire utilisera les graphes signés afin de modéliser, visualiser et analyser les réseaux complexes formés par les entreprises (fournisseurs) et les collectivités (donneurs d'ordres). Il s'agit de graphes dont les liens sont caractérisés par un signe, pouvant être positif ou négatif, afin de représenter des relations antagonistes. Ces graphes seront construits à partir des données obtenues à la première étape. Comme illustré dans la Figure ci-dessous, plusieurs méthodes sont possibles pour effectuer cette opération, que le stagiaire devra mettre en oeuvre et comparer. Une fois les graphes obtenus, ils seront principalement utilisés pour deux tâches. La première est leur analyse via des outils descriptifs classiques dans le champ des réseaux complexes (taille, densité, transitivité, centralités diverses...). La seconde vise à résoudre des problèmes de partitionnement définis sur les graphes signés en utilisant les méthodes de résolution existantes plus adaptées [3,4] aux réseaux obtenus. Avec les solutions obtenues émergeront des groupes d'acteurs (acheteurs publics et entreprises fournisseurs) susceptibles d'être liés entre eux par des pratiques délictueuses. Perspectives Sous réserve qu'à la fois le stagiaire et les encadrants soient satisfaits du déroulement du stage, celui-ci est susceptible de déboucher sur un doctorat prévu dans le cadre du projet ANR DéCoMaP déjà mentionné. Ce doctorat sera co-encadré par Rosa Figueiredo et Vincent Labatut (LIA - AU), comme le stage, et en plus par Christine Largeron (Laboratoire Hubert Curien - Université Jean Monnet). Références [1] Fazekas, Mihály, et István János Tóth. New ways to measure institutionalised grand corruption in public procurement, U4 Brief, n°9 (2014). [2] Ferwerda, Joras, et Ioana Deleanu. Identifying and Reducing Corruption in Public Procurement in the EU. European Commission, OLAF, 2013. [3] Figueiredo, Rosa et Yuri Frota. The maximum balanced subgraph of a signed graph: Applications and solution approaches. European Journal of Operational Research, 236(2) : 473-487, 2014. [4] Labatut, Vincent. Generalized Measures for the Evaluation of Community Detection Methods, International Journal of Social Network Mining, n°2(2015):44-63. Thématique(s) associée(s) au stage / Keywords Analyse de graphes signés / Signed graphs analysis