Publications
Super-resolution community detection for layer-aggregated multilayer networks
September 26, 2017
Journal Article
Published in:
Phys. Rev. X, Vol. 7, No. 3, July-September 2017, 031056.
Summary
Applied network science often involves preprocessing network data before applying a network-analysis method, and there is typically a theoretical disconnect between these steps. For example, it is common to aggregate time-varying network data into windows prior to analysis, and the trade-offs of this preprocessing are not well understood. Focusing on the problem of detecting small communities in multilayer networks, we study the effects of layer aggregation by developing random-matrix theory for modularity matrices associated with layer-aggregated networks with N nodes and L layers, which are drawn from an ensemble of Erdős–Rényi networks with communities planted in subsets of layers. We study phase transitions in which eigenvectors localize onto communities (allowing their detection) and which occur for a given community provided its size surpasses a detectability limit K*. When layers are aggregated via a summation, we obtain K* is proportional to O(square root of NL/T), where T is the number of layers across which the community persists. Interestingly, if T is allowed to vary with L, then summation-based layer aggregation enhances small-community detection even if the community persists across a vanishing fraction of layers, provided that T=L decays more slowly than O(L^−1/2). Moreover, we find that thresholding the summation can, in some cases, cause K* to decay exponentially, decreasing by orders of magnitude in a phenomenon we call super-resolution community detection. In other words, layer aggregation with thresholding is a nonlinear data filter enabling detection of communities that are otherwise too small to detect. Importantly, different thresholds generally enhance the detectability of communities having different properties, illustrating that community detection can be obscured if one analyzes network data using a single threshold.
Summary
Applied network science often involves preprocessing network data before applying a network-analysis method, and there is typically a theoretical disconnect between these steps. For example, it is common to aggregate time-varying network data into windows prior to analysis, and the trade-offs of this preprocessing are not well understood. Focusing on...
READ MORE
SIAM data mining "brings it" to annual meeting
February 17, 2017
Project Report
Published in:
MIT Lincoln Laboratory Report 113081
Summary
The Data Mining Activity Group is one of SIAM's most vibrant and dynamic activity groups. To better share our enthusiasm for data mining with the broader SIAM community, our activity group organized six minisymposia at the 2016 Annual Meeting. These minisymposia included 48 talks organized by 11 SIAM members.
Summary
The Data Mining Activity Group is one of SIAM's most vibrant and dynamic activity groups. To better share our enthusiasm for data mining with the broader SIAM community, our activity group organized six minisymposia at the 2016 Annual Meeting. These minisymposia included 48 talks organized by 11 SIAM members.
READ MORE
Very large graphs for information extraction (VLG) - detection and inference in the presence of uncertainty
September 21, 2015
Project Report
Published in:
MIT Lincoln Laboratory Report VLG-2
Summary
In numerous application domains relevant to the Department of Defense and the Intelligence Community, data of interest take the form of entities and the relationships between them, and these data are commonly represented as graphs. Under the Very Large Graphs for Information Extraction effort--a one year proof-of-concept study--MIT LL developed novel techniques for anomalous subgraph detection, building on tools in the signal processing research literature. This report documents the technical results of this effort. Two datasets--a snapshot of Thompson Reuters' Web of Science database and a stream of web proxy logs--were parsed, and graphs were constructed from the raw data. From the phenomena in these datasets, several algorithms were developed to model the dynamic graph behavior, including a preferential attachment mechanism with memory, a streaming filter to model a graph as a weighted average of its past connections, and a generalized linear model for graphs where connection probabilities are determined by additional side information or metadata. A set of metrics was also constructed to facilitate comparison of techniques. The study culminated in a demonstration of the algorithms on the datasets of interest, in addition to simulated data. Performance in terms of detection, estimation, and computational burden was measured according to the metrics. Among the highlights of this demonstration were the detection of emerging coauthor clusters in the Web of Science data, detection of botnet activity in the web proxy data after 15 minutes (which took 10 days to detect using state-of-the-practice techniques), and demonstration of the core algorithm on a simulated 1-billion-vertex graph using a commodity computing cluster.
Summary
In numerous application domains relevant to the Department of Defense and the Intelligence Community, data of interest take the form of entities and the relationships between them, and these data are commonly represented as graphs. Under the Very Large Graphs for Information Extraction effort--a one year proof-of-concept study--MIT LL developed...
READ MORE
Advisory services for user composition tools
February 7, 2015
Conference Paper
Published in:
9th IEEE Int. Conf. on Semantic Computing, IEEE ICSC 2015, 7-9 February 2015.
Summary
We have developed an ontology based framework that evaluates compatibility between processing modules within an end user development framework, using MIT Lincoln Laboratory's Composable Analytics environment as a test case. In particular, we focus on inter-module semantic compatibility as well as compatibility between data and modules. Our framework includes a core ontology that provides an extendible vocabulary that can describe module attributes, module input and output requirements and preferences, and data characteristics that are pertinent to selecting appropriate modules in a given situation. Based on the ontological description of the modules and data, we first present a framework that takes a rule based approach in measuring semantic compatibility. Later, we extend the rule based approach to a flexible fuzzy logic based semantic compatibility evaluator. We have built an initial simulator to test module compatibility under varying situations. The simulator takes in the ontological description of the modules and data and calculates semantic compatibility. We believe the framework and simulation environment together will help both the developers test new modules they create as well as support end users in composing new capabilities. In this paper, we describe the details of the framework, the simulation environment, and our iterative process in developing the module ontology.
Summary
We have developed an ontology based framework that evaluates compatibility between processing modules within an end user development framework, using MIT Lincoln Laboratory's Composable Analytics environment as a test case. In particular, we focus on inter-module semantic compatibility as well as compatibility between data and modules. Our framework includes a...
READ MORE
Time delay integration and in-pixel spatiotemporal filtering using a nanoscale digital CMOS focal plane readout
November 1, 2009
Journal Article
Published in:
IEEE Trans. on Electron Devices, Vol. 56, No. 11, November 2009, pp. 2516-2533.
Summary
A digital focal plane array (DFPA) architecture has been developed that incorporates per-pixel full-dynamic-range analog-to-digital conversion and orthogonal-transfer-based realtime digital signal processing capability. Several long-wave infrared-optimized pixel processing focal plane readout integrated circuit (ROIC) designs have been implemented, each accommodating a 256 x 256 30-um-pitch detector array. Demonstrated in this paper is the application of this DFPA ROIC architecture to problems of background pedestal mitigation, wide-field imaging, image stabilization, edge detection, and velocimetry. The DFPA architecture is reviewed, and pixel performance metrics are discussed in the context of the application examples. The measured data reported here are for DFPA ROICs implemented in 90-nm CMOS technology and hybridized to HgxCd1-xTe (MCT) detector arrays with cutoff wavelengths ranging from 7 to 14.5 m and a specified operating temperature of 60 K-80 K.
Summary
A digital focal plane array (DFPA) architecture has been developed that incorporates per-pixel full-dynamic-range analog-to-digital conversion and orthogonal-transfer-based realtime digital signal processing capability. Several long-wave infrared-optimized pixel processing focal plane readout integrated circuit (ROIC) designs have been implemented, each accommodating a 256 x 256 30-um-pitch detector array. Demonstrated in this...
READ MORE
Miss distance analysis for command guided missiles
December 1, 1988
Journal Article
Published in:
J. Guid. Control Dyn., Vol. 11, No. 6, November-December 1988, pp. 481-487.
Summary
A concise theoretical technique is presented for estimating the minimum miss distance capability of command guided missile systems using synthetic proportional navigation. The effect of the parameter values on the system capability is shown to be a function of range-to-intercept; the technique enables the system designer and analyst to quantify system performance and to develop a systematic understanding of the performance limitations of command guidance systems at each intercept range. New analytical equations based upon adjoint theory are developed for statistical miss distance caused by target maneuver, range-dependent, servo, glint and atmosphere noises for command guided systems. An optimal total system time constant is derived which yields the minimum statistical miss distance. Realistic constraints on the minimum achievable system time constant are considered. The equations derived for the optimal total system time constant are valuable to the system designer for minimizing miss distance over the ranges of system parameters and limitations, and intercept conditions.
Summary
A concise theoretical technique is presented for estimating the minimum miss distance capability of command guided missile systems using synthetic proportional navigation. The effect of the parameter values on the system capability is shown to be a function of range-to-intercept; the technique enables the system designer and analyst to quantify...
READ MORE