Proximal-gradient algorithms for tracking cascades over social networks

Brian Baingana, Gonzalo Mateos, Georgios B. Giannakis

Research output: Contribution to journalArticle

46 Scopus citations

Abstract

Many real-world processes evolve in cascades over complex networks, whose topologies are often unobservable and change over time. However, the so-termed adoption times when blogs mention popular news items, individuals in a community catch an infectious disease, or consumers adopt a trendy electronics product are typically known, and are implicitly dependent on the underlying network. To infer the network topology, a dynamic structural equation model is adopted to capture the relationship between observed adoption times and the unknown edge weights. Assuming a slowly time-varying topology and leveraging the sparse connectivity inherent to social networks, edge weights are estimated by minimizing a sparsity-regularized exponentially-weighted least-squares criterion. To this end, solvers with complementary strengths are developed by leveraging (pseudo) real-time sparsity-promoting proximal gradient iterations, the improved convergence rate of accelerated variants, or reduced computational complexity of stochastic gradient descent. Numerical tests with both synthetic and real data demonstrate the effectiveness of the novel algorithms in unveiling sparse dynamically-evolving topologies, while accounting for external influences in the adoption times. Key events in the political leadership in North Korea and the initial public offering of LinkedIn explain connectivity changes observed in the associated networks inferred from global cascades of online media.

Original languageEnglish (US)
Article number6797935
Pages (from-to)563-575
Number of pages13
JournalIEEE Journal on Selected Topics in Signal Processing
Volume8
Issue number4
DOIs
StatePublished - Aug 2014

Keywords

  • Structural equation model
  • contagion
  • dynamic network
  • social network
  • sparsity

Fingerprint Dive into the research topics of 'Proximal-gradient algorithms for tracking cascades over social networks'. Together they form a unique fingerprint.

  • Cite this