Guimerà and Amaral find that low-degree metabolites that connect different modules are more conserved than hubs whose links are mostly within a single module. If one is to extract the significant information from the topology of a large complex network, the knowledge of the role of each node is of crucial importance. A cartographic analogy is helpful to illustrate this point. Consider the network formed by all cities and towns in a country-the nodes-and all the roads that connect them-the links. It is clear that a map in which each city and town is represented by a circle of fixed size and each road is represented by a line of fixed width is hardly useful. Rather, real maps emphasize capitals and important communication lines so that one can obtain scale-specific information at a glance. Similarly, it is difficult, if not impossible, to obtain information from a network with hundreds or thousands of nodes and links, unless the information about nodes and links is conveniently summarized. This is particularly true for biological networks. Here, we propose a methodology, which is based on the connectivity of the nodes, that yields a "cartographic representation" of a complex network. The first step in our method is to identify the functional modules 4,5 in the network. In the cartographic picture, modules are analogous to countries or regions, and enable a coarse-grained, and thus simplified, description of the network. Then, we classify the nodes in the network into a small number of systemindependent "universal roles." Modules. It is a matter of common experience that social networks have communities of highly interconnected nodes that are less connected to nodes in other communities. Such modular structures have been reported not only in social networks 5, 10, 11, 12 , but also in food webs 13 and biochemical networks 4, 14, 15, 16 . It is widely believed that the modular structure of complex networks plays a critical role in their functionality 4, 14, 16 . There is therefore a clear need to develop algorithms to identify modules accurately 5, 11, 17,18, 19, 20 . We identify modules by maximizing the network's modularity 11,18,21 using simulated annealing 22 (see Methods). Simulated annealing enables us to carry out an exhaustive search and to minimize the problem of finding sub-optimal partitions. It is noteworthy that, in our method, Letter to Nature Guimerà and Amaral one does not need to specify a priori the number of modules; rather, this number is an outcome of the algorithm. Our algorithm, which significantly outperforms the best algorithm in the literature, is able to reliably identify modules in a network whose nodes have as many as 50% of their connections outside their own module (Fig. 1) . Roles in modular networks. It is plausible to surmise that the nodes in a network are connected according to the role they fulfill. This fact has been long recognized in the analysis of social networks 23 . For example, in a classical hierarchical organization, the CEO is not directly connected to plant employees but is connected to the members of the board of directors. Importantly, such a statement holds for virtually any organization, that is, the role of CEO is defined irrespective of the particular organization one considers. We propose a new method to determine the role of a node in a complex network. Our approach is based on the idea that nodes with the same role should have similar topological properties 24 (see Supplementary Information for a discussion on how our approach relates to previous work). We hypothesize that the role of a node can be determined, to a great extent, by its within-module degree and its participation coefficient, which define how the node is positioned in its own module and with respect to other modules 25, 26 (see Methods). These two properties are easily computed once the modules of a network are known. The within-module degree z i measures how "well-connected" node i is to other nodes in the module. High values of z i indicate high within-module degrees and vice versa. The participation coefficient P i measures how "well-distributed" the links of node i are among different modules. The participation coefficient P i is close to one if its links are uniformly distributed among all the modules and zero if all its links are within its own module. We define heuristically seven different "universal roles," each defined by a different region in the zP parameters-space (Fig. 2) . According to the within-module degree, we classify nodes with z ≥ 2.5 as module hubs and nodes z < 2.5 as non-hubs. Both hub and non-hub nodes are then more finely characterized by using the values of the participation coefficient (see Supplementary Information for a detailed justification of this classification scheme, and for a 3 Letter to Nature Guimerà and Amaral discussion on possible alternatives). We find that non-hub nodes can be naturally divided into four different roles: (R1) ultraperipheral nodes, i.e., nodes with all its links within their module (P ≤ 0.05); (R2) peripheral nodes, i.e., nodes with most links within their module (0.05 < P ≤ 0.62); (R3) non-hub connector nodes, i.e., nodes with many links to other modules (0.62 < P ≤ 0.80); and (R4) non-hub kinless nodes, i.e., nodes with links homogeneously distributed among all modules (P > 0.80). We find that hub nodes can be naturally divided into three different roles: (R5) provincial hubs. i.e., hub nodes with the vast majority of links within their module (P ≤ 0.30); (R6) connector hubs, i.e., hubs with many links to most of the other modules (0.30 < P ≤ 0.75); and (R7) kinless hubs, i.e., hubs with links homogeneously distributed among all modules (P > 0.75). To test the applicability of our approach to complex biological networks, we consider the metabolic network 6,7, 14, 8,9 of twelve organisms: Next, we identify the role of each metabolite. In Fig. 2b we show the roles identified in the metabolic network of E. coli. Remarkably, other organisms display a similar distribution of the nodes in the different roles, even though they correspond to organisms that are very distant from an evolutionary standpoint (see Supplementary Information). Role R1, which contains ultra-peripheral metabolites with small degree and no between-module links, comprises 76-86% of all the metabolites in the networks. This considerably simplifies the coarse-grained representation of the network as these nodes do not need to be identified separately. Note that this finding alone represents an important step towards the goal of extracting scale-specific information from complex networks. The information about modules and roles enables us to build a "cartographic representation" of the metabolic network of, for example, E. coli (Fig. 3) . This representation enables us to recover relevant biological information. For instance, we find that the metabolism is mostly organized around the module containing pyru- Letter to Nature Guimerà and Amaral vate, which, in turn, is strongly connected to the module whose hub is acetyl-CoA. These two molecules are key to connect the metabolism of carbohydrates, amino acids, and lipids to the TCA cycle from which ATP is obtained. These two modules are connected to more peripheral ones by key metabolites such as D-glyceraldehyde 3-phosphate and D-fructose 6-phosphate (which connect to the glucose and galactose metabolisms), D-ribose 5-phosphate (which connects to the metabolism of certain nucleotides), and glycerone phosphate (which connects to the metabolism of certain lipids). Importantly, our analysis also uncovers nodes with key connector roles that take part in only a small but fundamental set of reactions. For example, N-carbamoyl-L-aspartate takes part in only three reactions but is vital because it connects the pyrimidine metabolism, whose hub is uracil, to the core of the metabolism through the alanine and aspartate metabolism. The potential importance of such non-hub connectors points to another consideration. It is a plausible hypothesis that nodes with different roles are under different evolutionary constraints and pressures. In particular, one expects that nodes with structurally relevant roles are more necessary and therefore more conserved across species. To quantify the relation between roles and conservation, we define the loss rate p lost (R) (see Methods). Structurally relevant roles are expected to have low values of p lost (R) and vice versa. Remarkably, we find that the different roles have, indeed, different loss rates (Fig. 4) . As expected, ultra-peripheral nodes (role R1) have the highest loss rate while connector hubs (role R6) are the most conserved across all species considered. The results for the comparison of p lost (R) for ultra-peripheral nodes and connector hubs is illustrative, but hardly surprising. The comparison of p lost (R) for non-hub connectors (role R3) and provincial hubs (role R5), however, yields a surprising and remarkable finding. The metabolites in the provincial hubs class have many within-module connections, sometimes as much as five standard deviations more connections than the average node in the module. Conversely, non-hub connector metabolites have few links relative to other nodes in their modules-and fewer total connections than the metabolites in role R5 (see Supplementary Figs . S12b,c). The 6 Letter to Nature Guimerà and Amaral links of non-hub connectors, however, are distributed among several different modules, while the links of provincial hubs are mainly within their modules. We find that non-hub connectors are systematically and significantly more conserved than provincial hub metabolites (Fig. 4) . A possible explanation for the high degree of conservation of non-hub connectors is the following. Connector nodes are responsible for inter-module fluxes. These modules are, otherwise, poorly connected or not connected at all to each other, so the elimination of connector metabolites will likely have a large impact on the global structure of fluxes in the network. On the contrary, the pathways in which provincial hubs are involved may be backed up within the module, in such a way that elimination of these metabolites may have a comparatively smaller impact, which, in addition, would likely be confined to the module containing the provincial hub. Our results therefore point to the need to consider each complex biological network as a whole, instead of focusing on local properties. In protein networks, for example, it has been reported that hubs are more essential than non-hubs 30 . Notwithstanding the relevance of such a finding, our results suggest that the global role of nodes in the network might be a better indicator of their importance than degree 26 . Our "cartography" provides a scale-specific method to process the information contained in the structure of complex networks, and to extract knowledge about the function carried out by the network and its constituents. An open question is how to adapt current module-detection algorithms to networks with a hierarchical structure. For metabolic networks, a comparatively well studied and well understood case, our method allows us to recover firmly established biological facts, and to uncover important new results, such as the significant conservation of non-hub connector metabolites. Similar results can be expected when our method is applied to other complex networks that are not as well studied as metabolic networks. Among those, protein interaction and gene regulation networks may be the most significant. Letter to Nature Guimerà and Amaral Methods For a given partition of the nodes of a network into modules, the modularity M of this partition is 11, 18, 21  where N M is the number of modules, L is the number of links in the network, l s is the number of links between nodes in module s, and d s is the sum of the degrees of the nodes in module s. The rationale for this definition of modularity is the following. A good partition of a network into modules must comprise many within-module links and as few as possible between-module links. However, if one just tries to minimize the number of between-module links (or, equivalently, maximize the number of within-module links) the optimal partition consists of a single module and no between-module links. Equation (1) addresses this difficulty by imposing that M = 0 if nodes are placed at random into modules or if all nodes are in the same cluster 11, 18, 21 . The objective of a module identification algorithm is to find the partition with largest modularity, and several methods have been proposed to attain such a goal. Most of them rely on heuristic procedures and use M-or a similar measure-only to assess their performance. In contrast, we use simulated annealing 22 to find the partition with the largest modularity. Simulated annealing 22 is a stochastic optimization technique that enables one to find "low cost" configurations without getting trapped in "high-cost" local minima. This is achieved by introducing a computational temperature T . When T is high, the system can explore configurations of high cost while at low T the system only explores low cost regions. By starting at high T and slowly decreasing T , the system descends gradually toward deep minima, eventually overcoming small cost barriers. Letter to Nature When identifying modules, the objective is to maximize the modularity and, thus, the cost is C = −M, where M is the modularity as defined in Eq. (1). At each temperature, we perform a number of random updates and accept them with probability where C f is the cost after the update and C i is the cost before the update. Specifically, at each T we propose n i = f S 2 individual node movements from one module to another, where S is the number of nodes in the network. We also propose n c = f S collective movements, which involve either the merging two modules or splitting a module. For f we typically choose f = 1. After the movements are evaluated at a certain T , the system is cooled down to T ′ = cT , with c = 0.995. Each module can be organized in very different ways, ranging from totally centralized-with one or a few nodes connected to all the others-to totally decentralized-with all nodes having similar connectivities. Nodes with similar roles are expected to have similar relative withinmodule connectivity. If κ i is the number of links of node i to other nodes in its module s i , κ s i is the average of κ over all the nodes in s i , and σ κs i is the standard deviation of κ in s i , then is the so-called z-score. The within-module degree z-score measures how "well-connected" node i is to other nodes in the module. Different roles can also arise because of the connections of a node to modules other than its own. For example, two nodes with the same z-score will play different roles if one of them is connected to several nodes in other modules while the other is not. We define the participation coefficient P i of node i as Letter to Nature where κ is is the number of links of node i to nodes in module s, and k i is the total degree of node i. The participation coefficient of a node is therefore close to one if its links are uniformly distributed among all the modules and zero if all its links are within its own module. To quantify the relation between roles and conservation, we calculate to which extent metabolites are conserved in the different species depending on the role they play. Specifically, for a pair of species, A and B, we define the loss rate as the probability p(R A = 0|R B = R) ≡ p lost (R) that a metabolite is not present in one of the species (R A = 0) given that it plays role R in the other species (R B = R). Structurally relevant roles are expected to have low values of p lost (R) and vice versa.
With respect to core node detection, Roger Guimera and Luis A.Nunes Amaral propose a methodology that classifies nodes into universal roles according to their pattern of intra-and inter-module connections REF .
Functional cartography of complex metabolic networks
Nature 433, 895-900 (2005)
Biology Physics Medicine