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 the O’Reilly learning platform.

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