Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints

Abstract Exponential Random Graph Models (ERGMs) have gained increasing popularity over the years. Rooted into statistical physics, the ERGMs framework has been successfully employed for reconstructing networks, detecting statistically significant patterns in graphs, counting networked configuration...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Nicolò Vallarano, Matteo Bruno, Emiliano Marchese, Giuseppe Trapani, Fabio Saracco, Giulio Cimini, Mario Zanon, Tiziano Squartini
Formato:	article
Lenguaje:	EN
Publicado:	Nature Portfolio 2021
Materias:	Medicine R Science Q
Acceso en línea:	https://doaj.org/article/00f9f8db37124723b7faa9a1b6954d4c
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:00f9f8db37124723b7faa9a1b6954d4c
record_format	dspace
spelling	oai:doaj.org-article:00f9f8db37124723b7faa9a1b6954d4c2021-12-02T16:31:02ZFast and scalable likelihood maximization for Exponential Random Graph Models with local constraints10.1038/s41598-021-93830-42045-2322https://doaj.org/article/00f9f8db37124723b7faa9a1b6954d4c2021-07-01T00:00:00Zhttps://doi.org/10.1038/s41598-021-93830-4https://doaj.org/toc/2045-2322Abstract Exponential Random Graph Models (ERGMs) have gained increasing popularity over the years. Rooted into statistical physics, the ERGMs framework has been successfully employed for reconstructing networks, detecting statistically significant patterns in graphs, counting networked configurations with given properties. From a technical point of view, the ERGMs workflow is defined by two subsequent optimization steps: the first one concerns the maximization of Shannon entropy and leads to identify the functional form of the ensemble probability distribution that is maximally non-committal with respect to the missing information; the second one concerns the maximization of the likelihood function induced by this probability distribution and leads to its numerical determination. This second step translates into the resolution of a system of O(N) non-linear, coupled equations (with N being the total number of nodes of the network under analysis), a problem that is affected by three main issues, i.e. accuracy, speed and scalability. The present paper aims at addressing these problems by comparing the performance of three algorithms (i.e. Newton’s method, a quasi-Newton method and a recently-proposed fixed-point recipe) in solving several ERGMs, defined by binary and weighted constraints in both a directed and an undirected fashion. While Newton’s method performs best for relatively little networks, the fixed-point recipe is to be preferred when large configurations are considered, as it ensures convergence to the solution within seconds for networks with hundreds of thousands of nodes (e.g. the Internet, Bitcoin). We attach to the paper a Python code implementing the three aforementioned algorithms on all the ERGMs considered in the present work.Nicolò VallaranoMatteo BrunoEmiliano MarcheseGiuseppe TrapaniFabio SaraccoGiulio CiminiMario ZanonTiziano SquartiniNature PortfolioarticleMedicineRScienceQENScientific Reports, Vol 11, Iss 1, Pp 1-33 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	Medicine R Science Q
spellingShingle	Medicine R Science Q Nicolò Vallarano Matteo Bruno Emiliano Marchese Giuseppe Trapani Fabio Saracco Giulio Cimini Mario Zanon Tiziano Squartini Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
description	Abstract Exponential Random Graph Models (ERGMs) have gained increasing popularity over the years. Rooted into statistical physics, the ERGMs framework has been successfully employed for reconstructing networks, detecting statistically significant patterns in graphs, counting networked configurations with given properties. From a technical point of view, the ERGMs workflow is defined by two subsequent optimization steps: the first one concerns the maximization of Shannon entropy and leads to identify the functional form of the ensemble probability distribution that is maximally non-committal with respect to the missing information; the second one concerns the maximization of the likelihood function induced by this probability distribution and leads to its numerical determination. This second step translates into the resolution of a system of O(N) non-linear, coupled equations (with N being the total number of nodes of the network under analysis), a problem that is affected by three main issues, i.e. accuracy, speed and scalability. The present paper aims at addressing these problems by comparing the performance of three algorithms (i.e. Newton’s method, a quasi-Newton method and a recently-proposed fixed-point recipe) in solving several ERGMs, defined by binary and weighted constraints in both a directed and an undirected fashion. While Newton’s method performs best for relatively little networks, the fixed-point recipe is to be preferred when large configurations are considered, as it ensures convergence to the solution within seconds for networks with hundreds of thousands of nodes (e.g. the Internet, Bitcoin). We attach to the paper a Python code implementing the three aforementioned algorithms on all the ERGMs considered in the present work.
format	article
author	Nicolò Vallarano Matteo Bruno Emiliano Marchese Giuseppe Trapani Fabio Saracco Giulio Cimini Mario Zanon Tiziano Squartini
author_facet	Nicolò Vallarano Matteo Bruno Emiliano Marchese Giuseppe Trapani Fabio Saracco Giulio Cimini Mario Zanon Tiziano Squartini
author_sort	Nicolò Vallarano
title	Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
title_short	Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
title_full	Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
title_fullStr	Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
title_full_unstemmed	Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints
title_sort	fast and scalable likelihood maximization for exponential random graph models with local constraints
publisher	Nature Portfolio
publishDate	2021
url	https://doaj.org/article/00f9f8db37124723b7faa9a1b6954d4c
work_keys_str_mv	AT nicolovallarano fastandscalablelikelihoodmaximizationforexponentialrandomgraphmodelswithlocalconstraints AT matteobruno fastandscalablelikelihoodmaximizationforexponentialrandomgraphmodelswithlocalconstraints AT emilianomarchese fastandscalablelikelihoodmaximizationforexponentialrandomgraphmodelswithlocalconstraints AT giuseppetrapani fastandscalablelikelihoodmaximizationforexponentialrandomgraphmodelswithlocalconstraints AT fabiosaracco fastandscalablelikelihoodmaximizationforexponentialrandomgraphmodelswithlocalconstraints AT giuliocimini fastandscalablelikelihoodmaximizationforexponentialrandomgraphmodelswithlocalconstraints AT mariozanon fastandscalablelikelihoodmaximizationforexponentialrandomgraphmodelswithlocalconstraints AT tizianosquartini fastandscalablelikelihoodmaximizationforexponentialrandomgraphmodelswithlocalconstraints
_version_	1718383851304124416

Fast and scalable likelihood maximization for Exponential Random Graph Models with local constraints

Ejemplares similares