Browse ORBi

- What it is and what it isn't
- Green Road / Gold Road?
- Ready to Publish. Now What?
- How can I support the OA movement?
- Where can I learn more?

ORBi

Graph-based Algorithms for Smart Mobility Planning and Large-scale Network Discovery Changaival, Boonyarit 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 ▲] Detailed reference viewed: 9 (3 UL)Chaotic Traversal (CHAT): Very Large Graphs Traversal Using Chaotic Dynamics Changaival, Boonyarit ; Rosalie, Martin ; Danoy, Grégoire et al 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 ▲] Detailed reference viewed: 116 (19 UL)Exploring chaotic dynamics by partition of bifurcation diagram Changaival, Boonyarit ; Rosalie, Martin in Proceeding of Workshop on Advance in Nonlinear Complex Systems and Applications (WANCSA) (2017) Chaotic dynamical systems have been recently successfully used to replace uniform probability functions in several algorithms in optimization and machine learning. In this work, we propose a study on the ... [more ▼] Chaotic dynamical systems have been recently successfully used to replace uniform probability functions in several algorithms in optimization and machine learning. In this work, we propose a study on the use of bifurcation diagrams and first return map in the Rössler system for producing chaotic dynamics. Then, we plan to use these chaotic dynamic for optimization problem. With a bifurcation diagram we can also distinguish the periodic solutions apart from the chaotic solutions. By studying the chaotic solutions, we can then achieve a first return map which is a signature of the dynamical system and thoroughly study the complexity of the latter with a certain set of parameters. As a result, the partition in the bifurcation diagram is provided. From the first return maps, we are able to confirm the complexity of the dynamics in those partitions along with the transitions between them. [less ▲] Detailed reference viewed: 61 (5 UL)Metaheuristic Based Clustering Algorithms for Biological Hypergraphs Changaival, Boonyarit ; Danoy, Grégoire ; Ostaszewski, Marek et al 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 ▲] Detailed reference viewed: 120 (12 UL) |
||