Scalable Detection and Optimization of N-ARY Linkages
Final technical rept. Sep 2001-Feb 2006
CARNEGIE-MELLON UNIV PITTSBURGH PA
Pagination or Media Count:
Link detection and analysis has long been important in the social sciences where a single link can be the key evidence that leads an intelligence analyst to additional clues to a threat event. A significant effort is focused on the structural and functional analysis of known networks. Similarly, the detection of individual links is important but is usually done with techniques that result in known links. More recently, the internet and other sources have led to a flood of circumstantial data that provide probabilistic evidence of links. Co-occurrence in news articles and simultaneous travels to the same location are two examples. We propose a probabilistic model of link generation based on membership in groups. The model considers both observed link evidence and demographic information about the entities. The parameters of the model are learned via a maximum likelihood search. In this paper, we describe the model and then show several heuristics that make the search tractable. We test our model and optimization methods on synthetic data sets with a known ground truth and a database of news articles.
- Operations Research