Community structure in social and biological networks

Analyzing protein lists with large networks: edge-count probabilities in random graphs with given expected degrees

We present an analytical framework to analyze lists of proteins with large undirected graphs representing their known functional relationships. We consider edge-count variables such as the number of interactions between a protein and a list, the size of a subgraph induced by a list, and the number of interactions bridging two lists. We derive approximate analytical expressions for the probability distributions of these variables in a model of a random graph with given expected degrees. Probabilities obtained with the analytical expressions are used to mine a protein interaction network for functional modules, characterize the connectedness of protein functional categories, and measure the strength of relations between modules.

Lethality and synthetic lethality in the genome-wide metabolic network of Escherichia coli

Recent genomic analyses on the cellular metabolic network show that reaction flux across enzymes are diverse and exhibit power-law behavior in its distribution. While intuition might suggest that the reactions with larger fluxes are more likely to be lethal under the blockade of its catalysing gene products or gene knockouts, we find, by in silico flux analysis, that the lethality rarely has correlations with the flux level owing to the widespread backup pathways innate in the genome-wide metabolism of Escherichia coli. Lethal reactions, of which the deletion generates cascading failure of following reactions up to the biomass reaction, are identified in terms of the Boolean network scheme as well as the flux balance analysis. The avalanche size of a reaction, defined as the number of subsequently blocked reactions after its removal, turns out to be a useful measure of lethality. As a means to elucidate phenotypic robustness to a single deletion, we investigate synthetic lethality in reaction level, where simultaneous deletion of a pair of nonlethal reactions leads to the failure of the biomass reaction. Synthetic lethals identified via flux balance and Boolean scheme are consistently shown to act in parallel pathways, working in such a way that the backup machinery is compromised.

Uncovering the overlapping community structure of complex networks in nature and society

Many complex systems in nature and society can be described in terms of networks capturing the intricate web of connections among the units they are made of. A key question is how to interpret the global organization of such networks as the coexistence of their structural subunits (communities) associated with more highly interconnected parts. Identifying these a priori unknown building blocks (such as functionally related proteins, industrial sectors and groups of people) is crucial to the understanding of the structural and functional properties of networks. The existing deterministic methods used for large networks find separated communities, whereas most of the actual networks are made of highly overlapping cohesive groups of nodes. Here we introduce an approach to analysing the main statistical features of the interwoven sets of overlapping communities that makes a step towards uncovering the modular structure of complex systems. After defining a set of new characteristic quantities for the statistics of communities, we apply an efficient technique for exploring overlapping communities on a large scale. We find that overlaps are significant, and the distributions we introduce reveal universal features of networks. Our studies of collaboration, word-association and protein interaction graphs show that the web of communities has non-trivial correlations and specific scaling properties.

The implications of network structure for epidemic dynamics

It has long been realised that the standard assumptions of mass-action mixing are a crude approximation of the true mechanistic processes that govern the transmission of infection. In particular, many infections can be considered to be spread through a limited network of contacts. Yet, despite the underlying discrepancies, mass-action models continue to be used and provide a remarkably accurate description of epidemic behaviour. Here, the differences between mass-action and network-based models are investigated. This allows us to determine when mass-action models are a reliable tool, and suggest ways in which their behaviour should be refined.

Identifying the role that animals play in their social networks

Techniques recently developed for the analysis of human social networks are applied to the social network of bottlenose dolphins living in Doubtful Sound, New Zealand. We identify communities and subcommunities within the dolphin population and present evidence that sex- and age-related homophily play a role in the formation of clusters of preferred companionship. We also identify brokers who act as links between sub-communities and who appear to be crucial to the social cohesion of the population as a whole. The network is found to be similar to human social networks in some respects but different in some others, such as the level of assortative mixing by degree within the population. This difference elucidates some of the means by which the network forms and evolves.

Subgraph centrality in complex networks

We introduce a new centrality measure that characterizes the participation of each node in all subgraphs in a network. Smaller subgraphs are given more weight than larger ones, which makes this measure appropriate for characterizing network motifs. We show that the subgraph centrality [C(S)(i)] can be obtained mathematically from the spectra of the adjacency matrix of the network. This measure is better able to discriminate the nodes of a network than alternate measures such as degree, closeness, betweenness, and eigenvector centralities. We study eight real-world networks for which C(S)(i) displays useful and desirable properties, such as clear ranking of nodes and scale-free characteristics. Compared with the number of links per node, the ranking introduced by C(S)(i) (for the nodes in the protein interaction network of S. cereviciae) is more highly correlated with the lethality of individual proteins removed from the proteome.

Clique percolation in random networks

The notion of k-clique percolation in random graphs is introduced, where k is the size of the complete subgraphs whose large scale organizations are analytically and numerically investigated. For the Erdos-Rényi graph of N vertices we obtain that the percolation transition of k-cliques takes place when the probability of two vertices being connected by an edge reaches the threshold p(c) (k) = [(k - 1)N](-1/(k - 1)). At the transition point the scaling of the giant component with N is highly nontrivial and depends on k. We discuss why clique percolation is a novel and efficient approach to the identification of overlapping communities in large real networks.

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 (LJ13) with one labeled atom and the 38-atom cluster (LJ38) , 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.

Subnets of scale-free networks are not scale-free: sampling properties of networks

Most studies of networks have only looked at small subsets of the true network. Here, we discuss the sampling properties of a network's degree distribution under the most parsimonious sampling scheme. Only if the degree distributions of the network and randomly sampled subnets belong to the same family of probability distributions is it possible to extrapolate from subnet data to properties of the global network. We show that this condition is indeed satisfied for some important classes of networks, notably classical random graphs and exponential random graphs. For scale-free degree distributions, however, this is not the case. Thus, inferences about the scale-free nature of a network may have to be treated with some caution. The work presented here has important implications for the analysis of molecular networks as well as for graph theory and the theory of networks in general.

Functional cartography of complex metabolic networks

High-throughput techniques are leading to an explosive growth in the size of biological databases and creating the opportunity to revolutionize our understanding of life and disease. Interpretation of these data remains, however, a major scientific challenge. Here, we propose a methodology that enables us to extract and display information contained in complex networks. Specifically, we demonstrate that we can find functional modules in complex networks, and classify nodes into universal roles according to their pattern of intra- and inter-module connections. The method thus yields a 'cartographic representation' of complex networks. Metabolic networks are among the most challenging biological networks and, arguably, the ones with most potential for immediate applicability. We use our method to analyse the metabolic networks of twelve organisms from three different superkingdoms. We find that, typically, 80% of the nodes are only connected to other nodes within their respective modules, and that nodes with different roles are affected by different evolutionary constraints and pressures. Remarkably, we find that metabolites that participate in only a few reactions but that connect different modules are more conserved than hubs whose links are mostly within a single module.

The use of edge-betweenness clustering to investigate biological function in protein interaction networks

Background

This paper describes an automated method for finding clusters of interconnected proteins in protein interaction networks and retrieving protein annotations associated with these clusters.

Results

Protein interaction graphs were separated into subgraphs of interconnected proteins, using the JUNG implementation of Girvan and Newman's Edge-Betweenness algorithm. Functions were sought for these subgraphs by detecting significant correlations with the distribution of Gene Ontology terms which had been used to annotate the proteins within each cluster. The method was implemented using freely available software (JUNG and the R statistical package). Protein clusters with significant correlations to functional annotations could be identified and included groups of proteins know to cooperate in cell metabolism. The method appears to be resilient against the presence of false positive interactions.

Conclusion

This method provides a useful tool for rapid screening of small to medium size protein interaction datasets.

Flexible construction of hierarchical scale-free networks with general exponent

Extensive studies have been done to understand the principles behind architectures of real networks. Recently, evidence for hierarchical organization in many real networks has also been reported. Here, we present a hierarchical model that reproduces the main experimental properties observed in real networks: scale-free of degree distribution P (k) [frequency of the nodes that are connected to k other nodes decays as a power law P (k) approximately k(-gamma) ] and power-law scaling of the clustering coefficient C (k) approximately k(-1) . The major points of our model can be summarized as follows. (a) The model generates networks with scale-free distribution for the degree of nodes with general exponent gamma>2 , and arbitrarily close to any specified value, being able to reproduce most of the observed hierarchical scale-free topologies. In contrast, previous models cannot obtain values of gamma>2.58 . (b) Our model has structural flexibility because (i) it can incorporate various types of basic building blocks (e.g., triangles, tetrahedrons, and, in general, fully connected clusters of n nodes) and (ii) it allows a large variety of configurations (i.e., the model can use more than n-1 copies of basic blocks of n nodes). The structural features of our proposed model might lead to a better understanding of architectures of biological and nonbiological networks.

Growing network model for community with group structure

We propose a growing network model for a community with a group structure. The community consists of individual members and groups, gatherings of members. The community grows as a new member is introduced by an existing member at each time step. The new member then creates a new group or joins one of the groups of the introducer. We investigate the emerging community structure analytically and numerically. The group size distribution shows a power-law distribution for a variety of growth rules, while the activity distribution follows an exponential or a power law depending on the details of the growth rule. We also present an analysis of empirical data from online communities the "Groups" in http://www.yahoo.com and the "Cafe" in http://www.daum.net, which show a power-law distribution for a wide range of group sizes.

Subgraphs and network motifs in geometric networks

Many real-world networks describe systems in which interactions decay with the distance between nodes. Examples include systems constrained in real space such as transportation and communication networks, as well as systems constrained in abstract spaces such as multivariate biological or economic data sets and models of social networks. These networks often display network motifs: subgraphs that recur in the network much more often than in randomized networks. To understand the origin of the network motifs in these networks, it is important to study the subgraphs and network motifs that arise solely from geometric constraints. To address this, we analyze geometric network models, in which nodes are arranged on a lattice and edges are formed with a probability that decays with the distance between nodes. We present analytical solutions for the numbers of all three- and four-node subgraphs, in both directed and nondirected geometric networks. We also analyze geometric networks with arbitrary degree sequences and models with a bias for directed edges in one direction. Scaling rules for scaling of subgraph numbers with system size, lattice dimension, and interaction range are given. Several invariant measures are found, such as the ratio of feedback and feed-forward loops, which do not depend on system size, dimension, or connectivity function. We find that network motifs in many real-world networks, including social networks and neuronal networks, are not captured solely by these geometric models. This is in line with recent evidence that biological network motifs were selected as basic circuit elements with defined information-processing functions.

Kinetic theory of random graphs: from paths to cycles

The structural properties of evolving random graphs are investigated. Treating linking as a dynamic aggregation process, rate equations for the distribution of node to node distances (paths) and of cycles are formulated and solved analytically. At the gelation point, the typical length of paths and cycles, l , scales with the component size k as l approximately k(1/2) . Dynamic and finite-size scaling laws for the behavior at and near the gelation point are obtained. Finite-size scaling laws are verified using numerical simulations.

Cartography of complex networks: modules and universal roles

Integrative approaches to the study of complex systems demand that one knows the manner in which the parts comprising the system are connected. The structure of the complex network defining the interactions provides insight into the function and evolution of the components of the system. Unfortunately, the large size and intricacy of these networks implies that such insight is usually difficult to extract. Here, we propose a method that allows one to systematically extract and display information contained in complex networks. Specifically, we demonstrate that one can (i) find modules in complex networks and (ii) classify nodes into universal roles according to their pattern of within- and between-module connections. The method thus yields a 'cartographic representation' of complex networks.

Modelling development of epidemics with dynamic small-world networks

We discuss the dynamics of a minimal model for spreading of infectious diseases, such as various types of influenza. The spreading takes place on a dynamic small-world network and can be viewed as comprising short- and long-range spreading processes. We derive approximate equations for the epidemic threshold as well as the spreading dynamics, and show that there is a good agreement with numerical discrete time-step simulations. We then analyse the dependence of the epidemic saturation time on the initial conditions, and outline a possible method of utilizing the model in predicting the development of epidemics based on early figures of infected. Finally, we compare time series calculated with our model to real-world data.

Self-similar disk packings as model spatial scale-free networks

The network of contacts in space-filling disk packings, such as the Apollonian packing, is examined. These networks provide an interesting example of spatial scale-free networks, where the topology reflects the broad distribution of disk areas. A wide variety of topological and spatial properties of these systems is characterized. Their potential as models for networks of connected minima on energy landscapes is discussed.

Coarse-graining and self-dissimilarity of complex networks

Can complex engineered and biological networks be coarse-grained into smaller and more understandable versions in which each node represents an entire pattern in the original network? To address this, we define coarse-graining units as connectivity patterns which can serve as the nodes of a coarse-grained network and present algorithms to detect them. We use this approach to systematically reverse-engineer electronic circuits, forming understandable high-level maps from incomprehensible transistor wiring: first, a coarse-grained version in which each node is a gate made of several transistors is established. Then the coarse-grained network is itself coarse-grained, resulting in a high-level blueprint in which each node is a circuit module made of many gates. We apply our approach also to a mammalian protein signal-transduction network, to find a simplified coarse-grained network with three main signaling channels that resemble multi-layered perceptrons made of cross-interacting MAP-kinase cascades. We find that both biological and electronic networks are "self-dissimilar," with different network motifs at each level. The present approach may be used to simplify a variety of directed and nondirected, natural and designed networks.

Vulnerability and protection of infrastructure networks

Infrastructure systems are a key ingredient of modern society. We discuss a general method to find the critical components of an infrastructure network, i.e., the nodes and the links fundamental to the perfect functioning of the network. Such nodes, and not the most connected ones, are the targets to protect from terrorist attacks. The method, used as an improvement analysis, can also help to better shape a planned expansion of the network.

Networking genetic regulation and neural computation: directed network topology and its effect on the dynamics

Two different types of directed networks are investigated, transcriptional regulation networks and neural networks. The directed network structure is studied and is also shown to reflect the different processes taking place on the networks. The distribution of influence, identified as the the number of downstream vertices, are used as a tool for investigating random vertex removal. In the transcriptional regulation networks we observe that only a small number of vertices have a large influence. The small influences of most vertices limit the effect of a random removal to, in most cases, only a small fraction of vertices in the network. The neural network has a rather different topology with respect to the influence, which are large for most vertices. To further investigate the effect of vertex removal we simulate the biological processes taking place on the networks. Opposed to the presumed large effect of random vertex removal in the neural network, the high density of edges in conjunction with the dynamics used makes the change in the state of the system to be highly localized around the removed vertex.

Finding community structure in very large networks

The discovery and analysis of community structure in networks is a topic of considerable recent interest within the physics community, but most methods proposed so far are unsuitable for very large networks because of their computational cost. Here we present a hierarchical agglomeration algorithm for detecting community structure which is faster than many competing algorithms: its running time on a network with n vertices and m edges is O (md log n) where d is the depth of the dendrogram describing the community structure. Many real-world networks are sparse and hierarchical, with m approximately n and d approximately log n, in which case our algorithm runs in essentially linear time, O (n log(2) n). As an example of the application of this algorithm we use it to analyze a network of items for sale on the web site of a large on-line retailer, items in the network being linked if they are frequently purchased by the same buyer. The network has more than 400 000 vertices and 2 x 10(6) edges. We show that our algorithm can extract meaningful communities from this network, revealing large-scale patterns present in the purchasing habits of customers.

Detecting fuzzy community structures in complex networks with a Potts model

A fast community detection algorithm based on a q-state Potts model is presented. Communities (groups of densely interconnected nodes that are only loosely connected to the rest of the network) are found to coincide with the domains of equal spin value in the minima of a modified Potts spin glass Hamiltonian. Comparing global and local minima of the Hamiltonian allows for the detection of overlapping ("fuzzy") communities and quantifying the association of nodes with multiple communities as well as the robustness of a community. No prior knowledge of the number of communities has to be assumed.

Method to find community structures based on information centrality

Community structures are an important feature of many social, biological, and technological networks. Here we study a variation on the method for detecting such communities proposed by Girvan and Newman and based on the idea of using centrality measures to define the community boundaries [M. Girvan and M. E. J. Newman, Proc. Natl. Acad. Sci. U.S.A. 99, 7821 (2002)]. We develop an algorithm of hierarchical clustering that consists in finding and removing iteratively the edge with the highest information centrality. We test the algorithm on computer generated and real-world networks whose community structure is already known or has been studied by means of other methods. We show that our algorithm, although it runs to completion in a time O(n4) , is very effective especially when the communities are very mixed and hardly detectable by the other methods.

Models of social networks based on social distance attachment

We propose a class of models of social network formation based on a mathematical abstraction of the concept of social distance. Social distance attachment is represented by the tendency of peers to establish acquaintances via a decreasing function of the relative distance in a representative social space. We derive analytical results (corroborated by extensive numerical simulations), showing that the model reproduces the main statistical characteristics of real social networks: large clustering coefficient, positive degree correlations, and the emergence of a hierarchy of communities. The model is confronted with the social network formed by people that shares confidential information using the Pretty Good Privacy (PGP) encryption algorithm, the so-called web of trust of PGP.

Analysis of weighted networks

The connections in many networks are not merely binary entities, either present or not, but have associated weights that record their strengths relative to one another. Recent studies of networks have, by and large, steered clear of such weighted networks, which are often perceived as being harder to analyze than their unweighted counterparts. Here we point out that weighted networks can in many cases be analyzed using a simple mapping from a weighted network to an unweighted multigraph, allowing us to apply standard techniques for unweighted graphs to weighted ones as well. We give a number of examples of the method, including an algorithm for detecting community structure in weighted networks and a simple proof of the maximum-flow-minimum-cut theorem.

Analyzing cellular biochemistry in terms of molecular networks

One way to understand cells and circumscribe the function of proteins is through molecular networks. These networks take a variety of forms including webs of protein-protein interactions, regulatory circuits linking transcription factors and targets, and complex pathways of metabolic reactions. We first survey experimental techniques for mapping networks (e.g., the yeast two-hybrid screens). We then turn our attention to computational approaches for predicting networks from individual protein features, such as correlating gene expression levels or analyzing sequence coevolution. All the experimental techniques and individual predictions suffer from noise and systematic biases. These problems can be overcome to some degree through statistical integration of different experimental datasets and predictive features (e.g., within a Bayesian formalism). Next, we discuss approaches for characterizing the topology of networks, such as finding hubs and analyzing subnetworks in terms of common motifs. Finally, we close with perspectives on how network analysis represents a preliminary step toward a systems approach for modeling cells.

Scale-free trees: the skeletons of complex networks

We investigate the properties of the spanning trees of various real-world and model networks. The spanning tree representing the communication kernel of the original network is determined by maximizing the total weight of the edges, whose weights are given by the edge betweenness centralities. We find that a scale-free tree and shortcuts organize a complex network. Especially, in ubiquitous scale-free networks, it is found that the scale-free spanning tree shows very robust betweenness centrality distributions and the remaining shortcuts characterize the properties of the original network, such as the clustering coefficient and the classification of scale-free networks by the betweenness centrality distribution.

The interactome as a tree--an attempt to visualize the protein-protein interaction network in yeast

The refinement and high-throughput of protein interaction detection methods offer us a protein-protein interaction network in yeast. The challenge coming along with the network is to find better ways to make it accessible for biological investigation. Visualization would be helpful for extraction of meaningful biological information from the network. However, traditional ways of visualizing the network are unsuitable because of the large number of proteins. Here, we provide a simple but information-rich approach for visualization which integrates topological and biological information. In our method, the topological information such as quasi-cliques or spoke-like modules of the network is extracted into a clustering tree, where biological information spanning from protein functional annotation to expression profile correlations can be annotated onto the representation of it. We have developed a software named PINC based on our approach. Compared with previous clustering methods, our clustering method ADJW performs well both in retaining a meaningful image of the protein interaction network as well as in enriching the image with biological information, therefore is more suitable in visualization of the network.

Networking the seceder model: Group formation in social and economic systems

The seceder model illustrates how the desire to be different from the average can lead to formation of groups in a population. We turn the original, agent based, seceder model into a model of network evolution. We find that the structural characteristics of our model closely match empirical social networks. Statistics for the dynamics of group formation are also given. Extensions of the model to networks of companies are also discussed.

Modularity from fluctuations in random graphs and complex networks

The mechanisms by which modularity emerges in complex networks are not well understood but recent reports have suggested that modularity may arise from evolutionary selection. We show that finding the modularity of a network is analogous to finding the ground-state energy of a spin system. Moreover, we demonstrate that, due to fluctuations, stochastic network models give rise to modular networks. Specifically, we show both numerically and analytically that random graphs and scale-free networks have modularity. We argue that this fact must be taken into consideration to define statistically significant modularity in complex networks.

Design of a directed molecular network

An ability to rationally design complex networks from the bottom up can offer valuable quantitative model systems for use in gaining a deeper appreciation for the principles governing the self-organization and functional characteristics of complex systems. We report herein the de novo design, graph prediction, experimental analysis, and characterization of simple self-organized, nonlinear molecular networks. Our approach makes use of the sequence-dependent auto- and cross-catalytic functional characteristics of template-directed peptide fragment condensation reactions in neutral aqueous solutions. Starting with an array of 81 sequence similar 32-residue coiled-coil peptides, we estimated the relative stability difference between all plausible A(2)B-type coiled-coil ensembles and used this information to predict the auto- and cross-catalysis pathways and the resulting plausible network motif and connectivities. Similar to most complex systems, the generated graph displays clustered nodes with an overall hierarchical architecture. To test the validity of the design principles used, nine nodes composing a main segment of the graph were experimentally analyzed for their capacity in establishing the predicted network connectivity. The resulting self-organized chemical network is shown to display 25 directed edges in good agreement with the graph analysis estimations. Moreover, we show that by varying the system parameters (presence or absence of certain substrates or templates), its operating network motif can be altered, even to the extremes of turning pathways on or off. We suggest that this approach can be expanded for the construction of large-scale networks, offering a means to study and to understand better the emergent, collective behaviors of networks.

Fast algorithm for detecting community structure in networks

Many networks display community structure--groups of vertices within which connections are dense but between which they are sparser--and sensitive computer algorithms have in recent years been developed for detecting this structure. These algorithms, however, are computationally demanding, which limits their application to small networks. Here we describe an algorithm which gives excellent results when tested on both computer-generated and real-world networks and is much faster, typically thousands of times faster, than previous algorithms. We give several example applications, including one to a collaboration network of more than 50,000 physicists.

Networks, dynamics, and modularity

The identification of general principles relating structure to dynamics has been a major goal in the study of complex networks. We propose that the special case of linear network dynamics provides a natural framework within which a number of interesting yet tractable problems can be defined. We report the emergence of modularity and hierarchical organization in evolved networks supporting asymptotically stable linear dynamics. Numerical experiments demonstrate that linear stability benefits from the presence of a hierarchy of modules and that this architecture improves the robustness of network stability to random perturbations in network structure. This work illustrates an approach to network science which is simultaneously structural and dynamical in nature.

Edge vulnerability in neural and metabolic networks

Biological networks, such as cellular metabolic pathways or networks of corticocortical connections in the brain, are intricately organized, yet remarkably robust toward structural damage. Whereas many studies have investigated specific aspects of robustness, such as molecular mechanisms of repair, this article focuses more generally on how local structural features in networks may give rise to their global stability. In many networks the failure of single connections may be more likely than the extinction of entire nodes, yet no analysis of edge importance (edge vulnerability) has been provided so far for biological networks. We tested several measures for identifying vulnerable edges and compared their prediction performance in biological and artificial networks. Among the tested measures, edge frequency in all shortest paths of a network yielded a particularly high correlation with vulnerability and identified intercluster connections in biological but not in random and scale-free benchmark networks. We discuss different local and global network patterns and the edge vulnerability resulting from them.

Coauthorship networks and patterns of scientific collaboration

By using data from three bibliographic databases in biology, physics, and mathematics, respectively, networks are constructed in which the nodes are scientists, and two scientists are connected if they have coauthored a paper. We use these networks to answer a broad variety of questions about collaboration patterns, such as the numbers of papers authors write, how many people they write them with, what the typical distance between scientists is through the network, and how patterns of collaboration vary between subjects and over time. We also summarize a number of recent results by other authors on coauthorship patterns.

Gene duplication and hierarchical modularity in intracellular interaction networks

Networks of interactions evolve in many different domains. They tend to have topological characteristics in common, possibly due to common factors in the way the networks grow and develop. It has been recently suggested that one such common characteristic is the presence of a hierarchically modular organization. In this paper, we describe a new algorithm for the detection and quantification of hierarchical modularity, and demonstrate that the yeast protein-protein interaction network does have a hierarchically modular organization. We further show that such organization is evident in artificial networks produced by computational evolution using a gene duplication operator, but not in those developing via preferential attachment of new nodes to highly connected existing nodes.

Model for cascading failures in complex networks

Large but rare cascades triggered by small initial shocks are present in most of the infrastructure networks. Here we present a simple model for cascading failures based on the dynamical redistribution of the flow on the network. We show that the breakdown of a single node is sufficient to collapse the efficiency of the entire system if the node is among the ones with largest load. This is particularly important for real-world networks with a highly hetereogeneous distribution of loads as the Internet and electrical power grids.

Control of yeast filamentous-form growth by modules in an integrated molecular network

On solid growth media with limiting nitrogen source, diploid budding-yeast cells differentiate from the yeast form to a filamentous, adhesive, and invasive form. Genomic profiles of mRNA levels in Saccharomyces cerevisiae yeast-form and filamentous-form cells were compared. Disparate data types, including genes implicated by expression change, filamentation genes known previously through a phenotype, protein-protein interaction data, and protein-metabolite interaction data were integrated as the nodes and edges of a filamentation-network graph. Application of a network-clustering method revealed 47 clusters in the data. The correspondence of the clusters to modules is supported by significant coordinated expression change among cluster co-member genes, and the quantitative identification of collective functions controlling cell properties. The modular abstraction of the filamentation network enables the association of filamentous-form cell properties with the activation or repression of specific biological processes, and suggests hypotheses. A module-derived hypothesis was tested. It was found that the 26S proteasome regulates filamentous-form growth.

Defining and identifying communities in networks

The investigation of community structures in networks is an important issue in many domains and disciplines. This problem is relevant for social tasks (objective analysis of relationships on the web), biological inquiries (functional studies in metabolic and protein networks), or technological problems (optimization of large infrastructures). Several types of algorithms exist for revealing the community structure in networks, but a general and quantitative definition of community is not implemented in the algorithms, leading to an intrinsic difficulty in the interpretation of the results without any additional nontopological information. In this article we deal with this problem by showing how quantitative definitions of community are implemented in practice in the existing algorithms. In this way the algorithms for the identification of the community structure become fully self-contained. Furthermore, we propose a local algorithm to detect communities which outperforms the existing algorithms with respect to computational cost, keeping the same level of reliability. The algorithm is tested on artificial and real-world graphs. In particular, we show how the algorithm applies to a network of scientific collaborations, which, for its size, cannot be attacked with the usual methods. This type of local algorithm could open the way to applications to large-scale technological and biological systems.

Widespread occurrence of the inverse square distribution in social sciences and taxonomy

The widespread occurrence of an inverse square relation in the hierarchical distribution of subcommunities within communities (or subspecies within species) has been recently invoked as a signature of hierarchical self-organization within social and ecological systems. Here we show that, whether such systems are self-organized or not, this behavior is the consequence of the treelike classification method. Different treelike classifications (both of real and truly random systems) display a similar statistical behavior when considering the sizes of their sub-branches.