Triadic Substructures in Complex Networks

Abstract

An important topological characteristic which has been studied on networks of diverse origin is the abundance of motifs – subgraph patterns which occur significantly more often than expected at random. We investigate whether motifs occur homogeneously or heterogeneously distributed over a graph. Analyzing real-world datasets, it is found that there are networks in which motifs are distributed highly heterogeneously, bound to the proximity of only very few nodes. Moreover, we study whole graphs with respect to the homogeneity and homophily of their node-specific triadic structure. The former describes the similarity of subgraphs in the neighborhoods of individual vertices. The latter quantifies whether connected vertices are structurally more similar than non-connected ones. These features are discovered to be characteristic for the networks' origins. Beyond, information on a graph's node-specific triadic structure can be used to detect groups of structurally similar vertices.