Networks have in recent years emerged as an invaluable tool for describing and quantifying complex systems in many branches of science [1, 2, 3]. Recent studies suggest that networks often exhibit hierarchical organization, where vertices divide into groups that further subdivide into groups of groups, and so forth over multiple scales. In many cases these groups are found to correspond to known functional units, such as ecological niches in food webs, modules in biochemical networks (protein interaction networks, metabolic networks, or genetic regulatory networks), or communities in social networks [4, 5, 6, 7] . Here we present a general technique for inferring hierarchical structure from network data and demonstrate that the existence of hierarchy can simultaneously explain and quantitatively reproduce many commonly observed topological properties of networks, such as right-skewed degree distributions, high clustering coefficients, and short path lengths. We further show that knowledge of hierarchical structure can be used to predict missing connections in partially known networks with high accuracy, and for more general network structures than competing techniques [8] . Taken together, our results suggest that hierarchy is a central organizing principle of complex networks, capable of offering insight into many network phenomena. A great deal of recent work has been devoted to the study of clustering and community structure in networks [5, 6, 9, 10, 11] . Hierarchical structure goes beyond simple clustering, however, by explicitly including organization at all scales in a network simultaneously. Conventionally, hierarchical structure is represented by a tree or dendrogram in which closely related pairs of vertices have lowest common ancestors that are lower in the tree than those of more distantly related pairs-see Fig. 1 . We expect the probability of a connection between two vertices to depend on their degree of relatedness. Structure of this type can be modelled mathematically using a probabilistic approach in which we endow each internal node r of the dendrogram with a probability p r and then connect each pair of vertices for whom r is the lowest common ancestor independently with probability p r (Fig. 1) . This model, which we call a hierarchical random graph, is similar in spirit (although different in realization) to the treebased models used in some studies of network search and navigation [12, 13] . Like most work on community structure, it * This paper was published as Nature 453, 98 -101 (2008); doi:10.1038/nature06830. assumes that communities at each level of organization are disjoint. Overlapping communities have occasionally been studied (see, for example [14] ) and could be represented using a more elaborate probabilistic model, but as we discuss below the present model already captures many of the structural features of interest. Given a dendrogram and a set of probabilities p r , the hierarchical random graph model allows us to generate artificial networks with a specified hierarchical structure, a procedure that might be useful in certain situations. Our goal here, however, is a different one. We would like to detect and analyze the hierarchical structure, if any, of networks in the real world. We accomplish this by fitting the hierarchical model to observed network data using the tools of statistical inference, combining a maximum likelihood approach possible dendrograms. This technique allows us to sample hierarchical random graphs with probability proportional to the likelihood that they generate the observed network. To obtain the results described below we combine information from a large number of such samples, each of which is a reasonably likely model of the data. The success of this approach relies on the flexible nature of our hierarchical model, which allows us to fit a wide range of network structures. The traditional picture of communities or modules in a network, for example, corresponds to connections that are dense within groups of vertices and sparse between them-a behaviour called "assortativity" in the literature [17] . The hierarchical random graph can capture behaviour of this kind using probabilities p r that decrease as we move higher up the tree. Conversely, probabilities that increase as we move up the tree correspond to "disassortative" structures in which vertices are less likely to be connected on small scales than on large ones. By letting the p r values vary arbitrarily throughout the dendrogram, the hierarchical random graph can capture both assortative and disassortative structure, as well as arbitrary mixtures of the two, at all scales and in all parts of the network. To demonstrate our method we have used it to construct hierarchical decompositions of three example networks drawn from disparate fields: the metabolic network of the spirochete Treponema pallidum [18] , a network of associations between terrorists [19] , and a food web of grassland species [20] . To test whether these decompositions accurately capture the networks' important structural features, we use the sampled dendrograms to generate new networks, different in detail from the originals but, by definition, having similar hierarchical structure (see the Supplementary Information for more details). We find that these "resampled" networks match the statistical properties of the originals closely, including their degree distributions, clustering coefficients, and distributions of shortest path lengths between pairs of vertices, despite the fact that none of these properties is explicitly represented in the hierarchical random graph (Table I , and Fig. S3 in the Supplementary Information). Thus it appears that a network's hierarchical structure is capable of explaining a wide variety of other network features as well. The dendrograms produced by our method are also of interest in themselves, as a graphical representation and summary of the hierarchical structure of the observed network. As dis- . Note that in several cases, a set of parasitoids is grouped into a disassortative community by the algorithm, not because they prey on each other, but because they prey on the same herbivore. cussed above, our method can generates not just a single dendrogram but a set of dendrograms, each of which is a good fit to the data. From this set we can, using techniques from phylogeny reconstruction [21] , create a single consensus dendrogram, which captures the topological features that appear consistently across all or a large fraction of the dendrograms and typically represents a better summary of the network's structure than any individual dendrogram. Figure 2a shows such a consensus dendrogram for the grassland species network, which clearly reveals communities and sub-communities of plants, herbivores, parasitoids, and hyper-parasitoids. Another application of the hierarchical decomposition is the prediction of missing interactions in networks. In many settings, the discovery of interactions in a network requires significant experimental effort in the laboratory or the field. As a result, our current pictures of many networks are sub-3 stantially incomplete [22, 23, 24, 25, 26, 27, 28 ]. An attractive alternative to checking exhaustively for a connection between every pair of vertices in a network is to try to predict, in advance and based on the connections already observed, which vertices are most likely to be connected, so that scarce experimental resources can be focused on testing for those interactions. If our predictions are good, we can in this way reduce substantially the effort required to establish the network's topology. The hierarchical decomposition can be used as the basis for an effective method of predicting missing interactions as follows. Given an observed but incomplete network, we generate as described above a set of hierarchical random graphsdendrograms and the associated probabilities p r -that fit that network. Then we look for pairs of vertices that have a high average probability of connection within these hierarchical random graphs but which are unconnected in the observed network. These pairs we consider the most likely candidates for missing connections. (Technical details of the procedure are given in the Supplementary Information.) We demonstrate the method using our three example networks again. For each network we remove a subset of connections chosen uniformly at random and then attempt to predict, based on the remaining connections, which ones have been removed. A standard metric for quantifying the accuracy of prediction algorithms, commonly used in the medical and machine learning communities, is the AUC statistic, which is equivalent to the area under the receiver-operating characteristic (ROC) curve [29] . In the present context, the AUC statistic can be interpreted as the probability that a randomly chosen missing connection (a true positive) is given a higher score by our method than a randomly chosen pair of unconnected vertices (a true negative). Thus, the degree to which the AUC exceeds 1/2 indicates how much better our predictions are than chance. Figure 3 shows the AUC statistic for the three networks as a function of the fraction of the connections known to the algorithm. For all three networks our algorithm does far better than chance, indicating that hierarchy is a strong general predictor of missing structure. It is also instructive to compare the performance of our method to that of other methods for link prediction [8] . Previously proposed methods include assuming that vertices are likely to be connected if they have many common neighbours, if there are short paths between them, or if the product of their degrees is large. These approaches work well for strongly assortative networks such as the collaboration and citation networks [8] and for the metabolic and terrorist networks studied here (Fig. 3a,b) . Indeed, for the metabolic network the shortest-path heuristic performs better than our algorithm. However, these simple methods can be misleading for networks that exhibit more general types of structure. In food webs, for instance, pairs of predators often share prey species, but rarely prey on each other. In such situations a commonneighbour or shortest-path-based method would predict connections between predators where none exist. The hierarchical model, by contrast, is capable of expressing both assortative and disassortative structure and, as Fig. 3c shows, gives substantially better predictions for the grassland network. (In- deed, in Fig. 2b there are several groups of parasitoids that our algorithm has grouped together in a disassortative community, in which they prey on the same herbivore but not on each other.) The hierarchical method thus makes accurate predictions for a wider range of network structures than the previous methods. In the applications above, we have assumed for simplicity 4 that there are no false positives in our network data, i.e., that every observed edge corresponds to a real interaction. In networks where false positives may be present, however, they too could be predicted using the same approach: we would simply look for pairs of vertices that have a low average probability of connection within the hierarchical random graph but which are connected in the observed network. The method described here could also be extended to incorporate domain-specific information, such as species morphological or behavioural traits for food webs [28] or phylogenetic or binding-domain data for biochemical networks [23] , by adjusting the probabilities of edges accordingly. As the results above show, however, we can obtain good predictions even in the absence of such information, indicating that topology alone can provide rich insights. In closing, we note that our approach differs crucially from previous work on hierarchical structure in networks [1, 4, 5, 6, 7, 9, 11, 30] in that it acknowledges explicitly that most realworld networks have many plausible hierarchical representations of roughly equal likelihood. Previous work, by contrast, has typically sought a single hierarchical representation for a given network. By sampling an ensemble of dendrograms, our approach avoids over-fitting the data and allows us to explain many common topological features, generate resampled networks with similar structure to the original, derive a clear and concise summary of a network's structure via its consensus dendrogram, and accurately predict missing connections in a wide variety of situations.
Based on the similarity of the network topology, reference REF analyzed the effects of some indices on link prediction of social cooperation networks.
Hierarchical structure and the prediction of missing links in networks
Nature 453, 98 - 101 (2008)
Biology Mathematics Physics Medicine