Please use this identifier to cite or link to this item:
|Title:||Modelling and Analysing Adaptive Networks: From Graph Transformation System to Ordinary Differential Equation|
|Authors:||Hussein, Mudhafar Saber|
|Abstract:||Online social networks pose particular challenges to designing effective algorithms and protocols. Apart from their distributed nature, their behaviour depends on user behaviour and is difficult to test at a realistic scale. Stochastic graph transformation systems can model the operation of such networks but due to the inherent complexity they are hard to analyse. Techniques such as model checking and simulation, which can be used to verify a range of quantitative properties, do not scale well to systems with large graphs and state spaces. Aiming for an efficient alternative, we propose to derive a system of differential equations approximating the average evolution of the network. Variables in these equations represent numbers of occurrences of patterns selected to observe structural features. To keep the number of patterns small, rather than aiming for a fully accurate model we approximate complex patterns by the composition of simpler ones. We describe the approximation and its implementation based on critical pair analysis, illustrate and validate the process by examples of a social network protocol for P2P content policing and a voter model. We will also point out limitations in our approach to approximation and the use of differential equations more generally and discuss how they can be overcome.|
|Rights:||Copyright © the author. All rights reserved.|
|Appears in Collections:||Leicester Theses|
Theses, Dept. of Informatics
Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.