Publications
Toward matched filter optimization for subgraph detection in dynamic networks
Summary
Summary
This paper outlines techniques for optimization of filter coefficients in a spectral framework for anomalous subgraph detection. Restricting the scope to the detection of a known signal in i.i.d. noise, the optimal coefficients for maximizing the signal's power are shown to be found via a rank-1 tensor approximation of the...
A stochastic system for large network growth
Summary
Summary
This letter proposes a new model for preferential attachment in dynamic directed networks. This model consists of a linear time-invariant system that uses past observations to predict future attachment rates, and an innovation noise process that induces growth on vertices that previously had no attachments. Analyzing a large citation network...
A scalable signal processing architecture for massive graph analysis
Summary
Summary
In many applications, it is convenient to represent data as a graph, and often these datasets will be quite large. This paper presents an architecture for analyzing massive graphs, with a focus on signal processing applications such as modeling, filtering, and signal detection. We describe the architecture, which covers the...
Goodness-of-fit statistics for anomaly detection in Chung-Lu random graphs
Summary
Summary
Anomaly detection in graphs is a relevant problem in numerous applications. When determining whether an observation is anomalous with respect to the model of typical behavior, the notion of "goodness of fit" is important. This notion, however, is not well understood in the context of graph data. In this paper...
Moments of parameter estimates for Chung-Lu random graph models
Summary
Summary
As abstract representations of relational data, graphs and networks find wide use in a variety of fields, particularly when working in non- Euclidean spaces. Yet for graphs to be truly useful in in the context of signal processing, one ultimately must have access to flexible and tractable statistical models. One...
Dynamic Distributed Dimensional Data Model (D4M) database and computation system
Summary
Summary
A crucial element of large web companies is their ability to collect and analyze massive amounts of data. Tuple store databases are a key enabling technology employed by many of these companies (e.g., Google Big Table and Amazon Dynamo). Tuple stores are highly scalable and run on commodity clusters, but...
Fundamental Questions in the Analysis of Large Graphs
Summary
Summary
Graphs are a general approach for representing information that spans the widest possible range of computing applications. They are particularly important to computational biology, web search, and knowledge discovery. As the sizes of graphs increase, the need to apply advanced mathematical and computational techniques to solve these problems is growing...
A knowledge-based operator for a genetic algorithm which optimizes the distribution of sparse matrix data
Summary
Summary
We present the Hogs and Slackers genetic algorithm (GA) which addresses the problem of improving the parallelization efficiency of sparse matrix computations by optimally distributing blocks of matrices data. The performance of a distribution is sensitive to the non-zero patterns in the data, the algorithm, and the hardware architecture. In...
Eigenspace analysis for threat detection in social networks
Summary
Summary
The problem of detecting a small, anomalous subgraph within a large background network is important and applicable to many fields. The non-Euclidean nature of graph data, however, complicates the application of classical detection theory in this context. A recent statistical framework for anomalous subgraph detection uses spectral properties of a...
Anomalous subgraph detection via sparse principal component analysis
Summary
Summary
Network datasets have become ubiquitous in many fields of study in recent years. In this paper we investigate a problem with applicability to a wide variety of domains - detecting small, anomalous subgraphs in a background graph. We characterize the anomaly in a subgraph via the well-known notion of network...