In the last few years, we have seen that many applications or computer problems are mobilized as a graph since this data structure gives a particular handling for some use cases such as social networks, bioinformatics, road networks and communication networks. Despite its importance, the graph processing remains a challenge when dealing with large graphs. In this context, several solutions and works have been proposed to support large graph processing and storage. Nevertheless, new needs are emerging to support the dynamism of the graph (Dynamic Graph) and properties variation of the graph during the time (temporal graph). In this paper, we rst present the concepts of dynamic and temporal graphs. Secondly, we show some frameworks that treat static, dynamic and temporal graphs. Finally, we propose a new framework based on the limits of the frameworks study.
Graph data structure represents an appropriate model for several applications
in various domains such that social network (e.g., FaceBook, Twitter),
bioinformatics [
The graph processing topic has attracted many researchers and industrial
institutes [
Based on the theoretical study of the above-mentioned frameworks, we propose a novel distributed framework for temporal and dynamic graph representation and analysis. Figure 1 presents the global architecture of our proposed framework. We mention that the proposed system aims to overcome the limits of the abovementioned frameworks and to meet all the requirements for processing dynamic and temporal big graphs. As shown in Figure 1, the proposed system is divided into several layers.
The storage layer allows saving and persisting the considered graph. This layer has been implemented in some frameworks. However, others solutions do not implement this component or do not support very big graphs. In our framework, we use distributed le systems in order to store large graphs and to guarantee a fault tolerant storage solution.
The execution layer represents the core of our proposed framework. It is implemented to support e ciently all the requirements for large graph processing. Among these requirements, we cite basically the scalability of processing and the fault tolerance. In this context, we note that several solutions such as GPS and Graphast do not take into consideration some aspects such as the scalability and the distributed computing, while others like BLADYG, Pregel and GraphX ensure them. However, the latter can not guarantee fault tolerance. To handle this limit, we have implemented a checkpoint service which aims to ensure and capture the di erent processing states in real-time.
We notice that the changes that occur to the graph data are mainly addition and/or deletion of nodes/edges. The Stream Graph layer ensure the streaming of graph changes/updates. To do that, we use Kafka Broker [11] as a streaming tool that ensures the continuity and the scalability of data ows.
Graph Model describes the data structure used by the di erent layers and component of the proposed framework. The Graph Model component describes the edges and the vertices of the considered graph. It also describes the graph updates. We also mention that the Graph Model layer allows to represent time dependent costs on the edges. In our model, nodes and edges can have timedependent costs as well as other properties such as the distance between nodes, geographical coordinates, and description. Temporal functions represent timedependent costs, mapping time periods to values. The model is exible enough to allow the addition or removal of properties. It also allows dynamic updates on property values. All the other modules of the framework interact with the Graph Model. To facilitate the development of user applications and to ensure a high level of abstraction that allow the exploitation of this framework in several applications, we propose an API level. It implements a programming interface that helps the user to build several applications. We also mention that the level API allow the implementation of e cient algorithms / queries on the graph model.
In this component, we propose a RestFul module which seeks to ensure the compatibility with other systems or applications and to manipulate data e ciently. This layer is responsible for importing/exporting data from given data sources and formats, like GML, GraphML, and GraphSON, to build the Graph Model. New data import/export services are easily added to the framework by the implementation of a standard interface. 4
In this paper we present the architecture of a novel distributed framework for dynamic and temporal graph processing. The proposed framework provides various tools for graph processing like graph storage, graph streaming and programming interfaces that allow the users to build concurrent and distributed time-dependent graph applications. In future works, we aim to evaluate this framework and compare it with existing systems in real world applications. 8. Gonzalez, J.E., Low, Y., Gu, H., Bickson, D., Guestrin, C.: Powergraph: Distributed graph-parallel computation on natural graphs. In: OSDI, vol. 12, p. 2 (2012) 9. Han, B., Liu, L., Omiecinski, E.: Neat: Road network aware trajectory clustering. In: Distributed Computing Systems (ICDCS), 2012 IEEE 32nd International Conference on, pp. 142{151. IEEE (2012) 10. Intanagonwiwat, C., Govindan, R., Estrin, D.: Directed di usion: A scalable and robust communication paradigm for sensor networks. In: Proceedings of the 6th annual international conference on Mobile computing and networking, pp. 56{67.
ACM (2000) 11. Kreps, J., Narkhede, N., Rao, J., et al.: Kafka: A distributed messaging system for log processing. In: Proceedings of the NetDB, pp. 1{7 (2011) 12. Lee, P., Lakshmanan, L.V., Milios, E.E.: Incremental cluster evolution tracking from highly dynamic network data. In: Data Engineering (ICDE), 2014 IEEE 30th International Conference on, pp. 3{14. IEEE (2014) 13. Li, X., Han, J., Lee, J.G., Gonzalez, H.: Tra c density-based discovery of hot routes in road networks. Advances in Spatial and Temporal Databases pp. 441{459 (2007) 14. Magalha~es, R.P., Coutinho, G., Mac^edo, J., Ferreira, C., Cruz, L., Nascimento, M.: Graphast: an extensible framework for building applications on time-dependent networks. In: Proceedings of the 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems, p. 93. ACM (2015) 15. Malewicz, G., Austern, M.H., Bik, A.J., Dehnert, J.C., Horn, I., Leiser, N., Czajkowski, G.: Pregel: a system for large-scale graph processing. In: Proceedings of the 2010 ACM SIGMOD International Conference on Management of data, pp. 135{146. ACM (2010) 16. Moon, S., Lee, J.G., Kang, M., Choy, M., Lee, J.w.: Parallel community detection on large graphs with mapreduce and graphchi. Data & Knowledge Engineering 104, 17{31 (2016) 17. Roy, A., Mihailovic, I., Zwaenepoel, W.: X-stream: Edge-centric graph processing using streaming partitions. In: Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles, pp. 472{488. ACM (2013) 18. Scholliers, C., Tanter, E., De Meuter, W.: Parallel actor monitors: Disentangling task-level parallelism from data partitioning in the actor model. Science of Computer Programming 80, 52{64 (2014) 19. Sengupta, D., Sundaram, N., Zhu, X., Willke, T.L., Young, J., Wolf, M., Schwan, K.: Graphin: An online high performance incremental graph processing framework. In: Euro-Par, pp. 319{333 (2016)