Graph-based Algorithms for Smart Mobility Planning and Large-scale Network Discovery

Doctoral thesis (2019)

Graph theory has become a hot topic in the past two decades as evidenced by the increasing number of citations in research. Its applications are found in many fields, e.g. database, clustering, routing ... [more ▼]

Graph theory has become a hot topic in the past two decades as evidenced by the increasing number of citations in research. Its applications are found in many fields, e.g. database, clustering, routing, etc. In this thesis, two novel graph-based algorithms are presented. The first algorithm finds itself in the thriving carsharing service, while the second algorithm is about large graph discovery to unearth the unknown graph before any analyses can be performed. In the first scenario, the automatisation of the fleet planning process in carsharing is proposed. The proposed work enhances the accuracy of the planning to the next level by taking an advantage of the open data movement such as street networks, building footprints, and demographic data. By using the street network (based on graph), it solves the questionable aspect in many previous works, feasibility as they tended to use rasterisation to simplify the map, but that comes with the price of accuracy and feasibility. A benchmark suite for further research in this problem is also provided. Along with it, two optimisation models with different sets of objectives and contexts are proposed. Through a series of experiment, a novel hybrid metaheuristic algorithm is proposed. The algorithm is called NGAP, which is based on Reference Point based Non-dominated Sorting genetic Algorithm (NSGA-III) and Pareto Local Search (PLS) and a novel problem specific local search operator designed for the fleet placement problem in carsharing called Extensible Neighbourhood Search (ENS). The designed local search operator exploits the graph structure of the street network and utilises the local knowledge to improve the exploration capability. The results show that the proposed hybrid algorithm outperforms the original NSGA-III in convergence under the same execution time. The work in smart mobility is done on city scale graphs which are considered to be medium size. However, the scale of the graphs in other fields in the real-world can be much larger than that which is why the large graph discovery algorithm is proposed as the second algorithm. To elaborate on the definition of large, some examples are required. The internet graph has over 30 billion nodes. Another one is a human brain network contains around 1011 nodes. Apart of the size, there is another aspect in real-world graph and that is the unknown. With the dynamic nature of the real-world graphs, it is almost impossible to have a complete knowledge of the graph to perform an analysis that is why graph traversal is crucial as the preparation process. I propose a novel memoryless chaos-based graph traversal algorithm called Chaotic Traversal (CHAT). CHAT is the first graph traversal algorithm that utilises the chaotic attractor directly. An experiment with two well-known chaotic attractors, Lozi map and Rössler system is conducted. The proposed algorithm is compared against the memoryless state-of-the-art algorithm, Random Walk. The results demonstrate the superior performance in coverage rate over Random Walk on five tested topologies; ring, small world, random, grid and power-law. In summary, the contribution of this research is twofold. Firstly, it contributes to the research society by introducing new study problems and novel approaches to propel the advance of the current state-of-the-art. And Secondly, it demonstrates a strong case for the conversion of research to the industrial sector to solve a real-world problem. [less ▲]

Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics

in International Journal of Bifurcation and Chaos (2017), 27(14), 1750215

Graph Traversal algorithms can find their applications in various fields such as routing problems, natural language processing or even database querying. The exploration can be considered as a first ... [more ▼]

Graph Traversal algorithms can find their applications in various fields such as routing problems, natural language processing or even database querying. The exploration can be considered as a first stepping stone into knowledge extraction from the graph which is now a popular topic. Classical solutions such as Breadth First Search (BFS) and Depth First Search (DFS) require huge amounts of memory for exploring very large graphs. In this research, we present a novel memoryless graph traversal algorithm, Chaotic Traversal (CHAT) which integrates chaotic dynamics to traverse large unknown graphs via the Lozi map and the Rössler system. To compare various dynamics effects on our algorithm, we present an original way to perform the exploration of a parameter space using a bifurcation diagram with respect to the topological structure of attractors. The resulting algorithm is an efficient and nonresource demanding algorithm, and is therefore very suitable for partial traversal of very large and/or unknown environment graphs. CHAT performance using Lozi map is proven superior than the, commonly known, Random Walk, in terms of number of nodes visited (coverage percentage) and computation time where the environment is unknown and memory usage is restricted. [less ▲]

Metaheuristic Based Clustering Algorithms for Biological Hypergraphs

in Proceedings of META’2016, 6th International Conference on Metaheuristics and Nature Inspired computing (2016, October 27)

Hypergraphs are widely used for modeling and representing relationships between entities, one such field where their application is prolific is in bioinformatics. In the present era of big data, sizes and ... [more ▼]

Hypergraphs are widely used for modeling and representing relationships between entities, one such field where their application is prolific is in bioinformatics. In the present era of big data, sizes and complexity of these hypergraphs grow exponentially, it is impossible to process them manually or even visualize their interconnectivity superficially. A common approach to tackle their complexity is to cluster similar data nodes together in order to create a more comprehensible representation. This enables similarity discovery and hence, extract hidden knowledge within the hypergraphs. Several state-of-the-art algorithms have been proposed for partitioning and clustering of hypergraphs. Nevertheless, several issues remain unanswered, improvement to existing algorithms are possible, especially in scalability and clustering quality. This article presents a concise survey on hypergraph-clustering algorithms with the emphasis on knowledge-representation in systems biomedicine. It also suggests a novel approach to clustering quality by means of cluster-quality metrics which combines expert knowledge and measurable objective distances in existing biological ontology. [less ▲]