Nowadays, networks (weighted graphs) are widely used for data analysis. The enthusiasm for this method of analysis is due to the fact that graph visualization facilitates the analysis of existing relationships between entities (persons, web pages, ...). These relationships can be automatically computed from the data, for instance, by computing a correlation matrix between entities and then thresholding it. These relationships can also evolve over time giving rise to dynamic-graphs or timestamped-graphs. By abstracting from the type of data and focusing only on relationships, graph visualization offers a remarkable tool for analysis of heterogeneous and dynamic Big Data.
In graph-based analysis methods, a first step is to lay out (or draw) the graph. This step algorithmically assigns a position to entities and relationships. The algorithmic complexity of the methods used is in the general case of the order of O(n^3). They cannot therefore be used on real data sets. For instance, in territorial surveillance tools to guarantee internal security the graphs have often hundred thousand of entities and millions of relationships. Recent work has shown that by combining "Barnes and Hut" or "fast multipole" (FMM) resolution methods and a multi-scale decomposition of graphs, it is possible to reduce this complexity to O(nlog(n)) while maintaining the properties of the original algorithm. Algorithms with O(nlog(n)) complexity can be efficiently launched on BigData infrastructures. Therefore, it is theoretically possible to create methods that efficiently lay out graphs on these architectures.
At the moment, only heuristics exist to lay out graphs on big data infrastructure and there is no method guaranteeing the same results as the original algorithms. Using of the resolution methods developed for HPC infrastructures on Big Data infrastructures remains an unresolved problem. The success the adaptation of these HPC resolution methods will allow to device graph layout algorithms which can be integrated into Big Data analysis ecosystems. This type of algorithm and study find their place in areas such as the observation and monitoring of social networks.