4. Graph energy: it is defined as the sum of the absolute values of
the adjacency matrix eigenvalues. This descriptor is strongly
grounded into Chemical Graph Theory, aimed at describing
chemico-physical properties of organic molecules from connectivity indices of chemical structural graphs [19]. Graph energy
for protein contact networks highlights special features of enzymatic allostery [20] and of protein-protein interactions [21].
3.3 Clustering
Cooperativity in proteins is a direct effect of their modularity
[22]. Thus, a key step in protein allostery analysis is to identify
modules in protein structures, which somehow correspond to
recognized functional domains.
Protein contact networks formalism strongly helps in this direction by means of network clustering: clusters in protein contact
networks well match with protein domains [20].
Two methods have been devised to partition PCNs into clusters [23]: a geometrical method, based on the k-means algorithm
and spectral clustering, which demonstrated to be very effective in
identifying functional regions in proteins (see the azurin case discussed in ref. 23).
Spectral clustering is based on the spectral decomposition of
the laplacian matrix L, defined as follows:
L ¼ D À A
ð6Þ
A being the adjacency matrix and D the degree matrix, i.e., a
diagonal matrix whose diagonal is the degree vector. The eigenvalue decomposition is applied to the laplacian L: the eigenvector
corresponding to the second minor of eigenvalue v 2 is of interest
for the clustering partition. Considering the partition in two clusters, for instance, nodes are divided into the two clusters according
to the sign of the corresponding components of the vector v 2 .
Spectral clustering is a clustering based on binary partition, so
the number of clusters that can be obtained is only a power of two
(2,4,8, . . .).
Spectral clustering allows to identify cluster of nodes maximally
interacting with each other, rather than nodes close in the space
(such as in geometrical clustering). In this respect, spectral clustering is specifically apt to identify functional regions [23].
Once clusters have been specified (see Note 3), two descriptors
assign the topological role of nodes with regard to their communication attitude:
(a) the participation coefficient is defined for the node i in the
cluster s as:
P i ¼ 1 À
k si
k i
2
ð7Þ
14
Luisa Di Paola et al.
the adjacency matrix eigenvalues. This descriptor is strongly
grounded into Chemical Graph Theory, aimed at describing
chemico-physical properties of organic molecules from connectivity indices of chemical structural graphs [19]. Graph energy
for protein contact networks highlights special features of enzymatic allostery [20] and of protein-protein interactions [21].
3.3 Clustering
Cooperativity in proteins is a direct effect of their modularity
[22]. Thus, a key step in protein allostery analysis is to identify
modules in protein structures, which somehow correspond to
recognized functional domains.
Protein contact networks formalism strongly helps in this direction by means of network clustering: clusters in protein contact
networks well match with protein domains [20].
Two methods have been devised to partition PCNs into clusters [23]: a geometrical method, based on the k-means algorithm
and spectral clustering, which demonstrated to be very effective in
identifying functional regions in proteins (see the azurin case discussed in ref. 23).
Spectral clustering is based on the spectral decomposition of
the laplacian matrix L, defined as follows:
L ¼ D À A
ð6Þ
A being the adjacency matrix and D the degree matrix, i.e., a
diagonal matrix whose diagonal is the degree vector. The eigenvalue decomposition is applied to the laplacian L: the eigenvector
corresponding to the second minor of eigenvalue v 2 is of interest
for the clustering partition. Considering the partition in two clusters, for instance, nodes are divided into the two clusters according
to the sign of the corresponding components of the vector v 2 .
Spectral clustering is a clustering based on binary partition, so
the number of clusters that can be obtained is only a power of two
(2,4,8, . . .).
Spectral clustering allows to identify cluster of nodes maximally
interacting with each other, rather than nodes close in the space
(such as in geometrical clustering). In this respect, spectral clustering is specifically apt to identify functional regions [23].
Once clusters have been specified (see Note 3), two descriptors
assign the topological role of nodes with regard to their communication attitude:
(a) the participation coefficient is defined for the node i in the
cluster s as:
P i ¼ 1 À
k si
k i
2
ð7Þ
14
Luisa Di Paola et al.