Journée d'Automne Optimisation dans les Réseaux 2014

Programme de la journée (Amphi Hermite)

9h00-9h30 : Accueil café

9h30-10h30 : Matthieu Latapy (LIP6-UPMC)

Cliques, graphes bipartis, compression et flots de liens.

Les grands graphes rencontrés en pratique ont des propriétés qui les différencient fortement des graphes aléatoires. En particulier, ils ont une forte densité locale et donc de nombreuses cliques non-triviales. Ceci amène à les représenter comme des graphes bipartis, voire k-partis, qui s'avèrent bien plus compacts que les objets originaux. On peut alors voir ces graphes bipartis comme des compressions des graphes originaux, et le défi est alors d'effectuer les calculs sans décompression.
Par ailleurs, nous proposons une nouvelle approche pour étudier la dynamique des interactions, qui consiste en l'étude de flots de liens (link streams). Ceci amène à définir tout un nouvel ensemble de notions jouant pour ces objets le même rôle que la théorie des graphes pour les réseaux. On arrive notamment à des nouvelles notions de cliques et de communautés, qui soulèvent des défis algorithmiques nouveaux.

10h30-11h00 : Pause café

11h-11h45 : Jean-Loup Guillaume (Université de la Rochelle)

Communautés multi-ego-centrées

           L’explosion de la taille des réseaux complexes tels que Facebook ou Wikipedia offre de nouvelles opportunités d’établir de nouveaux contacts et de partager de                l’information et des savoir. L’excès d’information peut cependant être également néfaste : sur Facebook, à quels contacts envoyer un message sachant que la                plupart des utilisateurs ont plusieurs centaines d’amis ? Quelles pages Wikipedia faut-il lire en priorité pour apprendre le plus possible sur un sujet donné. Ces                deux exemples peuvent s’étudier via la notion de communauté dans les graphes et leur détection automatique. Les approches classiques peuvent se classer en             plusieurs groupes :

                – Les méthodes de partitionnement pour lesquelles les sommets du graphe appartiennent à une unique communauté. Cette vision simple reste limitée car,                           dans la plupart des contextes, les sommets appartiennent à plusieurs communautés.

                – Les méthodes recouvrantes qui sont beaucoup plus proches de la réalité, mais qui posent en pratique de nombreux problèmes de définition et de calcul.

                – Les méthodes ego-centrées qui se limitent à la recherche des communautés autour d’un sommet et sont donc un compromis plus accessible à l’heure                             actuelle.

            Je vais présenter dans cet exposé des réflexions sur cette troisième vision. En particulier, afin de contourner les problèmes classiques des fonctions de qualité,              je présenterai deux fonctions de proximité, une basée sur la dynamique d’opinion et la seconde basée sur la proximité topologique. Toutes deux permettent                     d’identifier rapidement les sommets proches d’un sommet d’intérêt et ont chacune un intérêt spécifique selon l’application recherchée.

            Je présenterai également le concept de communauté multi-ego-centrée, c’est-à-dire de communauté centrée sur un ensemble de sommets. Je montrerai qu’il est             possible avec les fonctions de proximité, notamment celles introduites précédemment, de répondre à deux problèmes proches : (i) comment identifier la                         communauté contenant un ensemble de sommets fixés et (ii) comment extraire toutes les communautés autour d’un sommet. Je présenterai des éléments de                 validation sur un jeu de données constitué de pages Wikipedia.

11h45-12h30 : Júlio Louzada (SAMOVAR-Télécom Paris Sud)

Diffusion dans les réseaux sociaux

             We present a framework to model information diffusion in social networks based on linear multivariate Hawkes processes. 
            Our model exploits the effective broadcasting times of information by users, which guarantees a more realistic view of the
            information diffusion process. The proposed model takes into consideration not only interactions between users but also 
            interactions between topics, which provides a deeper analysis of influences in social networks. We provide an estimation
            algorithm based on nonnegative matrix factorization (NMF) techniques, which together with a dimensionality reduction 
            argument is able to discover, in addition, the latent community structure of the social network.

            In a second moment, we couple our Hawkes model with the latent Dirichlet allocation (LDA) topic model, where users broadcast 
            now information as a mixture of different latent topics. We provide, again, an estimation algorithm based on NMF techniques, which 
            are coupled together with a modified collapsed Gibbs sampler and a modified variational Bayes method. This allows a more data-driven 
            estimation of hidden influences in social networks. 

12h30-14h00 : Déjeuner – Buffet offert

14h00-15h00 : Zbigniew Smoreda (Orange)

Géographie des réseaux de communications via donnée du mobile

Dans cette communication je partirais d’une conception continuiste des relations sociales hors ligne et en ligne – que ce soit pour le téléphone ou, par la suite, pour internet – qui a été travaillée au sein du laboratoire des sciences sociales d’Orange Labs (CNET). Les enquêtes sociologiques, associées à l’analyse du trafic téléphonique, ont largement fait la preuve de la cohérence de leurs résultats avec les recherches classiques : l’univers social du téléphone n’est pas différent de l’espace relationnel des personnes. Les résultats mis en avant par ces enquêtes témoignent de l’étroite relation de la communication téléphonique avec la rencontre de visu. Elles établissent le même constat : « plus on se voit et plus on s’appelle ». Cette corrélation témoigne, d’une part, de l’inscription des pratiques de communication dans un double mouvement par rapport aux relations sociales, puisque les appels fréquents avec des personnes que l’on voit également fréquemment servent de support à l’interaction en face-à-face et, d’autre part, du fait que la répétition et la stabilité dans le temps des contacts téléphoniques apparaissent comme un signe de la force de la relation. Loin d’une opposition ou, à tout le moins, de la constitution d’un univers autonome et séparé, il apparaît que les échanges téléphoniques sont très étroitement articulés aux relations sociales ordinaires des personnes et qu’ils permettent d’en dessiner l’architecture de manière économe et efficace. La sociabilité téléphonique se superpose donc très étroitement à la cartographie des relations sociales ordinaires.

Fort de ce constat et des nouvelles possibilités offertes par l’accès aux bases de données de la téléphonie mobile d’une grande taille, nous avons pu établir le dialogue avec les chercheurs des grands réseaux et systèmes complexes afin d’analyser les relations interpersonnelles et comportement  à l’échelle d’un pays ou d’une société. 

Dans la seconde partie, je vais donc essayer de montrer comment les hypothèses des sciences sociales peuvent être éclairées avec l’apport des méthodes d’analyse mathématique ou informatique. Je prendrai des exemples des travaux réalisés récemment sur la structure géographique des réseaux et la mobilité humaine qui s’appuie sur la localisation des communications présente dans les données du téléphone mobile.

15h00-15h30 : Pause café

15h30-16h15 : Fabrice Rossi (SAMM, Paris 1)

Tri-classification d'interactions estampillées temporellement

Nous étudions dans ce travail des données d'interaction, constituées de
triplets source, destination, instant. Ce type de données est assez
fréquent dans les relations intermediées informatiquement, comme par
exemple les emails (expéditeur, récepteur, horodatage de la connexion au
serveur STMP), les appels téléphoniques, les SMS, etc. On peut les voir
comme un graphe dynamique : les sources et destinations forment les
sommets du graphe, alors que les arcs sont les traces des interactions.
Une fonction de présence indique si un arc est actif à un instant donné.

Nous proposons une méthode d'analyse exploratoire de ce type de données
par tri-classification : nous construisons des classes de sources, des
classes de destinations et des intervalles de temps qui garantissent une
forme de stationnarité locale des interactions à l'intersection de trois
classes. La méthode proposée ne demande aucun paramètre utilisateur et
donne des résultats très satisfaisants sur des données réelles volumineuses.

16h15-17h00 : Nicolas Gensollen (SAMOVAR-Télécom Paris Sud)

 Coalition Formation Algorithm of Prosumers in a Smart Grid Environment

            Nous étudions la formation, dans le smart grid, de coalitions de prosumers cherchant à vendre de l’énergie sur le marché. 
            Il est primordial pour l’opérateur du réseau électrique que les producteurs d’énergie soient à même de soutenir la demande 
            du réseau à la fois en terme de stabilité et de production minimale. Nous avons ainsi construit un algorithme cherchant à former 
            des coalitions répondant à ces deux pré-requis : un niveau minimum d’énergie produite et une production stable dans le temps. 
            Ceci nous amène à rechercher des sources d’énergie non corrélées pour former les coalitions. Nous proposons donc un algorithme
             qui utilise des outils de la théorie des graphes comme les graphes de corrélation ou la percolation de cliques afin de former des 
            coalitions répondant à ces contraintes complexes. Nous validons  l’algorithme face à un processus de regroupement aléatoire et 
            nous montrons que notre algorithme se révèle plus performant non seulement en terme d’utilité globale, mais aussi en terme de robustesse 
            face à des variations de production non prévues, dues par exemple à des changements de conditions climatiques.