"Contacts between individuals serve as pathways where infections may propagate. These contact patterns can be represented by network structures. Static structures have been the common modeling paradigm but recent results suggest that temporal structures play different roles to regulate the spread of infections or infection-like dynamics. On temporal networks a vertex is active only at certain moments and inactive otherwise such that a contact is not continuously available. In several empirical networks, the time between two consecutive vertex-activation events typically follows heterogeneous activity (e.g. bursts). In this chapter, we present a simple and intuitive stochastic model of a temporal network and investigate how epidemics co-evolves with the temporal structures, focusing on the growth dynamics of the epidemics. The model assumes no underlying topological structure and is only constrained by the time between two consecutive events of vertex activation. The main observation is that the speed of the infection spread is different in case of heterogeneous and homogeneous temporal patterns but the differences depend on the stage of the epidemics. In comparison to the homogeneous scenario, the power law case results in a faster growth in the beginning but turns out to be slower after a certain time, taking several time steps to reach the whole network."

"We present a general algorithm for learning the structure of discrete Markov random fields from i.i.d. samples. Several algorithms have been proposed for structure learning algorithms earlier and each of these address the learning problem under different assumptions. Our algorithm provides a unified view in the following sense: when our algorithm is applied to each of the special cases, it results in a the same computational complexity as earlier algorithms. More importantly, our approach also provides a new low-computational complexity algorithm for the case of Ising models where the underlying graph is the Erdos-Renyi random graph G(p,c/p)."

When would you ever want to learn an Ising model on an E-R graph?

"Human brain functional networks are embedded in anatomical space and have topological properties—small-worldness, modularity, fat-tailed degree distributions—that are comparable to many other complex networks. Although a sophisticated set of measures is available to describe the topology of brain networks, the selection pressures that drive their formation remain largely unknown. Here we consider generative models for the probability of a functional connection (an edge) between two cortical regions (nodes) separated by some Euclidean distance in anatomical space. In particular, we propose a model in which the embedded topology of brain networks emerges from two competing factors: a distance penalty based on the cost of maintaining long-range connections; and a topological term that favors links between regions sharing similar input. We show that, together, these two biologically plausible factors are sufficient to capture an impressive range of topological properties of functional brain networks. Model parameters estimated in one set of functional MRI (fMRI) data on normal volunteers provided a good fit to networks estimated in a second independent sample of fMRI data. Furthermore, slightly detuned model parameters also generated a reasonable simulation of the abnormal properties of brain functional networks in people with schizophrenia. We therefore anticipate that many aspects of brain network organization, in health and disease, may be parsimoniously explained by an economical clustering rule for the probability of functional connectivity between different brain areas."

Judging from the table of contents (which is unfair), a weird mix of reviewing truly elementary concepts and some actually interesting stuff. (And yes, I know who Bonacich is.)

"On a finite inhomogeneous graph model for complex network, we define the Ising model, which is a paradigm model in statistical mechanics. For the ferromagnetic Ising model,we calculate the Thermodynamic limit of pressure per particle. From our results, we compute other physical quantities such as the magnetization and susceptibility, and investigate the critical behaviour of this model. Our calculations use large deviation principles (developed recently) for suitably defined empirical neighbourhood measures on inhomogeneous random graph."

"Network modeling plays a critical role in identifying statistical regularities and structural principles common to many systems. The large majority of recent modeling approaches are connectivity driven, in the sense that the structural pattern of the network is at the basis of the mechanisms ruling the network formation. Connectivity driven models necessarily provide a time-aggregated representation that may fail to describe the instantaneous and fluctuating dynamics of many networks. We address this challenge by defining the activity potential, a time invariant function characterizing the agents' interactions in real-world networks and constructing an activity driven model capable of encoding the instantaneous time description of the network dynamics. The model provides an explanation of structural features such as the presence of hubs, which simply originate from the heterogeneous activity of agents. Additionally, we find that diffusive processes in highly dynamical networks can be described analytically in terms of the activity potential, allowing a quantitative discussion of the biases induced by the time-aggregated network representation in the analysis of dynamical processes in evolving networks."

"We study the problem of reaching consensus in complex networks where each node knows nothing about the overall topology, other than its own neighbors. We assume that there exist a set of malicious or stubborn nodes in the network that do not follow the same dynamics as the rest of the nodes. When the normal nodes act on purely local information, previous work has established that standard graph notions such as connectivity are no longer sufficient to characterize the ability of the non-malicious nodes to reach agreement. Instead, the network must satisfy a property known as robustness. In this paper we investigate the robustness properties of common random graph models for complex networks, including the preferential attachment model, the Erdos-Renyi model, and the geometric random graph model. We show that these models exhibit a thresholding behavior for robustness. In particular, we show that the notions of connectivity and robustness coincide on various random graph models, indicating that purely local knowledge is sufficient when the objective is to reach agreement on an appropriate function of the initial values."

"In this paper we use the Birkhoff–von Neumann decomposition of the diffusion kernel to compute a polytopal measure of graph complexity. We decompose the diffusion kernel into a series of weighted Birkhoff combinations and compute the entropy associated with the weighting proportions (polytopal complexity). The maximum entropy Birkhoff combination can be expressed in terms of matrix permanents. This allows us to introduce a phase-transition principle that links our definition of polytopal complexity to the heat flowing through the network at a given diffusion time. The result is an efficiently computed complexity measure, which we refer to as flow complexity. Moreover, the flow complexity measure allows us to analyze graphs and networks in terms of the thermodynamic depth. We compare our method with three alternative methods described in the literature (Estrada's heterogeneity index, the Laplacian energy, and the von Neumann entropy). Our study is based on 217 protein-protein interaction (PPI) networks including histidine kinases from several species of bacteria. We find a correlation between structural complexity and phylogeny (more evolved species have statistically more complex PPIs). Although our methods outperform the alternatives, we find similarities with Estrada's heterogeneity index in terms of network size independence and predictive power."

"Complex networks have acquired a great popularity in recent years, since the graph representation of many natural, social and technological systems is often very helpful to characterize and model their phenomenology. Additionally, the mathematical tools of statistical physics have proven to be particularly suitable for studying and understanding complex networks. Nevertheless, an important obstacle to this theoretical approach is still represented by the difficulties to draw parallelisms between network science and more traditional aspects of statistical physics. In this paper, we explore the relation between complex networks and a well known topic of statistical physics: renormalization. A general method to analyze renormalization flows of complex networks is introduced. The method can be applied to study any suitable renormalization transformation. Finite-size scaling can be performed on computer-generated networks in order to classify them in universality classes. We also present applications of the method on real networks."

"Considerable attention has been paid, in recent years, to the use of networks in modeling complex real-world systems. Among the many dynamical processes involving networks, propagation processes -- in which final state can be obtained by studying the underlying network percolation properties -- have raised formidable interest. In this paper, we present a bond percolation model of multitype networks with an arbitrary joint degree distribution that allows heterogeneity in the edge occupation probability. As previously demonstrated, the multitype approach allows many non-trivial mixing patterns such as assortativity and clustering between nodes. We derive a number of useful statistical properties of multitype networks as well as a general phase transition criterion. We also demonstrate that a number of previous models based on probability generating functions are special cases of the proposed formalism. We further show that the multitype approach, by naturally allowing heterogeneity in the bond occupation probability, overcomes some of the correlation issues encountered by previous models. We illustrate this point in the context of contact network epidemiology."

"We study the statistical behavior under random sequential renormalization (RSR) of several network models including Erdös-Rényi (ER) graphs, scale-free networks, and an annealed model related to ER graphs. In RSR the network is locally coarse grained by choosing at each renormalization step a node at random and joining it to all its neighbors. Compared to previous (quasi-)parallel renormalization methods [Song et al., Nature (London) 433 392 (2005)], RSR allows a more fine-grained analysis of the renormalization group (RG) flow and unravels new features that were not discussed in the previous analyses. In particular, we find that all networks exhibit a second-order transition in their RG flow. This phase transition is associated with the emergence of a giant hub and can be viewed as a new variant of percolation, called agglomerative percolation. We claim that this transition exists also in previous graph renormalization schemes and explains some of the scaling behavior seen there. For critical trees it happens as N/N0→0 in the limit of large systems (where N0 is the initial size of the graph and N its size at a given RSR step). In contrast, it happens at finite N/N0 in sparse ER graphs and in the annealed model, while it happens for N/N0→1 on scale-free networks. Critical exponents seem to depend on the type of the graph but not on the average degree and obey usual scaling relations for percolation phenomena. For the annealed model they agree with the exponents obtained from a mean-field theory. At late times, the networks exhibit a starlike structure in agreement with the results of Radicchi et al. [ Phys. Rev. Lett. 101 148701 (2008)]. While degree distributions are of main interest when regarding the scheme as network renormalization, mass distributions (which are more relevant when considering “supernodes” as clusters) are much easier to study using the fast Newman-Ziff algorithm for percolation, allowing us to obtain very high statistics."

17 pp. review paper. "Infectious disease remains, despite centuries of work to control and mitigate its effects, a major problem facing humanity. This paper reviews the mathematical modelling of infectious disease epidemics on networks, starting from the simplest Erdos-Renyi random graphs, and building up structure in the form of correlations, heterogeneity and preference, paying particular attention to the links between random graph theory, percolation and dynamical systems representing transmission. Finally, the problems posed by networks with a large number of short closed looks are discussed."

Even the abstract was tl;dr.

"In this paper we present a new ODE based framework for modelling disease transmission on dynamic contact networks. We adapt and extend the effective degree model for a static network to account for the random creation and deletion of links between individuals. The resulting set of ODEs is solved numerically and results are compared to those obtained using individual-based stochastic network simulations. We show that the ODEs display excellent agreement for the evolution of both the disease and the network, and is able to accurately capture the epidemic threshold for a wide range of parameters. Using the proposed model we show that mild epidemics can be controlled while keeping the contact network well connected, and this is in contrast with severe epidemics, where successful control via link removal leads to a disconnected network."

"We construct an infinitely exchangeable process on the set $cate$ of subsets of the power set of the natural numbers $mathbb{N}$ via a Poisson point process with mean measure $Lambda$ on the power set of $mathbb{N}$. Each $Eincate$ has a least monotone cover in $catf$, the collection of monotone subsets of $cate$, and every monotone subset maps to an undirected graph $Gincatg$, the space of undirected graphs with vertex set $mathbb{N}$. We show a natural mapping $caterightarrowcatfrightarrowcatg$ which induces an infinitely exchangeable measure on the projective system $catg^{rest}$ of graphs $catg$ under permutation and restriction mappings given an infinitely exchangeable family of measures on the projective system $cate^{rest}$ of subsets with permutation and restriction maps. We show potential connections of this process to applications in cluster analysis, machine learning, classification and Bayesian inference."

"We study the realizability of scale-free networks with a given degree sequence, showing that the fraction of realizable sequences undergoes two first-order transitions at the values 0 and 2 of the power-law exponent. We substantiate this finding by analytical reasoning and by a numerical method, proposed here, based on extreme value arguments, which can be applied to any given degree distribution. Our results reveal a fundamental reason why large scale-free networks without constraints on minimum and maximum degree must be sparse."

"The structure of the control network of transnational corporations affects global market competition and financial stability. So far, only small national samples were studied and there was no appropriate methodology to assess control globally. We present the first investigation of the architecture of the international ownership network, along with the computation of the control held by each global player. We find that transnational corporations form a giant bow-tie structure and that a large portion of control flows to a small tightly-knit core of financial institutions. This core can be seen as an economic "super-entity" that raises new important issues both for researchers and policy makers."

--- The definition of "control" looks VERY strange.

"Recent research has explored the increasingly important role of social media by examining the dynamics of individual and group behavior, characterizing patterns of information diffusion, and identifying influential individuals. In this paper we suggest a measure of causal relationships between nodes based on the information-theoretic notion of transfer entropy, or information transfer. This theoretically grounded measure is based on dynamic information, captures fine-grain notions of influence, and admits a natural, predictive interpretation. Causal networks inferred by transfer entropy can differ significantly from static friendship networks because most friendship links are not useful for predicting future dynamics. We demonstrate through analysis of synthetic and real-world data that transfer entropy reveals meaningful hidden network structures. In addition to altering our notion of who is influential, transfer entropy allows us to differentiate between weak influence over large groups and strong influence over small groups."

"We investigate the evolutionary dynamics in directed and/or weighted networks. We study the fixation probability of a mutant in finite populations in stochastic voter-type dynamics for several update rules. The fixation probability is defined as the probability of a newly introduced mutant in a wild-type population taking over the entire population. In contrast to the case of undirected and unweighted networks, the fixation probability of a mutant in directed networks is characterized not only by the degree of the node that the mutant initially invades but by the global structure of networks. Consequently, the gross connectivity of networks such as small-world property or modularity has a major impact on the fixation probability."

"We consider a large class of exponential random graph models and prove the existence of a region of parameter space corresponding to multipartite structure, separated by a phase transition from a region of disordered graphs."

"This paper investigates how employment intermediaries affected the inter-firm network of worker mobility in an region of Italy in response of the reform that first allowed for temporary employment agencies in 1997. We map worker reallocations from a matched employer-employee dataset onto a directed graph, where vertices indicate firms, and links denote transfers of workers between firms. Using network-based methodologies we find that temporary employment agencies significantly increase network integration and practicability, while fastly increasing control over hiring channels. The policy implications of the results are discussed, highlighting the potential of network analysis as monitoring tool for regional and local labour markets."

Christakis & Fowler respond to critics. Unsurprisingly, I am unconvinced.

"We propose a model for evolving networks by merging building blocks represented as complete graphs, reminiscent of modules in biological system or communities in sociology. The model shows power-law degree distributions, power-law clustering spectra, and high average clustering coefficients independent of network size. The analytical solutions indicate that a degree exponent is determined by the ratio of the number of merging nodes to that of all nodes in the blocks, demonstrating that the exponent is tunable, and are also applicable when the blocks are classical networks such as Erdös-Rényi or regular graphs. Our model becomes the same model as the Barabási-Albert model under a specific condition."

There's an arxiv version as well...

"It is shown that homogeneous, short-range, two-dimensional (2D) cortical connectivity, without modularity, hierarchy, or other specialized structure, reproduces key observed properties of cortical networks, including low path length, high clustering and modularity index, and apparent hierarchical block-diagonal structure in connection matrices. Geometry strongly influences connection matrices, implying that simple interpretations of connectivity measures as reflecting specialized structure can be misleading: Such apparent structure is seen in strictly uniform, locally connected architectures in 2D. Geometry is thus a proxy for function, modularity, and hierarchy and must be accounted for when structural inferences are made."

"We introduce a broad class of analytically solvable processes on networks. In the special case, they reduce to random walk and consensus process, the two most basic processes on networks. Our class differs from previous models of interactions (such as the stochastic Ising model, cellular automata, infinite particle systems, and the voter model) in several ways, the two most important being (i) the model is analytically solvable even when the dynamical equation for each node may be different and the network may have an arbitrary finite graph and influence structure and (ii) when local dynamics is described by the same evolution equation, the model is decomposable, with the equilibrium behavior of the system expressed as an explicit function of network topology and node dynamics."

I am going to presume that there is something more to this than "hey! we can make the coupling weights of a linear system into a matrix", but from the abstract I can't tell what that is.

Sounds very like Pemantle and Skyrms... which is in the bibliography; need to see what's new here.

"We propose a class of random scale-free spatial networks with nested community structures and analyze Reed-Frost epidemics with community related independent transmissions. We show that the epidemic threshold may be trivial or not depending on the relation among community sizes, distribution of the number of communities and transmission rates"

I am a bit boggled that they write a whole paper about how to explain economic fluctuations in terms of input-output matrices without even mentioning the name of Leontief...

"Complex social networks have received increasing attention from researchers. Recent work has focused on mechanisms that produce scale-free networks. We theoretically and empirically characterize the buyer–supplier network of the US economy and find that purely scale-free models have trouble matching key attributes of the network. We construct an alternative model that incorporates realistic features of firms’ buyer–supplier relationships and estimate the model’s parameters using microdata on firms’ self-reported customers. This alternative framework is better able to match the attributes of the actual economic network and aids in further understanding several important economic phenomena."

"A general theory of top-down cascades in complex networks is described which explains two similar types of perturbation amplifications in the complex networks of business supply chains (the `bullwhip effect') and ecological food webs (trophic cascades). The dependence of the strength of the effects on the interaction strength and covariance in the dynamics as well as the graph structure allows both explanation and prediction of widely recognized effects in each type of system."

Heard the talk at ISIT 2011; it was very good.

Dunno if there's much to this yet

The "to teach" tag is conditional...

"Many complex systems, from power grids and the internet, to the brain and society, can be modeled using modular networks. Modules, densely interconnected groups of elements, often overlap due to elements that belong to multiple modules. The elements and modules of these networks perform individual and collective tasks such as generating and consuming electrical load, transmitting data, or executing parallelized computations. We study the robustness of these systems to the failure of random elements. We show that it is possible for the modules themselves to become isolated or uncoupled (non-overlapping) well before the network falls apart. When modular organization is critical to overall functionality, networks may be far more vulnerable than expected."

"For a broad range single-seed contagion processes acting on generalized random networks, we derive a unifying analytic expression for the possibility of global spreading events in a straightforward, physically intuitive fashion. Our reasoning lays bare a direct mechanical understanding of an archetypal spreading phenomena that is not evident in circuitous extant mathematical approaches."  (Are they really that circuitous?)

"We study polytopes that are convex hulls of vectors of subgraph densities. Many graph theoretical questions can be expressed in terms of these polytopes, and statisticians use them to understand exponential random graph models.
Relations among their Ehrhart polynomials are described, their duals are applied to certify that polynomials are non-negative, and we find some of their faces.
For the general picture we inscribe cyclic polytopes in them and calculate volumes. From the volume calculations we conjecture that a variation of the Selberg integral indexed by Schur polynomials has a combinatorial formula. We inscribe polynomially parametrized sets, called curvy zonotopes, in the polytopes and show that they approximate the polytopes arbitrarily close."

"A model of “ephemeral” population structure is pre- sented that applies not only to biological systems in which discrete groups form but also to networks without group boundaries. The evolution of altruistic behaviors is discussed. Nonrandom interaction and nonlinear fitness structures are modeled; together, these factors can produce stable polymorphisms of altruistic and selfish types, as well as bistability. Empirical applications of the model may be found in microbes, marine invertebrates, annual plants, and other organisms."

"The relationship between a network's degree-degree correlation and a loose version of graph coloring is studied on networks with broad degree distributions. We find that, given similar conditions on the number of nodes, number of links, and clustering levels, fewer colors are needed to color disassortative than assortative networks. Since fewer colors create fewer independent sets, our finding implies that disassortative networks may have higher concurrency potential than assortative networks. This in turn suggests another reason for the disassortative mixing pattern observed in biological networks such as those of protein-protein interaction and gene regulation. In addition to the functional specificity and stability suggested by Maslov and Sneppen, a disassortative network topology may also enhance the ability of cells to perform crucial tasks concurrently..." Related to Judd/Kearns experiments on human graph coloring?

We consider a decision network on an undirected graph in which each node corresponds to a decision variable, and each node and edge of the graph is associated with a reward function whose value depends only on the variables of the corresponding nodes. The goal is to construct a decision vector which maximizes the total reward. This decision problem encompasses a variety of models, including maximum-likelihood inference in graphical models (Markov Random Fields), combinatorial optimization on graphs, economic team theory and statistical physics. The network is endowed with a probabilistic structure in which costs are sampled from a distribution. Our aim is to identify sufficient conditions to guarantee average-case polynomiality of the underlying optimization problem. ... we prove that [in some case we can] find near optimal solutions with high probability in a decentralized way ... based on the network exhibiting a correlation decay (long-range independence) property."

"human-subject experiments on the problems of coloring (a social differentiation task) and consensus (a social agreement task) [on a network]. Both [are] coordination games, and despite their cognitive similarity, we find that ... network structure elicits opposing behavioral effects in the two problems, with increased long-distance connectivity making consensus easier for subjects and coloring harder. We investigate the influence that subjects have on their network neighbors and the collective outcome, and find that it varies considerably, beyond what can be explained by network position alone. ... strong correlations between influence and other features of individual subject behavior. ... much of the recent research in network science ... often emphasizes network topology out of the context of any specific problem and places primacy on network position, our findings highlight the potential importance of the details of tasks and individuals in social networks."

I'll be doing a poster version of "Homophily, Contagion & Confounding"

Not sure of the relevance to the "re:" paper. "knowledge acquisition as performed by multiple agents interacting as they infer, under [noise], respective models of a complex system. ... at each time step, each agent takes into account its current observation as well as the average of the models of its neighbors. The agents are connected by a network... of Erdős-Rényi or Barabási-Albert type. .. [if] one [agent] has a different [error rate] (higher or lower). ... [t]he influence of this special agent over the quality of the models inferred by the rest of the network can be substantial, varying linearly with the ... degree of the [special] agent ... [if] the degree of this agent is taken as a respective fitness parameter, the effect of the different [error rate] is ... superlinear.. when the agents are grouped into communities ... edges between agents (within a community) having higher probability of observation error [worsens] the estimation of the agents in the other communities."

"Neuroimaging studies of cognitive control have identified two distinct networks with dissociable resting state connectivity patterns. This study, in patients with heterogeneous damage to these networks, demonstrates network independence through a double dissociation of lesion location on two different measures of network integrity: functional correlations among network nodes and within-node graph theory network properties. The degree of network damage correlates with a decrease in functional connectivity within that network while sparing the nonlesioned network. Graph theory properties of intact nodes within the damaged network show evidence of dysfunction compared with the undamaged network. The effect of anatomical damage thus extends beyond the lesioned area, but remains within the bounds of the existing network connections. Together this evidence suggests that networks defined by their role in cognitive control processes exhibit independence in resting data."

"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. Specifically, in a network with communication rates {R_{i,j}} between the nodes, we ask what is the set of all achievable joint distributions p(x1, ..., xm) of actions at the nodes of the network. Several networks are solved, including arbitrarily large cascade networks.
Distributed cooperation can be the solution to many problems such as distributed games, distributed control, and establishing mutual information bounds on the influence of one part of a physical system on another."

I'll have to revise this (in light of arxiv:1004.4704, no less!), but it was a very fun lecture to write and give, and covers the essential points. (& of course blew most of the kids minds.)

"his introduction to some of the principal models in the theory of disordered systems leads the reader through the basics, to the very edge of contemporary research, with the minimum of technical fuss. Topics covered include random walk, percolation, self-avoiding walk, interacting particle systems, uniform spanning tree, random graphs, as well as the Ising, Potts, and random-cluster models for ferromagnetism, and the Lorentz model for motion in a random medium. Schramm–Löwner evolutions (SLE) arise in various contexts. The choice of topics is strongly motivated by modern applications and focuses on areas that merit further research. Special features include a simple account of Smirnov's proof of Cardy's formula for critical percolation, and a fairly full account of the theory of influence and sharp-thresholds. Accessible to a wide audience of mathematicians and physicists, this book can be used as a graduate course text. Each chapter ends with a range of exercises."

"Regulatory interactions between genes show a large amount of cross-species variability, even when the underlying functions are conserved ... investigate the ability of regulatory networks to reproduce given expression levels within a simple model of gene regulation ... find an exponentially large space of regulatory networks compatible with a given set of expression level"

More large graph drawing software; part of graphviz.