Application of the spectral bisection algorithm for the analysis of criminal communities in social networks

Abstract

Objective. The purpose of the study is to substantiate the use of one of the graph separation methods – the spectral bisection algorithm for the analysis of social networks, as well as to evaluate the possibilities of software implementation of this algorithm during the collection of evidence-based information in the investigation of crimes committed using information and telecommunications technologies.Method. The methods of scientific research used in the work include: analysis of social networks, methods based on graph decomposition algorithms, methods of data analysis from open sources, methods of linear algebra and algorithmization.Result. Taking into account the objectives of the study, the main direction of the structural analysis of the social network is justified – the definition of communities and an approach to solving the problem of community research is proposed, which involves two stages. At the first, preparatory stage, the graph of the source network is formed taking into account the intensity of connections between the participants, and at the second, the main separation of the source and obtaining the target fragment of the graph containing the most connected nodes that will correspond to the most active members of the community is performed. It is shown that the key element of the graph separation algorithm – the spectral bisection algorithm is the calculation of the Fiedler vector, which can be implemented based on the Lanczoc algorithm. A software implementation of the algorithm in the form of a Python function and using the Numpy library is also proposed. The possibilities of controlling the size of the target fragment of the source graph by means of a function parameter – the value of the weighted median are shown.Conclusions. Experimental evaluations of the algorithm showed its positive capabilities as part of a set of tools for researching social networks. The use of this solution will reduce the number of community participants being studied, focusing on the most active and closely related ones, and the inclusion of additional parameters in the software implementation of the algorithm will provide the opportunity to study the community, taking into account the intensity and nature of the interaction of participants.

Keywords

• social network analysis
• graph decomposition algorithms
• spectral bisection
• matrix processing
• numpy library