A Combinatorial Analysis of Link Discovery

Abstract

Link discovery and analysis, or connecting the dots, is a key component of intelligence analysis. Little principled analysis of this process has oc- curred. This paper presents a quantitative analy- sis of this process using a model based on the metaphor of identifying and assembling pieces of jigsaw puzzles. Specifically, it evaluates the probability that a particular puzzle can be recog- nized and classified based on various parameters describing data volumes, number of analysts, number of pieces required for recognition, and fraction of interesting puzzles. Combinatorial techniques are used to provide a closed-form so- lution for both single-analyst and multi-analyst collaborative situations. Computational experi- ments that demonstrate the effects of different parameters and structures are described. The key result is that factors that affect the likelihood of related pieces’ being presented to a single ana- lyst – such as the collection of more data – dominate the solution probability.