Page 326 - Becoming Metric Wise

319
Networks

In directed networks, one makes a distinction between strongly con-
nected components and weakly connected ones. A strongly connected
component is a subgraph such that it satisfies the definition of a compo-
nent using only directed paths. If a subgraph in a directed network is a
component when ignoring directions one says that it is a weakly con-
nected component.

10.2 NETWORK INDICATORS (WASSERMAN & FAUST, 1994)

Next we define some indicators describing the structure (cohesion) of
networks and the role played by particular nodes. Many more are
described in the literature, but we will restrict ourselves to the following
elementary ones.

10.2.1 Density

Definition: density (D)
The density is an indicator for the general level of connectedness of
the graph. If every node is directly connected to every other node, we
have a complete graph. The density of a graph is defined as the number
of links divided by the number of vertices in a complete graph with the
same number of nodes. For a complete, undirected graph G with N

N NðN 2 1Þ
nodes, the number of links is equal to 5 . Hence the
2 2
density D of an undirected network is defined as:
2 ð#EÞ
D 5 (10.1)
NðN 2 1Þ
where E denotes the set of edges or links in the graph and # means “the
number of elements in.”
In a directed network D is defined as
#E
D 5 (10.2)
NðN 2 1Þ

10.2.2 Centrality Indicators
The use of centrality measures, originating from social network analysis
(Scott, 1991; Wasserman & Faust, 1994) has led to valuable methods in all
types of networks (Bollen et al., 2009; Borgatti et al., 2009; Otte &