"We investigate higher-order Voronoi diagrams in the city metric. This metric is induced by quickest paths in the L1 metric in the presence of an accelerating transportation network of axis-parallel line segments. …"

"Network coding is studied when an adversary controls a subset of nodes in the network of limited quantity but unknown location. This problem is shown to be more difficult than when the adversary controls a given number of edges in the network, in that linear codes are insufficient. To solve the node problem, the class of Polytope Codes is introduced. Polytope Codes are constant composition codes operating over bounded polytopes in integer vector fields. The polytope structure creates additional complexity, but it induces properties on marginal distributions of code vectors so that validities of codewords can be checked by internal nodes of the network. It is shown that Polytope Codes achieve a cut-set bound for a class of planar networks. It is also shown that this cut-set bound is not always tight, and a tighter bound is given for an example network."

"We proposed two new exact algorithms to detect network motifs of size 3 and 4. Considering that motifs need to count the isomorphic patterns in the original graph $G(V,E)$ and in a set of randomized graphs, the following complexities concern about count isomorphic patterns in a single graph. Let $m=|E|$ and let $a(G)$ be the arboricity of $G$. Assume $|E|geq|V|$. We describe a $O(a(G)m)$ time complexity algorithm to count isomorphic patterns of size 3. The complexity is a $O({msqrt{m}})$ in the worst graph. The second algorithm is a $O(m^2)$ complexity algorithm to count isomorphic patterns of size 4. The final result was expressive faster when compared with other implemented algorithms."

"In this paper, we study the consensus problem of multiple agents on a kind of famous graph, Peterson graph. It is an undirected graph with 10 vertices and 15 edges. Each agent randomly walks on this graph and communicates with each other if and only if they coincide on a node at the same time. We conduct numerical study on the consensus problem in this framework and show that global consensus can be achieved."

"In this paper we define what we call an affinity system, which is a set of individuals, each with a vector characterizing its preference for all other individuals in the set. The preference of a member can be given either by a ranking of all members or by a weighted vector that defines the degrees of its affinity to others. Affinity systems are useful for modeling social systems as well as general data sets, as social interactions are often determined by affinities among the members. We also define a natural notion of (potentially overlapping) communities in an affinity system, in which the members of a given community collectively prefer each other to anyone else outside the community. Thus these communities are "self-determined" or "self-certified" by the affinity system. We provide a tight polynomial bound on the number of self-determined communities as a function of the robustness of the community. Moreover, we present a polynomial-time algorithm for enumerating these communities, as well as a local algorithm with a strong stochastic performance guarantee that can find a community in time nearly linear in the of size the community.…"

"In a recent paper, we analyzed the self-assembly of a complex cooperation network. The network was shown to approach a state, where every agent invests the same amount of resources. Nevertheless, highly-connected agents arise that extract extra-ordinarily high payoffs while contributing comparably little to any of their cooperations. Here, we investigate a variant of the model, in which highly-connected agents have access to additional resources. We study analytically and numerically whether these resources are invested in existing collaborations, leading to a fairer load distribution, or in establishing new collaborations, leading to an even less fair distribution of loads and payoffs."

Many algorithms have been proposed for predicting missing edges in networks, but they do not usually take account of which edges are missing. We focus on networks which have missing edges of the form that is likely to occur in real networks, and compare algorithms that find these missing edges. We also investigate the effect of this kind of missing data on community detection algorithms.

A community of agents is subject to a stream of messages, which are represented as points on a plane of issues. Messages are sent by media and by agents themselves. Messages from media shape the public opinion. They are unbiased, i.e. positive and negative opinions on a given issue appear with equal frequencies. In our previous work, the only criterion to receive a message by an agent is if the distance between this message and the ones received earlier does not exceed the given value of the tolerance parameter. Here we introduce a possibility to address a message to a given neighbour. We show that this option reduces the unanimity effect, what improves the collective performance.

We propose a nonlinear voter model to study the emergence of global consensus in opinion dynamics. In our model, agent $i$ agrees with one of binary opinions with the probability that is a power function of the number of agents holding this opinion among agent $i$ and its nearest neighbors, where an adjustable parameter $alpha$ controls the effect of herd behavior on consensus. We find that there exists an optimal value of $alpha$ leading to the fastest consensus for lattices, random graphs, small-world networks and scale-free networks. Qualitative insights are obtained by examining the spatiotemporal evolution of the opinion clusters.

"Optimal power flow (OPF) is an important problem for power generation and it is in general non-convex. With the employment of renewable energy, it will be desirable if OPF can be solved very efficiently so its solution can be used in real time. With some special network structure, e.g. trees, the problem has been shown to have a zero duality gap and the convex dual problem yields the optimal solution. In this paper, we propose a primal and a dual algorithm to coordinate the smaller subproblems decomposed from the convexified OPF. We can arrange the subproblems to be solved sequentially and cumulatively in a central node or solved in parallel in distributed nodes. We test the algorithms on IEEE radial distribution test feeders, some random tree-structured networks, and the IEEE transmission system benchmarks. Simulation results show that the computation time can be improved dramatically with our algorithms over the centralized approach of solving the problem without decomposition, especially in tree-structured problems. The computation time grows linearly with the problem size with the cumulative approach while the distributed one can have size-independent computation time."

"We consider in this paper top-k query answering in social tagging systems, also known as folksonomies. This problem requires a significant departure from existing, socially agnostic techniques. In a network-aware context, one can (and should) exploit the social links, which can indicate how users relate to the seeker and how much weight their tagging actions should have in the result build-up. We propose an algorithm that has the potential to scale to current applications. While the problem has already been considered in previous literature, this was done either under strong simplifying assumptions or under choices that cannot scale to even moderate-size real world applications. We first consider a key aspect of the problem, which is accessing the closest or most relevant users for a given seeker. We describe how this can be done on the fly (without any pre-computations) for several possible choices - arguably the most natural ones - of proximity computation in a user network. Based on this, our top-k algorithm is sound and complete, while addressing the scalability issues of the existing ones. Importantly, our technique is instance optimal in the case when the search relies exclusively on the social weight of tagging actions. To further reduce response times, we then consider directions for efficiency by approximation. Extensive experiments on real world data show that our techniques can drastically improve the response time, without sacrificing precision."

"Disease awareness in infection dynamics can be modeled with adaptive contact networks whose rewiring rules reflect the attempt by susceptibles to avoid infectious contacts. Simulations of this type of models show an active phase with constant infected node density in which the interplay of disease dynamics and link rewiring prompts the convergence towards a well defined degree distribution, irrespective of the initial network topology. We develop a method to study this dynamic equilibrium and give an analytic description of the structure of the characteristic degree distributions and other network measures. The method applies to a broad class of systems and can be used to determine the steady-state topology of many other adaptive networks."

"The “performativity thesis” is the claim that parts of contemporary economics and finance, when carried out into the world by professionals and popularizers, reformat and reorganize the phenomena they purport to describe, in ways that bring the world into line with theory. Practical technologies, calculative devices and portable algorithms give actors tools to implement particular models of action. I argue that social network analysis is performative in the same sense as the cases studied in this literature. Social network analysis and finance theory are similar in key aspects of their development and effects. For the case of economics, evidence for weaker versions of the performativity thesis in quite good, and the strong formulation is circumstantially supported. Network theory easily meets the evidential threshold for the weaker versions; I offer empirical examples that support the strong (or “Barnesian”) formulation. Whether these parallels are a mark in favor of the thesis or a strike against it is an open question. I argue that the social network technologies and models now being “performed” build out systems of generalized reciprocity, connectivity, and commons-based production. This is in contrast both to an earlier network imagery that emphasized self-interest and entrepreneurial exploitation of structural opportunities, and to the model of action typically considered to be performed by economic technologies."

"Biology presents many examples of planar distribution and structural networks having dense sets of closed loops. An archetype of this form of network organization is the vasculature of dicotyledonous leaves, which showcases a hierarchically-nested architecture containing closed loops at many different levels. Although a number of methods have been proposed to measure aspects of the structure of such networks, a robust metric to quantify their hierarchical organization is still lacking. We present an algorithmic framework, the hierarchical loop decomposition, that allows mapping loopy networks to binary trees, preserving in the connectivity of the trees the architecture of the original graph. We apply this framework to investigate computer generated graphs, such as artificial models and optimal distribution networks, as well as natural graphs extracted from digitized images of dicotyledonous leaves and vasculature of rat cerebral neocortex. We calculate various metrics based on the Asymmetry, the cumulative size distribution and the Strahler bifurcation ratios of the corresponding trees and discuss the relationship of these quantities to the architectural organization of the original graphs. This algorithmic framework decouples the geometric information (exact location of edges and nodes) from the metric topology (connectivity and edge weight) and it ultimately allows us to perform a quantitative statistical comparison between predictions of theoretical models and naturally occurring loopy graphs."

"Network or graph structures are ubiquitous in the study of complex systems. Often, we are interested in complexity trends of these system as it evolves under some dynamic. An example might be looking at the complexity of a food web as species enter an ecosystem via migration or speciation, and leave via extinction.

In a previous paper, a complexity measure of networks was proposed based on the {em complexity is information content} paradigm. To apply this paradigm to any object, one must fix two things: a representation language, in which strings of symbols from some alphabet describe, or stand for the objects being considered; and a means of determining when two such descriptions refer to the same object. With these two things set, the information content of an object can be computed in principle from the number of equivalent descriptions describing a particular object.

The previously proposed representation language had the deficiency that the fully connected and empty networks were the most complex for a given number of nodes. A variation of this measure, called zcomplexity, applied a compression algorithm to the resulting bitstring representation, to solve this problem. Unfortunately, zcomplexity proved too computationally expensive to be practical.
In this paper, I propose a new representation language that encodes the number of links along with the number of nodes and a representation of the linklist. This, like zcomplexity, exhibits minimal complexity for fully connected and empty networks, but is as tractable as the original measure."

"This paper addresses weight optimization problem in distributed consensus averaging algorithm over networks with symmetric star topology. We have determined optimal weights and convergence rate of the network in terms of its topological parameters. In addition, two alternative topologies with more rapid convergence rates have been introduced. The new topologies are Complete-Cored Symmetric (CCS) star and K-Cored Symmetric (KCS) star topologies. It has been shown that the optimal weights for the edges of central part in symmetric and CCS star configurations are independent of their branches. By simulation optimality of obtained weights under quantization constraints have been verified."

"This article examines the relationship between acquaintanceship and coauthorship patterns in a multi-disciplinary, multi-institutional, geographically distributed research center. Two social networks are constructed and compared: a network of coauthorship, representing how researchers write articles with one another, and a network of acquaintanceship, representing how those researchers know each other on a personal level, based on their responses to an online survey. Statistical analyses of the topology and community structure of these networks point to the importance of small-scale, local, personal networks predicated upon acquaintanceship for accomplishing collaborative work in scientific communities."

"Using the Arts & Humanities Citation Index (A&HCI) 2008, we apply mapping techniques previously developed for mapping journal structures in the Science and Social Science Citation Indices. Citation relations among the 110,718 records were aggregated at the level of 1,157 journals specific to the A&HCI, and the journal structures are questioned on whether a cognitive structure can be reconstructed and visualized. Both cosine-normalization (bottom up) and factor analysis (top down) suggest a division into approximately twelve subsets. The relations among these subsets are explored using various visualization techniques. However, we were not able to retrieve this structure using the ISI Subject Categories, including the 25 categories which are specific to the A&HCI. We discuss options for validation such as against the categories of the Humanities Indicators of the American Academy of Arts and Sciences, the panel structure of the European Reference Index for the Humanities (ERIH), and compare our results with the curriculum organization of the Humanities Section of the College of Letters and Sciences of UCLA as an example of institutional organization."

"…We compare our algorithm with six state-of-the-art routing algorithms coming from the telecommunications and machine learning fields. The algorithms' performance is evaluated over a set of realistic testbeds. We run many experiments over real and artificial IP datagram networks with increasing number of nodes and under several paradigmatic spatial and temporal traffic distributions. Results are very encouraging. AntNet showed superior performance under all the experimental conditions with respect to its competitors. We analyze the main characteristics of the algorithm and try to explain the reasons for its superiority."

"We consider the problem of locating a black hole in synchronous anonymous networks using finite state agents. A black hole is a harmful node in the network that destroys any agent visiting that node without leaving any trace. The objective is to locate the black hole without destroying too many agents. This is difficult to achieve when the agents are initially scattered in the network and are unaware of the location of each other. Previous studies for black hole search used more powerful models where the agents had non-constant memory, were labelled with distinct identifiers and could either write messages on the nodes of the network or mark the edges of the network. In contrast, we solve the problem using a small team of finite-state agents each carrying a constant number of identical tokens that could be placed on the nodes of the network. Thus, all resources used in our algorithms are independent of the network size. We restrict our attention to oriented torus networks and first show that no finite team of finite state agents can solve the problem in such networks, when the tokens are not movable. In case the agents are equipped with movable tokens, we determine lower bounds on the number of agents and tokens required for solving the problem in torus networks of arbitrary size. Further, we present a deterministic solution to the black hole search problem for oriented torus networks, using the minimum number of agents and tokens."

"We consider a network of coupled agents playing the Prisoner's Dilemma game, in which players are allowed to pick a strategy in the interval [0,1], with 0 corresponding to defection, 1 to cooperation, and intermediate values representing mixed strategies in which each player may act as a cooperator or a defector over a large number of interactions with a certain probability. Our model is payoff-driven, i.e., we assume that the level of accumulated payoff at each node is a relevant parameter in the selection of strategies. Also, we consider that each player chooses his/her strategy in a context of limited information. We present a deterministic nonlinear model for the evolution of strategies. We show that the final strategies depend on the network structure and on the choice of the parameters of the game. We find that polarized strategies (pure cooperator/defector states) typically emerge when (i) the network connections are sparse, (ii) the network degree distribution is heterogeneous, (iii) the network is assortative, and surprisingly, (iv) the benefit of cooperation is high."

"We study a networked version of the minority game in which agents can choose to follow the choices made by a neighbouring agent in a social network. We show that for a wide variety of networks a leadership structure always emerges, with most agents following the choice made by a few agents. We find a suitable parameterisation which highlights the universal aspects of the behaviour and which also indicates where results depend on the type of social network."

"An effective procedure to determine the optimal parameters appearing in artificial flockings is proposed in terms of optimization problems. We numerically examine genetic algorithms (GAs) to determine the optimal set of parameters such as the weights for three essential interactions in BOIDS by Reynolds (1987) under `zero-collision' and `no-breaking-up' constraints. As a fitness function (the energy function) to be maximized by the GA, we choose the so-called the $gamma$-value of anisotropy which can be observed empirically in typical flocks of starling. We confirm that the GA successfully finds the solution having a large $gamma$-value leading-up to a strong anisotropy. The numerical experience shows that the procedure might enable us to make more realistic and efficient artificial flocking of starling even in our personal computers. We also evaluate two distinct types of interactions in agents, namely, metric and topological definitions of interactions. We confirmed that the topological definition can explain the empirical evidence much better than the metric definition does."

"They leave us with some strong statements and suggestions:

A private foundation clearly has the legal right to spend money however it wishes within the limits of the law; yet, in an environment where private foundations influence the future direction of, for example, what programs will be introduced into a foreign community, in a manner that does not necessarily involve directorship or voting from the community members themselves, it is reasonable to subject the decision-making processes of these entities to public debate, especially if these funds were to have otherwise been collected for public redistribution through federal taxation."

"We understand the dynamics of the world around us as by associating pairs of events, where one event has some influence on the other. These pairs of events can be aggregated into a web of memories representing our understanding of an episode of history. The events and the associations between them need not be directly experienced-they can also be acquired by communication. In this paper we take a network approach to study the dynamics of memories of history. First we investigate the network structure of a data set consisting of reported events by several individuals and how associations connect them. We focus our measurement on degree distributions, degree correlations, cycles (which represent inconsistencies as they would break the time ordering) and community structure.…"

"We consider problems of Bayesian inference for a spatial epidemic on a graph, where the final state of the epidemic corresponds to bond percolation, and where only the set or number of finally infected sites is observed. We develop appropriate Markov chain Monte Carlo algorithms, demonstrating their effectiveness, and we study problems of optimal experimental design. In particular, we demonstrate that for lattice-based processes an experiment on a sparsified lattice can yield more information on model parameters than one conducted on a complete lattice. We also prove some probabilistic results about the behaviour of estimators associated with large infected clusters."

"Zipf's law seems to be ubiquitous in human languages and appears to be a universal property of complex communicating systems. Following an early proposal made by Zipf concerning the presence of a tension between the efforts of speaker and hearer in a communication system, we introduce evolution by means of a variational approach to the problem based on Kullback's Minimum Discrimination of Information Principle. Using a formalism fully embedded in the framework of information theory, we demonstrate that Zipf's law is the only expected outcome of an evolving, communicative system under a rigorous definition of the communicative tension described by Zipf."

"We study the dynamics of the Naming Game [Baronchelli et al., (2006) J. Stat. Mech.: Theory Exp. P06014] in empirical social networks. This stylized agent-based model captures essential features of agreement dynamics in a network of autonomous agents, corresponding to the development of shared classification schemes in a network of artificial agents or opinion spreading and social dynamics in social networks. Our study focuses on the impact that communities in the underlying social graphs have on the outcome of the agreement process. We find that networks with strong community structure hinder the system from reaching global agreement; the evolution of the Naming Game in these networks maintains clusters of coexisting opinions indefinitely. Further, we investigate agent-based network strategies to facilitate convergence to global consensus."

"Many complex systems present an intrinsic bipartite nature and are often described and modeled in terms of networks [1-5]. Examples include movies and actors [1, 2, 4], authors and scientific papers [6-9], email accounts and emails [10], plants and animals that pollinate them [11, 12]. Bipartite networks are often very heterogeneous in the number of relationships that the elements of one set establish with the elements of the other set. … Here we introduce an unsupervised method to statistically validate each link of the projected network against a null hypothesis taking into account the heterogeneity of the system. We apply our method to three different systems…. In all these systems, both different in size and level of heterogeneity, we find that our method is able to detect network structures which are informative about the system…"

"We discuss the complex dynamics of a non-linear random networks model, as a function of the connectivity k between the elements of the network. We show that this class of networks exhibit an order-chaos phase transition for a critical connectivity k = 2. Also, we show that both, pairwise correlation and complexity measures are maximized in dynamically critical networks. These results are in good agreement with the previously reported studies on random Boolean networks and random threshold networks, and show once again that critical networks provide an optimal coordination of diverse behavior."

"…We tested our algorithm on a small benchmark graph and on a network of about 500 papers in information science (weighted with the Salton index of bibliographic coupling). In our tests, this approach results in characteristic ranges of resolution where a large resolution change does not lead to a growth of the natural community. Such stable modules were also obtained by applying the LFK algorithm but since we determine communities for all resolution values in one run, our approach is faster than the LFK reference. And our algorithm reveals the hierarchical structure of the graph more easily."

"A parameterisation of generalised network clustering, in the form of four-motif prevalences, is presented. This involves three real parameters that are conditional on one- two- and three-motif prevalences. Interpretations of these real parameters are presented that motivate a set of rewiring schemes to create appropriately clustered networks. Finally, the dynamical implications of higher order structure, as parameterised, for a contact process are considered."

"We have developed a framework to study the struc- ture and function of complex networks in purely geomet- ric terms. In this framework, two common properties of complex network topologies, strong heterogeneity and clustering, turn out to be simple reflections of the basic properties of an underlying hyperbolic geometry. Heterogeneity, measured in terms of the power-law degree distribution exponent, is a function of the negative curvature of the hyperbolic space, while clustering reflects its metric property."

"We describe the structure of the graphs with the smallest average distance and the largest average clustering given their order and size. There is usually a unique graph with the largest average clustering, which at the same time has the smallest possible average distance. In contrast, there are many graphs with the same minimum average distance, ignoring their average clustering. The form of these graphs is shown with analytical arguments. Finally, we measure the sensitivity to rewiring of this architecture with respect to the clustering coefficient, and we devise a method to make these networks more robust with respect to vertex removal."

"In this paper, we tackle the problem of innovation spreading from a modeling point of view. We consider a networked system of individuals, with a competition between two groups. We show its relation to the innovation spreading issues. We introduce an abstract model and show how it can be interpreted in this framework, as well as what conclusions we can draw form it. We further explain how model-derived conclusions can help to investigate the original problem, as well as other, similar problems. The model is an agent-based model assuming simple binary attributes of those agents. It uses a majority dynamics (Ising model to be exact), meaning that individuals attempt to be similar to the majority of their peers, barring the occasional purely individual decisions that are modeled as random. We show that this simplistic model can be related to the decision-making during innovation adoption processes. …"

"A single target is hidden at a location chosen from a predetermined probability distribution. Then, a searcher must find a second probability distribution from which random search points are sampled such that the target is found in the minimum number of trials. Here it will be shown that if the searcher must get very close to the target to find it, then the best search distribution is proportional to the square root of the target distribution…"

"Networks portray a multitude of interactions through which people meet, ideas are spread, and infectious diseases propagate within a society. Identifying the most efficient "spreaders" in a network is an important step to optimize the use of available resources and ensure the more efficient spread of information. Here we show that, in contrast to common belief, the most influential spreaders in a social network do not correspond to the best connected people or to the most central people (high betweenness centrality). Instead, we find: (i) The most efficient spreaders are those located within the core of the network as identified by the k-shell decomposition analysis. (ii) When multiple spreaders are considered simultaneously, the distance between them becomes the crucial parameter that determines the extend of the spreading.…"

"As we have shown, Cluster Reverberation is a mechanism available to neural systems for robust short-term memory without synaptic learning. To the best of our knowledge, this is the first mechanism proposed which has these charac- teristics – essential for, say, sensory memory or certain working-memory tasks. All that is needed is for the network topology to be highly clustered or modu- lar, and for small groups of neurons to store one bit of information, as opposed to the conventional view which assumes one bit per neuron. Considering the enormous number of neurons in the brain, and the fact that real individual neu- rons are probably too noisy to store information reliably, these hypotheses do not seem farfetched.…"

"In this work we study a weak Prisoner's Dilemma game in which both strategies and update rules are subjected to evolutionary pressure. Interactions among agents are specified by complex topologies, and we consider both homogeneous and heterogeneous situations. We consider deterministic and stochastic update rules for the strategies, which in turn may consider single links or full context when selecting agents to copy from. Our results indicate that the co-evolutionary process preserves heterogeneous networks as a suitable framework for the emergence of cooperation. Furthermore, on those networks, the update rule leading to a larger fraction of cooperation, replicator dynamics, is selected during co-evolution.…We conclude that for a variety of topologies, the fact that the dynamics coevolves with the strategies leads in general to more cooperation in the weak Prisoner's Dilemma game."

"Dynamics of evolutionary games strongly depend on underlying networks. We study the coevolutionary prisoner's dilemma in which players change their local networks as well as strategies (i.e., cooperate or defect). This topic has been increasingly explored by many researchers. On the basis of active linking dynamics [J. M. Pacheco et al., J. Theor. Biol. 243, 437 (2006), J. M. Pacheco et al., Phys. Rev. Lett. 97, 258103 (2006)], we show that cooperation is enhanced fairly robustly. In particular, cooperation evolves when the payoff of the player is normalized by the number of neighbors; this is not the case in the evolutionary prisoner's dilemma on static networks."

"Biological networks of interacting agents exhibit similar topological properties for a wide range of scales, from cellular to ecological levels, suggesting the existence of a common evolutionary origin. A general evolutionary mechanism based on global stability has been proposed recently [J I Perotti, O V Billoni, F A Tamarit, D R Chialvo, S A Cannas, Phys. Rev. Lett. 103, 108701 (2009)]. This mechanism is incorporated into a model of a growing network of interacting agents in which each new agent's membership in the network is determined by the agent's effect on the network's global stability. We show that, out of this stability constraint, several topological properties observed in biological networks emerge in a self organized manner. The influence of the stability selection mechanism on the dynamics associated to the resulting network is analyzed as well."

"We consider the problem of scheduling in multihop wireless networks subject to interference constraints. We consider a graph based representation of wireless networks, where scheduled links adhere to the K-hop link interference model. We develop a distributed greedy heuristic for this scheduling problem. Further, we show that this distributed greedy heuristic computes the exact same schedule as the centralized greedy heuristic."

"The study of networks has grown into a substantial interdisciplinary endeavor across the natural, social, and information sciences. Yet there have been very few attempts to investigate the interrelatedness of the different classes of networks studied by different disciplines. Here, we introduced a framework to establish a taxonomy of networks from various origins. The provision of this family tree not only helps understand the kinship of networks, but also facilitates the transfer of empirical analysis, theoretical modeling, and conceptual developments across disciplinary boundaries. The framework is based on probing the mesoscopic properties of networks, an important source of heterogeneity for their structure and function. Using our method, we computed a taxonomy for 752 individual networks and a separate taxonomy for 12 network classes. We also computed three within-class taxonomies for political, fungal, and financial networks, and found them to be insightful in each case."

"…The h index is compared with the Degree centrality (a local measure), the Betweenness and Eigenvector centralities (two non-local measures) in the case of a biological network (Yeast interaction protein-protein network) and a linguistic network (Moby Thesaurus II). In both networks, the Hirsch index has poor correlation with Betweenness centrality but correlates well with Eigenvector centrality, specially for the more important nodes that are relevant for ranking purposes, say in Search Engine Optimization. In the thesaurus network, the h index seems even to outperform the Eigenvector centrality measure as evaluated by simple linguistic criteria."

"Systems whose organization displays causal asymmetry constraints, from evolutionary trees to river basins or transport networks, can be often described in terms of directed paths (causal flows) on a discrete state space. Such a set of paths defines a feed-forward, acyclic network. A key problem associated with these systems involves characterizing their intrinsic degree of path reversibility: given an end node in the graph, what is the uncertainty of recovering the process backwards until the origin? Here we propose a novel concept, \textit{topological reversibility}, which rigorously weigths such uncertainty in path dependency quantified as the minimum amount of information required to successfully revert a causal path.…"

"We have embarked on a research program designed to develop universal models that can recreate empiri- cally observed phenomena in dynamic complex networks. We have shown that, using a suitable reinforced random walk on a “long-term” underlay network, one is able to produce instantaneous networks which reproduce qualitatively characteristic features of real world dynamic networks. This includes, in particular, the construc- tion of scale-free sub-networks of a scale-free “underlay” network, whose local hubs substantially differ from sub- network to sub-network and from those of the underlay.…"

"In real communication and transportation networks, the geographical positions of nodes are very important for the efficiency and the tolerance of connectivity. Considering spatially inhomogeneous positions of nodes according to a population, we introduce a multi-scale quartered (MSQ) network that is stochastically constructed by recursive subdivision of polygonal faces as a self-similar tiling. It has several advantages: the robustness of connectivity, the bounded short path lengths, and the shortest distance routing algorithm in a distributive manner. Furthermore, we show that the MSQ network is more efficient with shorter link lengths and more suitable with lower load for avoiding traffic congestion than other geographical networks which have various topologies ranging from river to scale-free networks. These results will be useful for providing an insight into the future design of ad hoc network infrastructures."

"We propose a degree-based coarse graining approach that not just accelerates the evaluation of dynamics on complex networks, but also satisfies the consistency conditions for both equilibrium statistical distributions and nonequilibrium dynamical flows. For the Ising model and susceptible-infected-susceptible epidemic model, we introduce these required conditions explicitly and further prove that they are satisfied by our coarse-grained network construction within the annealed network approximation. Finally, we numerically show that the phase transitions and fluctuations on the coarse-grained network are all in good agreements with those on the original one."

Frankly, I've alway thought this, especially after some early "confusing" experiments that never got published because they were part of my first Ph.D. thesis research: "…We argue that the presence of only the frozen phase in the work of Kauffman et al. was due simply to the specific parametrization used, and is not an inherent feature of this class of functions. However, these networks are significantly more stable than the variants where all possible Boolean functions are allowed."

"We’ve open sourced Tickery in order to show other developers the insides of a non-trivial application that uses FluidDB. Tickery was written over a three month period (November 2009 to January 2010), and much of it was done at a fairly fast pace. While the code could be cleaner and better documented, it’s not bad. We’re of course interested to help people understand the code, so please feel free to join the FluidDB users mailing list, or join us in #fluiddb on irc.freenode.net. Naturally we’ll be happy and interested to receive improvements or patches, and you can of course run your own instance of Tickery."

"The study of evolution of networks has received increased interest with the recent discovery that many real-world networks possess many things in common, in particular the manner of evolution of such networks. By adding a dimension of time to graph analysis, evolving graphs present opportunities and challenges to extract valuable information. This paper introduces the Evolving Graph Markup Language (EGML), an XML application for representing evolving graphs and related results. Along with EGML, a software tool is provided for the study of evolving graphs. New evolving graph drawing techniques based on the force-directed graph layout algorithm are also explored. Our evolving graph techniques reduce vertex movements between graph instances, so that an evolving graph can be viewed with smooth transitions"

"Here we propose a generic mechanism - networked buffering - for generating robust traits in complex systems that requires two basic conditions to be satisfied: 1) agents are versatile enough to perform more than one single functional role within a system and 2) agents are degenerate, i.e. there exists partial overlap in the functional capabilities of agents. Given these prerequisites, degenerate systems can readily produce a distributed systemic response to local perturbations. Reciprocally, excess resources related to a single function can indirectly support multiple unrelated functions within a degenerate system.…"

"This paper presents a complex systems overview of a power grid network. In recent years, concerns about the robustness of the power grid have grown because of several cascading outages in different parts of the world. In this paper, cascading effect has been simulated on three different networks, the IEEE 300 bus test system, the IEEE 118 bus test system, and the WSCC 179 bus equivalent model, using the DC Power Flow Model. Power Degradation has been discussed as a measure to estimate the damage to the network, in terms of load loss and node loss. A network generator has been developed to generate graphs with characteristics similar to the IEEE standard networks and the generated graphs are then … have been suggested."

"… Using wireless sensor network technology, we obtained high-resolution data of CPIs during a typical day at an American high school, permitting the reconstruction of the social network relevant for infectious disease transmission. At a 94% coverage, we collected 762,868 CPIs at a maximal distance of 3 meters among 788 individuals. The data revealed a high density network with typical small world properties and a relatively homogenous distribution of both interaction time and interaction partners among subjects.…"

"We present a framework for simulating signal propagation in geometric networks (i.e. networks that can be mapped to geometric graphs in some space) and for developing algorithms that estimate (i.e. map) the state and functional topology of complex dynamic geometric net- works. Within the framework we define the key features typically present in such networks and of particular relevance to biological cellular neural networks: Dynamics, signaling, observation, and control. The framework is particularly well-suited for estimating functional connectivity in cellular neural networks from experimentally observable data, and has been implemented using graphics processing unit (GPU) high performance computing. Computationally, the framework can simulate cellular network signaling close to or faster than real time. We further propose a standard test set of networks to measure performance and compare different mapping algorithms."

"We present a methodology to extract the backbone of complex networks based on the weight and direction of links, as well as on nontopological properties of nodes. We show how the methodology can be applied in general to networks in which mass or energy is flowing along the links. In particular, the procedure enables us to address important questions in economics, namely, how control and wealth are structured and concentrated across national markets. We report on the first cross-country investigation of ownership networks, focusing on the stock markets of 48 countries around the world. On the one hand, our analysis confirms results expected on the basis of the literature on corporate control, namely, that in Anglo-Saxon countries control tends to be dispersed among numerous shareholders. On the other hand, it also reveals that in the same countries, control is found to be highly concentrated at the global level, namely, lying in the hands of very few important shareholders. …"

"We propose a novel distributed algorithm to cluster graphs. The algorithm recovers the solution obtained from spectral clustering without the need for expensive eigenvalue/vector computations. We prove that, by propagating waves through the graph, a local fast Fourier transform yields the local component of every eigenvector of the Laplacian matrix, which are used to cluster graphs. For large graphs, the proposed algorithm is orders of magnitude faster than random walk based approaches. We prove the equivalence of the proposed algorithm to spectral clustering and derive convergence rates. We also demonstrate the benefit of using this decentralized clustering algorithm to accelerate distributed estimation for sensor networks and for efficient computation of distributed multi-agent search strategies."

"The Library of Babel, described by Jorge Luis Borges, stores an enormous amount of information. The Library exists {\it ab aeterno}. Wikipedia, a free online encyclopaedia, becomes a modern analogue of such a Library. Information retrieval and ranking of Wikipedia articles become the challenge of modern society. We analyze the properties of two-dimensional ranking of all Wikipedia English articles and show that it gives their reliable classification with rich and nontrivial features. Detailed studies are done for countries, universities, personalities, physicists, chess players, Dow-Jones companies and other categories."

"The prisoner's dilemma (PD) game is a simple model for understanding cooperative patterns in complex systems consisting of selfish individuals. Here, we study a PD game problem in scale-free networks containing hierarchically organized modules and controllable shortcuts connecting separated hubs. We find that cooperator clusters exhibit a percolation transition in the parameter space (p,b), where p is the occupation probability of shortcuts and b is the temptation payoff in the PD game. The cluster size distribution follows a power law at the transition point. Such a critical behavior, resulting from the combined effect of stochastic processes in the PD game and the heterogeneous structure of complex networks, illustrates the diversity of social relationships and the self-organization of cooperator communities in real-world systems."

ME: what would 'well-designed' biochemical nets look like, if you evolved them in silico?

"The reliability with which a network can transmit a particular frequency component of the input signal tra- jectory is determined by the gain-to-noise ratio of the net- work as a function of frequency. For systems that obey the spectral addition rule [32], that is those for which downstream reactions do not affect the input signal, the gain-to-noise ratio is an intrinsic property of the processing network. For networks that do not obey the spectral addition rule the gain-to-noise ratio will be dependent on the statistics of the input signal. The mutual information between input and output signals, which quantifies the information which can be transmitted about a particular input ensemble, also depends on the particular choice of the input signal.…"

"The feed-forward relationship naturally observed in time-dependent processes and in a diverse number of real systems -such as some food-webs and electronic and neural wiring- can be described in terms of so-called directed acyclic graphs (DAGs). An important ingredient of the analysis of such networks is a proper comparison of their observed architecture against an ensemble of randomized graphs, thereby quantifying the {\em randomness} of the real systems with respect to suitable null models. This approximation is particularly relevant when the finite size and/or large connectivity of real systems make inadequate a comparison with the predictions obtained from the so-called {\em configuration model}. In this paper we analyze four methods of DAG randomization as defined by the desired combination of topological invariants (directed and undirected degree sequence and component distributions) aimed to be preserved.…"

"We present a method for the reconstruction of networks, based on the order of nodes visited by a stochastic branching process. Our algorithm reconstructs a network of minimal size that ensures consistency with the data. Crucially, we show that global consistency with the data can be achieved through purely local considerations, inferring the neighbourhood of each node in turn. The optimisation problem solved for each individual node can be reduced to a Set Covering Problem, which is known to be NP-hard but can be approximated well in practice. We then extend our approach to account for noisy data, based on the Minimum Description Length principle. We demonstrate our algorithms on synthetic data, generated by an SIR-like epidemiological model."

"Many functions have been recently defined to assess the similarity among networks as tools for quantitative comparison. They stem from very different frameworks - and they are tuned for dealing with different situations. Here we show an overview of the spectral distances, highlighting their behavior in some basic cases of static and dynamic synthetic and real networks."

"We develop elements of a theory of cooperation and coordination in networks. Rather than considering a communication network as a means of distributing information, or of reconstructing random processes at remote nodes, we ask what dependence can be established among the nodes given the communication constraints.…"

"The obtained results and trends suggest a number of further investigations. For instance, it would be interest- ing to consider other network models and measurements, as well as to assess the effect of different types of hard- ware, compilers and operating systems."

"In many networks, vertices have hidden attributes, or types, that are correlated with the networks topology. If the topology is known but these attributes are not, and if learning the attributes is costly, we need a method for choosing which vertex to query in order to learn as much as possible about the attributes of the other vertices. We assume the network is generated by a stochastic block model, but we make no assumptions about its assortativity or disassortativity. We choose which vertex to query using two methods: 1) maximizing the mutual information between its attributes and those of the others (a well-known approach in active learning) and 2) maximizing the average agreement between two independent samples of the conditional Gibbs distribution. Experimental results show that both these methods do much better than simple heuristics. They also consistently identify certain vertices as important by querying them early on."

"We propose a fluctuation analysis to quantify spatial correlations in complex networks. The approach considers the sequences of degrees along shortest paths in the networks and quantifies the fluctuations in analogy to time series. In this work, the Barabasi-Albert (BA) model, the Cayley tree at the percolation transition, a fractal network model, and examples of real-world networks are studied. While the fluctuation functions for the BA model show exponential decay, in the case of the Cayley tree and the fractal network model the fluctuation functions display a power-law behavior. The fractal network model comprises long-range anti-correlations. The results suggest that the fluctuation exponent provides complementary information to the fractal dimension."

"Community structure is one of the key properties of complex networks and plays a crucial role in their topology and function. While an impressive amount of work has been done on the issue of community detection, very little attention has been so far devoted to the investigation of communities in real networks. We present a systematic empirical analysis of the statistical properties of communities in large information, communication, technological, biological, and social networks. We find that the mesoscopic organization of networks of the same category is remarkably similar. This is reflected in several characteristics of community structure, which can be used as ``fingerprints'' of specific network categories.…"

"… We find that SF networks generate oscillations much more easily than ER networks do, and this may explain why SF networks are more evolvable than ER networks are for oscillatory phenotypes. In spite of their greater evolvability, we find that networks with SFout topologies are also more robust to mutations than ER networks. Furthermore, the SFout topologies are more robust to changes in initial conditions (environmental robustness). For both topologies, we find that once a population of networks has reached the target state, further neutral evolution can lead to an increase in both the mutational robustness and the environmental robustness to changes in initial conditions."

"Adaptive networks have been recently introduced in the context of disease propagation on complex networks. They account for the mutual interaction between the network topology and the states of the nodes. Until now, existing models have been analyzed using low-complexity analytic formalisms, revealing nevertheless some novel dynamical features. However, current methods have failed to reproduce with accuracy the simultaneous time evolution of the disease and the underlying network topology. In the framework of the adaptive SIS model of Gross et al. [Gross et al., Phys. Rev. Lett. 96, 208701 (2006)], we introduce an improved compartmental formalism able to handle this coevolutionary task successfully. With this approach, we analyze the interplay and outcomes of both dynamical elements, process and structure, on adaptive networks featuring different degree distributions at the initial stage."

"Heterogeneity in the degree distribution is known to suppress global synchronization in complex networks of symmetrically coupled oscillators. Scale-free networks present strong heterogeneity, there are a few highly connected nodes, termed hubs, while the majority of nodes has only a few connections. We show that a stable partially synchronized state may take place in scale-free networks: hubs undergo a transition to synchronization while the remaining nodes are unsynchronized. This phenomenon may occur in any large heterogeneous network, regardless of the network global synchronization properties. We provide theory and numerical evidence to establish this phenomenon."

"Connections in complex networks are inherently fluctuating over time and exhibit more dimensionality than analysis based on standard static graph measures can capture. Here, we introduce the concepts of temporal paths and distance in time-varying graphs. We define as temporal small world a time-varying graph in which the links are highly clustered in time, yet the nodes are at small average temporal distances. We explore the small-world behavior in synthetic time-varying networks of mobile agents, and in real social and biological time-varying systems."

"Small world networks interpolate between fully regular and fully random topologies and simultaneously exhibit large local clustering as well as short average path length. Small world topology has therefore been suggested to support network synchronization. Here we study the asymptotic speed of synchronization of coupled oscillators in dependence on the degree of randomness of their interaction topology in generalized Watts-Strogatz ensembles. We find that networks with fixed in-degree synchronize faster the more random they are, with small worlds just appearing as an intermediate case. For any generic network ensemble, if synchronization speed is at all extremal at intermediate randomness, it is slowest in the small world regime. This phenomenon occurs for various types of oscillators, intrinsic dynamics and coupling schemes."

"Empirical studies show that real world networks often exhibit multiple scales of topological descriptions. However, it is still an open problem how to identify the intrinsic multiple scales of networks. In this article, we consider detecting the multi-scale community structure of networks from the perspective of dimension reduction. …Theoretical analysis indicates that all these three transformations are crucial to identify the multi-scale community structure of networks. Extensive tests on real world and artificial networks demonstrate that the correlation matrix significantly outperforms the modularity matrix as regards identifying the multi-scale community structure of networks."

"In this paper we consider spatial networks that realize a balance between an infrastructure cost (the cost of wire needed to connect the network in space) and communication efficiency, measured by average shortest pathlength. A global optimization procedure yields network topologies in which this balance is optimized. These are compared with network topologies generated by a competitive process in which each node strives to optimize its own cost-communication balance. Three phases are observed in globally optimal configurations for different cost-communication trade-offs: (i) regular small worlds, (ii) star-like networks and (iii) trees with a centre of interconnected hubs. In the latter regime, i.e. for very expensive wire, power laws in the link length distributions $P(w)\propto w^{-\alpha}$ are found, which can be explained by a hierarchical organization of the networks…"

"A recent study by researchers in Yale and published in PNAS shows that there are significant differences between the network topologies of living systems like E. coli and complex pieces of software such as the Linux Operating System."