2013/03/22 by Steven T. Smith, Edward K. Kao, Kenneth D. Senne +2 · 18 citations
Computer Science · Mathematics · Physics and Astronomy · #Algorithm #Artificial intelligence #Bayesian network #Bayesian probability #Complex Network Analysis Techniques #Computer science #Covert #Data mining #Discrete mathematics #Equivalence (formal languages) #Graph #Mathematics #Network Security and Intrusion Detection #Opinion Dynamics and Social Influence #Random graph #Random walk #Statistics #Theoretical computer science #cs.LG #cs.SI #math.ST #physics.soc-ph #stat.ML #stat.TH
paper · pdf · open access · doi:10.1109/tsp.2014.2336613
published in IEEE Transactions on Signal Processing 62(20), 5324-5338 (Institute of Electrical and Electronics Engineers) · Submitted to IEEE Trans. Signal Processing
arxiv created 2013/03/22 · openalex publication_date 2014/09/09 · arxiv updated 2018/04/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
Network detection is an important capability in many areas of applied research in which data can be represented as a graph of entities and relationships. Oftentimes the object of interest is a relatively small subgraph in an enormous, potentially uninteresting background. This aspect characterizes network detection as a "big data" problem. Graph partitioning and network discovery have been major research areas over the last ten years, driven by interest in internet search, cyber security, social networks, and criminal or terrorist activities. The specific problem of network discovery is addressed as a special case of graph partitioning in which membership in a small subgraph of interest must be determined. Algebraic graph theory is used as the basis to analyze and compare different network detection methods. A new Bayesian network detection framework is introduced that partitions the graph based on prior information and direct observations. The new approach, called space-time threat propagation, is proved to maximize the probability of detection and is therefore optimum in the Neyman-Pearson sense. This optimality criterion is compared to spectral community detection approaches which divide the global graph into subsets or communities with optimal connectivity properties. We also explore a new generative stochastic model for covert networks and analyze using receiver operating characteristics the detection performance of both classes of optimal detection techniques.