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

Zreik, Rawya; Latouche, Pierre; Bouveyron, Charles

Journal de la société française de statistique, Tome 156 (2015) no. 3, pp. 166-191.

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 nœuds 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.

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.

Mot clés : Réseau dynamique, sous-graphes, random subgraph model (RSM), modèle à espace d’état, classification automatique, algorithme VEM, données Enron
Keywords: Dynamic networks, subgraphs, random subgraph model, state space model, Automatic classification, variational inference, variational expectation maximization, Enron data

[1] Airoldi, E.M.; Blei, D.M.; Fienberg, S.E.; Xing, E.P. Mixed membership stochastic blockmodels, The Journal of Machine Learning Research, Volume 9 (2008), pp. 1981-2014 | Zbl

[2] Ahmed, A.; Xing, E. P. On tight approximate inference of logistic-normal admixture model, In Proceedings of the International Conference on Artificial Intelligence and Statistics (2007), pp. 1-8

[3] Bickel, P.J.; Chen, A. A nonparametric view of network models and Newman–Girvan and other modularities, Proceedings of the National Academy of Sciences, Volume 106 (2009) no. 50, pp. 21068-21073 | Zbl

[4] Blei, D.M.; Lafferty, J.D. A correlated topic model of science, The Annals of Applied Statistics (2007), pp. 17-35 | MR | Zbl

[5] Blei, D.; Lafferty, J. A correlated topic model of Science, Annals of Applied Statistics, Volume 1 (2007) no. 1, pp. 17-35 | MR | Zbl

[6] Csisz, I; Tusnády, Gábor Information geometry and alternating minimization procedures, Statistics and decisions (1984) | MR | Zbl

[7] Dubois, C.; Butts, C.T.; Smyth, P. Stochastic blockmodelling of relational event dynamics, International Conference on Artificial Intelligence and Statistics, Volume 31 of the Journal of Machine Learning Research Proceedings (2013), pp. 238-246

[8] Dempster, Arthur P; Laird, Nan M; Rubin, Donald B Maximum likelihood from incomplete data via the EM algorithm, Journal of the Royal Statistical Society. Series B (Methodological) (1977), pp. 1-38 | MR | Zbl

[9] Daudin, J-J.; Picard, F.; Robin, S. A mixture model for random graphs, Statistics and Computing, Volume 18 (2008) no. 2, pp. 173-183 | MR

[10] Fienberg, S.E.; Wasserman, S.S. Categorical data analysis of single sociometric relations, Sociological Methodology, Volume 12 (1981), pp. 156-192

[11] Girvan, M.; Newman, M.E.J. Community structure in social and biological networks, Proceedings of the National Academy of Sciences, Volume 99 (2002) no. 12, pp. 7821-7826 | DOI | MR | Zbl

[12] Harvey, A.C. Forecasting, structural time series models and the Kalman filter, Cambridge University Press, Cambridge, UK, 1989 | Zbl

[13] Hathaway, Richard J Another interpretation of the EM algorithm for mixture distributions, Statistics & Probability Letters, Volume 4 (1986) no. 2, pp. 53-56 | MR | Zbl

[14] Heaukulani, Creighton; Ghahramani, Zoubin Dynamic probabilistic models for latent feature propagation in social networks, Proceedings of the 30th International Conference on Machine Learning (ICML-13) (2013), pp. 275-283

[15] Handcock, M.S.; Raftery, A.E.; Tantrum, J.M. Model-based clustering for social networks, Journal of the Royal Statistical Society : Series A (Statistics in Society), Volume 170 (2007) no. 2, pp. 301-354 | MR

[16] Hofman, J.M.; Wiggins, C.H. Bayesian approach to network modularity, Physical review letters, Volume 100 (2008) no. 25 | DOI

[17] Jordan, M.; Ghahramani, Z.; Jaakkola, T.; Saul, L. K. An introduction to variational methods for graphical models, Machine learning, Volume 37 (1999) no. 2, pp. 183-233 | Zbl

[18] Jernite, Y.; Latouche, P.; Bouveyron, C.; Rivera, P.; Jegou, L.; Lamassé, S. The random subgraph model for the analysis of an acclesiastical network in merovingian gaul, Annals of Applied Statistics, Volume 8 (2014) no. 1, pp. 55-74 | MR | Zbl

[19] Krishnan, THRIYAMBAKAM; McLachlan, GJ The EM algorithm and extensions, John Wiley, New York, 1997 | MR

[20] Lafferty, John D.; Blei, David M. Correlated Topic Models, Advances in Neural Information Processing Systems 18 (Weiss, Y.; Schölkopf, B.; Platt, J.C., eds.), MIT Press, 2006, pp. 147-154

[21] Latouche, P.; Birmelé, E; Ambroise, C. Overlapping stochastic block models with application to the French political blogosphere, Annals of Applied Statistics, Volume 5 (2011) no. 1, pp. 309-336 | MR | Zbl

[22] Minka, T.P. From hidden Markov models to linear dynamical systems (1998) (Technical report)

[23] Moreno, J.L. Who shall survive ? : A new approach to the problem of human interrelations., Nervous and Mental Disease Publishing Co, 1934

[24] Matias, Catherine.; Robin, Stéphane. Modeling heterogeneity in random graphs through latent space models : a selective review., Esaim Proc. and Surveys, Volume 47 (2014), pp. 55-74 | MR | Zbl

[25] Mariadassou, M.; Robin, S.; Vacher, C. Uncovering latent structure in valued graphs : a variational approach, Annals of Applied Statistics, Volume 4 (2010) no. 2, pp. 715-742 | MR | Zbl

[26] Nowicki, K.; Snijders, T.A.B. Estimation and prediction for stochastic blockstructures, Journal of the American Statistical Association, Volume 96 (2001) no. 455, pp. 1077-1087 | MR | Zbl

[27] Rand, W.M. Objective criteria for the evaluation of clustering methods, Journal of the American Statistical association (1971), pp. 846-850

[28] Rauch, H.E.; Tung, F.; Striebel, T. Maximum likelihood estimates of linear dynamic systems, AIASS Journal, Volume 3 (1965) no. 8, pp. 1445-1450 | MR

[29] Svensén, M.; Bishop, C.M. Robust Bayesian mixture modelling, Neurocomputing, Volume 64 (2004), pp. 235-252

[30] Sarkar, Purnamrita; Moore, Andrew W Dynamic social network analysis using latent space models, ACM SIGKDD Explorations Newsletter, Volume 7 (2005) no. 2, pp. 31-40

[31] White, H.C.; Boorman, S.A.; Breiger, R.L. Social structure from multiple networks. I. Blockmodels of roles and positions, American Journal of Sociology (1976), pp. 730-780

[32] Wang, Y.J.; Wong, G.Y. Stochastic blockmodels for directed graphs, Journal of the American Statistical Association, Volume 82 (1987), pp. 8-19 | MR | Zbl

[33] Xing, E.P.; Fu, W.; Song, L. A state-space mixed membership blockmodel for dynamic network tomography, The Annals of Applied Statistics, Volume 4 (2010) no. 2, pp. 535-566 | MR | Zbl

[34] Xu, Kevin S; Hero III, Alfred O Dynamic stochastic blockmodels : Statistical models for time-evolving networks, Social Computing, Behavioral-Cultural Modeling and Prediction, Springer, 2013, pp. 201-210

[35] Yang, Tianbao; Chi, Yun; Zhu, Shenghuo; Gong, Yihong; Jin, Rong Detecting communities and their evolutions in dynamic social networks—a Bayesian approach, Machine learning, Volume 82 (2011) no. 2, pp. 157-189 | MR | Zbl