In this work we consider the problem of learning an Erdos-Renyi graph over a diffusion network when: i) data from only a limited subset of nodes are available (partial observation); ii) and the inferential goal is to discover the graph of interconnections linking the accessible nodes (local structure learning). We propose three matrix estimators, namely, the Granger, the onelag correlation, and the residual estimators, which, when followed by a universal clustering algorithm, are shown to retrieve the true subgraph in the limit of large network sizes. Remarkably, it is seen that a fundamental role is played by the uniform concentration of node degrees, rather than by sparsity.

Graph Learning with Partial Observations: Role of Degree Concentration

Matta, V;
2019

Abstract

In this work we consider the problem of learning an Erdos-Renyi graph over a diffusion network when: i) data from only a limited subset of nodes are available (partial observation); ii) and the inferential goal is to discover the graph of interconnections linking the accessible nodes (local structure learning). We propose three matrix estimators, namely, the Granger, the onelag correlation, and the residual estimators, which, when followed by a universal clustering algorithm, are shown to retrieve the true subgraph in the limit of large network sizes. Remarkably, it is seen that a fundamental role is played by the uniform concentration of node degrees, rather than by sparsity.
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11386/4750902
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? 0
social impact