AESOP home

News Archive

Congratulations to Daniel Dubois for his best paper at IEEE ICCAC 2015! on 28th September 2015 by Dr Casale:
Congratulations to Daniel Dubois for his paper \"Autonomic Provisioning and Application Mapping on Spot Cloud Resources\", which received the best paper award at ICCAC 2015, the IEEE International Conference on Cloud and Autonomic Computing.
Congratulations to our AESOP PhD Graduates on 6th May 2015 by Prof. Knottenbelt:
No less than six AESOP PhD graduates featured in the Postgraduate Graduation Ceremony of Wednesday 6 May 2015.
They were: Marcel (Chris) Guenther, Gareth Jones, Marily Nika, Demetris Spanias, Iryna Tsimashenka and Polyvios Tsirimpas. Marily also received an Outstanding Achievement Award. Many congratulations to all!
Marily Nika honoured for her outstanding achievements on 15th September 2014 by Dr Jones:
Congratulations to Marily Nika who has been awarded the Imperial College Student Award for Outstanding Achievement for her work as an ambassador and role model for women in computing.
Chris Guenther wins research award on 16th July 2013 by Dr Bradley:
AESOP is delighted to learn that Chris Guenther has just been awarded a 2013 Intel Doctoral Student Honour.
The award was given in recognition of his research into spatial stochastic systems with applications in wireless sensor networks and bicycle hire schemes in cities.
The award citation said:
This was a highly competitive process with many outstanding quality applicants across several universities and exciting areas of research.
Chris was only one of two students to receive the award at Imperial College this year. He will collect the award at the Europe Research and Innovation Conference (ERIC) in October.
Last year Gareth Jones and Daniel (Jack) Kelly both won the 2012 Intel Doctoral Student award.
Congratulations Chris!
Richard Hayden runner up in Distinguished Dissertation Competition on 4th October 2012 by Dr Jones:
Congratulations to Richard Hayden who was awarded runner up prize in the 2012 CPHC/BCS Distinguished Dissertation Competition for his PhD thesis.
Gareth Jones and Daniel (Jack) Kelly on 3rd October 2012 by Dr Hayden:
Congratulations to Gareth Jones and Daniel (Jack) Kelly of AESOP who have both been awarded the highly competitive 2012 Intel Doctoral Student Honor Programme award. The award includes a grant of $35k and technical mentorship from an Intel researcher.
Professor Stephen Gilmore on 17th October 2011 by Dr Bradley:
It is with great pleasure that AESOP learns of Stephen Gilmore's promotion to chair of Software Systems Modelling.
Many congratulations to Stephen from all in AESOP and the Department of Computing.
Jeremy Bradley promoted on 7th April 2011 by Dr Hayden:
Congratulations to Jeremy Bradley who was promoted to Reader today!
Everyone in AESOP offers Jeremy many congratulations!
Dr Douglas De Jager on 5th May 2010 by Dr Bradley:
Dr Douglas De Jager today graduated with his PhD from Imperial College London.
He completed staunch work on asynchronous iterations in performance models and PageRank in March 2009. Many congratulations from everyone in AESOP.
Dr Abigail Lebrecht on 28th January 2010 by Dr Dingle:
Many congratulations from everyone at AESOP to Abigail Lebrecht who successfully passed her PhD viva today!
Giuliano Casale joins AESOP on 12th January 2010 by Dr Bradley:
The AESOP group is delighted to welcome Dr Giuliano Casale as a Junior Research Fellow to the group.
Giuliano joins us from SAP Research, Belfast where he held an industrial research position. He has held previous positions at the College of William and Mary, UCLA and Milan.
His research interests include: Quantitative evaluation of computer systems and networks; Performance modelling: capacity planning, queueing, burstiness, demand estimation; and Simulation tools, workload characterization, cost-performance optimization.
The Junior Research Fellow (JRF) programme is a prestige fellowship run by Imperial College and offered to only a few very talented researchers every year from any science or engineering discipline.
Will Knottenbelt promoted on 13th July 2009 by Dr Bradley:
Many congratulations go to Will Knottenbelt who is promoted to Reader, it was announced today.
Jeff Magee said of the promotion "I am sure you will join me in congratulating Will Knottenbelt - promoted to Reader in Applied Performance Modelling. Well done Will."
Everyone in AESOP offers Will many congratulations.
Helen Yu Zhang and Douglas de Jager pass PhD viva on 29th June 2009 by Dr Bradley:
Helen Yu Zhang and Douglas de Jager are to be congratulated on passing their PhD vivas.
Both passed with minor corrections. Peter Harrison said that he was delighted by Helen's success which was hugely deserved. Douglas received excellent comments from his examiners who were impressed with his developments in asynchronous iterative solution of performance models. Well done both.
AESOP friends get promotion on 25th June 2009 by Dr Bradley:
AESOP is delighted to congratulate Helen Wilson, Nigel Thomas and Aad van Moorsel on their recent promotions.
Helen and Nigel have recently been promoted to Reader at UCL and Newcastle and Aad van Moorsel has got a chair at Newcastle. Congratulations to all of them!
AMPS PostDoc RA Vacancy on 14th February 2009 by Dr Bradley:
Deadline for applications 24 February.
We are looking for a highly qualified person to fill a PostDoc RA with the AESOP research group, Dept. of Computing, Imperial College London.
Position: Research Associate
Project: Analysis of Massively Parallel Stochastic Systems
Funding body: EPSRC
Duration: 36 months with possibility of 6 month extension
Starting: between March and August 2009
Salary: £26,580–£29,550 per annum
Closing Date: ** 24 February 2009 **
Project details: AMPS project
Apply now: Hard copy application form and further details
Please contact Jeremy Bradley for any informal queries.
Complexity Science Seminars on 29th January 2009 by Dr Harder:
The Maths Institute is running a seminar series with some interesting titles.
Dr Tamas Suto on 3rd December 2008 by Dr Bradley:
Many congratulations from everyone at AESOP to Tamas Suto who successfully passed his PhD viva today.
Will emailed the group with the following news:
Congratulations to Tamas who has just passed his viva with (very) minor corrections :)! I'm sure an announcement about drinks with Dr Suto will follow shortly!
Computer Journal Lecture on 18th November 2008 by Dr Bradley:
Professor Harrison to give Computer Journal Lecture at the BCS on 18 December 2008.
The Computer Journal presents: Turning Back Time - What Impact on Performance?
A Lecture by Professor Peter Harrison - Imperial College London. The Lecture will be followed by a debate. The Lecture itself and the discussion following it will be edited by the Computer Journal.
Date: Thursday 18th December 2008
Venue: BCS London Office
Time: 5.30pm Registration, 6.30pm Lecture and debate followed by a drinks and buffet reception.
Booking and location information: through BCS website
AMPS PhD Studentship available on 14th November 2008 by Dr Bradley:
Applications open for a PhD in performance analysis and stochastic modelling as applied to large distributed software systems.
AMPS (Analysis of Massively Parallel Stochastic Systems) is an ambitious project designed to apply the very latest fluid performance analysis techniques to massively parallel software architectures such as publish-subscribe systems and electronic voting systems. The project involves collaboration between the Department of Computing's AESOP group, Newcastle University, IBM Hursley and the University of Illinois's PERFORM research group. The overall goal of the project is to integrate new mathematical techniques into major performance toolsets and use them to assess performance and scalability of important software and security architectures.
The PhD studentship will initially focus on developing performance models in the target application area, that of distributed software architectures. We will aim to develop some initial performance models for some generic publish-subscribe architectures relatively quickly. It will be expected that the successful student will collaborate closely with researchers and engineers at IBM Hursley over a period of several months over the lifetime of the studentship. After this initial stage there is flexibility in the scope of the project, with possible avenues including exploration of: novel fluid analysis techniques, optimised solution algorithms, parallelisation of analysis techniques and integration with existing performance toolsets.
The successful student will be expected to work as part of a team, with the academics, project RA and other project members and associates as part of AMPS. They will also be expected to participate fully in the research activities of the AESOP research group at Imperial. Detailed knowledge of at least one of Java, C/C++, Matlab, Mathematica or Maple will be essential. Applicants should have or expect to receive a high 2:1 or 1st in a Computing or Mathematically-based degree; or a distinction in an MSc in Computer Science. The studentship is expected to commence either in April or October 2009.
For further project information visit: AMPS project page
Potential applicants should contact Jeremy Bradley in the first instance:
Applications will be processed through the college's online PhD admissions system. Note that full support is available only to UK/EU applicants.
AMPS Awarded on 15th September 2008 by Dr Bradley:
We are pleased to announce that EPSRC decided on 19 Sept to fund the project, Analysis of Massively Parallel Stochastic Systems (AMPS).
The project represents a substantial step forward in efforts to deliver fast fluid-style analysis of massive computer systems and industrially-sized applications. It is a major collaboration with Nigel Thomas and Aad van Moorsel, Newcastle University. Also as project partners are IBM Hursley who are interested in applying the technology to their PubSub systems and the University of Illinois at Urbana-Champaign through Bill Sanders and the PERFORM group. We look forward to working successfully with all of them.
SPECTS Best Paper Award on 18th June 2008 by Dr Bradley:
Congratulations to Oliver Haggarty for winning the best paper award at SPECTS 2008.
Oliver's paper was based on his MSc thesis and covered the implementation of passage time calculations based on the Google MapReduce distributed framework:
Oliver's paper is entitled Distributed Response Time Analysis of GSPN Models with MapReduce and was selected from 140 submissions.
FAQ Awarded on 25th April 2008 by Dr Bradley:
Peter Harrison and Tony Field receive £429000 from EPSRC for the project Fluid Approximations for Quantitative Analysis (FAQ).
They aim to study fluid analysis of networks of queues, specifically, hierarchical approaches in the analysis of fluid systems, analogous to those that are well developed in traditional discrete-state models.
UKPEW 2008 on 11th February 2008 by Dr Harder:
The AESOP group is hosting this year (2008) 24th UK Performance Engineering Workshop.
The workshop takes place 3-4 July 2008. More details can be found at the UKPEW website.
iPODS PhD Studentship on 19th October 2007 by Prof. Knottenbelt:
Applications are invited for a PhD studentship funded by our EPSRC grant Intelligent Performance Optimisation of Virtualised Data Storage Systems (iPODS). More details on
Closing Date: 7 November 2007
Richard Hayden wins SET award on 21st September 2007 by Dr Bradley:
Many congratulations to Richard Hayden who last night won The Microsoft Research Award for the Best Computational Science Student at the Science, Engineering & Technology Student of the Year.
The event took place after a dinner reception at Alexandra Palace in London. Richard won the prize for his undergraduate project: Fluid-flow solutions to the state space explosion problem.
PASTA workshop closes on 27th July 2007 by Dr Bradley:
PASTA 2007 came to a successful conclusion today. We had over 30 attendees and 16 presenters making it one of the largest PASTA workshops held. Many thanks to all the attendees who contributed enormously to the workshop; a special mention to Ashok Argent-Katwala and Uli Harder who looked after all the organisation.
It was a splendid event, and much enjoyed by everyone. The PASTA 2007 proceedings and slides can be found online. Look out on the AESOP conference page for next year's PASTA announcment.
Tony Field wins Imperial teaching award on 2nd July 2007 by Dr Bradley:
Congratulations to Tony on winning the Award for Teaching Excellence in Engineering.
Head of Department, Jeff Magee, said in a mail to the department:
"I am sure you will all join me in congratulating Tony Field who has just won a very prestigious Award for Teaching Excellence in Engineering. These awards are given in recognition of individuals or teams who are renowned for the excellence of their teaching and who have made a broad and deep impact on enhancing the student learning experience at Imperial College. I think we all - staff and student alike - agree that the award is richly deserved."
iPODS success on 1st July 2007 by Dr Bradley:
Congratulations to Will and Pete for getting their latest grant, iPODS, which will hopefully see Nick Dingle return from the wilds. It will be splendid to have Nick back in the group again!
HPCS Best Paper Award on 6th June 2007 by Prof. Knottenbelt:
Many congratulations to Pete and Soraya who have won the Best Paper award at the 2007 High Performance Computing and Simulation Conference (HPCS 2007) for their paper "Multi-RAID Queueing Model for Zoned Disks".
Peer to Peer meeting on 21st May 2007 by Dr Harder:
On Wednesday 13 June 2007 from 3.30pm to 5pm we have arranged a meeting with members of the networking group from EE at UCL.
They are working on a project called Peerlive that explores market models for selling network bandwidth. At the meeting we will have short presentation and a hopefully lively discussion. The meeting is in 217 and all AESOP members are welcome to join in.
Dr Argent-Katwala and Dr Trifunovic graduate on 9th May 2007 by Dr Bradley:
Congratulations to Dr Ashok Argent-Katwala and Dr Aleksander Trifunovic on their PhD graduation last Wednesday.
Pictures of the protagonists can be found below:
Dr Aleksander Trifunovic
Dr Ashok Argent-Katwala
Will Knottenbelt receives RAE Engineering Teaching Prize on 3rd May 2007 by Dr Bradley:
Many congratulations to Will Knottenbelt who has been awarded a prestigious teaching award by the Royal Academy of Engineering.
The award, which was officially announced at the end of March, recognises "lecturers who have been seen to promote engineering as a rewarding and creative career and in establishing industrial-academic links".
Only 6 prizes were awarded. More information can be found at: Royal Academy of Engineering Teaching Prize 2007
Royal Society meeting - Networks: modelling and control on 2nd May 2007 by Dr Harder:
A two-day Royal Society discussion meeting on Networks: modelling and control will be held in London on September 24-25.
This meeting will discuss mathematical, computational, and statistical issues common to transport and communication networks.
A draft program is available, where you can also register to attend. Registration is free.
QEST 07 deadline extended on 14th March 2007 by Dr Thornley:
The QEST 2007 submission deadlines have been extended to abstract March 24th, full paper March 31st.
PhD Ads for Spartacos and Grid Markets on 30th January 2007 by Prof. Harrison:
PhD Studentships (UK/EU)
We invite applications for two EPSRC funded PhD positions with the AESOP group in the Department of Computing at Imperial College London.
1) A PhD studentship is available for an interdisciplinary project "Market Models for Grid Computing". The project involves theory and numerical simulation of agent based models that describe human behaviour in competitive market situations involving a perishable resource. In particular the project will address the types of markets in services, compute cycles and other resources that could arise in the context of the next-generation Internet. The project brings together expertise in complex systems, econophysics, agent based simulations, stochastic modelling and performance evaluation in networked systems. Opportunities exist for collaborations with physicists, economists and operations research specialists in Europe and North America. The project Investigators are Professors Peter Harrison and John Darlington at Imperial College and it is coordinated by Dr. Uli Harder with close involvement of the Complexity Science Group at the University of Calgary.
2) A PhD studentship is available for the project "Spartacos", which is investigating the theory and development of Markovian Process Algebra (MPA), properties of response time distributions and algorithms for response times in networks. In particular, the PhD student will have the opportunity to explore the new area of fluid MPA, where models have a continuous (real number) state and so are analysed through (coupled) differential, as opposed to difference, equations. The theoretical output offers the prospect of a new approach to the quantitative design of systems of interacting processes: in ICT, commerce, the environment and perhaps biology through fluid models. The practical impact will be to endow diverse system design tools with a powerful and efficient performance analysis capability. This will be overseen and disseminated through active collaboration with industrial partners that include IBM.
Both studentships ideally start on 1 April 2007, but can be deferred to 1 October 2007. The closing date for applications is 1 May 2007. The studentships cover EU fees and are at the standard EPSRC rate of about £13k p.a. for three years. Students with a background in computing, theoretical computing, complexity, theoretical physics or applied mathematics are encouraged to apply. Applications should include a full CV and include the names and addresses of two referees. The successful applicant will be asked to register as an Imperial College PhD student.

Please note that the closing date for applications has passed.

Market Models for Grid Computing on 1st August 2006 by Dr Harder:
A PhD studentship in the Department of Computing at Imperial College London is available for an interdisciplinary project "Market Models for Grid Computing".
The project involves theory and numerical simulation of agent based models that describe human behaviour in competitive market situations involving a perishable resource. In particular the project will address the types of markets in services, compute cycles and other resources that could arise in the context of the next-generation Internet. The project brings together expertise in complex systems, econophysics, agent based simulations, stochastic modelling and performance evaluation in networked systems. Opportunities exist for collaborations with physicists, economists and operations research specialists in Europe and North America. The project Investigators are Professors Peter Harrison and John Darlington at Imperial College and it is coordinated by Dr. Uli Harder with close involvement of the Complexity Science Group at the University of Calgary. Students with a background in theoretical physics, complexity, computing or applied mathematics are encouraged to request an application pack.
Please note that the closing date for applications has passed.
PASTA 2006 at Imperial on 1st July 2006 by Dr Bradley:
Friday saw the completion of PASTA 2006, an informal gathering of academics who share an interest in stochastic process algebra research.
This PASTA was a most enjoyable event with a meal at Jakobs, a trout from Tony, a bowl of pasta from Ashok, football in the evening and some excellent papers and tutorials. Many thanks to all who contributed to a great couple of days.
Camelot cluster now available! on 5th June 2006 by Prof. Knottenbelt:
Thanks to the sterling work of CSG, the AESOP group's "camelot" cluster is now available for use!
The camelot cluster consists of 16 dual processor, dual core nodes called camelot01..16. Each node is a Sun Fire x4100 with two 64-bit Opteron 275 processors and 8GB of RAM, and is connected with both gigabit ethernet and Infiniband interfaces. These run the 64-bit version of the current DoC Linux distribution; 32-bit binaries *may* run but there are no guarantees -- you are strongly recommended to recompile any software to native 64-bit.
The Infiniband fabric runs at 2.5Gbit/s and is managed by a Silverstorm 9024 switch.
A fileserver called excalibur (not for general login at the moment) provides NFS access to /vol/grail/ -- a 4.7TByte filesystem, stored on a Sun Storedge 3120 across 12 500GB disks. This space is not currently backed up -- CSG have plans to do this in the future but are not yet able to do so.
Although this cluster was bought for use on the GRAIL grant, AESOP members should please feel free to use it (and the associated file space) for other projects!
More detailed usage instructions.
QEST paper for Thornley and Zatschler on 24th May 2006 by Dr Thornley:
After a tense wait for the delayed notification, we learn that our paper – Exploring correctness and accuracy of solutions to matrix polynomial equations in queues – has been accepted to the QEST 2006 conference this year.
The paper explains and illustrates previously unrecognized shortcomings of the matrix geometric approach to queue solution. It also finally establishes that the spectral expansion approach is necessary for the solution of a class of queues to which our favourite queue based on geometric batches belongs.
Dr Harini Kulatunga I presume! on 23rd May 2006 by Dr Bradley:
Many congratulations to Harini on passing her PhD viva with very minor corrections on Monday 22nd May!
Jane Hillston awarded personal chair on 4th April 2006 by Dr Bradley:
We are delighted to learn that Jane Hillston has been awarded a personal chair in quantitative modelling at The University of Edinburgh, while Stephen Gilmore has been promoted to Reader.
In a mail to the aesop list, Stephen said:
The University [of Edinburgh] has promoted Jane Hillston to a personal chair in stochastic modelling, in recognition of her work on PEPA and her work in developing the field of stochastic process algebra. She has the distinction of being the first woman to be promoted to a personal chair in the subject area of computer science at The University of Edinburgh.
In response Jane replied:
Stephen forgot to mention that he also has good news of his own. The University has also recognised his excellent work on PEPA and decided to promote him to Reader.
We all wish them many congratulations on their hugely deserved promotions.
New and interesting looking papers on 28th March 2006 by Dr Harder:
This is a list of papers that caught my attention this morning whilst browsing the listings.

Computer simulation of language competition by physicists
Authors: Christian Schulze, Dietrich Stauffer
Comments: For econosociophysics book edited by Chakrabarti, Chakraborti and Chatterjee; 24 page review
Subj-class: Physics and Society
Computer simulation of languages is an old subject, but since the paper of Abrams and Strogatz (2003) several physics groups independently took up this field. We shortly review their work and bring more details on our own simulations.

Self-Assembly of Information in Networks
Authors: M. Rosvall, K. Sneppen
Comments: 4 pages and 4 figures, Java simulation available at this http URL
Subj-class: Physics and Society
We model self-assembly of information in networks to investigate necessary conditions for building a global perception of a system by local communication. Our approach is to let agents chat in a model system to self-organize distant communication-pathways. We demonstrate that simple local rules allow agents to build a perception of the system, that is robust to dynamical changes and mistakes. We find that messages are most effectively forwarded in the presence of hubs, while transmission in hub-free networks is more robust against misinformation and failures.

Structure of Peer-to-Peer Social Networks
Authors: Fang Wang, Yamir Moreno, Yaoru Sun
Comments: APS Style, 8 pages, 5 figures and 4 tables. Final version
Subj-class: Physics and Society
Journal-ref: Physical Review E 73, 036123 (2006)
DOI: 10.1103/PhysRevE.73.036123
This paper presents a statistical analysis of the structure of Peer-to-Peer (P2P) social networks that captures social associations of distributed peers in resource sharing. Peer social networks appear to be mainly composed of pure resource providers that guarantee high resource availability and reliability of P2P systems. The major peers that both provide and request resources are only a small fraction. The connectivity between peers, including undirected, directed (out and in) and weighted connections, is scale-free and the social networks of all peers and major peers are small world networks. The analysis also confirms that peer social networks show in general disassortative correlations, except that active providers are connected between each other and by active requesters. The study presented in this paper gives a better understanding of peer relationships in resource sharing, which may help a better design of future P2P networks and open the path to the study of transport processes on top of real P2P topologies.

Trainspotting: Extraction and Analysis of Traffic and Topologies of Transportation Networks
Authors: Maciej Kurant, Patrick Thiran
Comments: 9 pages, 7 figures
Subj-class: Physics and Society
The knowledge of real-life traffic pattern is crucial for good understanding and analysis of transportation systems. This data is quite rare. In this paper we propose an algorithm for extracting both the real physical topology and the network of traffic flows from timetables of public mass transportation systems. We apply this algorithm to timetables of three large transportation networks. This enables us to make a systematic comparison between three different approaches to construct a graph representation of a transportation network; the resulting graphs are fundamentally different. We also find that the real-life traffic pattern is very heterogenous, both in space and traffic flow intensities.

Laws of Graph Evolution: Densification and Shrinking Diameters
Authors: Jure Leskovec, Jon Kleinberg, Christos Faloutsos
Subj-class: Physics and Society; Data Analysis, Statistics and Probability
How do real graphs evolve over time? What are ``normal'' growth patterns in social, technological, and information networks? We study a wide range of real graphs, and we observe some surprising phenomena. First, most of these graphs densify over time, with the number of edges growing super-linearly in the number of nodes. Second, the average distance between nodes often shrinks over time, in contrast to the conventional wisdom that such distance parameters should increase slowly as a function of the number of nodes (like O(log n) or O(log(log n)).
Existing graph generation models do not exhibit these types of behavior, even at a qualitative level. We provide a new graph generator, based on a ``forest fire'' spreading process, that has a simple, intuitive justification, requires very few parameters (like the ``flammability'' of nodes), and produces graphs exhibiting the full range of properties observed both in prior work and in the present study.
We also notice that ``forest fire'' exhibits a sharp transition between sparse graphs and graphs that are densifying. Graphs with decreasing distance between the nodes are generated around this transition point. Last, we analyze the connection between the temporal evolution of degree distribution and densification of a graph. We find that the two are fundamentally related.

Effect of CSMA/CD on Self-Similarity of Network Traffic
Authors: Altyeb Altaher
Comments: 4 pages, 2 figures
Subj-class: Networking and Internet Architecture
ACM-class: C.2.5
It is now well known that Internet traffic exhibits self-similarity, which cannot be described by traditional Markovian models such as the Poisson process. The causes of self-similarity of network traffic must be identified because understanding the nature of network traffic is critical in order to properly design and implement computer networks and network services like the World Wide Web. While some researchers have argued self similarity is generated by the typical applications or caused by Transport layer Protocols, it is also possible that the CSMA/CD protocol may cause or at least contribute to this phenomenon. In this paper, we use NS simulator to study the effect of CSMA/CD Exponential Backoff retransmission algorithm on Traffic Self similarity.
Triple grant success for AESOP on 19th March 2006 by Dr Bradley:
Members of AESOP have had 3 EPSRC grants come through in the first 3 months of 2006: SPARTACOS, PerformDB and Grid Market.
The success of SPARTACOS, PerformDB and grid-market means initially that Maria Vigliotti, Uli Harder and Ashok Argent-Katwala will be able to stay on as RAs with AESOP for another 2-3 years. Excellent news!
Tim Evans on Complex Networks on 8th February 2006 by Dr Harder:
Tim Evans will give a talk on Complex Networks.
Ash and I have attended talks by him previously on the same subject. You can find the summaries of those talks in the News Archive. Tim will present an updated version of those talks.
Talk details:
Tim Evans
Complex Networks
21 Feb 2006, 4pm
Room 217
Links for Tuesday's talk on 18th January 2006 by Dr Harder:
Here is the collection of URLs that I pointed to in my presentation on 17 January 2006.
Mark Newman's power law review:
Paper showing that rank/frequency plots and cdfs are equivalent:
Renormalisation for Pedestrians:
Maya's paper: or at
Dr. Trifunovic I presume? on 8th January 2006 by Prof. Knottenbelt:
Congratulations to Alex Trifunovic who passed his PhD viva (with minor corrections) on Friday 6 January!
The examiners (Prof. Rob Bisseling from the University of Utrecht, Netherlands, and Dr. Richard Overill from Kings College London) were impressed by Alex's contribution to and mastery of parallel hypergraph partitioning.
New member of AESOP - Harini Kulatunga on 16th November 2005 by Dr Bradley:
A big welcome to Harini Kulatunga, who joins AESOP as an RA on the GRAIL project.
She is about to submit her PhD. in electrical engineering and specifically signal processing at Sheffield University.
Promotions on 11th July 2005 by Dr Argent-Katwala:
Congratulations to Tony Field and Will Knottenbelt on their recent promotions.
Tony is now a Reader in Performance Engineering and Will is a Senior Lecturer.
AESOP PhD/MSc Graduation on 18th May 2005 by Dr Bradley:
AESOP members Nick Dingle, Douglas de Jager, Maria Vigliotti and Harf Zatschler were awarded their respective PhDs and MSc in the Royal Albert Hall today.
In a moving ceremony - it moved incredibly slowly - in which nearly 2500 MSc and PhD students received their higher degrees - proceedings were brightened by the conferring of 4 stalwart AESOP members. Many congratulations from all!
Paparazzi shots of the event were taken by a hidden camera.
Erol Gelenbe elected member of Academia Europaea on 17th May 2005 by Dr Harder:
Erol Gelenbe has been elected on first nomination to the Academia Europaea in the Math/CS section.
He was was the only computer scientist elected this year, together with two mathematicians. The Academia Europaea membership in CS includes 29 members, all in the theory of programming and algorithms areas including logicians such as Burstall, Milner and Dana Scott. Erol Gelenbe is the only member of the Math/CS section who is in the systems/networks areas. In the applied probability areas the current members are David Cox, David Kendall, and Dieter Stoyan, while in more theoretical stochastic modelling, members include JM Bismut and Alain Bensoussan. The pure math folks include all the living European Fields Medalists plus some others. Imperial College members include emeritii David Cox FRS, Eric Ash FRS, as well as Roy Anderson FRS who is the current chief scientist of the UK MoD, and Simon Donaldson FRS, the Fields Medalist.
The impact of vaccination on the epidemiology of infectious diseases: the role of Mathematics on 28th April 2005 by Dr Harder:
Sketchy notes of Roy Anderson's talk on 27 April 2005 as part of the Institute of Mathematical Sciences Launch week.
- history of epidemiology starts with Hippocrates
- first mathematical model: Daniel Bernoulli 1760
- vaccination success, eradication, is possible if the traget develops genetically slow.
- smallpox eradiacted, but it still exists
- Influenza A: France has got the "best" reporting (daily) system
- antibodies in saliva
- study individuals in labs
- SIR model:
- critical population density, i.e. it's a modern problem
- basic reproductive number, no. of secondary infections caused by one individual, R_0
- development of disease: establishment, exp. growth, exhaustion of susceptibiles, equilibrium (this is less predictable the faster the growth is)
- immunization perturbs situation and can make things worse
- introduce age as parameter -> PDE w.r.t. age
- immunization tries to reduce R_0 < 1
- there tends to be a critical magnitude for each cohort of birth that needs to be immunised
- measles show cyclic behaviour, school holidays act as oscillatory force
- SEIR model:
- heterogenous age mixing -> better results
- introduce 'Who acquires infection from whom', or WAIFW, matrix
- the same disease can have different effects with age, that's how immunisation can make things worse
- this shift of disease peak depending on age can be predicted
- plot percetage of vaccination against benfits -> critical percentage
- waiting times between epidemics and sizes of epidemics follow a power law
- there is a critical community size
- stochastic models not well understood
- meta-population models mixing SEIR models: one way to include spatial dynamics
- parameters: census data OR mobile phones! Distribution of distance travlled against no. of people is broadly distributed, looks log-normal or Cauchy-ish, 1/(1+x^a), Ferguson et al. 2005 to be published
- source of world population data: Landscan:
Hotel Ceilidh-Donia WiFi network on 2nd April 2005 by Dr Bradley:
AESOP's favourite Edinburgh hotel has just installed a WiFi router in the bar area.
Coverage does not extend beyond the ground floor but according to Max, they plan to extend it to cover all the rooms soon.
Imperial College London day on networks on 1st April 2005 by Dr Harder:
Imperial College London day on networks: dynamics, function and properties.
31 March 2005 09:30 - 31 March 2005 17:00
Ash and I went to this workshop in Clore Lecture Theatre organised by Prof. Henrik Jeldtoft Jensen. Below is an annotated programme of the event.
9.00-9.10 Introduction. Henrik J. Jensen
This meeting was backed financially by the Mathematics Institute. There was talk about a network initiative by the institute similar to the current programmes they run. Also, there was a possibility of a bigger workshop in Spring 2006.
9.10-9.40 Michael Stumpf , Sampling properties of random graphs and their role in molecular networks.
This talk was mainly about protein interaction networks (PINs). One thing he was looking at was network changes in the connection of evolution. He showed some network graphs where the degree of the nodes was colour coded which looked quite nice. In a recent paper (below) he investigated how random sampling of a network reflects the actual network structure. Whilst random subnetworks of ER-graphs are the same as the original, this is not true for scale-free graphs. Proportional sampling makes this even worse. Also, mentioned "network motifs".
Michael P. H. Stumpf, Carsten Wiuf, and Robert M. May
From the Cover: Subnets of scale-free networks are not scale-free: Sampling properties of networks PNAS 2005 102: 4221-4224;
9.40-10.10 Jeroen Lamb, Bifurcations in networks.
Mainly about smaller networks where symmetry influences the dynamics. Networks describe differential equations. Designer dynamics are possible where a system can not go into certain oscillations/rhythms. Lie-algebras.
10.10-10.40 Mauricio Barahona Dynamics on networks: synchronization and other biologically motivated examples.
Networks are everywhere but not necessarily meaningful. However, for instance the mammalian cell cycle and the New York power grid do look similar! Described an interesting "experiment" to see how the graph structure effects the behaviour of a dynamical system, by varying the structure from deterministic graphs, over small-world/scale-free networks to random graphs. One of PhD students works with stochastic processes on lattices (Martin Hemberg).
10.40-11.10 Coffee.
11.10-11.40 Martin Howard, A stochastic subcellular oscillator in bacteria.
Not much networking in this talk, still use of Monte Carlo simulations and stochastic processes.
11.40-12.10 Tim Evans, Scale Free Networks from Self-Organisation.
The power law in the Barabassi style preferential attachment models creating scale-free networks depends crucially on the attachment probability being linear. This seems to be a bit unrealistic. Is there a more robust way to create these graphs? Introduces random walk that only uses local information to rewire any existing graph into a scale-free network. The degree correlation lengths trend to be small. The random walks can be used to measure the degree distribution for the underlying graph. (Good news for web-crawls!). It's possible to work out finite size effects. For more details see Scale Free Networks from Self-Organisation.
12.10-13.30 Lunch break
13.30 - 14.30 Kim Sneppen, Guest Speaker. Structure and communication in complex networks
Talks about Yeast (see Specificity and stability in topology of protein networks, Science, 296, 910 (2002) 02870 (2005)) and how the amplification factor (number of nodes infected after one step) favours fast spreading in power law networks. This makes broadcasts easy. Different network types behave differently for searches and information flows more easily in some directions (hierarchical networks). This effects for instance navigation in a city, see Networks and Cities: An Information Perspective and Navigating Networks with Limited Information. So, there are "good" and "bad" cities. Betweenness of a node: how often is a node part of a path between other nodes. Information Horizons in Networks searches in real networks are difficult. There are short paths, but how do you find it? See also Hierarchy measures in complex networks, Phys. Rev. Lett. 92, 178702 (2004).
14.30-15.00 Ray Rivers, Modelling trading links in the Early Bronze Age Aegean; More than another phase transition?
15.00-15.30 Coffee
15.30-15.50 Catherine O'Sullivan, Networks and granular materials.
Interesting work on network structures in soil that changes under stress.
15.50-16.10 Michael Bell, Risk-averse in-vehicle route guidance for road networks.
Outline of the "OFFENSIVE" project. P2P networks for car navigation? Route search algorithm: A* Hart & Nilson 1968, presumably this is the complete reference: P.E. Hart, N.J. Nilsson, and B. Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. on Systems Science and Cybernetics, 4(2):100--107, 1968.
16.10-16.30 Roger Woledge, Modelling the crossbridge cycle in muscle contraction.
Modelling muscle movement.
16.30-16.50 John Polak, Dealing with problems of partial and incomplete data in large scale transport network modelling
This had interesting ideas how to extract pdfs of processes from various sources of incomplete data.
Mathematics for Networks on 24th March 2005 by Dr Harder:
Wednesday 23 March at Queen Mary University of London
Ash and I went to the above meeting and here is a quick summary of the notes I took.
Some problems related to power control in mobile wireless networks
Sverrir Olafsson, British Telecom
Sverrir Olafsson
There are difficulties using the power control algorithm for cellular systems for ad hoc networks. The main aims of any power algorithm are
- reduce near/far effect
- reduce interference
- reduce background noise level
This can be done by optimising the signal to noise ratio for a set of mobile devices. There is an iterative algorithm by G.J. Foschini and Z. Miljanic, "A simple distributed autonomous power control algorithm and its convergence," IEEE Trans. veh. Technol., vol. 42, no. 4, pp. 641--646, November 1993, that has been shown to be Pareto optimal by Mitra. However, in an ad hoc network there is no base station and the problem is therefore not centralised.
Current research for dynamic power control aims to be better than MAC-level heuristics in use today. New approaches including the use of differential equations have been made. Another way is to use game theory for a common shared resource, see .
Internet Routing Dynamics
Timothy Griffin, Intel/University of Cambridge
this talk was mainly about BGP, the protocol used by internet routers to exhange information about best routes. BGP is a distributed algorithm where information flows to nearest neighbours only. Mainly information is exchanged when changes happen (hard-state protocol). If there are no route changes, there is no flow of information. Timothy showed a lot of graphs of the information flow between routers. To gather this data one can use Zebra: which pretends to be a router and collects the update information. There are also archives for such information:
To decrypt the data you need a program like route_btoa, .
Another interesting invention are BGP beacons: . These "router" send periodic signals into the BGP system that can be used for calibration of experiments.
Some numbers: 50,000 - 200,000 routers run BGP, this number is guessed as there is no way to find out. There are roughly 100,000 ASNs in use.
Something about cellular networks
C.K. Toh, Electronic Engineering QMUL
Hm. Well, I think I was longing for coffee during this talk. I even forgot to write down its title!
Markov Chains and Buffering Strategies in Networks
Richard Clegg, University of York
Richard showed how to use infinite Markov chains to create long range dependent data that can be used to model network traffic. I think this is summarised in . He also reported strange discrepancies in the behaviour of auto-correlation function.
Utilising public in formation in Network Coding
Soren Riis, QMUL
The main thing I took away from this talk is that you can think about data flows as waves subject to interference. More information about network coding is at: .
Traffic, Topology, Congestion and Scalability
Raul Mondragon, QMUL
Raul showed how an addition to the Barabasi-Albert model can produce a more realistic model of internet connectivity. In this model existing nodes also grow new links with other existing nodes. This capture the rich-club core feature. More is at this webpage:
Complex Networks on 9th March 2005 by Dr Harder:
Talk by Tim Evans
Ashok and I went to a talk by Tim Evans this afternoon (9 March). At the beginning of the talk a College Network Day on 31 March was mentioned, organised Prof. Jensen.
Executive summary as I remember:
The talk was loosely based on a recent publication, "Complex Networks" in Contemporary Physics. For an electronic version go to Contemporary Physics or
In his talk Tim Evans introduced first introduced Random Networks (Erdos,Renyi) and basic concepts for graphs (or networks):
- nodes and vertices
- network distance: shortest paths between nodes
- diameter of a graph: the longest of the shortest paths
- degree of a node: the number of nearest neighbours
- clustering coefficient: the fraction of nearest neighbours that are connected. This conveys information on the local structure
After Random Networks there came "small world networks", Watts & Strogatz 1998. Motivated by the fact that real networks are neither lattices nor random graphs (Milgram). One way to get a small world graph is to to start with a ring of nodes where the nearest and 2nd nearest neighbours have a direct connection. Then some connections get randomly rewired creating shortcuts: This brings the distance down whilst maintaining the clustering coefficient (almost). Too many rewiring operations create a random network. A small world network has got local structure and shortcuts.
Barabassi & Albert introduce a new model in 1999: scale-free networks. This is inspired by looking at degree distributions of www graphs. They show a power law in the degree distribution, which neither lattices, random networks or small world networks do. Power law indicate scale free behaviour, this is what gets physicists excited! Scale-free refers to the fact that for a scale free distribution (like a power law) the ratio of number this "things" (like vertices in the network) at scale k and scale N*k, for example, is fixed. The system has got no intrinsic scale.
Power law are necessary but not sufficient for exciting physics to happen:
- 2nd order phase transitions
- critical phenomena <-> renormalisation group
- scaling in particle physics
Power laws have been known for a long time:
- Biology: Kleiber's law of the metabolic rate
- Social Sciences: Zipf (1949), city size, word frequency
(compression), Pareto: wealth
Is the power law a statistical quirk or a sign that the system is in a state of optimal organisation?
In self-organised criticiality there are power laws in:
- Earthquakes
- forest fires
- rice piles
- rainfall distributions
- etc.
People have looked at e-bay buyer/seller networks, Greek Gods, data from Imperial's lending library. Interesting for areas such as:
- search algorithm (Milgram's original experiment)
- network resilience, failure under random and targeted attack.
Anyone interested in more details this should read the paper by Tim Evans, or get Duncan Watt's book "Six degrees". I'm reading the latter at the moment and can only recommend it.
Luna Cluster operational on 9th February 2005 by Dr Argent-Katwala:
New 8-node computational cluster for the group.
Will Knottenbelt writes:

i'm very happy to announce the availability of the "luna" computational cluster.

we have 8 dual processor nodes (called luna01, luna02, ... , luna08), each with two 3GHz processors and 2GB RAM. the interconnect is gigabit ethernet. the nodes run linux and are connected to the department's file space by NFS (so you can just ssh in as usual). all aesop members are welcome to use the cluster - it makes a good training ground for mpi applications before they are ported to the viking cluster for example.

thank you to our PASTRAMI grant for the money, stuart for ordering everything and to CSG - esp. matt johnson - for hardware and software installation expertise.

the performance of the cluster is not yet optimised (initial experiments with jumbo packets etc. resulted in various operational failures), but we will continue to work on this.

Parkway-2.0 Beta Version is Now Available on 22nd December 2004 by Dr Trifunovic:
An MPI-based parallel hypergraph partitioning library, parkway-2.0, written in C++ for a Linux platform, is now available.
Roger Needham Lecture Royal Society 8th December 6:30pm on 29th November 2004 by Prof. Knottenbelt:
Jane Hillston will be giving her Roger Needham Lecture Tuning Systems: From Composition to Performance at the Royal Society on the 8th December at 6:30pm.
All AESOPers are invited! More details from the BCS.
Mathematics of Networks meeting on 30th September 2004 by Dr Harder:
The next meeting in the series "Mathematics of Networks" (3rd meeting, Christmas edition) will be on Monday 20 December 2004.
Attendance is open to "everyone" and free. More details are at the meeting's website maintained by Richard Clegg.
Network meeting at BT Martlesham on 20th July 2004 by Dr Harder:
A quick summary of the Network meeting at BT Martlesham that Ashok and Uli attended.
Richard Clegg maintains a website that contains links to slides of most talks.
The meeting kicked off with a talk about modelling ad-hoc wireless networks by Sverrir Olafsson from BT Exact. He explained the typical tradeoffs wireless networks experience. Unfortunately his research seems to be too secret for the slides to be allowed to be shown on the web. Following, a talk by Richard Clegg summarising the joy he had trying to compute the Hurst parameter of real network data and also some results from simulation he performed with a network simulator from QMUL.
After a well-deserved lunch-break in which BT demonstrated that building works can be louder than those carried out in Huxley at the moment (there was a pneumatic drill just outside the coffee bar!) Damon Wischik talked about Hurstiness. Hurstiness is a well-defined property related to the Hurst parameter. He is co-author of a recent book that he throroughly recommends we should buy: Big Queues.
Focussing more on network topology there was Maziar Nekovee's talk on the spread of biological and computer diseases. Owen Jones from Southampton showed how to calculate the Hurst parameter using crossing trees. This method allows to measure the change of the Hurst parameters over time for instance. On his website you will free matlab code demonstrating his technique.
To wrap up Keith Briggs gave a short notice talk about facts of graphs. In particular how you find out how many graphs of a certain type exist.
The next meeting is likely to be at Imperial in December 2004.
Parallel Hypergraph Partitioning talk on 16th June 2004 by Dr Argent-Katwala:
June 17th at 16:00.
Aleks Trifunovic will be giving his transfer seminar in room 144.
A hypergraph is an extension of a graph data structure in which edges (hyperedges) are allowed to connect arbitrary, non-empty sets of vertices. Like graphs, hypergraphs can be used to represent the structure of many sparse irregular problems such as data dependencies in distributed databases and component connectivity in VLSI circuits. Hypergraphs may also be partitioned such that a cut metric (a function of the interconnect in a partition) is minimised subject to a load balancing criterion. Hypergraph cut metrics provide a more accurate model than graph partitioning in many cases of practical interest such as the row-wise decomposition of a sparse-matrix for parallel matrix-vector multiplication. Algorithms for serial hypergraph partitioning have been studied extensively and tool support exists. However, these are limited by the processing power and memory available on a single processor. Unlike graph partitioning, there have so far been no parallel formulations of the serial hypergraph partitioning algorithms. This talk will outline the state-of-the-art serial hypergraph partitioning algorithms and describe two parallel algorithm formulations based on these. The second algorithm will formally be shown to be scalable. The two algorithms have been experimentally evaluated on large hypergraphs (with O(107) vertices) from domains of performance modelling and VLSI circuit design against state-of-the-art serial partitioning tools. Where problem size became intractable by serial computation, a parallel graph partitioning tool provided approximate partitions for comparison.
Dr. Maria Vigliotti! on 14th May 2004 by Dr Thornley:
This Aesop member just bumped into an overjoyed Maria Vigliotti coming out of her Ph.D viva, which she has passed, and apparently the examiners were really nice.
Well done Maria!
Professor Erol Gelenbe's Inaugural Lecture on 8th April 2004 by Dr Dingle:
Professor Erol Gelenbe, Dennis Gabor Chair in the Department of Electrical and Electronic Engineering at Imperial College London, gave his Inaugural Lecture on April 1st 2004.
The title was 'Stochastic networks: biologically inspired models, and quality of service in the Internet', and one of the topics discussed by Professor Gelenbe was the use of 'cognitive packets' to meet QoS targets for Internet-based services. This is of particular importance for applications such as live video streaming, and employs packets which are capable of altering their route through a network (and the routes of accompanying 'dumb' packets) based on the conditions they encounter and the QoS requirements of the end-users.
The AESOP group was well represented in the audience - indeed, the presence of members of the Markov Chain Appreciation Society of Florida was noted several times by Professor Gelenbe. Amongst those also present from the performance engineering community were Professor Isi Mitrani and Dr. Jane Hillston.
Dennis Gabor was a Hungarian-born electrical engineer who was awarded the Nobel Prize for Physics in 1971 for his work on holography. He began working at Imperial in 1949 and was made Professor of Applied Electron Physics in 1958 (thanks to for this information).
Dynamical systems for modelling internet traffic on 29th January 2004 by Dr Harder:
Departmental Seminar by David Arrowsmith from the Maths department at QMUL on 18 February 2004, usual room and time
Dynamical systems for modelling internet traffic
Internet traffic rates have been shown to exhibit aspects of self-similarity and long-range-dependence. The talk will describe some simple iterative which can be used to model the behaviour of internet traffic. A discussion of congestion phenomena for such models on regular and scale-free networks will be given.
PASTA 2004 on 19th January 2004 by Dr Bradley:
PASTA'04 workshop date set for June 10-11 2004.
Following on from last years successful PASTA workshop in Edinburgh, PASTA 2004 has been set for June 10-11 this year. It is being organised from DOC this year but will again be hosted in the National e-Science Centre in the heart of Edinburgh. Bookings at the Hotel Ceilidh-donia are expected to be brisk!
New AESOP members on 12th December 2003 by Dr Bradley:
Maria Vigliotti and Susanna Au-Yeung join the AESOP group.
We are pleased to announce the appointment of two new members to the AESOP group. Maria Vigliotti joins us from her PhD in ambient calculus as an RA on the PROFORMA project. Susanna Au-Yeung joins as a PhD student under Will Knottenbelt. She already has a storming start with her first publication due to appear in WOSP'04 in January.
AESOP in the Press! on 31st October 2003 by Dr Bradley:
AESOP scoop top industry award for second time running!
The AESOP group has won the prestigious Markov Research Group of the Month award for the second time in a row. The award, endowed by the Markov Chain Appreciation Society of Florida, was announced in their quarterly newsletter yesterday (30th October 2003).
The award cited Nick Dingle's excellent "presentation skills" at the recent MASCOTS 2003 conference, held this October in Orlando, FL, where he presented new work on the Imperial PEPA Compiler and its use with stochastic probes.
"The group were amazed and surprised to win the first award", commented Professor Harrison, "but to win it again is unprecedented. The guys have done staunch work. We've all been inspired by Becky's determination and single-minded attitude. It's really staunch!"
LFCS Seminar on 29th October 2003 by Dr Bradley:
October 28th in Edinburgh
Jeremy Bradley gave the the LFCS seminar yesterday, entitled "Measuring Uncertainty using stochastic probes".
DNAmaca / HYDRA on 19th September 2003 by Dr Bradley:
Release coming soon.
Nick's uploaded the single processor HYDRA version of DNAmaca to the aesop CVS archive. This should now compile with gcc 2.X and 3.X on the new lab machines. We'll be doing some internal testing but are aiming for a joint release with ipc in the next month or so. HYDRA uses uniformisation across (solely) Markovian models to obtain passage time densities and cumulative distributions.