Robust link prediction in criminal networks: A case study of the Sicilian Mafia

Diviák T.

Data quality is considered to be among the greatest challenges in research on covert networks. This study identifies six aspects of network data collection, namely nodes, ties, attributes, levels, dynamics, and context. Addressing these aspects presents challenges, but also opens theoretical and methodological opportunities. Furthermore, specific issues arise in this research context, stemming from the use of secondary data and the problem of missing data. While each of the issues and challenges has some specific solution in the literature on organized crime and social networks, the main argument of this paper is to try and follow a more systematic and general solution to deal with these issues. To this end, three potentially synergistic and combinable techniques for data collection are proposed for each stage of data collection – biographies for data extraction, graph databases for data storage, and checklists for data reporting. The paper concludes with discussing the use of statistical models to analyse covert networks and the cultivation of relations within the research community and between researchers and practitioners.

Bouchard M.

AbstractA network approach helps us better specify and model collaboration among people involved in organized crime. The focus on collaboration raises the boundary specification problem: Where do c...

De Moor S., Vandeviver C., Vander Beken T.

• Forensic DNA data can be used to study missing data in network analysis. • Important advancement over previous studies on missing data in network analysis. • Police data on known offenders is integrated with DNA data on unknown offenders. • Unknown offenders have an impact on degree, but not on betweenness centrality. • Confirmation of importance of studying unknown offenders in social network analysis. Missing data is pertinent to criminal networks due to the hidden nature of crime. Generally, researchers evaluate the impact of incomplete network data by extracting or adding nodes and/or edges from a known network. Statistics on this reduced or completed network are then compared with statistics from the known network. In this study, we integrate police data on known offenders with DNA data on unknown offenders. Statistics from the integrated dataset (‘known network’) are compared with statistics from the police data (‘reduced network’). Networks with both known and unknown offenders are bigger but also have a different structure to networks with only known offenders.

Li C., Tang Y.

We study the problem of representation learning in heterogeneous information networks. Its unique challenges come from the existence of multiple types of vertices and edges. Existing proximity-based network embedding techniques ignore the type information when evaluating the proximity and limits their usage in heterogeneous scenario. In this paper, we propose a heterogeneous proximity preserving network embedding model via meta path guided random walk, which is capable of capturing the high-order proximity between vertices specified by the given path. To improve the learning efficiency, we introduce a sampling based learning strategy which can incrementally learn representations. We conduct experiments on two real world heterogeneous information networks. Experimental results on several mining tasks prove the effectiveness of our approach over many competitive baselines. The model is very efficient and is able to learn embeddings for large networks both in offline and online scenarios. Besides, for expert system, our approach can be applied to improve the representation of knowledge entities by depicting the knowledge base as a heterogeneous information network.

Avrachenkov K., Chebotarev P., Rubanov D.

We analytically study proximity and distance properties of various kernels and similarity measures on graphs. This helps to understand the mathematical nature of such measures and can potentially be useful for recommending the adoption of specific similarity measures in data analysis.

Pandey B., Bhanodia P.K., Khamparia A., Pandey D.K.

Recent development in the area of social networks has sought attention of the researchers to crunch and analyse the data and information of the users to retrieve relevant knowledge for further predictions and recommendations. Edge prediction is one such instance of social network analysis problem exploiting the prevailing data and information pertaining to the network such as: the attributes of the nodes and edges connecting the nodes in order to predict relationships potentially likely to exist in near future. Edge prediction has various applications in significant areas such as: knowledge mining, business recommendation systems, expert systems and bio informatics. In this work, we have classified the edge prediction problem in social network from five aspects: type of SN, feature used for edge prediction, edge prediction method, solution to edge prediction problem and performance measure. The strength of this article is the categorical review of the edge prediction methods in way to draw specific research problems to address further such as: complexity, accuracy, computational overhead and cost, scalability, generalization and performance issues. In addition to this, we have also provided an insightful of edge prediction method applied across various social network categories to understand the advantages and disadvantages to derive future work. The experimental exercise on real world social network particularly Face-book exhibits that the computation time taken in processing large network could be improved significantly may be through distributed techniques or so as the performance of edge prediction methods degrades with the scalability of the social networks. We did not focused upon any appropriate edge prediction methodology as it is out of the scope of the paper because we have exclusively reviewed the existing work done and we are exploring an appropriate ensemble method to precisely predict the future edges between nodes.

Calderoni F., Superchi E.

Criminal leaders enhance their social capital by strategically brokering information among associates. To balance security and efficiency, leaders may favor meetings instead of telephones, potentially affecting analyses relying solely on wiretap data. Yet, few studies explored criminal leaders’ use of meetings in the management of criminal groups. We analyze criminal leaders’ participation in meetings and telephone calls in four distinct investigations. For each case, we extracted meetings and wiretap networks, analyzed leaders’ network positioning and identified leadership roles through logistic regressions relying on network centrality. Results show that leaders minimize telephone use (20% missing in wiretap net-works), and act as brokers, particularly in meeting networks (betweenness 18 times higher than non-leaders). Regressions on meeting networks identify leaders more effectively than wiretap networks, with betweenness centrality as the strongest predictor of leadership. Leaders’ centrality in meetings shows their strategic brokering position and the social embeddedness of criminal groups. While meeting participation is a sign of power, it is also a social obligation that leaders can hardly minimize. This makes them more visible, with possible benefits to investigations and intelligence.

Duxbury S.W., Haynie D.L.

Criminal networks are frequently at risk of disruption through arrest and interorganizational violence. Difficulties in designing empirical studies of criminal network recovery, however, have problematized research into network responses to disruption. In this study, we evaluate criminal network resilience by examining network recovery from disruption in an array of different criminal networks and across different disruption strategies. We use an agent-based model to evaluate how criminal networks recover from disruption. Our results reveal the vulnerabilities and time to recovery of numerous criminal organizations, and through them, we identify which disruption strategies are most effective at damaging various criminal networks.

Lim M., Abdullah A., Jhanjhi N., Supramaniam M.

Criminal network activities, which are usually secret and stealthy, present certain difficulties in conducting criminal network analysis (CNA) because of the lack of complete datasets. The collection of criminal activities data in these networks tends to be incomplete and inconsistent, which is reflected structurally in the criminal network in the form of missing nodes (actors) and links (relationships). Criminal networks are commonly analyzed using social network analysis (SNA) models. Most machine learning techniques that rely on the metrics of SNA models in the development of hidden or missing link prediction models utilize supervised learning. However, supervised learning usually requires the availability of a large dataset to train the link prediction model in order to achieve an optimum performance level. Therefore, this research is conducted to explore the application of deep reinforcement learning (DRL) in developing a criminal network hidden links prediction model from the reconstruction of a corrupted criminal network dataset. The experiment conducted on the model indicates that the dataset generated by the DRL model through self-play or self-simulation can be used to train the link prediction model. The DRL link prediction model exhibits a better performance than a conventional supervised machine learning technique, such as the gradient boosting machine (GBM) trained with a relatively smaller domain dataset.

Grassi R., Calderoni F., Bianchi M., Torriero A.

Brokerage is crucial for dark networks. In analyzing communications among criminals, which naturally induce bipartite networks, previous studies have focused on the classic Freeman's betweenness, conceived for one-mode matrices and possibly biasing the results. We explore different betweenness centrality including three inspired by the dual projection approach recently suggested by Everett and Borgatti 2013. We test these measures in identifying criminal leaders in a meeting participation network. Despite the expected high correlations among them, the measures yield different node rankings, capturing different characteristics of brokerage. Overall, the dual projection approaches show higher success than classic approaches in identifying the criminal leaders.

Parisi F., Caldarelli G., Squartini T.

Link-prediction is an active research field within network theory, aiming at uncovering missing connections or predicting the emergence of future relationships from the observed network structure. This paper represents our contribution to the stream of research concerning missing links prediction. Here, we propose an entropy-based method to predict a given percentage of missing links, by identifying them with the most probable non-observed ones. The probability coefficients are computed by solving opportunely defined null-models over the accessible network structure. Upon comparing our likelihood-based, local method with the most popular algorithms over a set of economic, financial and food networks, we find ours to perform best, as pointed out by a number of statistical indicators (e.g. the precision, the area under the ROC curve, etc.). Moreover, the entropy-based formalism adopted in the present paper allows us to straightforwardly extend the link-prediction exercise to directed networks as well, thus overcoming one of the main limitations of current algorithms. The higher accuracy achievable by employing these methods - together with their larger flexibility - makes them strong competitors of available link-prediction algorithms.

Fan C., Liu Z., Lu X., Xiu B., Chen Q.

Quality of information is crucial for decision-makers to judge the battlefield situations and design the best operation plans, however, real intelligence data are often incomplete and noisy, where missing links prediction methods and spurious links identification algorithms can be applied, if modeling the complex military organization as the complex network where nodes represent functional units and edges denote communication links. Traditional link prediction methods usually work well on homogeneous networks, but few for the heterogeneous ones. And the military network is a typical heterogeneous network, where there are different types of nodes and edges. In this paper, we proposed a combined link prediction index considering both the nodes’ types effects and nodes’ structural similarities, and demonstrated that it is remarkably superior to all the 25 existing similarity-based methods both in predicting missing links and identifying spurious links in a real military network data; we also investigated the algorithms’ robustness under noisy environment, and found the mistaken information is more misleading than incomplete information in military areas, which is different from that in recommendation systems, and our method maintained the best performance under the condition of small noise. Since the real military network intelligence must be carefully checked at first due to its significance, and link prediction methods are just adopted to purify the network with the left latent noise, the method proposed here is applicable in real situations. In the end, as the FINC-E model, here used to describe the complex military organizations, is also suitable to many other social organizations, such as criminal networks, business organizations, etc., thus our method has its prospects in these areas for many tasks, like detecting the underground relationships between terrorists, predicting the potential business markets for decision-makers, and so on.

Calderoni F., Brunetto D., Piccardi C.

Criminal organizations tend to be clustered to reduce risks of detection and information leaks. Yet, the literature exploring the relevance of subgroups for their internal structure is so far very limited. The paper applies methods of community analysis to explore the structure of a criminal network representing the individuals’ co-participation in meetings. It draws from a case study on a large law enforcement operation (“Operazione Infinito”) tackling the ‘Ndrangheta, a mafia organization from Calabria, a southern Italian region. The results show that the network is indeed clustered and that communities are associated, in a non-trivial way, with the internal organization of the ‘Ndrangheta into different “locali” (similar to mafia families). Furthermore, the results of community analysis can improve the prediction of the “locale” membership of the criminals (up to two thirds of any random sample of nodes) and the leadership roles (above 90% precision in classifying nodes as either bosses or non-bosses). The implications of these findings on the interpretation of the structure and functioning of the criminal network are discussed.

Hric D., Peixoto T.P., Fortunato S.

The empirical validation of community detection methods is often based on available annotations on the nodes that serve as putative indicators of the large-scale network structure. Most often, the suitability of the annotations as topological descriptors itself is not assessed, and without this it is not possible to ultimately distinguish between actual shortcomings of the community detection algorithms on one hand, and the incompleteness, inaccuracy or structured nature of the data annotations themselves on the other. In this work we present a principled method to access both aspects simultaneously. We construct a joint generative model for the data and metadata, and a nonparametric Bayesian framework to infer its parameters from annotated datasets. We assess the quality of the metadata not according to its direct alignment with the network communities, but rather in its capacity to predict the placement of edges in the network. We also show how this feature can be used to predict the connections to missing nodes when only the metadata is available, as well as missing metadata. By investigating a wide range of datasets, we show that while there are seldom exact agreements between metadata tokens and the inferred data groups, the metadata is often informative of the network structure nevertheless, and can improve the prediction of missing nodes. This shows that the method uncovers meaningful patterns in both the data and metadata, without requiring or expecting a perfect agreement between the two.

Agreste S., Catanese S., De Meo P., Ferrara E., Fiumara G.

In this paper we present the results of the study of Sicilian Mafia organization by using Social Network Analysis. The study investigates the network structure of a Mafia organization, describing its evolution and highlighting its plasticity to interventions targeting membership and its resilience to disruption caused by police operations. We analyze two different datasets about Mafia gangs built by examining different digital trails and judicial documents spanning a period of ten years: the former dataset includes the phone contacts among suspected individuals, the latter is constituted by the relationships among individuals actively involved in various criminal offenses. Our report illustrates the limits of traditional investigation methods like tapping: criminals high up in the organization hierarchy do not occupy the most central positions in the criminal network, and oftentimes do not appear in the reconstructed criminal network at all. However, we also suggest possible strategies of intervention, as we show that although criminal networks (i.e., the network encoding mobsters and crime relationships) are extremely resilient to different kind of attacks, contact networks (i.e., the network reporting suspects and reciprocated phone calls) are much more vulnerable and their analysis can yield extremely valuable insights.

Lu C., Durante D., Friel N.

Abstract Criminal networks arise from the attempt to balance a need of establishing frequent ties among affiliates to facilitate coordination of illegal activities, with the necessity to sparsify the overall connectivity architecture to hide from law enforcement. This efficiency-security trade-off is also combined with the creation of groups of redundant criminals that exhibit similar connectivity patterns, thus guaranteeing resilient network architectures. State-of-the-art models for such data are not designed to infer these unique structures. In contrast to such solutions, we develop a tractable Bayesian zero-inflated Poisson stochastic block model (ZIP–SBM), which identifies groups of redundant criminals having similar connectivity patterns, and infers both overt and covert block interactions within and across these groups. This is accomplished by modelling the weighted ties (corresponding to counts of interactions among pairs of criminals) via zero-inflated Poisson distributions with block-specific parameters that quantify complex patterns in the excess of zero ties in each block (security) relative to the distribution of the observed weighted ties within that block (efficiency). The performance of ZIP–SBM is illustrated in simulations and in a study of summit co-attendances in a complex Mafia organization, where we unveil efficiency-security structures adopted by the criminal organization that were hidden to previous analyses.

Zhou L., Liao H., Tan F., Chen Z.

Chaudhary N., Kaur G., Nanwal J.

Wang R., Cheung C.F., Wang C.

Chen K., Zhang T., Zhao Y., Qian T.

The exponential expansion of information has made text feature extraction based on simple semantic information insufficient for the multidimensional recognition of textual data. In this study, we construct a text semantic structure graph based on various perspectives and introduce weight coefficients and node clustering coefficients of co-occurrence granularity to enhance the link prediction model, in order to comprehensively capture the structural information of the text. Firstly, we jointly build the semantic structure graph based on three proposed perspectives (i.e., scene semantics, text weight, and graph structure), and propose a candidate keyword set in conjunction with an information probability retrieval model. Subsequently, we propose weight coefficients of co-occurrence granularity and node clustering coefficients to improve the link prediction model based on the semantic structure graph, enabling a more comprehensive acquisition of textual structural information. Experimental results demonstrate that our research method can reveal potential correlations and obtain more complete semantic structure information, while the WPAA evaluation index validates the effectiveness of our model.

Liu S., Feng X., Yang J.

Random walk-based link prediction algorithms have achieved desirable results for complex network mining, but in these algorithms, the transition probability of particles usually only considers node degrees, resulting in particles being able to randomly select adjacent nodes for random walks in an equal probability manner, to solve this problem, the asymmetric influence-based superposed random walk link prediction algorithm is proposed in this paper. This algorithm encourages particles to choose the next node at each step of the random walk process based on the asymmetric influence between nodes. To this end, we fully consider the topological information around each node and propose the asymmetric influence between nodes. Then, an adjustable parameter is applied to normalize the degree of nodes and the asymmetric influence between nodes into transition probability. Based on this, the proposed new transition probability is applied to superposed random walk process to measure the similarity between all nodes in the network. Empirical experiments are conducted on 16 real-world network datasets such as social network, ecology network, and animal network. The experimental results show that the proposed algorithm has high prediction accuracy in most network, compared with 10 benchmark indices.

Wang Z., Chai Y., Sun C., Rui X., Mi H., Zhang X., Yu P.S.

Link prediction is an important task in social network analysis and mining because of its various applications. A large number of link prediction methods have been proposed. Among them, the deep learning-based embedding methods exhibit excellent performance, which encodes each node and edge as an embedding vector, enabling easy integration with traditional machine learning algorithms. However, there still remain some unsolved problems for this kind of methods, especially in the steps of node embedding and edge embedding. First, they either share exactly the same weight among all neighbors or assign a completely different weight to each node to obtain the node embedding. Second, they can hardly keep the symmetry of edge embeddings obtained from node representations by direct concatenation or other binary operations such as averaging and Hadamard product. In order to solve these problems, we propose a weighted symmetric graph embedding approach for link prediction. In node embedding, the proposed approach aggregates neighbors in different orders with different aggregating weights. In edge embedding, the proposed approach bidirectionally concatenates node pairs both forwardly and backwardly to guarantee the symmetry of edge representations while preserving local structural information. The experimental results show that our proposed approach can better predict network links, outperforming the state-of-the-art methods. The appropriate aggregating weight assignment and the bidirectional concatenation enable us to learn more accurate and symmetric edge representations for link prediction.

Ding H., Wei L., Li F., Hu F., Li P., Chen J.

Jhee J.H., Kim M.J., Park M., Yeon J., Shin H.

One of the interesting characteristics of crime data is that criminal cases are often interrelated. Criminal acts may be similar, and similar incidents may occur consecutively by the same offender or by the same criminal group. Among many machine learning algorithms, network-based approaches are well-suited to reflect these associative characteristics. Applying machine learning to criminal networks composed of cases and their associates can predict potential suspects. This narrows the scope of an investigation, saving time and cost. However, inference from criminal networks is not straightforward as it requires being able to process complex information entangled with case-to-case, person-to-person, and case-to-person connections. Besides, being useful at a crime scene requires urgency. However, predictions from network-based machine learning algorithms are generally slow when the data is large and complex in structure. These limitations are an immediate barrier to any practical use of the criminal network geared by machine learning. In this study, we propose a criminal network-based suspect prediction framework. The network we designed has a unique structure, such as a sandwich panel, in which one side is a network of crime cases and the other side is a network of people such as victims, criminals, and witnesses. The two networks are connected by relationships between the case and the persons involved in the case. The proposed method is then further developed into a fast inference algorithm for large-scale criminal networks. Experiments on benchmark data showed that the fast inference algorithm significantly reduced execution time while still being competitive in performance comparisons of the original algorithm and other existing approaches. Based on actual crime data provided by the Korean National Police, several examples of how the proposed method is applied are shown.

Spelta A., Pecora N.

Abstract We propose a flexible link forecast methodology for weighted temporal networks. Our probabilistic model estimates the evolving link dynamics among a set of nodes through Wasserstein barycentric coordinates arising within the optimal transport theory. Optimal transport theory is employed to interpolate among network evolution sequences and to compute the probability distribution of forthcoming links. Besides generating point link forecasts for weighted networks, the methodology provides the probability that a link attains weights in a certain interval, namely a quantile of the weights distribution. We test our approach to forecast the link dynamics of the worldwide Foreign Direct Investments network and of the World Trade Network, comparing the performance of the proposed methodology against several alternative models. The performance is evaluated by applying non-parametric diagnostics derived from binary classifications and error measures for regression models. We find that the optimal transport framework outperforms all the competing models when considering quantile forecast. On the other hand, for point forecast, our methodology produces accurate results that are comparable with the best performing alternative model. Results also highlight the role played by model constraints in the determination of future links emphasising that weights are better predicted when accounting for geographical rather than economic distance.

Algaba E., Prieto A., Saavedra‐Nieves A.

AbstractThis article introduces the Banzhaf and the Banzhaf–Owen values as novel measures of risk analysis of a terrorist attack, determining the most dangerous terrorists in a network. This new approach counts with the advantage of integrating at the same time the complete topology (i.e., nodes and edges) of the network and a coalitional structure on the nodes of the network. More precisely, the characteristics of the nodes (e.g., terrorists) of the network and their possible relationships (e.g., types of communication links), as well as coalitional information (e.g., level of hierarchies) independent of the network. First, for these two new measures of risk analysis, we provide and implement approximation algorithms. Second, as illustration, we rank the members of the Zerkani network, responsible for the attacks in Paris (2015) and Brussels (2016). Finally, we give a comparison between the rankings established by the Banzhaf and the Banzhaf–Owen values as measures of risk analysis.

Ficara A., Curreri F., Fiumara G., De Meo P.

B D.P., Johnson T.P., Balakrishnan K.

Yu J., Wu M., Bichler G., Aros-Vera F., Gao J.

Network structure provides critical information for understanding the dynamic behavior of complex systems. However, the complete structure of real-world networks is often unavailable, thus it is crucially important to develop approaches to infer a more complete structure of networks. In this paper, we integrate the configuration model for generating random networks into an Expectation–Maximization–Aggregation (EMA) framework to reconstruct the complete structure of multiplex networks. We validate the proposed EMA framework against the Expectation–Maximization (EM) framework and random model on several real-world multiplex networks, including both covert and overt ones. It is found that the EMA framework generally achieves the best predictive accuracy compared to the EM framework and the random model. As the number of layers increases, the performance improvement of EMA over EM decreases. The inferred multiplex networks can be leveraged to inform the decision-making on monitoring covert networks as well as allocating limited resources for collecting additional information to improve reconstruction accuracy. For law enforcement agencies, the inferred complete network structure can be used to develop more effective strategies for covert network interdiction.

Ficara A., Fiumara G., De Meo P., Catanese S.

Random walks simulate the randomness of objects, and are key instruments in various fields such as computer science, biology and physics. The counter part of classical random walks in quantum mechanics are the quantum walks. Quantum walk algorithms provide an exponential speedup over classical algorithms. Classical and quantum random walks can be applied in social network analysis, and can be used to define specific centrality metrics in terms of node occupation on single-layer and multilayer networks. In this paper, we applied these new centrality measures to three real criminal networks derived from an anti-mafia operation named Montagna and a multilayer network derived from them. Our aim is to (i) identify leaders in our criminal networks, (ii) study the dependence between these centralities and the degree, (iii) compare the results obtained for the real multilayer criminal network with those of a synthetic multilayer network which replicates its structure.