Network Detection Theory and Performance
arXiv:1303.5613 · doi:10.1109/TSP.2014.2336613
Abstract
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.
arXiv commentSubmitted to IEEE Trans. Signal Processing
References in corpus (11)
- The structure and function of complex networks
- Community structure in social and biological networks
- Community detection in graphs
- Finding community structure in networks using the eigenvectors of matrices
- Resolution limit in community detection
- Mixed membership stochastic blockmodels
- Average path length in random networks
- Average path length in uncorrelated random networks with hidden variables
- Graph spectra and the detectability of community structure in networks
- Limited resolution in complex network community detection with Potts model approach
- Spreading paths in partially observed social networks
Cited by in corpus (7)
- Automatic Detection of Influential Actors in Disinformation Networks
- Streaming Graph Challenge: Stochastic Block Partition
- A Spectral Framework for Anomalous Subgraph Detection
- Contagion Source Detection in Epidemic and Infodemic Outbreaks: Mathematical Analysis and Network Algorithms
- Influence Estimation on Social Media Networks Using Causal Inference
- From random walks to distances on unweighted graphs
- The Power of Side-information in Subgraph Detection