Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Estimating the Topology of Preferential Attachment Graphs Under Partial Observability
 
Loading...
Thumbnail Image
research article

Estimating the Topology of Preferential Attachment Graphs Under Partial Observability

Cirillo, Michele
•
Matta, Vincenzo
•
Sayed, Ali H.  
February 1, 2023
Ieee Transactions On Information Theory

This work addresses the problem of learning the topology of a network from the signals emitted by the network nodes. These signals are generated over time through a linear diffusion process, where neighboring nodes exchange messages according to the underlying network topology, and aggregate them according to a certain combination matrix. We consider the demanding setting of graph learning under partial observability, where signals are available only from a limited fraction of nodes, and we want to establish whether the topology of these nodes can be estimated faithfully, despite the presence of possibly many latent nodes. Recent results examined this problem when the network topology is generated according to an Erdos-Renyi random model. However, Erdos-Renyi graphs feature homogeneity across nodes and independence across edges, while, over several real-world networks, significant heterogeneity is observed between very connected "hubs" and scarcely connected peripheral nodes, and the edge construction process entails significant dependencies across edges. Preferential attachment random graphs were conceived primarily to fill these gaps. We tackle the problem of graph learning over preferential attachment graphs by focusing on the following setting: first-order vector autoregressive models equipped with a stable Laplacian combination matrix, and a network topology drawn according to the popular Bollobas-Riordan preferential attachment model. The main result established in this work is that a combination-matrix estimator known as Granger estimator achieves graph learning under partial observability.

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

09912646.pdf

Type

Publisher's Version

Access type

openaccess

License Condition

CC BY

Size

1.82 MB

Format

Adobe PDF

Checksum (MD5)

b52b08ef4426096450badd73062172d8

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés