On the Role of Triadic Substructures in Complex Networks
arXiv:1606.03989
Abstract
In the course of the growth of the Internet and due to increasing availability of data, over the last two decades, the field of network science has established itself as an own area of research. With quantitative scientists from computer science, mathematics, and physics working on datasets from biology, economics, sociology, political sciences, and many others, network science serves as a paradigm for interdisciplinary research. One of the major goals in network science is to unravel the relationship between topological graph structure and a network's function. As evidence suggests, systems from the same fields, i.e. with similar function, tend to exhibit similar structure. However, it is still vague whether a similar graph structure automatically implies likewise function. This dissertation aims at helping to bridge this gap, while particularly focusing on the role of triadic structures. After a general introduction to the main concepts of network science, existing work devoted to the relevance of triadic substructures is reviewed. A major challenge in modeling such structure is the fact that not all three-node subgraphs can be specified independently of each other, as pairs of nodes may participate in multiple triadic subgraphs. In order to overcome this obstacle, a novel class of generative network models based on pair-disjoint triadic building blocks is suggested. It is further investigated whether triad motifs - subgraph patterns which appear significantly more frequently than expected at random - occur homogeneously or heterogeneously distributed over graphs. Finally, the influence of triadic substructure on the evolution of dynamical processes acting on their nodes is studied. It is observed that certain motifs impose clear signatures on the systems' dynamics, even when embedded in a larger network structure.
arXiv comment195 pages, dissertation
References in corpus (38)
- Understanding individual human mobility patterns
- Lethality and centrality in protein networks
- The structure of scientific collaboration networks
- The diameter of the world wide web
- The architecture of complex weighted networks
- Random graphs with arbitrary degree distributions and their applications
- Classes of behavior of small-world networks
- Link Prediction in Complex Networks: A Survey
- Hierarchical structure and the prediction of missing links in networks
- Stochastic blockmodels and community structure in networks
- Growing Scale-Free Networks with Tunable Clustering
- The complex network of global cargo ship movements
- Structural Properties of the Caenorhabditis elegans Neuronal Network
- Clustering in Complex Directed Networks
- The Anatomy of the Facebook Social Graph
- Generalizations of the clustering coefficient to weighted complex networks
- Random graphs with clustering
- Understanding the spreading patterns of mobile phone viruses
- Highly clustered scale-free networks
- Dynamics of Social Balance on Networks
- Giant strongly connected component of directed networks
- On the uniform generation of random graphs with prescribed degree sequences
- Social Balance on Networks: The Dynamics of Friendship and Enmity
- Random graphs containing arbitrary distributions of subgraphs
- The energy landscape of social balance
- Topology of biological networks and reliability of information processing
- Early-warning signals of topological collapse in interbank networks
- Solution of the 2-star model of a network
- Tuning clustering in random networks with arbitrary degree distributions
- Solution for the properties of a clustered network
- Evolving Clustered Random Networks
- Motifs emerge from function in model gene regulatory networks
- Synchronization of chaotic networks with time-delayed couplings: An analytic study
- Synchronization Properties of Network Motifs
- Sublattice synchronization of chaotic networks with delayed couplings
- The interplay of microscopic and mesoscopic structure in complex networks
- Network motifs come in sets: correlations in the randomization process
- Motifs in Triadic Random Graphs based on Steiner Triple Systems