Triadic Substructures in Complex Networks

Triadic Substructures in Complex Networks

Marco Winkler (University of Wuerzburg, Germany)
Copyright: © 2016 |Pages: 23
DOI: 10.4018/978-1-4666-9964-9.ch005
OnDemand PDF Download:


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.
Chapter Preview

In the context of local subgraph analysis, most attention has been devoted to the investigation of triadic subgraphs (Milo et al., 2002; Shen-Orr et al., 2002; Milo et al., 2004; Sporns & Kötter, 2004; Albert & Albert, 2004). Apart from node permutations, there are 13 distinct connected triad patterns in directed unweighted networks as shown in Figure 1. It was found that certain patterns of third-order subgraphs occur significantly more frequently than expected in an ensemble of networks with the same degree distributions as the original network. Over- and underrepresentation of each pattern in a graph is quantified through a Z score,

Figure 1.

All 16 possible non-isomorphic triadic subgraphs (subgraph patterns) in directed unweighted networks

Complete Chapter List

Search this Book: