Enumeração efetiva de caminhos entre pares de nós em uma rede complexa

Abstract

This work aims to study the paths between two nodes that are each in a community and count how many effective paths exist between them. For this, initially, we introduce random networks addressing some concepts, mathematical representation, fundamental applications and some kinds of communities. Then, we made a brief review of the method of community detection based on statistical inference and a presentation on the concept of likelihood and how it is applied in such a method. We define a new concept that we call effective paths to determine the enumeration of segments in parallel between two nodes using the following process. Starting from any network, we assume that all connections are removed. After that we replace them one by one at random. Furthermore, we define a merging instant to be the number of edges that are placed before the nodes merge into the same cluster. The enumeration of effective paths determines the set of parallel segments that are most likely to produce the same distribution of merging instants. To obtain this enumeration, we use two different methods. The first method relies on finding an equation that can be used in a linear fit using general linear least squares. And the second method used was likelihood maximization algorithm with the same purpose of calculating the number of segments. Finally, we aimed to use and improve the results obtained by us in order to detect communities in networks. For that, we created artificial networks with community structures and investigated the enumeration in the case where the pairs of nodes are in the same community and in the case that they are in different communities. However, our results showed that this approach is too restricted to perfectly reproduce the distribution of merging instants. Thus, suggesting that more sophisticated models still need to be elaborated.