CiteULike: deanmalmgren's library [30 articles]

The Structure of Information Pathways in a Social Communication Network

Gueorgi Kossinets — 2008-06-22T06:04:17-00:00

(19 Jun 2008)

Social networks are of interest to researchers in part because they are thought to mediate the flow of information in communities and organizations. Here we study the temporal dynamics of communication using on-line data, including e-mail communication among the faculty and staff of a large university over a two-year period. We formulate a temporal notion of "distance" in the underlying social network by measuring the minimum time required for information to spread from one node to another -- a concept that draws on the notion of vector-clocks from the study of distributed computing systems. We find that such temporal measures provide structural insights that are not apparent from analyses of the pure social network topology. In particular, we define the network backbone to be the subgraph consisting of edges on which information has the potential to flow the quickest. We find that the backbone is a sparse graph with a concentration of both highly embedded edges and long-range bridges -- a finding that sheds new light on the relationship between tie strength and connectivity in social networks.

Reliability of genetic networks is evolvable

Stefan Braunewell — 2008-06-24T14:10:01-00:00

Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 77, No. 6. (2008)

Control of the living cell functions with remarkable reliability despite the stochastic nature of the underlying molecular networks—a property presumably optimized by biological evolution. We ask here to what extent the ability of a stochastic dynamical network to produce reliable dynamics is an evolvable trait. Using an evolutionary algorithm based on a deterministic selection criterion for the reliability of dynamical attractors, we evolve networks of noisy discrete threshold nodes. We find that, starting from any random network, reliability of the attractor landscape can often be achieved with only a few small changes to the network structure. Further, the evolvability of networks toward reliable dynamics while retaining their function is investigated and a high success rate is found.

Entropy Maximization in the Force Network Ensemble for Granular Solids

Brian Tighe — 2008-06-17T13:40:50-00:00

Physical Review Letters, Vol. 100, No. 23. (2008)

A long-standing issue in the area of granular media is the tail of the force distribution, in particular, whether this is exponential, Gaussian, or even some other form. Here we resolve the issue for the case of the force network ensemble in two dimensions. We demonstrate that conservation of the total area of a reciprocal tiling, a direct consequence of local force balance, is crucial for predicting the local stress distribution. Maximizing entropy while conserving the tiling area and total pressure leads to a distribution of local pressures with a generically Gaussian tail that is in excellent agreement with numerics, both with and without friction and for two different contact networks.

Is Turbulent Mixing a Self-Convolution Process?

Antoine Venaille — 2008-06-17T13:28:21-00:00

Physical Review Letters, Vol. 100, No. 23. (2008)

Experimental results for the evolution of the probability distribution function (PDF) of a scalar mixed by a turbulent flow in a channel are presented. The sequence of PDF from an initial skewed distribution to a sharp Gaussian is found to be nonuniversal. The route toward homogeneization depends on the ratio between the cross sections of the dye injector and the channel. In connection with this observation, advantages, shortcomings, and applicability of models for the PDF evolution based on a self-convolution mechanism are discussed.

Anticipatory Behavior Within Microbial Genetic Networks

Ilias Tagkopoulos — 2008-05-08T21:24:02-00:00

Science (8 May 2008), 1154456.

We question whether homeostasis alone adequately explains microbial responses to environmental stimuli, and explore the capacity of intra-cellular networks for predictive behavior in a fashion similar to metazoan nervous systems. We show that in silico biochemical networks, evolving randomly under precisely defined complex habitats, capture the dynamical, multi-dimensional structure of diverse environments by forming internal models that allow prediction of environmental change. We provide evidence for such anticipatory behavior by revealing striking correlations of Escherichia coli transcriptional responses to temperature and oxygen perturbations--precisely mirroring the co-variation of these parameters upon transitions between the outside world and the mammalian gastrointestinal-tract. We further show that these internal correlations reflect a true associative learning paradigm, since they show rapid de-coupling upon exposure to novel environments. 10.1126/science.1154456

Optimal partition and effective dynamics of complex networks.

Weinan E — 2008-02-29T09:21:03-00:00

Proc Natl Acad Sci U S A (26 February 2008)

Given a large and complex network, we would like to find the best partition of this network into a small number of clusters. This question has been addressed in many different ways. Here we propose a strategy along the lines of optimal prediction for the Markov chains associated with the dynamics on these networks. We develop the necessary ingredients for such an optimal partition strategy, and we compare our strategy with the previous ones. We show that when the Markov chain is lumpable, we recover the partition with respect to which the chain is lumpable. We also discuss the case of well-clustered networks. Finally, we illustrate our strategy on several examples.

New benchmark in community detection

Andrea Lancichinetti — 2008-06-02T15:41:19-00:00

(30 May 2008)

Community structure is one of the most important features of real networks and reveals the internal organization of the nodes as well as their mutual similarity. Many algorithms have been proposed but the crucial issue of testing, i.e. the question of how good an algorithm is, with respect to others, is still open. Standard tests include the analysis of simple artificial graphs with a built-in community structure, that the algorithm has to recover. However, the special graphs adopted in actual tests have a structure that does not reflect the real properties of nodes and communities found in real networks. Here we introduce a new class of benchmark graphs, that account for the heterogeneity in the distributions of node degrees and of community sizes. We use this new benchmark to test the most popular method of community detection, i.e. modularity optimization. The results show that the new benchmark poses a much more severe test to algorithms than standard benchmarks, revealing limits that may not be apparent at a first analysis.

A flood of hard data

2008-06-05T03:03:58-00:00

Nature, Vol. 453, No. 7196. (5 June 2008), pp. 698-698.

Understanding individual human mobility patterns

Marta Gonzalez — 2008-06-04T19:02:19-00:00

Nature, Vol. 453, No. 7196. (5 June 2008), pp. 779-782.

Modularity of stress response evolution

Amoolya Singh — 2008-06-02T15:48:51-00:00

Proceedings of the National Academy of Sciences, Vol. 105, No. 21. (27 May 2008), pp. 7500-7505.

Responses to extracellular stress directly confer survival fitness by means of complex regulatory networks. Despite their complexity, the networks must be evolvable because of changing ecological and environmental pressures. Although the regulatory networks underlying stress responses are characterized extensively, their mechanism of evolution remains poorly understood. Here, we examine the evolution of three candidate stress response networks (chemotaxis, competence for DNA uptake, and endospore formation) by analyzing their phylogenetic distribution across several hundred diverse bacterial and archaeal lineages. We report that genes in the chemotaxis and sporulation networks group into well defined evolutionary modules with distinct functions, phenotypes, and substitution rates as compared with control sets of randomly chosen genes. The evolutionary modules vary in both number and cohesiveness among the three pathways. Chemotaxis has five coherent modules whose distribution among species shows a clear pattern of interdependence and rewiring. Sporulation, by contrast, is nearly monolithic and seems to be inherited vertically, with three weak modules constituting early and late stages of the pathway. Competence does not seem to exhibit well defined modules either at or below the pathway level. Many of the detected modules are better understood in engineering terms than in protein functional terms, as we demonstrate using a control-based ontology that classifies gene function according to roles such as "sensor," "regulator," and "actuator." Moreover, we show that combinations of the modules predict phenotype, yet surprisingly do not necessarily correlate with phylogenetic inheritance. The architectures of these three pathways are therefore emblematic of different modes and constraints on evolution. 10.1073/pnas.0709764105

Synchronization in complex networks

Alex Arenas — 2008-05-21T13:03:07-00:00

(19 May 2008)

Synchronization processes in populations of locally interacting elements are in the focus of intense research in physical, biological, chemical, technological and social systems. The many efforts devoted to understand synchronization phenomena in natural systems take now advantage of the recent theory of complex networks. In this review, we report the advances in the comprehension of synchronization phenomena when oscillating elements are constrained to interact in a complex network topology. We also overview the new emergent features coming out from the interplay between the structure and the function of the underlying pattern of connections. Extensive numerical work as well as analytical approaches to the problem are presented. Finally, we review several applications of synchronization in complex networks to different disciplines: biological systems and neuroscience, engineering and computer science, and economy and social sciences.

Graphlet Arrival: Modeling and verifying a broad array of network properties

Zachary Saul — 2008-05-21T13:01:23-00:00

(12 May 2008)

Motivated by widely observed examples in nature, society and software, where groups of already related nodes arrive together and attach to an existing network, we consider network growth via sequential attachment of linked node groups, or graphlets. We analyze the simplest case, attachment of the three node V-graphlet, where, with probability alpha, we attach a peripheral node of the graphlet, and with probability (1-alpha), we attach the central node. Our analytical results and simulations show that tuning alpha produces a wide range in degree distribution and degree assortativity, achieving assortativity values that capture a diverse set of many real-world systems. We introduce a fifteen-dimensional attribute vector derived from seven well-known network properties, which enables comprehensive comparison between any two networks. Principal Component Analysis (PCA) of this attribute vector space shows a significantly larger coverage potential of real-world network properties by a simple extension of the above model when compared against a classic model of network growth.

A comparative evolutionary study of transcription networks

AL Sellerio — 2008-05-16T12:36:11-00:00

(15 May 2008)

We present a comparative analysis of large-scale topological and evolutionary properties of transcription networks in three species, the two distant bacteria E. coli and B. subtilis, and the yeast S. cerevisiae. The study focuses on the global aspects of feedback and hierarchy in transcriptional regulatory pathways. While confirming that gene duplication has a significant impact on the shaping of all the analyzed transcription networks, our results point to distinct trends between the bacteria, where time constraints in the transcription of downstream genes might be important in shaping the hierarchical structure of the network, and yeast, which seems able to sustain a higher wiring complexity, that includes the more feedback, intricate hierarchy, and the combinatorial use of heterodimers made of duplicate transcription factors.

Robustness of networks against fluctuation-induced cascading failures

Dominik Heide — 2008-05-18T13:06:28-00:00

Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 77, No. 5. (2008)

Fluctuating fluxes on a complex network lead to load fluctuations at the vertices, which may cause them to become overloaded and to induce a cascading failure. A characterization of the one-point load fluctuations is presented, revealing their dependence on the nature of the flux fluctuations and on the underlying network structure. Based on these findings, an alternate robustness layout of the network is proposed. Taking load correlations between the vertices into account, an analytical prediction of the probability for the network to remain fully efficient is confirmed by simulations. Compared to previously proposed mean-flux layouts, the alternate layout comes with significantly less investment costs in the high-confidence limit.

From the Cover: Quorum decision-making facilitates information transfer in fish shoals

Ashley Ward — 2008-05-14T13:48:38-00:00

Proceedings of the National Academy of Sciences, Vol. 105, No. 19. (13 May 2008), pp. 6948-6953.

Despite the growing interest in collective phenomena such as "swarm intelligence" and "wisdom of the crowds," little is known about the mechanisms underlying decision-making in vertebrate animal groups. How do animals use the behavior of others to make more accurate decisions, especially when it is not possible to identify which individuals possess pertinent information? One plausible answer is that individuals respond only when they see a threshold number of individuals perform a particular behavior. Here, we investigate the role of such "quorum responses" in the movement decisions of fish (three-spine stickleback, Gasterosteus aculeatus). We show that a quorum response to conspecifics can explain how sticklebacks make collective movement decisions, both in the absence and presence of a potential predation risk. Importantly our experimental work shows that a quorum response can reduce the likelihood of amplification of nonadaptive following behavior. Whereas the traveling direction of solitary fish was strongly influenced by a single replica conspecific, the replica was largely ignored by larger groups of four or eight sticklebacks under risk, and the addition of a second replica was required to exert influence on the movement decisions of such groups. Model simulations further predict that quorum responses by fish improve the accuracy and speed of their decision-making over that of independent decision-makers or those using a weak linear response. This study shows that effective and accurate information transfer in groups may be gained only through nonlinear responses of group members to each other, thus highlighting the importance of quorum decision-making. 10.1073/pnas.0710344105

The evolution of modularity in bacterial metabolic networks

Anat Kreimer — 2008-05-07T00:59:12-00:00

Proceedings of the National Academy of Sciences (6 May 2008), 0712149105.

Deciphering the modular organization of metabolic networks and understanding how modularity evolves have attracted tremendous interest in recent years. Here, we present a comprehensive large scale characterization of modularity across the bacterial tree of life, systematically quantifying the modularity of the metabolic networks of >300 bacterial species. Three main determinants of metabolic network modularity are identified. First, network size is an important topological determinant of network modularity. Second, several environmental factors influence network modularity, with endosymbionts and mammal-specific pathogens having lower modularity scores than bacterial species that occupy a wider range of niches. Moreover, even among the pathogens, those that alternate between two distinct niches, such as insect and mammal, tend to have relatively high metabolic network modularity. Third, horizontal gene transfer is an important force that contributes significantly to metabolic modularity. We additionally reconstruct the metabolic network of ancestral bacterial species and examine the evolution of modularity across the tree of life. This reveals a trend of modularity decrease from ancestors to descendants that is likely the outcome of niche specialization and the incorporation of peripheral metabolic reactions. 10.1073/pnas.0712149105

A truer measure of our ignorance

Luis Amaral — 2008-05-16T16:20:29-00:00

Proceedings of the National Academy of Sciences, Vol. 105, No. 19. (13 May 2008), pp. 6795-6796.

10.1073/pnas.0802459105

A model for interevent times with long tails and multifractality in human communications: An application to financial trading

J Perello — 2008-05-13T14:03:08-00:00

(9 May 2008)

Social, technological and economic time series are divided by events which are usually assumed to be random albeit with some hierarchical structure. It is well known that the interevent statistics observed in these contexts differs from the Poissonian profile being long-tailed distributed with resting and active periods interwoven. Understanding mechanisms generating consistent statistics have become a central issue. The approach we present is taken from the Continuous Time Random Walk formalism and represents an analytical alternative to mechanisms of non-trivial priority that have been recently proposed. Our analysis also goes one step further by looking at the multifractal structure of the interevent times of human decisions. We here analyze the inter-transaction time intervals of several financial markets. We observe that empirics describes a subtle multifractal behavior. Our model explains this structure by taking the pausing-time density in the form of a superstatistics where the integral kernel quantifies the heterogeneous nature of the executed tasks. An stretched exponential kernel provides a multifractal profile valid for a certain limited range. A suggested heuristic analytical profile is capable of covering a broader region.

Statistical Analysis of the Metropolitan Seoul Subway System: Network Structure and Passenger Flows

Keumsook Lee — 2008-05-13T14:00:14-00:00

(12 May 2008)

The Metropolitan Seoul Subway system, consisting of 380 stations, provides the major transportation mode in the metropolitan Seoul area. Focusing on the network structure, we analyze statistical properties and topological consequences of the subway system. We further study the passenger flows on the system, and find that the flow weight distribution exhibits a power-law behavior. In addition, the degree distribution of the spanning tree of the flows also follows a power law.

Transport in networks with multiple sources and sinks

Shai Carmi — 2008-05-13T13:56:03-00:00

(12 May 2008)

We study the electrical current and flow (number of parallel paths) between two sets of n sources and n sinks in complex networks. We derive analytical formulas for the change in current and flow as a function of n. We show that for small n, increasing n improves the total transport in the network, while for large n bottlenecks begin to form. For the case of flow, this leads to an optimal n* above which the transport is less efficient. For current, the typical decrease in the length of the connecting paths for large n compensates for the effect of the bottlenecks. Finally we show that for the common case where the transport takes place between specific pairs of sources and sinks, a percolation approach can be applied to calculate the total flow and predict the number of sources/sinks above which the network saturates and can carry no more flow.

A General Model for Food Web Structure

Stefano Allesina — 2008-05-02T18:35:54-00:00

Science, Vol. 320, No. 5876. (2 May 2008), pp. 658-661.

A central problem in ecology is determining the processes that shape the complex networks known as food webs formed by species and their feeding relationships. The topology of these networks is a major determinant of ecosystems' dynamics and is ultimately responsible for their responses to human impacts. Several simple models have been proposed for the intricate food webs observed in nature. We show that the three main models proposed so far fail to fully replicate the empirical data, and we develop a likelihood-based approach for the direct comparison of alternative models based on the full structure of the network. Results drive a new model that is able to generate all the empirical data sets and to do so with the highest likelihood. 10.1126/science.1156269

Power-law distributions in empirical data

Aaron Clauset — 2007-06-13T16:25:35-00:00

(7 Jun 2007)

Power-law distributions occur in many situations of scientific interest and have significant consequences for our understanding of natural and man-made phenomena. Unfortunately, the empirical detection and characterization of power laws is made difficult by the large fluctuations that occur in the tail of the distribution. In particular, standard methods such as least-squares fitting are known to produce systematically biased estimates of parameters for power-law distributions and should not be used in most circumstances. Here we describe statistical techniques for making accurate parameter estimates for power-law data, based on maximum likelihood methods and the Kolmogorov-Smirnov statistic. We also show how to tell whether the data follow a power-law distribution at all, defining quantitative measures that indicate when the power law is a reasonable fit to the data and when it is not. We demonstrate these methods by applying them to twenty-four real-world data sets from a range of different disciplines. Each of the data sets has been conjectured previously to follow a power-law distribution. In some cases we find these conjectures to be consistent with the data while in others the power law is ruled out.

Laws, power laws and statistics

Mark Buchanan — 2008-05-02T17:06:32-00:00

Nat Phys, Vol. 4, No. 5. (May 2008), pp. 339-339.

A Self-organized model for network evolution

Guido Caldarelli — 2008-05-05T12:58:45-00:00

(2 May 2008)

Here we provide a detailed analysis, along with some extensions and additonal investigations, of a recently proposed self-organised model for the evolution of complex networks. Vertices of the network are characterised by a fitness variable evolving through an extremal dynamics process, as in the Bak-Sneppen model representing a prototype of Self-Organized Criticality. The network topology is in turn shaped by the fitness variable itself, as in the fitness network model. The system self-organizes to a nontrivial state, characterized by a power-law decay of dynamical and topological quantities above a critical threshold. The interplay between topology and dynamics in the system is the key ingredient leading to an unexpected behaviour of these quantities.

Robustness of community structure in networks

Brian Karrer — 2008-05-03T13:13:39-00:00

Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 77, No. 4. (2008)

The discovery of community structure is a common challenge in the analysis of network data. Many methods have been proposed for finding community structure, but few have been proposed for determining whether the structure found is statistically significant or whether, conversely, it could have arisen purely as a result of chance. In this paper we show that the significance of community structure can be effectively quantified by measuring its robustness to small perturbations in network structure. We propose a suitable method for perturbing networks and a measure of the resulting change in community structure and use them to assess the significance of community structure in a variety of networks, both real and computer generated.

Hierarchical structure and the prediction of missing links in networks

Aaron Clauset — 2008-04-30T19:31:59-00:00

Nature, Vol. 453, No. 7191., pp. 98-101.

Theory of aces: high score by skill or luck?

MV Simkin — 2006-07-18T15:24:43-00:00

(12 Jul 2006)

We studied the distribution of WWI fighter pilots by the number of victories they were credited with along with casualty reports. Using the maximum entropy method we obtained the underlying distribution of pilots by their skill. We find that the variance of this skill distribution is not very large, and that the top aces achieved their victory scores mostly by luck. For example, the ace of aces, Manfred von Richthofen, most likely had a skill in the top 29% of the active WWI German fighter pilots, and was no more special than that. When combined with our recent study (<a href="/abs/cond-mat/0310049">cond-mat/0310049</a>), showing that fame grows exponentially with victory scores, these results (derived from real data) show that both outstanding achievement records and resulting fame are mostly due to chance.

GEOSCIENCE: Natural Complexity

Nicholas Watkins — 2008-04-18T08:00:22-00:00

Science, Vol. 320, No. 5874. (18 April 2008), pp. 323-324.

10.1126/science.1151611

MATHEMATICS: Frustration in Complexity

PM Binder — 2008-04-18T07:59:47-00:00

Science, Vol. 320, No. 5874. (18 April 2008), pp. 322-323.

10.1126/science.1156940

Voter models on heterogeneous networks

V Sood — 2008-04-28T17:35:05-00:00

Physical Review E (Statistical, Nonlinear, and Soft Matter Physics), Vol. 77, No. 4. (2008)

We study simple interacting particle systems on heterogeneous networks, including the voter model and the invasion process. These are both two-state models in which in an update event an individual changes state to agree with a neighbor. For the voter model, an individual “imports” its state from a randomly chosen neighbor. Here the average time TN to reach consensus for a network of N nodes with an uncorrelated degree distribution scales as Nµ12" align="middle">/µ2, where µk is the kth moment of the degree distribution. Quick consensus thus arises on networks with broad degree distributions. We also identify the conservation law that characterizes the route by which consensus is reached. Parallel results are derived for the invasion process, in which the state of an agent is “exported” to a random neighbor. We further generalize to biased dynamics in which one state is favored. The probability for a single fitter mutant located at a node of degree k to overspread the population—the fixation probability—is proportional to k for the voter model and to 1/k for the invasion process.