Joint Community and Anomaly Tracking in Dynamic Networks

Brian Baingana, Georgios B. Giannakis

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

Most real-world networks exhibit community structure, a phenomenon characterized by existence of node clusters whose intra-edge connectivity is stronger than edge connectivities between nodes belonging to different clusters. In addition to facilitating a better understanding of network behavior, community detection finds many practical applications in diverse settings. Communities in online social networks are indicative of shared functional roles, or affiliation to a common socio-economic status, the knowledge of which is vital for targeted advertisement. In buyer-seller networks, community detection facilitates better product recommendations. Unfortunately, reliability of community assignments is hindered by anomalous user behavior often observed as unfair self-promotion, or "fake" highly-connected accounts created to promote fraud. The present paper advocates a novel approach for jointly tracking communities while detecting such anomalous nodes in time-varying networks. By postulating edge creation as the result of mutual community participation by node pairs, a dynamic factor model with anomalous memberships captured through a sparse outlier matrix is put forth. Efficient tracking algorithms suitable for both online and decentralized operation are developed. Experiments conducted on both synthetic and real network time series successfully unveil underlying communities and anomalous nodes.

Original languageEnglish (US)
Article number7362023
Pages (from-to)2013-2025
Number of pages13
JournalIEEE Transactions on Signal Processing
Volume64
Issue number8
DOIs
StatePublished - Apr 15 2016

Bibliographical note

Funding Information:
Work in this paper was supported by NSF grants 1343248, 1442686, 1514056, NIH Grant No. 1R01GM104975-01, and AFOSR-MURI Grant No. FA9550-10- 1-0567. This research has been co-financed by the European Union (European Social Fund-ESF), and Greek national funds through the Operational Program "Education and Lifelong Learning" of the National Strategic Reference Framework (NSRF) - Research Funding Program: THALES. Investing in knowledge society through the ESF.

Keywords

  • Anomalies
  • community detection
  • low rank
  • nonnegative matrix factorization
  • sparsity

Fingerprint Dive into the research topics of 'Joint Community and Anomaly Tracking in Dynamic Networks'. Together they form a unique fingerprint.

Cite this