IDEAS home Printed from https://ideas.repec.org/a/eee/csdana/v152y2020ics0167947320301201.html
   My bibliography  Save this article

Large-scale estimation of random graph models with local dependence

Author

Listed:
  • Babkin, Sergii
  • Stewart, Jonathan R.
  • Long, Xiaochen
  • Schweinberger, Michael

Abstract

A class of random graph models is considered, combining features of exponential-family models and latent structure models, with the goal of retaining the strengths of both of them while reducing the weaknesses of each of them. An open problem is how to estimate such models from large networks. A novel approach to large-scale estimation is proposed, taking advantage of the local structure of such models for the purpose of local computing. The main idea is that random graphs with local dependence can be decomposed into subgraphs, which enables parallel computing on subgraphs and suggests a two-step estimation approach. The first step estimates the local structure underlying random graphs. The second step estimates parameters given the estimated local structure of random graphs. Both steps can be implemented in parallel, which enables large-scale estimation. The advantages of the two-step estimation approach are demonstrated by simulation studies with up to 10,000 nodes and an application to a large Amazon product recommendation network with more than 10,000 products.

Suggested Citation

  • Babkin, Sergii & Stewart, Jonathan R. & Long, Xiaochen & Schweinberger, Michael, 2020. "Large-scale estimation of random graph models with local dependence," Computational Statistics & Data Analysis, Elsevier, vol. 152(C).
    • Handle: RePEc:eee:csdana:v:152:y:2020:i:c:s0167947320301201
    DOI: 10.1016/j.csda.2020.107029
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167947320301201
    Download Restriction: Full text for ScienceDirect subscribers only.
    File URL: https://libkey.io/10.1016/j.csda.2020.107029?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Hunter D.R. & Lange K., 2004. "A Tutorial on MM Algorithms," The American Statistician, American Statistical Association, vol. 58, pages 30-37, February.
    2. Mark S. Handcock & Adrian E. Raftery & Jeremy M. Tantrum, 2007. "Model‐based clustering for social networks," Journal of the Royal Statistical Society Series A, Royal Statistical Society, vol. 170(2), pages 301-354, March.
    3. D. S. Choi & P. J. Wolfe & E. M. Airoldi, 2012. "Stochastic blockmodels with a growing number of classes," Biometrika, Biometrika Trust, vol. 99(2), pages 273-284.
    4. Michael Schweinberger & Mark S. Handcock, 2015. "Local dependence in random graph models: characterization, properties and statistical inference," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 77(3), pages 647-676, June.
    5. Angelo Mele, 2017. "A Structural Model of Dense Network Formation," Econometrica, Econometric Society, vol. 85, pages 825-850, May.
    6. Krivitsky, Pavel N., 2017. "Using contrastive divergence to seed Monte Carlo MLE for exponential-family random graph models," Computational Statistics & Data Analysis, Elsevier, vol. 107(C), pages 149-161.
    7. Hoff P.D. & Raftery A.E. & Handcock M.S., 2002. "Latent Space Approaches to Social Network Analysis," Journal of the American Statistical Association, American Statistical Association, vol. 97, pages 1090-1098, December.
    8. N. Binkiewicz & J. T. Vogelstein & K. Rohe, 2017. "Covariate-assisted spectral clustering," Biometrika, Biometrika Trust, vol. 104(2), pages 361-377.
    9. Daniel K. Sewell & Yuguo Chen, 2015. "Latent Space Models for Dynamic Networks," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 110(512), pages 1646-1657, December.
    10. Faming Liang & Ick Hoon Jin & Qifan Song & Jun S. Liu, 2016. "An Adaptive Exchange Algorithm for Sampling From Distributions With Intractable Normalizing Constants," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 111(513), pages 377-393, March.
    11. Hunter, David R. & Goodreau, Steven M. & Handcock, Mark S., 2008. "Goodness of Fit of Social Network Models," Journal of the American Statistical Association, American Statistical Association, vol. 103, pages 248-258, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Juan Nelson Mart'inez Dahbura & Shota Komatsu & Takanori Nishida & Angelo Mele, 2021. "A Structural Model of Business Card Exchange Networks," Papers 2105.12704, arXiv.org, revised Aug 2021.
    2. Alex Stivala & Garry Robins & Alessandro Lomi, 2020. "Exponential random graph model parameter estimation for very large directed networks," PLOS ONE, Public Library of Science, vol. 15(1), pages 1-21, January.
    3. Cornelius Fritz & Co-Pierre Georg & Angelo Mele & Michael Schweinberger, 2024. "Vulnerability Webs: Systemic Risk in Software Networks," Papers 2402.13375, arXiv.org, revised Nov 2024.
    4. Smith, Thomas Bryan & Vacca, Raffaele & Krenz, Till & McCarty, Christopher, 2021. "Great minds think alike, or do they often differ? Research topic overlap and the formation of scientific teams," Journal of Informetrics, Elsevier, vol. 15(1).

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Linardi, Fernando & Diks, Cees & van der Leij, Marco & Lazier, Iuri, 2020. "Dynamic interbank network analysis using latent space models," Journal of Economic Dynamics and Control, Elsevier, vol. 112(C).
    2. Teague R. Henry & Kathleen M. Gates & Mitchell J. Prinstein & Douglas Steinley, 2020. "Modeling Heterogeneous Peer Assortment Effects Using Finite Mixture Exponential Random Graph Models," Psychometrika, Springer;The Psychometric Society, vol. 85(1), pages 8-34, March.
    3. Haiyan Liu & Ick Hoon Jin & Zhiyong Zhang & Ying Yuan, 2021. "Social Network Mediation Analysis: A Latent Space Approach," Psychometrika, Springer;The Psychometric Society, vol. 86(1), pages 272-298, March.
    4. Samrachana Adhikari & Tracy Sweet & Brian Junker, 2021. "Analysis of longitudinal advice‐seeking networks following implementation of high stakes testing," Journal of the Royal Statistical Society Series A, Royal Statistical Society, vol. 184(4), pages 1475-1500, October.
    5. Chih‐Sheng Hsieh & Lung‐Fei Lee & Vincent Boucher, 2020. "Specification and estimation of network formation and network interaction models with the exponential probability distribution," Quantitative Economics, Econometric Society, vol. 11(4), pages 1349-1390, November.
    6. Fengqin Tang & Chunning Wang & Jinxia Su & Yuanyuan Wang, 2020. "Spectral clustering-based community detection using graph distance and node attributes," Computational Statistics, Springer, vol. 35(1), pages 69-94, March.
    7. Chih‐Sheng Hsieh & Xu Lin, 2021. "Social interactions and social preferences in social networks," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 36(2), pages 165-189, March.
    8. Lee, Jihui & Li, Gen & Wilson, James D., 2020. "Varying-coefficient models for dynamic networks," Computational Statistics & Data Analysis, Elsevier, vol. 152(C).
    9. Adrian E. Raftery, 2017. "Comment: Extending the Latent Position Model for Networks," Journal of the American Statistical Association, Taylor & Francis Journals, vol. 112(520), pages 1531-1534, October.
    10. Yingda Lu & Kinshuk Jerath & Param Vir Singh, 2013. "The Emergence of Opinion Leaders in a Networked Online Community: A Dyadic Model with Time Dynamics and a Heuristic for Fast Estimation," Management Science, INFORMS, vol. 59(8), pages 1783-1799, August.
    11. Sosa, Juan & Betancourt, Brenda, 2022. "A latent space model for multilayer network data," Computational Statistics & Data Analysis, Elsevier, vol. 169(C).
    12. Michael Braun & André Bonfrer, 2011. "Scalable Inference of Customer Similarities from Interactions Data Using Dirichlet Processes," Marketing Science, INFORMS, vol. 30(3), pages 513-531, 05-06.
    13. Patacchini, Eleonora & Hsieh, Chih-Sheng & Lin, Xu, 2019. "Social Interaction Methods," CEPR Discussion Papers 14141, C.E.P.R. Discussion Papers.
    14. Silvia D'Angelo & Marco Alfò & Thomas Brendan Murphy, 2020. "Modeling node heterogeneity in latent space models for multidimensional networks," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 74(3), pages 324-341, August.
    15. Joshua Daniel Loyal & Yuguo Chen, 2020. "Statistical Network Analysis: A Review with Applications to the Coronavirus Disease 2019 Pandemic," International Statistical Review, International Statistical Institute, vol. 88(2), pages 419-440, August.
    16. Laleh Tafakori & Armin Pourkhanali & Riccardo Rastelli, 2022. "Measuring systemic risk and contagion in the European financial network," Empirical Economics, Springer, vol. 63(1), pages 345-389, July.
    17. Samrachana Adhikari & Beau Dabbs, 2018. "Social Network Analysis in R: A Software Review," Journal of Educational and Behavioral Statistics, , vol. 43(2), pages 225-253, April.
    18. Guang Ouyang & Dipak K. Dey & Panpan Zhang, 2020. "Clique-Based Method for Social Network Clustering," Journal of Classification, Springer;The Classification Society, vol. 37(1), pages 254-274, April.
    19. West, Robert M. & House, Allan O. & Keen, Justin & Ward, Vicky L., 2015. "Using the structure of social networks to map inter-agency relationships in public health services," Social Science & Medicine, Elsevier, vol. 145(C), pages 107-114.
    20. Chiara Di Maria & Antonino Abbruzzo & Gianfranco Lovison, 2022. "Networks as mediating variables: a Bayesian latent space approach," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 31(4), pages 1015-1035, October.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:csdana:v:152:y:2020:i:c:s0167947320301201. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/csda .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.