Evolving graphs: dynamical models, inverse problems and propagation

Applications such as neuroscience, telecommunication, online 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 tractable framework for modelling 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 computationally and analytically to investigate the scenario where an evolutionary process, such as an epidemic, takes place on an evolving network. This allows us to study the cumulative effect of two distinct types of dynamics.

Social networks: evolving graphs with memory dependent edges

The plethora, and mass take up, of digital communication tech- nologies has resulted in a wealth of interest in social network data collection and analysis in recent years. Within many such networks the interactions are transient: thus those networks evolve over time. In this paper we introduce a class of models for such networks using evolving graphs with memory dependent edges, which may appear and disappear according to their recent history. We consider time discrete and time continuous variants of the model. We consider the long term asymptotic behaviour as a function of parameters controlling the memory dependence. In particular we show that such networks may continue evolving forever, or else may quench and become static (containing immortal and/or extinct edges). This depends on the ex- istence or otherwise of certain infinite products and series involving age dependent model parameters. To test these ideas we show how model parameters may be calibrated based on limited samples of time dependent data, and we apply these concepts to three real networks: summary data on mobile phone use from a developing region; online social-business network data from China; and disaggregated mobile phone communications data from a reality mining experiment in the US. In each case we show that there is evidence for memory dependent dynamics, such as that embodied within the class of models proposed here.

Performance evaluation of routing protocols for MANETs with known connectivity patterns using evolving graphs

The assessment of routing protocols for mobile wireless networks is a difficult task, because of the networks` dynamic behavior and the absence of benchmarks. However, some of these networks, such as intermittent wireless sensors networks, periodic or cyclic networks, and some delay tolerant networks (DTNs), have more predictable dynamics, as the temporal variations in the network topology can be considered as deterministic, which may make them easier to study. Recently, a graph theoretic model-the evolving graphs-was proposed to help capture the dynamic behavior of such networks, in view of the construction of least cost routing and other algorithms. The algorithms and insights obtained through this model are theoretically very efficient and intriguing. However, there is no study about the use of such theoretical results into practical situations. Therefore, the objective of our work is to analyze the applicability of the evolving graph theory in the construction of efficient routing protocols in realistic scenarios. In this paper, we use the NS2 network simulator to first implement an evolving graph based routing protocol, and then to use it as a benchmark when comparing the four major ad hoc routing protocols (AODV, DSR, OLSR and DSDV). Interestingly, our experiments show that evolving graphs have the potential to be an effective and powerful tool in the development and analysis of algorithms for dynamic networks, with predictable dynamics at least. In order to make this model widely applicable, however, some practical issues still have to be addressed and incorporated into the model, like adaptive algorithms. We also discuss such issues in this paper, as a result of our experience.

Contributions on agreement in dynamic distributed systems

139 p.

A hierarchical evolutionary algorithmic design (HEAD) system for generating and evolving building design models

This thesis develops a detailed conceptual design method and a system software architecture defined with a parametric and generative evolutionary design system to support an integrated interdisciplinary building design approach. The research recognises the need to shift design efforts toward the earliest phases of the design process to support crucial design decisions that have a substantial cost implication on the overall project budget. The overall motivation of the research is to improve the quality of designs produced at the author's employer, the General Directorate of Major Works (GDMW) of the Saudi Arabian Armed Forces. GDMW produces many buildings that have standard requirements, across a wide range of environmental and social circumstances. A rapid means of customising designs for local circumstances would have significant benefits. The research considers the use of evolutionary genetic algorithms in the design process and the ability to generate and assess a wider range of potential design solutions than a human could manage. This wider ranging assessment, during the early stages of the design process, means that the generated solutions will be more appropriate for the defined design problem. The research work proposes a design method and system that promotes a collaborative relationship between human creativity and the computer capability. The tectonic design approach is adopted as a process oriented design that values the process of design as much as the product. The aim is to connect the evolutionary systems to performance assessment applications, which are used as prioritised fitness functions. This will produce design solutions that respond to their environmental and function requirements. This integrated, interdisciplinary approach to design will produce solutions through a design process that considers and balances the requirements of all aspects of the design. Since this thesis covers a wide area of research material, 'methodological pluralism' approach was used, incorporating both prescriptive and descriptive research methods. Multiple models of research were combined and the overall research was undertaken following three main stages, conceptualisation, developmental and evaluation. The first two stages lay the foundations for the specification of the proposed system where key aspects of the system that have not previously been proven in the literature, were implemented to test the feasibility of the system. As a result of combining the existing knowledge in the area with the newlyverified key aspects of the proposed system, this research can form the base for a future software development project. The evaluation stage, which includes building the prototype system to test and evaluate the system performance based on the criteria defined in the earlier stage, is not within the scope this thesis. The research results in a conceptual design method and a proposed system software architecture. The proposed system is called the 'Hierarchical Evolutionary Algorithmic Design (HEAD) System'. The HEAD system has shown to be feasible through the initial illustrative paper-based simulation. The HEAD system consists of the two main components - 'Design Schema' and the 'Synthesis Algorithms'. The HEAD system reflects the major research contribution in the way it is conceptualised, while secondary contributions are achieved within the system components. The design schema provides constraints on the generation of designs, thus enabling the designer to create a wide range of potential designs that can then be analysed for desirable characteristics. The design schema supports the digital representation of the human creativity of designers into a dynamic design framework that can be encoded and then executed through the use of evolutionary genetic algorithms. The design schema incorporates 2D and 3D geometry and graph theory for space layout planning and building formation using the Lowest Common Design Denominator (LCDD) of a parameterised 2D module and a 3D structural module. This provides a bridge between the standard adjacency requirements and the evolutionary system. The use of graphs as an input to the evolutionary algorithm supports the introduction of constraints in a way that is not supported by standard evolutionary techniques. The process of design synthesis is guided as a higher level description of the building that supports geometrical constraints. The Synthesis Algorithms component analyses designs at four levels, 'Room', 'Layout', 'Building' and 'Optimisation'. At each level multiple fitness functions are embedded into the genetic algorithm to target the specific requirements of the relevant decomposed part of the design problem. Decomposing the design problem to allow for the design requirements of each level to be dealt with separately and then reassembling them in a bottom up approach reduces the generation of non-viable solutions through constraining the options available at the next higher level. The iterative approach, in exploring the range of design solutions through modification of the design schema as the understanding of the design problem improves, assists in identifying conflicts in the design requirements. Additionally, the hierarchical set-up allows the embedding of multiple fitness functions into the genetic algorithm, each relevant to a specific level. This supports an integrated multi-level, multi-disciplinary approach. The HEAD system promotes a collaborative relationship between human creativity and the computer capability. The design schema component, as the input to the procedural algorithms, enables the encoding of certain aspects of the designer's subjective creativity. By focusing on finding solutions for the relevant sub-problems at the appropriate levels of detail, the hierarchical nature of the system assist in the design decision-making process.

The evolving role of information specialists:change agents in process redesign

The research investigates the past, present and potential future role of Information Specialists (ISps) in process oriented companies. It tests the proposition that ISps in companies that have undertaken formal process reengineering exercises are likely to become more proactive and more business oriented (as opposed to technically oriented) than they had previously been when their organisations were organised along traditional, functional lines. A review of existing literature in the area of Business Process Reengineering and Information Management reveals a lack of consensus amongst researchers concerning the appropriate role for ISps during and after BPR. Opinion is divided as to whether IS professionals should reactively support BPR or whether IT/IS developments should be driving these initiatives. A questionnaire based ‘Descriptive Survey’ with 60 respondents is used as a first stage of primary data gathering. This is followed by follow-up interviews with 20 of the participating organisations to gather further information on their experiences. The final stage of data collection consists of further in-depth interview with four case study companies to provide an even richer picture of their experiences. The results of the questionnaire are analysed and displayed in the form of simple means, frequencies and bar graphs. The ‘NU-DIST’ computer based discourse analysis package was tried in relation to summarising the interview findings, but this proved cumbersome and a visual collation method is preferred. Overall, the researcher contends that the supposition outlined above is proven, and she concludes the research by suggesting the implications of these findings. In particular she offers a ‘Framework for Understanding and Action’ which is deemed to be relevant to both practitioners and future researchers.

A multi-hypothesis topological SLAM approach for loop closing on edge-ordered graphs

We present a method for topological SLAM that specifically targets loop closing for edge-ordered graphs. Instead of using a heuristic approach to accept or reject loop closing, we propose a probabilistically grounded multi-hypothesis technique that relies on the incremental construction of a map/state hypothesis tree. Loop closing is introduced automatically within the tree expansion, and likely hypotheses are chosen based on their posterior probability after a sequence of sensor measurements. Careful pruning of the hypothesis tree keeps the growing number of hypotheses under control and a recursive formulation reduces storage and computational costs. Experiments are used to validate the approach.

Evolving interactions : agile design for networked media performance

Network Jamming systems provide real-time collaborative performance experiences for novice or inexperienced users. In this paper we will outline the interaction design considerations that have emerged during through evolutionary development cycles of the jam2jam Network Jamming software that employs generative techniques that require particular attention to the human computer relationship. In particular we describe the co-evolution of features and uses, explore the role of agile development methods in supporting this evolution, and show how the provision of a clear core capability can be matched with options for enhanced features support multi-levelled user experience and skill develop.

eBusiness use in the United Arab Emirates : lessons for evolving markets

Since the early 1990’s the United Arab Emirates has been actively seeking to diversify into non-oil sectors. The nation has set out to market itself as a hub for foreign and domestic companies; realizing to achieve these goals that it must provide appropriate e-business frameworks and infrastructures. While the nation itself is paving the way for other nations in the Middle East to undertake electronic business initiatives, the use of everyday e-business in the UAE appears to be somewhat stifled. An investigation into reasons for the apparent low levels of adoption of e-business by UAE inhabitants has been conducted using an autoethnographic research methodology coupled with qualitative interviews of selected stakeholders. Findings from this research may contribute to a better understanding of how e-business initiatives in specific regions need to take into account local cultural and other issues which may be irrelevant elsewhere.

Evolving a locus based gait for a humanoid robot

This paper describes a process for evolving a stable humanoid walking gait that is based around parameterised loci of motion. The parameters of the loci are chosen by an evolutionary process based on the criteria that the robot's ZMP (zero moment point) follows a desirable path. The paper illustrates the evolution of a straight line walking gait. The gait has been tested on a 1.2 m tall humanoid robot (GuRoo). The results, apart form illustrating a successful walk, illustrate the effectiveness of the ZMP path criterion in not only ensuring a stable walk, but also in achieving efficient use of the actuators.

Evolving citizenship : "the right to protest and the right to dance"

Citizenship is a term of association among strangers. Access to it involves contested identities and symbolic meanings, differing power relations and strategies of inclusion, exclusion and action, and unequal room for maneuver or productivity in the uses of citizenship for any given group or individual. In the context of "rethinking communication," strenuous action is neede to associate such different life chances in a common enterprise at a national level or, more modestly, simply to claim equivalence for all such groups under the rule of one law.