Introduction to Modeling and Simulation

13Complex Networks

13.1 Introduction

This chapter deals with the analysis and applications of complex networks. Complex networks are ubiquitous in natural and engineered systems. Roughly speaking, a network is a collection of entities or agents that interact, i.e., that are interconnected, as in Figure 13.1.

Mathematically, we will represent networks as graphs with agents represented as nodes or vertices of the graph. Edges or links connecting the vertices represent the interactions among the agents. The agents may represent, for example, people in a social network, workstations in a computer network, power plants in an electrical grid, or proteins in a cell, to name but a few. The interconnections may represent friendships and acquaintances, fiber‐optic cable, transmission lines, or protein–protein interactions in such examples. We discuss general questions applicable to a wide range of complex networks, such as:

• Connectedness – with which agent can a given agent communicate?
• Centrality – which agents are the most important?
• Distance – how closely are agents related?
• Clustering – how do agents form groups and cliques?
• Degree distribution – how many neighbors does each agent have?
• Synchronization – how does global behavior emerge from local interactions?

A key feature of complexity is emergent behavior, which is the idea that the whole is more than the sum of the parts. For example, in biology, how does life emerge from the interactions of atoms and molecules, none of which ...