Resumen de Classification automatique de réseaux dynamiques avec sous-graphes : étude du scandale Enron

Rawya Zreik, Pierre Latouche, Charles Bouveyron

• français

  Ces dernières années, de nombreux modèles de graphes aléatoires ont été proposés pour extraire des informations à partir de réseaux dans des domaines variés. Parmi ces modèles, nous considérons les modèles de clustering qui consistent à chercher des groupes de noeuds ayant des profils de connexion homogènes. La majorité de ces modèles est limitée à des réseaux statiques ayant des arêtes binaires ou discrètes et ne prennent donc pas en compte une éventuelle dimension temporelle. Ce travail est motivé par la volonté d’analyser un réseau dynamique décrivant les communications électroniques (emails) entre les employés de l’entreprise Enron, bien connue pour son scandale financier, où nous le verrons, les positions sociales jouent un rôle important. Nous proposons dans cet article une extension au cadre dynamique du modèle de graphe aléatoire RSM (Randon Subgraph Model) qui a été récemment proposé pour modéliser à l’aide de groupes latents des réseaux statiques pour lesquels une partition en sous-graphes est connue. Notre approche est basée sur l’utilisation d’un modèle à espace d’état pour modéliser l’évolution au cours du temps des proportions des groupes latents. Le modèle ainsi obtenu est appelé modèle de sous-graphes aléatoires dynamiques (dRSM) et un algorithme de type VEM (Variational Expectation Maximization) est proposé pour en effectuer l’inférence. Nous montrons que les approximations variationnelles conduisent à un nouveau modèle à espace d’état à partir duquel les paramètres ainsi que les états cachés peuvent être estimés en utilisant le filtre de Kalman et le lisseur de Rauch-Tung-Striebel (RTS). Des données simulées sont considérées pour évaluer l’efficacité de notre approche. La méthodologie est finalement appliquée au jeu des données emails de l’entreprise Enron et permet de mettre en évidence une réaction anticipée des cadres par rapport aux autres employés concernant le scandale à venir.

• English

  In recent years, many clustering methods have been proposed to extract information from networks. The principle is to look for groups of vertices with homogenous connection profiles. Most of the models for clustering are suitable for static networks, that is to say, not taking into account the temporal dimension, but can handle different types of edges, whether binary or discrete. This work is motivated by the will of analysing an evolving network describing email communications between employees of the Enron company where social positions play an important role. Therefore, in this paper, we consider the random subgraph model (RSM) which was proposed recently to model a network through latent clusters built within a known partition into subgraphs. Using a state space model to characterize the cluster proportions, RSM is then extended in order to deal with dynamic networks. We call the latter the dynamic random subgraph model (dRSM). A variational expectation maximisation (VEM) algorithm is proposed to perform inference. We show that the variational approximations lead to a new state space model from which the parameters along with hidden states can be estimated using the standard Kalman filter and Rauch-Tung-Striebel (RTS) smoother.

  Simulated data sets are considered to assess the proposed approach. The methodology is finally applied to the Enron email data set and allows to discover an early reaction of the partners and directors compared to the other employees regarding the coming scandal.