Search

The role of an actor in a social network is identified through a set of measures called centrality. Degree centrality, betweenness centrality, closeness centrality, and clustering coefficient are the most frequently used metrics to compute the node centrality. Their computational complexity in some cases makes unfeasible, when not practically impossible, their computations. For this reason, we focused on two alternative measures, WERW-Kpath and Game of Thieves, which are at the same time highly descriptive and computationally affordable. Our experiments show that a strong correlation exists between WERW-Kpath and Game of Thieves and the classical centrality measures. This may suggest the possibility of using them as useful and more economic replacements of the classical centrality measures.

Social Network Analysis (SNA) is used to study the exchange of resources among individuals, groups, or organizations. The role of individuals or connections in a network is described by a set of centrality metrics which represent one of the most important results of SNA. Degree, closeness, betweenness and clustering coefficient are the most used centrality measures. Their use is, however, severely hampered by their computation cost. This issue can be overcome by an algorithm called Game of Thieves (GoT). Thanks to this new algorithm, we can compute the importance of all elements in a network (i.e. vertices and edges), compared to the total number of vertices. This calculation is done not in a quadratic time, as when we use the classical methods, but in polylogarithmic time. Starting from this we present our results on the correlation existing between GoT and the most widely used centrality measures. From our experiments emerge that a strong correlation exists, which makes GoT eligible as a centrality measure for large scale complex networks.

Compared to other types of social networks, criminal networks present hard challenges, due to their strong resilience to disruption, which poses severe hurdles to law-enforcement agencies. Herein, we borrow methods and tools from Social Network Analysis to (i) unveil the structure of Sicilian Mafia gangs, based on two real-world datasets, and (ii) gain insights as to how to efficiently disrupt them. Mafia networks have peculiar features, due to the links distribution and strength, which makes them very different from other social networks, and extremely robust to exogenous perturbations. Analysts are also faced with the difficulty in collecting reliable datasets that accurately describe the gangs' internal structure and their relationships with the external world, which is why earlier studies are largely qualitative, elusive and incomplete. An added value of our work is the generation of two real-world datasets, based on raw data derived from juridical acts, relating to a Mafia organization that operated in Sicily during the first decade of 2000s. We created two different networks, capturing phone calls and physical meetings, respectively. Our network disruption analysis simulated different intervention procedures: (i) arresting one criminal at a time (sequential node removal); and (ii) police raids (node block removal). We measured the effectiveness of each approach through a number of network centrality metrics. We found Betweeness Centrality to be the most effective metric, showing how, by neutralizing only the 5% of the affiliates, network connectivity dropped by 70%. We also identified that, due the peculiar type of interactions in criminal networks (namely, the distribution of the interactions frequency) no significant differences exist between weighted and unweighted network analysis. Our work has significant practical applications for tackling criminal and terrorist networks., 12 pages, 4 figures, paper submitted to PLOS ONE Journal

In this paper, we focus on the study of Sicilian Mafia organizations through Social Network Analysis. We analyse datasets reflecting two different Mafia Families, based on examinations of digital trails and judicial documents, respectively. The first dataset includes the phone calls logs among suspected individuals. The second one is based on police traces of meeting that have taken place among different types of criminals. Our breakthrough is twofold. First in the method followed to generate these new datasets. Second, in the method used to carry out a quantitative phenomena investigation that are hard to evaluate. Our networks are weighted ones, with each weight catching the frequency of interactions between criminals. Therefore, our analysis focuses on weight and shortest paths distributions in both networks. We identify new types of unusual interactions in the Mafia networks, leading to substantial differences between Mafia networks and other types of criminal or terrorist networks.

Link prediction exercises may prove particularly challenging with noisy and incomplete networks, such as criminal networks. Also, the link prediction effectiveness may vary across different relations within a social group. We address these issues by assessing the performance of different link prediction algorithms on a mafia organization. The analysis relies on an original dataset manually extracted from the judicial documents of operation “Montagna”, conducted by the Italian law enforcement agencies against individuals affiliated with the Sicilian Mafia. To run our analysis, we extracted two networks: one including meetings and one recording telephone calls among suspects, respectively. We conducted two experiments on these networks. First, we applied several link prediction algorithms and observed that link prediction algorithms leveraging the full graph topology (such as the Katz score) provide very accurate results even on very sparse networks. Second, we carried out extensive simulations to investigate how the noisy and incomplete nature of criminal networks may affect the accuracy of link prediction algorithms. The experimental findings suggest the soundness of link predictions is relatively high provided that only a limited amount of knowledge about connections is hidden or missing, and the unobserved edges follow some kind of generative law. The different results on the meeting and telephone call networks indicate that the specific features of a network should be taken into careful consideration.

Detecting communities in graphs is a fundamental tool to understand the structure of Web-based systems and predict their evolution. Many community detection algorithms are designed to process undirected graphs (i.e., graphs with bidirectional edges) but many graphs on the Web-e.g., microblogging Web sites, trust networks or the Web graph itself-are often directed . Few community detection algorithms deal with directed graphs but we lack their experimental comparison. In this paper we evaluated some community detection algorithms across accuracy and scalability. A first group of algorithms (Label Propagation and Infomap) are explicitly designed to manage directed graphs while a second group (e.g., WalkTrap) simply ignores edge directionality; finally, a third group of algorithms (e.g., Eigenvector) maps input graphs onto undirected ones and extracts communities from the symmetrized version of the input graph. We ran our tests on both artificial and real graphs and, on artificial graphs, WalkTrap achieved the highest accuracy, closely followed by other algorithms; Label Propagation has outstanding performance in scalability on both artificial and real graphs. The Infomap algorithm showcased the best trade-off between accuracy and computational performance and, therefore, it has to be considered as a promising tool for Web Data Analytics purposes.