الفهرس | Only 14 pages are availabe for public view |
Abstract Most of the critical real-world networks are continuously changing and evolving with time. The dynamic nature of these networks have gained a lot of attention motivated by the growing importance and wide spread impact of this type of networks. Because of their intrinsic and special characteristics, these networks are best represented by dynamic graph models. In order to cope with their evolving nature, the representation model must keep the historical information of the network along with its temporal time. Storing such amount of data, poses many problems from the perspective of dynamic graph data management. In this thesis, we provide an in depth overview on dynamic graph related problems. A novel categorization and classification of the state of the art dynamic graph models is also presented in a systematic and comprehensive way. Moreover, we discuss processing on dynamic graphs including both its algorithms and output representation, and give an insight on how to manage and handle the added time parameter to dynamic graph models. With the notable flourish of real-world networks based on graphs, it becomes crucial to find a dynamic graph model that is able to manage efficiently network evolution. So, this study proposes Modified G* (MG*) system that is able to manage the network consuming efficient performance. MG* consumes minimum update time, retrieve time, and minimum memory storage in an efficient manner compared to the existing dynamic graph models. Moreover, it provides results with a better quality. iii Most of the existing models use data structures to store sequence of snapshots, which are either historical or retrieved for processing purposes. Despite consuming minimal update time, these data structures induce storage redundancy, since consecutive snapshots share most of their nodes and edges in common. Compressed variants reduce this redundancy, but at the cost of increasing the update time, required to insert a new snapshot into the structure. Therefore, we propose Fast-CGI data structure to balance handling these downsides. |