Graph pattern matching has been widely used in large spectrum of real applications. In this context, different models along with their appropriate algorithms have been proposed. However, a major drawback on existing models is their limitation to find meaningful matches resulting in a number of failing queries. In this paper we introduce a new model for graph pattern matching allowing the relaxation of queries in order to avoid the empty-answer problem. Then we develop an efficient algorithm based on optimization strategies for computing the top k matches according to our model. Our experimental evaluation on four real datasets demonstrates both the effectiveness and the efficiency of our approach.

The proliferation in size of actual graph datasets impels the use of distributed graph processing frameworks which in turn, should consider a good partitioning of the graph dataset in order to see their performances enhanced. In this paper, we focus on a well known heuristic for graph partitioning named METIS, an offline method giving high quality partitions but unsuitable for processing large graphs due to the offline setting. A recently proposed alternative is the streaming partitioning heuristics aiming to alleviate the computational resources constraints when dealing with large graphs. In considering this matter, we propose a new partitioning method that benefits from the accuracy of METIS and the lightness of the streaming setting. This work introduces the Streaming METIS Partitioning method (SMP) which is an online counterpart of METIS, a fast and well known multilevel heuristic for graph partitioning. We show in a complexity analysis that SMP has a lower time complexity compared to METIS, which is confirmed by conducted experiments. Moreover, we show that SMP yields competitive results to its offline counterpart METIS, especially when it is run on a Depth First Search streaming order. Also, when compared to other online competitors, SMP is the best performing heuristic giving partitions with minimal edge cut.

We present GraphExploiter, a tool to import, visualize and manage data by representing them in a graph structure. The aim of this platform is (i) to facilitate the creation of graphs from real data sets, (ii) to propose an efficient tool of scalable visualization and (iii) to allow a user to import easily its own graph algorithms to the platform.

Graph partitioning is an important challenging problem when performing computation tasks over large distributed graphs; the reason is that a good partitioning leads to faster computations. In this work, we first introduce a new heuristic for streaming partitioning and show that it outperforms the state-of-the-art heuristics for streaming partitioning, leading to exact balance and lower cut. Secondly, we introduce the partial restreaming partitioning which is a hybrid streaming model allowing only several portions of the graph to be restreamed while the rest is to be partitioned on a single pass of the data stream. We show that our method yields partitions of similar quality than those provided by methods restreaming the whole graph (e.g ReLDG, ReFENNEL), while incurring lower cost in running time and memory since only several portions of the graph will be restreamed.

If we draw the virtual topology representing the communication in networks, we observe that the structure is similar to those of the social networks. Social networks are these networks with the characteristic relating densely some entities than others. These dense zones are called communities. Generally, the members of a same community share the same interest. In this work, we look for which virtual topology (called communication graph) emerged in communication network gives communities closer to the real one. Three different communication graphs are generated and compared with the graph representing the real communities, the reference graph. Microscopic and macroscopic comparisons are done.