Una propuesta de algoritmos de detección de comunidades en grafos mal condicionados

Abstract

[ES] Muchos sistemas complejos pueden ser modelados mediante grafos y redes. Existen muchos factores que deben considerarse al estudiar las propiedades de los grafos: el número de aristas representa un factor importante a considerar, ya que indica si la red está dispersa o altamente conectada; además el peso de las aristas es importante, pues es un indicador de si el grafo está mal condicionado o no. El estudio de aquellos subgrafos cuyos vértices tienen muchas conexiones entre sí con respecto a la estructura del grafo, las llamadas comunidades, son de gran interés. En algunos problemas, el estudio de las comunidades permite enfoques cuantitativos y cualitativos, y obtener conocimiento sobre la estructura del grafo y lo que representa. Existe una amplia literatura sobre el estado de las comunidades, principalmente centrada en grafos no dirigidos. En nuestro caso, enfocamos nuestro trabajo en el estudio de comunidades en grafos dirigidos, débilmente conectados y mal condicionados donde los algoritmos de detección de comunidades clásicos no son efectivos. En este documento, presentamos varias alternativas para obtener las comunidades en grafos dirigidos y proponemos un método basado en técnicas de convolución de imágenes aplicadas a grafos dirigidos que nos permiten podar aristas no significativas y estudiar el comportamiento de los diferentes procedimientos presentados.

[ES] Molts sistemes complexos es poden modelar mitjançant grafs i xarxes. Hi ha molts factors a considerar en l'estudi de les propietats dels grafs: el nombre d'arestes és un factor important a tenir en compte, ja que indica si la xarxa està dispersa o altament connectada; a més, el pes de les arestes és important, ja que indica si el graf està mal condicionat o no. L'estudi dels subgrafs on els vèrtexs tenen moltes connexions entre ells, coneguts com a comunitats, és d'un gran interès. En alguns problemes, l'estudi de les comunitats permet enfocaments quantitatius i qualitatius, i obtenir coneixement sobre l'estructura del graf i el que representa. Hi ha una àmplia literatura sobre l'estat de les comunitats, principalment centrada en grafs no dirigits. En el nostre cas, centrem el nostre treball en l'estudi de comunitats en grafs dirigits, feblement connectats i mal condicionats, on els algoritmes clàssics de detecció de comunitats no són efectius. En aquest document, presentem diverses alternatives per obtenir les comunitats en grafs dirigits i proposem un mètode basat en tècniques de convolució d'imatges aplicades a grafs dirigits. Aquesta aproximació ens permet podar arestes no significatives i estudiar el comportament dels diferents procediments presentats.

[EN] Many complex systems can be modeled by graphs and networks. Many factors must be considered when studying the properties of graphs: the number of edges in the graph represents an important factor to consider, as it indicates whether the network is dispersed or highly connected; moreover, the weight of their edges is important as it provides us an idea about whether the graph its bad-conditioned or not. The study of those subgraphs whose vertices have relatively many connections between/in themselves with respect to the graph structure, the socalled communities, is primarily interesting. In some problems, the study of communities allows quantitative and qualitative approaches and obtaining some knowledge about the structure of the graph and what it represents. There is a vast literature on the state of communities, primarily focused on undirected graphs. In our case, we focus our work on the study of communities in directed graphs that are weakly connected and poorly conditioned, where classical community detection algorithms are not effective. In this paper, we present various alternatives to obtain communities in directed graphs and propose a method based on convolution techniques applied to directed graphs. This approach allows us to prune non-significant edges and study the behavior of the different procedures presented.