A heuristic to detect community structures in dynamic complex networks

Abstract

Complex networks are ubiquitous; billions of people are connected through social networks; there is an equally large number of telecommunication users and devices generating implicit complex networks. Furthermore, several structures can be represented as complex networks in nature, genetic data, social behavior, financial transactions and many other structures. Most of these complex networks present communities in their structure. Unveiling these communities is highly relevant in many fields of study. However, depending on several factors, the discover of these communities can be computationally intensive. Several algorithms for detecting communities in complex networks have been introduced over time. We will approach some of them. Our goal in this work is to identify or create an understandable and applicable heuristic to detect communities in complex networks, with a focus on time repetitions and strength measures. This work proposes a semi-supervised clustering approach as a modification of the traditional K-means algorithm submitting each dimension of data to a weight in order to obtain a weighted clustering method. As a first case study, databases of companies that have participated in public bids in Paraná state, will be analyzed to detect communities that can suggest structures such as cartels. As a second case study, the same methodology will be used to analyze datasets of microarray data for gene expressions, representing the correlation of the genes through a complex network, applying community detection algorithms in order to witness such correlations between genes.