Identifying communities within energy landscapes

Potential energy landscapes can be represented as a network of minima linked by transition states. The community structure of such networks has been obtained for a series of small Lennard-Jones (LJ) clusters. This community structure is compared to the concept of funnels in the potential energy landscape. Two existing algorithms have been used to find community structure, one involving removing edges with high betweenness, the other involving optimization of the modularity. The definition of the modularity has been refined, making it more appropriate for networks such as these where multiple edges and self-connections are not included. The optimization algorithm has also been improved, using Monte Carlo methods with simulated annealing and basin hopping, both often used successfully in other optimization problems. In addition to the small clusters, two examples with known heterogeneous landscapes, the 13-atom cluster $\left({\mathrm{LJ}}_{13}\right)$ with one labeled atom and the 38-atom cluster $\left({\mathrm{LJ}}_{38}\right)$, were studied with this approach. The network methods found communities that are comparable to those expected from landscape analyses. This is particularly interesting since the network model does not take any barrier heights or energies of minima into account. For comparison, the network associated with a two-dimensional hexagonal lattice is also studied and is found to have high modularity, thus raising some questions about the interpretation of the community structure associated with such partitions.

Figure 1

Variation in the clustering coefficient of the ${\mathrm{LJ}}_{14}$ network as edges were rewired to form a random ensemble. Data collection began at five switches per edge.

Figure 2

(a) Dendrogram showing the results of the betweenness algorithm applied to ${\mathrm{LJ}}_{10}$. Each point on the $y$ axis represents a single node in the network (in arbitrary order). Drawing a vertical line at any point, as has been done at the best splits as determined by $Q_{\mathit{max}}$ and $Q_{\mathit{max}}^{\prime }$, gives the number and sizes of communities at that point. In the case of the betweenness algorithm, the initial point is the right-hand side where all nodes are in a single community. The scale of the $x$ axis is the number of edges remaining in the network. (b) Variation in $Q$ (solid line) and $Q^{\prime }$ (dashed line) as the algorithm progresses.

Figure 3

Degree of nodes separated from the main community by the betweenness algorithm for ${\mathrm{LJ}}_{10}$.

Figure 4

(a) Dendrogram showing the results of the greedy algorithm applied to ${\mathrm{LJ}}_{10}$. The initial point for the greedy algorithm is at the left-hand side with $N$ (64) communities. The $x$ axis represents the number of steps, where each step involves joining together two communities. The dashed line represents the best split found (with maximum $Q$). (b) Variation of $Q$ as the algorithm progresses.

Figure 5

Average probability of an edge between two nodes as a function of the product of the degrees of those nodes, calculated for ${\mathrm{LJ}}_{14}$. Values were calculated from an ensemble of random networks and are used to calculate $Q^{\prime }$. The number of edges predicted by this method is never larger than 1. The straight line shows the value $k_i{k}_j∕2M$ used in the original calculation of $Q$. For the two highest degree nodes, this takes the value 33.46.

Figure 6

(a) Dendrogram showing the results of the greedy algorithm using $Q^{\prime }$ applied to ${\mathrm{LJ}}_{10}$. The dashed line represents the best split found (with maximum $Q^{\prime }$). (b) Variation of $Q^{\prime }$ as the algorithm progresses.

Figure 7

$Q^{\prime }$ against $N$ for cluster networks and random ensembles, error bars are one standard deviation from an ensemble of 25 random networks. The results are (from bottom to top) for the betweenness algorithm, the greedy algorithm, simulated annealing, and basin hopping. The betweenness algorithm was only run on clusters with up to 12 atoms (515 nodes) as it is slow for larger networks.

Figure 8

(Color online) (a) Cumulative degree distribution and (b) energy distribution of minima for ${\mathrm{LJ}}_{13}$. The solid line is the overall distribution for the whole network and the dashed lines are those for the five communities found using basin hopping.

Figure 9

(Color online) Distributions of (a) the moments of inertia (the geometric mean of the principal moments of inertia) and (b) energies of minima found for ${\mathrm{LJ}}_{13}$ with one heavy atom, using basin hopping to optimize $Q$. The solid line shows the distribution for all minima. The dashed lines represent the four largest communities with sizes greater than 3000. The other communities all contained fewer than 20 nodes. Minima with larger moments of inertia have the heavy atom closer to the outside of the cluster.

Figure 10

The final 100 steps in the dendrogram for ${\mathrm{LJ}}_{38}$ using the greedy algorithm. If a community only consists of single nodes, i.e., is not composed of smaller communities, then for clarity only the first and last nodes to join that community are shown. The variation of $Q^{\prime }$ as the algorithm progresses is not shown, it has a single peak of value $Q_{\mathit{max}}^{\prime }=0.8311$ at level 5956 (indicated by a dashed line on the dendrogram).

Figure 11

(Color online) The partition with the highest modularity $(Q^{\prime }=0.8480)$ seen for a two-dimensional hexagonal lattice with 2500 nodes using periodic boundary conditions. This partition was found using basin hopping to optimize $Q^{\prime }$ from an initial partition into roughly equally sized hexagons.