The role of clustering in the stucture and function of complex networks

Abstract

The study of a system from a network perspective focuses on the impact that connectivity between the elements has on the function of the system. The observation and measurement of parameters of real-world networks reveals that these systems have highly complex structures that differ from those of lattices and random graphs, and which have striking effects on their behaviour. Moreover, some common topological properties shared by networks with completely different natures have been found. This suggests the existence of common fundamental principles that determine the structure and evolution of networks.

One of the most common features of real networks is the high presence of triangles or strong clustering. However, in contrast to other topological properties of real networks, little was known about the emergence of clustering and its effect on network structure and function. The reason for this was twofold. First of all, the mere presence of triangles in networks contradicts assumptions that are used almost across the board in mathematical tools that are applied in network theory, and therefore it hinders any analytical treatment. Second, there was a lack of appropriate clustered network models that allow empirical study. Therefore, clustering was the main factor that thwarted the possibility of applying network theories to real situations and became one of the most important challenges facing network science.

In this thesis we studied the role played by clustering in the structure and function of complex networks. In this direction, we first analyse the clustering generated by one of the most popular random network model: the configuration model. Our results show that, contrary to common believes strong heterogeneity can be enough to generate moderate levels of clustering.

Then, we studied the distribution of triangles within real networks. Interestingly enough, real networks tend to be closer to maximally random clustered graphs, although clear differences are evident. This fact have an impact on the study of clustering on network processes since it casts doubt on previous results derived from clustered network models in which triangles were organized in a very specific way.

Finally, we focus on the effect of clustering on the classical bond percolation problem. Our choice was based on the direct relation that this simple process has with robustness and epidemics dynamics of networks. Our results show that clustering makes weakly heterogeneous networks more fragile to random failure of their connections and less prone to spread infected agents. However, clustering in strongly heterogeneous networks can induce a core-periphery organization in which the core and periphery percolates independently. This phenomenon, namely a multiple percolation transition, has not been observed before. In this situation clustering makes the core more robust and the periphery more fragile.

Furthermore, I analytically prove that such multiple percolation transitions are possible in networks that are sufficiently weakly connected. This new scenario has very important implications for different aspects of the analysis of the percolation properties of complex networks. On the one hand, the existence of multiple critical points changes the way we need to address percolation as a critical phenomenon. We should not develop theories to find the true and unique percolation threshold, but to reveal the set of critical points and the nodes involved in each one of them. On the other hand, this new phenomenon implies that previous empirical methods for finding the percolation threshold are obsolete. The obvious incapacity to perform finite size scaling in a real finite system, together with the existence of multiple transitions, implies that no existent empirical method can be used to measure percolation thresholds.

La teoria de xarxes és útil per concentrar-se en l'impacte que els patrons de interacció entre elements tenen en la funció de sistemes. La mesura i observació de xarxes reals revela que aquests aquestes tenen unes estructures complexes amb un efecte molt important en el seu comportament. Aquest fet suggereix l'existència de patrons de formació comuns que determinen l'estructura i evolució de les xarxes.

Una de les propietats més comunes de les xarxes reals és l'alta presència de triangles o fort clustering. Al contrari que altres propietats topològiques, encara es desconeix l'origen de l'emergència del clustering i el seu efecte en l'estructura i funció del sistema. En primer lloc, això és degut a que la simple presència de triangles contradiu una hipòtesi molt utilitzada en la teoria de xarxes, complicant qualsevol possibilitat de un tractament analític. En segon lloc, hi ha un manca de models de xarxes amb clustering apropiats que permetin un estudi empíric. Per tant, el clustering és un dels factors més importants que dificulta la possibilitat d'aplicar els resultats de la teoria de xarxes a casos reals.

En aquesta direcció en aquesta tesi comencem estudiant el clustering generat pels models de xarxes més populars. Seguidament mirem com es distribueixen els triangles en les xarxes reals. Finalment ens concentrem en l'efecte del clustering en el clàssic problema de percolació. La nostra tria es basa en la relació que aquest procés simple té amb la robustesa i la dinàmica d'epidèmies en xarxes.

Anteriors estudis sobre les propietats de percolació de xarxes amb clustering són només vàlids per una estructura específica la qual mostrem que no reprodueix la organització global dels triangles present en les xarxes reals. Per tant, per respondre aquesta pregunta hem hagut de primer desenvolupar un model de xarxa amb clustering que reprodueixi la organització dels triangles de les xarxes reals. Finalment hem fet servir el nostre model per estudiar com el clustering efecte a la posició del llindar de percolació en xarxes complexes.