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 vV (where V is the set of nodes in the network), the neighborhood of v, denoted as Γ(v), is defined as Γ(v) = {uV|(u, v)∈ E} (where E is the set of links in the network). Then, the neighborhood of a subset SV is defined as the union of the neighborhoods of the nodes in S: Γ(S) = ∪vS Γ(v), and the network has GE if Γ(v) ≥ Ω |S| ∀ SV.

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

Get Analysis of Complex Networks now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.