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 language | English (US) |
---|---|
Title of host publication | 2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014 |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
Pages | 867-871 |
Number of pages | 5 |
ISBN (Electronic) | 9781479970889 |
DOIs | |
State | Published - Feb 5 2014 |
Event | 2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014 - Atlanta, United States Duration: Dec 3 2014 → Dec 5 2014 |
Publication series
Name | 2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014 |
---|
Other
Other | 2014 IEEE Global Conference on Signal and Information Processing, GlobalSIP 2014 |
---|---|
Country/Territory | United States |
City | Atlanta |
Period | 12/3/14 → 12/5/14 |
Bibliographical note
Publisher Copyright:© 2014 IEEE.
Keywords
- Anomalies
- Community detection
- Low rank
- Non-negative matrix factorization
- Sparsity