structure. If one considers the community structure as a network of
communities, then each node in such graph is a community and the
edge connecting two different communities is the sum of all (protein network) edges (with highest EBs) that have been removed
during the Girvan-Newman procedure. Thus, the community network represents a coarse-grained, where linked communities are
connected by edges that are weighted by the inter-communities EB
(IEB), i.e., the sum of the EBs associated to the pairs of residues
connecting the two communities. The IEBs indicate the strength of
the communication flow between pairs of communities and thus
represent a simplified way to represent the communication associated to correlated protein motions within a protein.
The optimal partition of the protein network into communities
is obviously not that where the number of communities equals the
number of nodes and, thus, the quality of the network partition has
to be evaluated in order to determine the best distribution of nodes
in the communities, i.e., the optimum community structure. The
modularity of a given network division, i.e., the difference in probability of intra- and inter-community connections [49], is a very
useful quantity to measure the quality (or strength) of a community
structure. The modularity, Q, is defined as
Q ¼
X
i
e ii À a
2
i
À
Á
ð4Þ
where e ij is the fractions of edges that link nodes in community i to
nodes in community j, and a i ¼ ∑ j e ij is the fraction of edges that
connect to nodes in community i. The modularity values range
from 0 to 1 (see Fig. 3), the higher the values, the higher the quality
of the community structure, with typical values for community
networks originated from 3D structures being >0.4 [49]. By
selecting the community structure with the maximal modularity
among those generated by the iterative Girvan-Newman algorithm,
the optimum community structure is chosen in such a way that each
community contains nodes that are highly intra-connected while
different communities are poorly inter-connected but through few
critical edges, representing the pairs of nodes crucial for communications among communities.
3.3 Assessment
of Cutoff Parameters
Choice
As mentioned in the previous sections, the adjacency matrix defining the dynamical weighted network is bound to the contact criterion associated to the distance and percentage cutoff parameters. As
a consequence, the generation of the optimum community structure for the dynamical weighted network, described in the above
section, is carried out for a given set of these two cutoff parameters,
i.e., one contact distance and one percentage of MD frames. In
order to assess the reliability of an optimum community structure
representing the correlated protein motions in a given MD simulation, thus, is necessary to analyze the effect of the cutoff
144
Ivan Rivalta and Victor S. Batista
communities, then each node in such graph is a community and the
edge connecting two different communities is the sum of all (protein network) edges (with highest EBs) that have been removed
during the Girvan-Newman procedure. Thus, the community network represents a coarse-grained, where linked communities are
connected by edges that are weighted by the inter-communities EB
(IEB), i.e., the sum of the EBs associated to the pairs of residues
connecting the two communities. The IEBs indicate the strength of
the communication flow between pairs of communities and thus
represent a simplified way to represent the communication associated to correlated protein motions within a protein.
The optimal partition of the protein network into communities
is obviously not that where the number of communities equals the
number of nodes and, thus, the quality of the network partition has
to be evaluated in order to determine the best distribution of nodes
in the communities, i.e., the optimum community structure. The
modularity of a given network division, i.e., the difference in probability of intra- and inter-community connections [49], is a very
useful quantity to measure the quality (or strength) of a community
structure. The modularity, Q, is defined as
Q ¼
X
i
e ii À a
2
i
À
Á
ð4Þ
where e ij is the fractions of edges that link nodes in community i to
nodes in community j, and a i ¼ ∑ j e ij is the fraction of edges that
connect to nodes in community i. The modularity values range
from 0 to 1 (see Fig. 3), the higher the values, the higher the quality
of the community structure, with typical values for community
networks originated from 3D structures being >0.4 [49]. By
selecting the community structure with the maximal modularity
among those generated by the iterative Girvan-Newman algorithm,
the optimum community structure is chosen in such a way that each
community contains nodes that are highly intra-connected while
different communities are poorly inter-connected but through few
critical edges, representing the pairs of nodes crucial for communications among communities.
3.3 Assessment
of Cutoff Parameters
Choice
As mentioned in the previous sections, the adjacency matrix defining the dynamical weighted network is bound to the contact criterion associated to the distance and percentage cutoff parameters. As
a consequence, the generation of the optimum community structure for the dynamical weighted network, described in the above
section, is carried out for a given set of these two cutoff parameters,
i.e., one contact distance and one percentage of MD frames. In
order to assess the reliability of an optimum community structure
representing the correlated protein motions in a given MD simulation, thus, is necessary to analyze the effect of the cutoff
144
Ivan Rivalta and Victor S. Batista