Subgraphs:loops and cliques in complex networks

How do complex networks look like locally? What is the interplay between large-scale properties of networks and their local structure?

After ten years of research on complex network structure we have learned how to characterize locally the networks with a large set of quantities as their clustering coefficient, their degree-degree correlations and their motifs. Nevertheless still we lack further understanding of their modular structure and their topology.

I found these questions extremely fascinating and I have contributed to the discussion on these topic with several papers addressing especially the local loop structure and clique structure of networks.

Scale-free networks have a special local loop structure, allowing for many more small loops than random networks. (Note however that usually the tree like assumption for solving critical phenomena on network is justified since the clustering coefficient is small). Moreover we have shown that the number of cliques in scale-free networks is much higher than in Poisson random graphs, actually we can prove that the maximal clique size, in scale-free networks, grows with the system size also if the average degree of the network is constant. These results can be found also in real networks, the prototypical case being the Internet at different time scale.

Finally in a paper in collaboration with N. Gulbahce and A. E. Motter we have formulated a criterion, based on spectral properties of the networks, able to assess if a real networks has a number of loops that is overrepresented or underrepresented respect to the random hypothesis. We studied in particular directed networks finding that many directed networks are undershortlooped, i.e. they have less short loops that in a random hypothesis. This is in contrast with the general tendency of undirected networks to have large clustering and high density of small loops.

Selected publications