Workshop Speakers
Prof. Krzysztof Apt (University of Amsterdam, Netherlands)
Title: Social Network Games
Abstract: In this lecture we survey our recent works on social network games. They are tailored to study a model of social networks introduced by Apt and Markakis in 2011 in which the nodes influenced by their neighbours can adopt one out of several products. In these games the payoff of each player weakly increases when more players choose his strategy, which is exactly opposite to the congestion games.
We show that such games may have no Nash equilibrium and that determining an existence of a Nash equilibrium is NP-complete. We also clarify the status and the complexity of the finite best response property (FBRP), the finite improvement property (FIP).
Further, we exhibit in this framework some paradoxes. One of them allows us to explain 'bubbles' in a financial market, in which a decision of a trader to switch to some new financial product triggers a sequence of transactions, as a result of which all traders involved become worse off.
Based on joint works with Evangelos Markakis and Sunil Simon.
Download Slides: Social Network Games
Prof. Ken Badcock (University of Liverpool, Pro-Vice Chancellor)
Prof. Themis Bowcock (University of Liverpool, UK)
Prof. Artur Czumaj (University of Warwick, UK)
Title: Testing Cluster Structure of Graphs
Abstract: Cluster analysis is a fundamental task in data analysis that aims at partitioning a set of objects into a disjoint collection of objects with similar characteristics. In this talk, we will use the concept of conductance to measure the quality of cluster structure and will focus on a question of approximately recognizing cluster structure of a graph in sublinear time in the framework of property testing in the bounded degree model. We show how to test in O*(\sqrt{n}) time whether a graph with nodes can be partitioned into no more than k parts (clusters) such that the outer-conductance of each cluster is \phi_o at most and the inner-conductance of the induced subgraph on each cluster is at least phi_i, for a large spectrum of parameters k, phi_o, phi_i. By the lower bound of \Omega(\sqrt{n}) for testing graph expansion, which corresponds to the case when k=1 in our problem, our algorithm is asymptotically optimal up to polylogarithmic factors. This is joint work with Pan Peng and Christian Sohler.
Download Slides: Testing Cluster Structure of Graphs
Prof. Francesco Falciani (University of Liverpool, UK)
Title: Discovering Biological mechanisms by integrating multi-level, large scale biological datasets
Abstract: With the advent of Functional genomics, any competent Biological laboratory can generate genome-wide measurements representing different levels of biological complexity. A consequence of this has been the rapid growth of public databases containing genetics information as well as the results of thousands of gene expression, proteomics and metabolomics experiments. This has generated the expectation that such vast amount of information would result in a rapid increase in our understanding of biology and that this in turn would contribute a whole spectrum of clinically relevant biomarkers, novel drug targets, and ultimately improved personalized therapies.
However, understanding this complexity has proven to be more challenging than expected. The main difficulty has been integrating such large datasets within a computational framework designed to infer the underlying structure of biological pathways from observational data.
In this talk, I will present several case studies demonstrating the successful identification of novel biological mechanisms using a set of network inference techniques. I will also explore the issue of biological interpretability in using computational models for the generation of testable hypothesis.
Prof. Antonio Fernández Anta (IMDEA, Spain)
Title: Saving Energy by Powering Down Links
Abstract: In this talk I will be presenting two related papers that have to do with energy savings in wired networks. In the first paper I present a model that allows to estimate the energy savings of links that implement the new standards IEEE 802.3az Energy Efficient Ethernet, as a function of simple traffic parameters. Under this standard, the link can go to a low power mode when there is not traffic over the link. Then, in a network of (idealized) EEE links, I present algorithms to schedule and route packets in order to reduce energy consumption while maintaining the latency low.
Prof. Paul Goldberg (University of Oxford, UK)
Title: Computing Nash equilibrium with low communication
Abstract: Various recent papers in the CS/game theory literature have attempted to model the computation of game-theoretic equilibria in a decentralised style. That is, for a solution concept to be realistic, it should be obtainable using distributed computation by the agents, as opposed to, say, passing all information about the game to a central controller, who in turn tells everyone how to play. In the talk I will present some results about communication-bounded computation, and how this helps to capture the notion of decentralisation.
Prof. David Hutchison (Lancaster University, UK)
Title: A strategy for network resilience
Abstract: Resilience needs to be one of the most important properties of future computer networks, because of the increasing use of networks as critical infrastructures and their support for mission-critical services. This talk introduces network resilience and a strategy for its realisation, alongside some relevant research issues.
Download Slides: A strategy for network resilience
Prof. Evangelos Kranakis (Carleton University, Canada)
Title: Displacing Random Sensors: Coverage and Interference Problems
Abstract: When placing sensors at random on a line we want to ensure that interference is minimized and coverage is guaranteed. Proximity between neighbouring sensors affects their transmission and reception signals and degrades network performance In fact, the closer their distance the higher the resulting interference and hence performance degradation. Similarly, monitoring a line domain requires that every point in the line is within the range of a sensor.
In general we are interested in the following questions: What is the expected min total sensor displacement required to avoid interference and/or ensure coverage? We study these two problems separately. For the interference problem we develop tradeoffs between theinter-sensor distance and the expected min total sensor displacement and prove the existence of a critical regime. Similarly, for the coverage problem we develop tradeoffs between the sensor range and the expected min total sensor displacement.
Download Slides: Displacing Random Sensors: Coverage and Interference Problems
Prof. Mirek Kutylowski (Wroclaw University of Technology, Poland)
Title: Optimizing Radio Channel Access
Abstract: One of the major challenges of radio communication in ad hoc networks is to synchronize the terminals attempting to send via a shared radio channel. As the prior knowledge of the network state may be unreliable and the state may change dynamically, it is hard to coordinate the terminals and avoid collisions of the transmissions. Our aim is to avoid such collisions and increase channel utilization via self organization strategies. We present some efficient solutions that lead to practical improvements over current industrial practice in terms of reduction of the communication overhead.
Download Slides: Optimizing Radio Channel Access
Dr. Paul Laycock (University of Liverpool, UK and CERN, Switzerland)
Title: How the ATLAS Collaboration used networks to discover the Higgs
Abstract: The ATLAS collaboration is a team of ~3,000 scientists working towards a better understanding of nature, using one of the most complicated experimental apparatus ever built, and analysing datasets measured in Petabytes. This talk will give a brief overview of the many ways in which ATLAS used networks, from computing networks to information networks, to discover the Higgs boson and produce ~300 publications that address fundamental questions in particle physics. The knowledge required to understand both the enormous experimental apparatus, and the diverse physical processes involved in the experimental measurements, is communicated by various means among the collaboration members. The unique detector-level dataset is processed in diverse ways to satisfy the various research interests of the collaboration's members, using a "Grid" of computing resources distributed worldwide. Maintaining individual flexibility for innovation while working efficiently as a collaboration is a complicated problem, both sociologically and technically. At the end of the first phase of the LHC, the ATLAS computing resources were stretched to their limit, provoking a review and subsequent update of the data analysis model and highlighting its importance.
Prof. Alan Marshall (University of Liverpool, Department of Electronics and Electrical Engineering, UK)
Title: Public Access Wireless Networks: Vulnerabilities, Detection and Mitigation Strategies
Abstract: This talk identifies a range of vulnerabilities and threats that can be mounted against domestic and public wireless access networks that employ 802.11 (or Wi-Fi) standards. Compared to enterprise or corporate networks that permit wireless access in a controlled manner, such networks are necessarily more open in nature, in order to provide access to a greater range of users and their wireless devices. Consequently the rapid increase in the use of these networks has led to an associated increase in the number and types of attacks that can be mounted against them, by malicious or criminal users. The talk will outline the types of attacks that can be launched against these types of networks, and identify detection and mitigation strategies.
Download Slides: Public Access Wireless Networks: Vulnerabilities, Detection and Mitigation Strat
Dr. George Mertzios (Durham University, UK)
Title: Determining Majority in Networks with Local Interactions and very Small Local Memory
Abstract: In this work we study the problem of determining the majority type in an arbitrary connected network, each vertex of which has initially two possible types (states). The vertices may have a few additional possible states and can interact in pairs only if they share an edge. We first provide a population protocol with 4 states per vertex that always computes the initial majority value, under any fair scheduler. Under the uniform probabilistic scheduler of pairwise interactions, we prove that our protocol stabilizes in expected polynomial time for any connected network and is quite fast on the clique. It turns out that this protocol is optimal, in the sense that there does not exist any population protocol that always computes majority with fewer than 4 states per vertex. Furthermore we analyze an elegant and very natural majority protocol with 3 states per vertex, introduced in (Angluin, Aspnes, Eisenstat, Distributed Computing, 21(2):87-102, 2008). As it is known that this protocol determines the correct initial majority type in the clique graph very fast and whp under the uniform probabilistic scheduler, we study the performance of this protocol in arbitrary networks. We prove that, when the two initial states are put uniformly at random on the vertices, the protocol of Angluin et al. converges to the initial majority with probability higher than the probability of converging to the initial minority. In contrast, we present an infinite family of graphs, on which the protocol of Angluin et al. can fail, i.e. it can converge to the initial minority type whp, even when the difference between the initial majority and the initial minority is $n - \Theta(\ln{n})$. Finally we present another infinite family of graphs in which the protocol of Angluin et al. takes an expected exponential time to converge. Surprisingly, the resistance of the clique to failure causes the failure in general graphs.
Download Slides: Determining Majority in Networks with Local Interactions and Small Local Memory
Dr. Kieran Sharkey (University of Liverpool, UK)
Title: Epidemic dynamics on networks
Abstract: I will briefly discuss the application of networks in epidemic modelling. I then hope to convey a flavour of two representations of Susceptible-Infectious-Removed (SIR) epidemic dynamics. These are the moment-closure representation as well as the message-passing formalism of Karrer and Newman. Particular focuses are the circumstances under which these two representations become equivalent and the circumstances when they become exact. I will discuss the relative merits of both representations. Although applied in an epidemic context, the underlying principles should be readily transferable to other domains.
Download Slides: Epidemic dynamics on networks
Prof. Iain Stewart (Durham University, UK)
Title: Topological aspects of optoelectronic interconnection networks
Abstract: Interconnection networks are becoming more and more prevalent in computing and appear: on the small-scale, within networks-on-chips; through the medium-scale, in distributed-memory parallel machines; and on the large scale, in datacentres. Whilst there is a lot of commonality as to the importance of their topological properties no matter what the scale, the application area also leads to some divergence. The implementation of the interconnection network also puts new demands on topologies. In this talk I will present an overview of interconnection networks designed to function in a hybrid optoelectronic world where both optical and electronic communication links are employed. The talk will review the swapped (a.k.a. OTIS) networks that were first proposed (along with their properties) before explaining how biswapped and multiswapped networks arose.