Social network analysis (SNA) has become an important analytic tool for analyzing terrorist networks, friendly command and control structures, arms trade, biological warfare, the spread of diseases, among other applications. Detecting dynamic changes over time from an SNA perspective, may signal an underlying change within an organization, and may even predict significant events or behaviors. The challenges in detecting network change includes the lack of underlying statistical distributions to quantify significant change, as well as high relational dependence affecting assumptions of independence and normality. Additional challenges involve determining an algorithm that maximizes the probability of detecting change, given a risk level for false alarm.

A suite of computational and statistical approaches for detecting change are identified and compared. The Neyman-Pearson most powerful test of simple hypotheses is extended as a cumulative sum statistical process control chart to detect network change over time. Anomaly detection approaches using exponentially weighted moving average or scan statistics investigate performance under conditions of potential time-series dependence. Fourier analysis and wavelets are applied to a spectral analysis of social networks over time. Parameter values are varied for all approaches. The results are put in a computational decision support framework.

This new approach is demonstrated in multi-agent simulation as well as on eight different real-world data sets. The results indicate that this approach is able to detect change even with high levels of uncertainty inherent in the data. The ability to systematically, statistically, effectively and efficiently detect these changes has the potential to enable the anticipation of change, provide early warning of change, and enable faster appropriate response to change.

176 pages

Return to: SCS Technical Report Collection
School of Computer Science homepage

This page maintained by reports@cs.cmu.edu