Extended Stochastic Block Models with Application to Criminal Networks
- URL: http://arxiv.org/abs/2007.08569v4
- Date: Mon, 4 Apr 2022 13:26:29 GMT
- Title: Extended Stochastic Block Models with Application to Criminal Networks
- Authors: Sirio Legramanti, Tommaso Rigon, Daniele Durante and David B. Dunson
- Abstract summary: We study covert networks that encode relationships among criminals.
The coexistence of noisy block patterns limits the reliability of routinely-used community detection algorithms.
We develop a new class of extended block models (ESBM) that infer groups of nodes having common connectivity patterns.
- Score: 3.2211782521637393
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Reliably learning group structures among nodes in network data is challenging
in several applications. We are particularly motivated by studying covert
networks that encode relationships among criminals. These data are subject to
measurement errors, and exhibit a complex combination of an unknown number of
core-periphery, assortative and disassortative structures that may unveil key
architectures of the criminal organization. The coexistence of these noisy
block patterns limits the reliability of routinely-used community detection
algorithms, and requires extensions of model-based solutions to realistically
characterize the node partition process, incorporate information from node
attributes, and provide improved strategies for estimation and uncertainty
quantification. To cover these gaps, we develop a new class of extended
stochastic block models (ESBM) that infer groups of nodes having common
connectivity patterns via Gibbs-type priors on the partition process. This
choice encompasses many realistic priors for criminal networks, covering
solutions with fixed, random and infinite number of possible groups, and
facilitates the inclusion of node attributes in a principled manner. Among the
new alternatives in our class, we focus on the Gnedin process as a realistic
prior that allows the number of groups to be finite, random and subject to a
reinforcement process coherent with criminal networks. A collapsed Gibbs
sampler is proposed for the whole ESBM class, and refined strategies for
estimation, prediction, uncertainty quantification and model selection are
outlined. The ESBM performance is illustrated in realistic simulations and in
an application to an Italian mafia network, where we unveil key complex block
structures, mostly hidden from state-of-the-art alternatives.
Related papers
- Implicit models, latent compression, intrinsic biases, and cheap lunches
in community detection [0.0]
Community detection aims to partition a network into clusters of nodes to summarize its large-scale structure.
Some community detection methods are inferential, explicitly deriving the clustering objective through a probabilistic generative model.
Other methods are descriptive, dividing a network according to an objective motivated by a particular application.
We present a solution that associates any community detection objective, inferential or descriptive, with its corresponding implicit network generative model.
arXiv Detail & Related papers (2022-10-17T15:38:41Z) - Toward Certified Robustness Against Real-World Distribution Shifts [65.66374339500025]
We train a generative model to learn perturbations from data and define specifications with respect to the output of the learned model.
A unique challenge arising from this setting is that existing verifiers cannot tightly approximate sigmoid activations.
We propose a general meta-algorithm for handling sigmoid activations which leverages classical notions of counter-example-guided abstraction refinement.
arXiv Detail & Related papers (2022-06-08T04:09:13Z) - Bayesian community detection for networks with covariates [16.230648949593153]
"Community detection" has arguably received the most attention in the scientific community.
We propose a block model with a co-dependent random partition prior.
Our model has the ability to learn the number of the communities via posterior inference without having to assume it to be known.
arXiv Detail & Related papers (2022-03-04T01:58:35Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
The critical node problem (CNP) aims to find a set of critical nodes from a network whose deletion maximally degrades the pairwise connectivity of the residual network.
This work proposes a feature importance-aware graph attention network for node representation.
It combines it with dueling double deep Q-network to create an end-to-end algorithm to solve CNP for the first time.
arXiv Detail & Related papers (2021-12-03T14:23:05Z) - Community models for networks observed through edge nominations [6.442024233731203]
Communities are a common and widely studied structure in networks, typically under the assumption that the network is fully and correctly observed.
We propose a general model for a class of network sampling mechanisms based on recording edges via querying nodes.
We show community detection can be performed by spectral clustering under this general class of models.
arXiv Detail & Related papers (2020-08-09T04:53:13Z) - A Multi-Semantic Metapath Model for Large Scale Heterogeneous Network
Representation Learning [52.83948119677194]
We propose a multi-semantic metapath (MSM) model for large scale heterogeneous representation learning.
Specifically, we generate multi-semantic metapath-based random walks to construct the heterogeneous neighborhood to handle the unbalanced distributions.
We conduct systematical evaluations for the proposed framework on two challenging datasets: Amazon and Alibaba.
arXiv Detail & Related papers (2020-07-19T22:50:20Z) - A general framework for defining and optimizing robustness [74.67016173858497]
We propose a rigorous and flexible framework for defining different types of robustness properties for classifiers.
Our concept is based on postulates that robustness of a classifier should be considered as a property that is independent of accuracy.
We develop a very general robustness framework that is applicable to any type of classification model.
arXiv Detail & Related papers (2020-06-19T13:24:20Z) - An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
We present a general framework for mining constraints from data.
In particular, we consider the inference in structured output prediction as an integer linear programming (ILP) problem.
We show that our approach can learn to solve 9x9 Sudoku puzzles and minimal spanning tree problems from examples without providing the underlying rules.
arXiv Detail & Related papers (2020-06-18T20:09:53Z) - Consistency of Spectral Clustering on Hierarchical Stochastic Block
Models [5.983753938303726]
We study the hierarchy of communities in real-world networks under a generic block model.
We prove the strong consistency of this method under a wide range of model parameters.
Unlike most of existing work, our theory covers multiscale networks where the connection probabilities may differ by orders of magnitude.
arXiv Detail & Related papers (2020-04-30T01:08:59Z) - Assortative-Constrained Stochastic Block Models [6.058868817939519]
Block models (SBMs) are often used to find assortative community structures in networks.
In this study, we discuss the implications of this model-inherent indifference towards assortativity or disassortativity.
We introduce a constrained SBM that imposes strong assortativity constraints, along with efficient algorithmic approaches to solve it.
arXiv Detail & Related papers (2020-04-21T19:52:59Z) - Seismic horizon detection with neural networks [62.997667081978825]
This paper is an open-sourced research of applying binary segmentation approach to the task of horizon detection on multiple real seismic cubes with a focus on inter-cube generalization of the predictive model.
The main contribution of this paper is an open-sourced research of applying binary segmentation approach to the task of horizon detection on multiple real seismic cubes with a focus on inter-cube generalization of the predictive model.
arXiv Detail & Related papers (2020-01-10T11:30:50Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.