Communities’ detection in weakly connected directed graphs.

J. M. Montañana (HLRS), A. Hervás (UPV) and P. P. Soriano (UPV)

Many complex systems can be modeled by graphs and networks, so that the elements are represented by vertices and the relations between elements by edges. These edges can be directed if the relationships are one-way, or non-directed if they are both ways. Additionally, these edges can be assigned a numerical value that we will call the weight or capacity of the edge. The number of edges that the graph has represents another factor to take into account, as it indicates whether the network is dispersed or highly connected. The study of those subgraphs whose vertices have relatively many connections themselves respect to the graph structure, the so-called communities, is also interesting. In some problems, the study of communities allows quantitative and qualitative approaches and obtaining some knowledge about the structure of the graph.

The existing algorithms are not capable of correctly classify date into the right communities in these types of graphs when there are many noise links connecting some communities with other ones. For this reason, we seek to propose a method that allows removing those links.

Before removing the noise
After removing noise

Conference: Mathematical Modelling Conference in Engineering & Human Behaviour 2020. 8-10 July 2020. Spain.