Accession Number : ADA454928


Title :   Scalable Detection and Optimization of N-ARY Linkages


Descriptive Note : Final technical rept. Sep 2001-Feb 2006


Corporate Author : CARNEGIE-MELLON UNIV PITTSBURGH PA


Personal Author(s) : Moore, Andrew ; Schneider, Jeff ; Kubica, Jeremy ; Goldenberg, Anna ; Dubrawski, Artur ; Ostlund, John ; Choi, Patrick ; Komarek, Jeanie ; Goode, Adam ; Sarkar, Purna


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/a454928.pdf


Report Date : Jun 2006


Pagination or Media Count : 12


Abstract : 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.


Descriptors :   *MATHEMATICAL MODELS , *ALGORITHMS , *OPTIMIZATION , *GROUP DYNAMICS , *NETWORKS , MAXIMUM LIKELIHOOD ESTIMATION , STRUCTURAL ANALYSIS , PROBABILITY , SCALING FACTOR , HEURISTIC METHODS , BAYES THEOREM , SURFACE TRUTH , SOCIAL SCIENCES


Subject Categories : Operations Research


Distribution Statement : APPROVED FOR PUBLIC RELEASE