Analysis of Complex Networks

4.4 Global Topological Organization of Complex Networks

Our objective here is to give a characterization of the global organization of complex networks. The first step for analyzing the global architecture of a network is to determine whether the network is homogeneous or modular. In a homogeneous network, what you see locally is what you get globally from a topological point of view. However, in a modular network, the organization of certain modules or clusters would be different from one to another and to the global characteristics of the network [27–29].

Formally, we consider a network homogeneous if it has good expansion (GE) properties. A network has GE if every subset S of nodes (S ≤ 50% of the nodes) has a neighborhood that is larger than some “expansion factor” Ω multiplied by the number of nodes in S. A neighborhood of S is the set of nodes that are linked to the nodes in S [30]. Formally, for each vertex v ∈ V (where V is the set of nodes in the network), the neighborhood of v, denoted as Γ(v), is defined as Γ(v) = {u ∈ V|(u, v)∈ E} (where E is the set of links in the network). Then, the neighborhood of a subset S ⊆ V is defined as the union of the neighborhoods of the nodes in S: Γ(S) = ∪_{v ∈S} Γ(v), and the network has GE if Γ(v) ≥ Ω |S| ∀ S ⊆ V.

Consequently, in a homogeneous network we should expect that some local topological properties scale as a power law of global topological properties. A power-law relationship between a two variables x and y of the network is ...