On the sensitivity of centrality metrics.

Despite the huge importance that the centrality metrics have in understanding the topology of a network, too little is known about the effects that small alterations in the topology of the input graph induce in the norm of the vector that stores the node centralities. If so, then it could be possible to avoid re-calculating the vector of centrality metrics if some minimal changes occur in the network topology, which would allow for significant computational savings. Hence, after formalising the notion of centrality, three of the most basic metrics were herein considered (i.e., Degree, Eigenvector, and Katz centrality). To perform the simulations, two probabilistic failure models were used to describe alterations in network topology: Uniform (i.e., all nodes can be independently deleted from the network with a fixed probability) and Best Connected (i.e., the probability a node is removed depends on its degree). Our analysis suggests that, in the case of degree, small variations in the topology of the input graph determine small variations in Degree centrality, independently of the topological features of the input graph; conversely, both Eigenvector and Katz centralities can be extremely sensitive to changes in the topology of the input graph. In other words, if the input graph has some specific features, even small changes in the topology of the input graph can have catastrophic effects on the Eigenvector or Katz centrality.

Criminal networks analysis in missing data scenarios through graph distances.

Data collected in criminal investigations may suffer from issues like: (i) incompleteness, due to the covert nature of criminal organizations; (ii) incorrectness, caused by either unintentional data collection errors or intentional deception by criminals; (iii) inconsistency, when the same information is collected into law enforcement databases multiple times, or in different formats. In this paper we analyze nine real criminal networks of different nature (i.e., Mafia networks, criminal street gangs and terrorist organizations) in order to quantify the impact of incomplete data, and to determine which network type is most affected by it. The networks are firstly pruned using two specific methods: (i) random edge removal, simulating the scenario in which the Law Enforcement Agencies fail to intercept some calls, or to spot sporadic meetings among suspects; (ii) node removal, modeling the situation in which some suspects cannot be intercepted or investigated. Finally we compute spectral distances (i.e., Adjacency, Laplacian and normalized Laplacian Spectral Distances) and matrix distances (i.e., Root Euclidean Distance) between the complete and pruned networks, which we compare using statistical analysis. Our investigation identifies two main features: first, the overall understanding of the criminal networks remains high even with incomplete data on criminal interactions (i.e., when 10% of edges are removed); second, removing even a small fraction of suspects not investigated (i.e., 2% of nodes are removed) may lead to significant misinterpretation of the overall network.

Disrupting resilient criminal networks through data analysis: The case of Sicilian Mafia.

Compared to other types of social networks, criminal networks present particularly hard challenges, due to their strong resilience to disruption, which poses severe hurdles to Law-Enforcement Agencies (LEAs). Herein, we borrow methods and tools from Social Network Analysis (SNA) to (i) unveil the structure and organization of Sicilian Mafia gangs, based on two real-world datasets, and (ii) gain insights as to how to efficiently reduce the Largest Connected Component (LCC) of two networks derived from them. Mafia networks have peculiar features in terms of the links distribution and strength, which makes them very different from other social networks, and extremely robust to exogenous perturbations. Analysts also face difficulties 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 extracted 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 analysis simulated different intervention procedures: (i) arresting one criminal at a time (sequential node removal); and (ii) police raids (node block removal). In both the sequential, and the node block removal intervention procedures, the Betweenness centrality was the most effective strategy in prioritizing the nodes to be removed. For instance, when targeting the top 5% nodes with the largest Betweenness centrality, our simulations suggest a reduction of up to 70% in the size of the LCC. 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 perturbing the operations of criminal and terrorist networks.

Estimating Graph Robustness Through the Randic Index.

Graph robustness-the ability of a graph to preserve its connectivity after the loss of nodes and edges-has been extensively studied to quantify how social, biological, physical, and technical systems withstand to external damages. In this paper, we prove that graph robustness can be quickly estimated through the Randic index, a parameter introduced in chemistry to study organic compounds. We prove that Erdos-Renyj (ER) graphs are a good specimen of robust graphs because they lack of a clear modular structure; we derive an analytical expression for the Randic index of ER graphs and use ER graphs as an effective term of comparison to decide about graph robustness. Experiments on real datasets from different domains (scientific collaboration networks, content-sharing systems, co-purchase networks from an e-commerce platform, and a road network) show that real-life large graphs are more robust than ER ones with the same number of nodes and edges. We also observe that if node degree distribution closely follows a power law, then few edges contribute for more than half of the Randic index, thus indicating that the selective removal of those edges has devastating impact on graph robustness. Finally, we describe sampling-based algorithms to efficiently but accurately approximate the Randic index.

Trust and compactness in social network groups.

Understanding the dynamics behind group formation and evolution in social networks is considered an instrumental milestone to better describe how individuals gather and form communities, how they enjoy and share the platform contents, how they are driven by their preferences/tastes, and how their behaviors are influenced by peers. In this context, the notion of compactness of a social group is particularly relevant. While the literature usually refers to compactness as a measure to merely determine how much members of a group are similar among each other, we argue that the mutual trustworthiness between the members should be considered as an important factor in defining such a term. In fact, trust has profound effects on the dynamics of group formation and their evolution: individuals are more likely to join with and stay in a group if they can trust other group members. In this paper, we propose a quantitative measure of group compactness that takes into account both the similarity and the trustworthiness among users, and we present an algorithm to optimize such a measure. We provide empirical results, obtained from the real social networks EPINIONS and CIAO, that compare our notion of compactness versus the traditional notion of user similarity, clearly proving the advantages of our approach.