Systems and approaches for processing information represented by large dynamic graphs

The paper performes an overview of the key features and advantages for the main existing approaches and systems for processing large graphs on a personal computer. The analysis involves single PC graph processing systems such as GraphChi, TurboGraph, GraphChi-DB and distributed systems like Apache GraphX. Special attention is paid to the problems that require significant changes in the graph structure during the commutation process and the details of implementing such algorithms in graph processing systems. The conducted experiments used a well-known algorithm for network inference based on the ob-served spread of infections among the population, or the spread of news and memes in social networks. The algorithm relies on a stochastic gradient to obtain estimates of the time-varying structure and tem-poral dynamics of the proposed network. The algorithm was implemented for GraphChi and Apache Spark computations models. The authors measured the performance for various real and synthetic da-tasets, described several limitations for these computation models discovered during experiments. Computations were performed on a single computer for GraphChi, and on a cluster of various sizes for the Apache Spark based implementation. According to the results of the review and the conducted experiments, the existing systems are divided into three classes: fast systems with static graph partition and expensive repartition with signifi-cant structure changes; on average, slower systems that are able to handle large amounts of changes efficiently; even more slower but highly scalable systems that compensate low single node performance with the ability to scale computation to a large number of nodes. The conclusion drawn from the conducted review and experiments shows that the problem of dynamic graphs efficient storage and processing is still not solved and requires additional research.