A Statistical Framework for Analyzing Streaming Graphs

James Fairbanks is presenting work on frameworks for analyzing the evolution of dynamic graphs using statistical techniques today at the 2013 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining (ASONAM 2013).

Abstract—In this paper we propose a new methodology for gaining insight into the temporal aspects of social networks. In order to develop higher-level, large-scale data analysis methodsfor classification, prediction, and  anomaly detection, a solid foundation of analytical techniques is required. We present a novel approach to the  analysis of these networks that leverages time series and statistical techniques to quantitatively describe the temporal nature of a social network. We report on the application of our approach toward a real data set and successfully visualize high-level changes to the network as well as discover outlying vertices.

The real-time prediction of new connections given the previous connections in a graph is a notoriously difficult task. The proposed technique avoids this difficulty by modeling statistics computed from the graph over time. Vertex statistics summarize topological information as real numbers, which allows us to leverage the existing fields of computational statistics and machine learning. This creates a modular approach to analysis in which methods can be developed that are agnostic to the metrics and algorithms used to process the graph.

We demonstrate these techniques using a collection of Twitter posts related to Hurricane Sandy. We study the temporal nature of betweenness centrality and clustering coefficients while producing multiple visualizations of a social network dataset with 1.2 million edges. We successfully detect vertices whose triangleforming behavior is anomalous.

J. Fairbanks, D. Ediger, R. McColl, D.A. Bader and E. Gilbert, ``A Statistical Framework for Streaming Graph Analysis,'' IEEE/ACM International Conference on Advances in Social Networks Analysis and Modeling (ASONAM), Niagara Falls, Canada, August 25-28, 2013.

<< Go back to the previous page