nips nips2011 nips2011-60 nips2011-60-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: David S. Choi, Patrick J. Wolfe, Edoardo M. Airoldi
Abstract: Latent variable models are frequently used to identify structure in dichotomous network data, in part because they give rise to a Bernoulli product likelihood that is both well understood and consistent with the notion of exchangeable random graphs. In this article we propose conservative confidence sets that hold with respect to these underlying Bernoulli parameters as a function of any given partition of network nodes, enabling us to assess estimates of residual network structure, that is, structure that cannot be explained by known covariates and thus cannot be easily verified by manual inspection. We demonstrate the proposed methodology by analyzing student friendship networks from the National Longitudinal Survey of Adolescent Health that include race, gender, and school year as covariates. We employ a stochastic expectation-maximization algorithm to fit a logistic regression model that includes these explanatory variables as well as a latent stochastic blockmodel component and additional node-specific effects. Although maximumlikelihood estimates do not appear consistent in this context, we are able to evaluate confidence sets as a function of different blockmodel partitions, which enables us to qualitatively assess the significance of estimated residual network structure relative to a baseline, which models covariates but lacks block structure. 1
[1] A. Goldenberg, A. X. Zheng, S. E. Fienberg, and E. M. Airoldi, “A survey of statistical network models”, Foundation and Trends in Machine Learning, vol. 2, pp. 1–117, Feb. 2010.
[2] R. Albert and A. L. Barabasi, “Statistical mechanics of complex networks”, Reviews of Modern Physics, vol. 74, no. 47, Jan. 2002.
[3] M. E. J. Newman, “The structure and function of complex networks”, SIAM Review, vol. 45, pp. 167–256, June 2003.
[4] C. Cooper and A. M. Frieze, “A general model of web graphs”, Random Structures and Algorithms, vol. 22, no. 3, pp. 311–335, Mar. 2003.
[5] M. O. Jackson, Social and Economic Networks, Princeton University Press, 2008.
[6] S. Wasserman and K. Faust, Social Network Analysis: Methods and Applications, Cambridge University Press, Cambridge, U.K., 1994.
[7] T. A. B. Snijders and K. Nowicki, “Estimation and prediction for stochastic blockmodels for graphs with latent block structure”, J. Classif., vol. 14, pp. 75–100, Jan. 1997.
[8] M. S. Handcock, A. E. Raftery, and J. M. Tantrum, “Model-based clustering for social networks”, J. R. Stat. Soc. A, vol. 170, pp. 301–354, Mar. 2007.
[9] E. M. Airoldi, D. M. Blei, S. E. Fienberg, and E. P. Xing, “Mixed membership stochastic blockmodels”, J. Mach. Learn. Res., vol. 9, pp. 1981–2014, June 2008.
[10] P. D. Hoff, “Multiplicative latent factor models for description and prediction of social networks”, Computational Math. Organization Theory, vol. 15, pp. 261–272, Dec. 2009.
[11] M. E. J. Newman, “Modularity and community structure in networks”, Proc. Natl Acad. Sci. U.S.A., vol. 103, pp. 8577–8582, June 2006.
[12] A. L. Traud, E. D. Kelsic, P. J. Mucha, and M. A. Porter, “Comparing community structure to characteristics in online collegiate social networks”, SIAM Rev., 2011, to appear.
[13] P. J. Bickel and A. Chen, “A nonparametric view of network models and Newman-Girvan and other modularities”, Proc. Natl Acad. Sci. U.S.A., vol. 106, pp. 21068–21073, Dec. 2009.
[14] D.S. Choi, P.J. Wolfe, and E.M. Airoldi, “Stochastic blockmodels with growing numbers of classes”, Biometrika, 2011, to appear.
[15] K. Rohe, S. Chatterjee, and B. Yu, “Spectral clustering and the high-dimensional stochastic blockmodel”, Ann. Stat., 2011, to appear.
[16] A. Celisse, J.J. Daudin, and L. Pierre, “Consistency of maximum-likelihood and variational estimators in the stochastic block model”, Arxiv preprint 1105.3288, 2011.
[17] B. Karrer, E. Levina, and MEJ Newman, “Robustness of community structure in networks”, Phys. Rev. E, vol. 77, pp. 46119–46128, Apr. 2008.
[18] C.P. Massen and J.P.K. Doye, “Thermodynamics of community structure”, Arxiv preprint cond-mat/0610077, 2006.
[19] J. Copic, M. O. Jackson, and A. Kirman, “Identifying community structures from network data via maximum likelihood methods”, B.E. J. Theoretical Economics, vol. 9, Sept. 2009.
[20] P.W. Holland and S. Leinhardt, “An exponential family of probability distributions for directed graphs”, J. Am. Stat. Assoc., vol. 76, pp. 33–50, Mar. 1981.
[21] SJ Haberman, “Comment on Holland and Leinhardt”, J. Am. Stat. Assoc., vol. 76, pp. 60–62, Mar. 1981.
[22] S. Wasserman and S.O.L. Weaver, “Statistical analysis of binary relational data: parameter estimation”, J. Math. Psychol., vol. 29, pp. 406–427, Dec. 1985.
[23] P. D. Hoff, “Modeling homophily and stochastic equivalence in symmetric relational data”, in Adv. in Neural Information Processing Systems, pp. 657–664. MIT Press, 2008.
[24] S.M. Goodreau, J.A. Kitts, and M. Morris, “Birds of a feather, or friend of a friend? using exponential random graph models to investigate adolescent social networks”, Demography, vol. 46, pp. 103–125, Feb. 2009.
[25] M.C. Gonz´ lez, H.J. Herrmann, J. Kert´ sz, and T. Vicsek, “Community structure and ethnic a e preferences in school friendship networks”, Physica A., vol. 379, no. 1, pp. 307–316, 2007. 9