Evolving Network Topologies

Many (natural) processes, most dominantly evolution, are constantly establishing new components and relations in any (biological) network. Mathematically we need to look at (stochastic) processes that are describing the dynamics of such evolving network topologies accurately. Understanding evolving networks is also essential for understanding the creation process of observed static networks, like road systems, or any other type of infrastructure network. Communication networks with moving entities create a complex constantly changing network topology. Similar transport networks can be found in biological systems, for example the cell. Morphogenetic processes build up networks of blood vessels or neuronal tissue in the developing embryo.

Please note the following time table is still preliminary.

10:00am - 10:30am Welcome Tea & Coffee, Mathematics Common Room.

10:30am - 11:00am Introduction to Workshop Day

11:00am - 12:30am

Peter Grindrod (Reading): Evolving Networks: concepts, inverse problems, propagation and applications 45min

Fatihcan Atay (Leipzig) - Consensus and Synchronization in Time-Varying Networks, 45min

12:30am - 1:30pm Lunch Break, Mathematics Common Room.

1:30pm -3:00pm

Harald Raecke (DIMAP, Warwick) - Hierarchical decompositions for congestion minimization in networks, 45min

Jianfeng Feng (Warwick and Fudan) - Neural Networks 45min

3:00pm - 3:30pm Tea & Coffee, Mathematics Common Room.

Abstracts:

Evolving networks: concepts, inverse problems, propagation and applications

By Peter Grindrod

Abstract: Applications such as neuroscience, telecommunication, on-line social networking, transport and retail trading give rise to connectivity patterns that change over time. In this work we address the resulting need for network models and computational algorithms that deal with dynamic links. We introduce a new class of evolving range-dependent random graphs that
gives a realistic but tractable framework for modeling and simulation.

We develop a spectral algorithm for calibrating a set of edge ranges from a sequence of network snapshots, and give a proof of principle illustration on some neuroscience data. We also show how the model can be used to investigate the scenario where an evolutionary process, such as an epidemic, takes place on an evolving network.

---

Abstract: The complexity of many networks arises not only from the topological structure, but also from the time evolution of the topology. Such networks are common in systems of moving agents, particles, cells, animals, vehicles, and so on. The study of collective behavior on time-varying networks is a challenging topic with many practical implications. In this talk we discuss the relationship of the dynamics to the relevant graph characteristics. In analytical terms, we present the Hajnal diameter of the coupling matrix sequence as a measure of the synchronizability of the graph. Several examples of time-varying graphs are given to illustrate the results, including i.i.d. sequences of random graphs with fixed wiring probability, groups of graphs with random switches between the individual graphs, and graphs with temporary random failures of nodes. In addition, networks with time delays will be considered. We will see that the temporal variation and randomness of the connection topology can enhance synchronizability in many cases; however, there are also instances where they reduce synchronizability.

---

Harald Raecke (DIMAP, University of Warwick, http://www.dcs.warwick.ac.uk/~harry/)
Hierarchical decompositions for congestion minimization in networks"

ABSTRACT: An oblivious routing protocol makes its routing decisions independent of the traffic in the underlying network. This means that the path chosen for a routing request may only depend on its source node, its destination node, and on some random input. In spite of these serious limitations it has been shown that there are oblivious routing algorithms that obtain a polylogarithmic competitive ratios w.r.t. the congestion in the network (i.e., maximum load of a network link).

In this talk I will present a new hierarchical decomposition technique that leads to good oblivious routing algorithms. This decomposition can also be used as a generic tool for solving a large variety of cut based problems in undirected graphs. In particular, it can e.g. be used to design an approximation algorithm for the Minimum Bisection Problem that improves upon the previously known approximation guarantees.