Tracking anomalous community memberships in time-varying networks

Brian Baingana, Georgios B Giannakis

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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. Formulated as a time-varying, outlier-aware, non-negative matrix factorization problem, an efficient tracking algorithm is developed. The efficacy of the proposed approach is demonstrated on synthetic network time series generated using the stochastic block model.

Original languageEnglish (US)
Title of host publication2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages867-871
Number of pages5
ISBN (Electronic)9781479970889
DOIs
StatePublished - Feb 5 2014
Event2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014 - Atlanta, United States
Duration: Dec 3 2014Dec 5 2014

Publication series

Name2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014

Other

Other2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014
Country/TerritoryUnited States
CityAtlanta
Period12/3/1412/5/14

Bibliographical note

Publisher Copyright:
© 2014 IEEE.

Keywords

  • Anomalies
  • Community detection
  • Low rank
  • Non-negative matrix factorization
  • Sparsity

Fingerprint

Dive into the research topics of 'Tracking anomalous community memberships in time-varying networks'. Together they form a unique fingerprint.

Cite this