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. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. Angelo Mele, 2017. "A Structural Model of Dense Network Formation," Econometrica, Econometric Society, vol. 85, pages 825-850, May.
    8. 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.
    9. 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.
    10. N. Binkiewicz & J. T. Vogelstein & K. Rohe, 2017. "Covariate-assisted spectral clustering," Biometrika, Biometrika Trust, vol. 104(2), pages 361-377.
    11. 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.
    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. 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.
    2. 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.
    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. De Nicola, Giacomo & Fritz, Cornelius & Mehrl, Marius & Kauermann, Göran, 2023. "Dependence matters: Statistical models to identify the drivers of tie formation in economic networks," Journal of Economic Behavior & Organization, Elsevier, vol. 215(C), pages 351-363.
    7. 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.
    8. 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.
    9. Patacchini, Eleonora & Hsieh, Chih-Sheng & Lin, Xu, 2019. "Social Interaction Methods," CEPR Discussion Papers 14141, C.E.P.R. Discussion Papers.
    10. 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.
    11. 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.
    12. Lee, Jihui & Li, Gen & Wilson, James D., 2020. "Varying-coefficient models for dynamic networks," Computational Statistics & Data Analysis, Elsevier, vol. 152(C).
    13. 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.
    14. Sosa, Juan & Betancourt, Brenda, 2022. "A latent space model for multilayer network data," Computational Statistics & Data Analysis, Elsevier, vol. 169(C).
    15. 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.
    16. 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.
    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. Chen, Mingli & Fernández-Val, Iván & Weidner, Martin, 2021. "Nonlinear factor models for network and panel data," Journal of Econometrics, Elsevier, vol. 220(2), pages 296-324.
    19. Cornelius Fritz & Michael Lebacher & Göran Kauermann, 2020. "Tempus volat, hora fugit: A survey of tie‐oriented dynamic network models in discrete and continuous time," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 74(3), pages 275-299, August.
    20. Ick Hoon Jin & Minjeong Jeon, 2019. "A Doubly Latent Space Joint Model for Local Item and Person Dependence in the Analysis of Item Response Data," Psychometrika, Springer;The Psychometric Society, vol. 84(1), pages 236-260, March.

    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.