Computational Systems Biology Methods and Protocols.7z

2.2.1 Network
Topological Characteristic
Comparison

There are many parameters for network topology measurement

which are shown in Table1. The most robust measures are node

degree distribution, network clustering coefficient, and average

path length. Degree is the number of edges connected to a vertex,

and the highest-degree nodes are often called hubs. For biological

networks, the degree distribution always has a power-law distribu-

tion, that is, a few nodes own a very high number of degree and lots

of nodes are connected to a few nodes. These networks have no

characteristic scales for the degrees; hence, they are called scale-free

networks. And the parameter of clustering coefficient is a measure

of the degree to which nodes in a graph tend to cluster together.

The networks tend to be modulated when it has a high clustering

coefficient. Average path length is defined as the average number of

steps along the shortest paths for all possible pairs of network

nodes. Most real networks have a very short average path length

leading to the concept of a small world where everyone is

Table 1
Network topological parameters for coexpression network comparison

Parameters Definition Formula

Degree The number of edges connected to a vertex

Power-law

degree

distribution

A network is said to have a power-law degree

distribution when for degreek, the

probability distribution ofkfollows a power

law

p(k)/kγ, where p(.) indicates the

probability mass function andγ1 is the

parameter of the power-law distribution

Clustering

coefficient

A measure of the degree to which nodes in a

graph tend to cluster together

C¼^1 n

P

i

Ci

Average path

length

Average number of steps along the shortest

paths for all possible pairs of networknodes

l¼nnðÞ^1  1

P

i 6 ¼j

dvi;vj



, wherenis the number

of vertices.v 1 ,v 2 ∈Vdenote the shortest

distance betweenv 1 andv 2

Network

diameter

The diameter of a network is the length

(in number of edges) of the longest geodesic

path between any two vertices

Betweenness

centrality

Number of shortest paths between all pairs of

vertices that go through the vertex

gkðÞ¼

P

s 6 ¼k 6 ¼t

σstðÞk

σst whereσstis the total number

of shortest paths from nodesto nodetand

σst(k) is the number of those paths that pass

throughk

Closeness

centrality

A measure ofcentralityin a network, calculated

as the sum of the length of theshortest paths

between the node and all other nodes in the

graph

CvðÞ¼P^1

udvðÞ;u

, whered(v,u) is the distance

between verticesvandu

Network

density

A ratio expressing the number of actual edges

between vertices to the number of possible

edges

Differential Coexpression Network Analysis for Gene Expression Data 159