Robustness study of emerged communities from exchanges in peer-to-peer networks

The study of emerged community structure is an important challenge in networks analysis. In fact, several methods have been proposed in the literature to statistically determine the significance of discovered structures. Nevertheless, most of existing analysis models consider only the structural aspect of emerged communities. We are interested in studying the robustness of emerged communities in peer-to-peer (P2P) networks. More precisely, we consider the emerged communities in the induced graph by all the exchanges in these networks. Hence, rather than examining the robustness only on the structural properties of the graph, we will focus on the parameters that allow the emergence of community structures. In fact, perturbing these parameters might destroy most of the obtained properties at the emerged level. To the best of our knowledge, robustness of networks has never been considered from this angle before. In this paper, we study the impact of perturbing the content and the profile of nodes on the emerged communities in P2P networks. We show how these alterations affect both structure and information supported by the emerged structures.     

A cluster based mobility prediction scheme for ad hoc networks

The ad hoc networks are completely autonomous wireless networks where all the users are mobile. These networks do not work on any infrastructure and the mobiles communicate either directly or via other nodes of the network by establishing routes. These routes are prone to frequent ruptures because of nodes mobility. If the future movement of the mobile can be predicted in a precise way, the resources reservation can be made before be asked, which enables the network to provide a better QoS. In this aim, we propose a virtual dynamic topology, which on one hand, will organize the network as well as possible and decreases the impact of mobility, and on the other hand, is oriented user mobility prediction. Our prediction scheme uses the evidence theory of Dempster–Shafer in order to predict the future position of the mobile by basing itself on relevant criteria. These ones are related to mobility and network operation optimisation. The proposed scheme is flexible and can be extended to a general framework. To show the relevance of our scheme, we combine it with a routing protocol. Then, we implemented the prediction-oriented topology and the prediction scheme which performs on it. We implemented also a mobility prediction based routing protocol. Simulations are made according to a set of elaborate scenarios.     

Efficient parallel edge-centric approach for relaxed graph pattern matching

Prior algorithms on graph simulation for distributed graphs are not scalable enough as they exhibit heavy message passing. Moreover, they are dependent on the graph partitioning quality that can be a bottleneck due to the natural skew present in real-world data. As a result, their degree of parallelism becomes limited. In this paper, we propose an efficient parallel edge-centric approach for distributed graph pattern matching. We design a novel distributed data structure called ST that allows a fine-grain parallelism, and hence guarantees linear scalability. Based on ST, we develop a parallel graph simulation algorithm called PGSim. Furthermore, we propose PDSim, an edge-centric algorithm that efficiently evaluates dual simulation in parallel. PDSim combines ST and PGSim in a Split-and-Combine approach to accelerate the computation stages. We prove the effectiveness and efficiency of these propositions through theoretical guarantees and extensive experiments on massive graphs. The achieved results confirm that our approach outperforms existing algorithms by more than an order of magnitude.

     

A survey on self-stabilizing algorithms for independence,domination, coloring,and matching in graphs

Dijkstra defined a distributed system to be self-stabilizing if, regardless of the initial state, the system is guaranteed to reach a legitimate (correct) state in a finite time. Even though the concept of self-stabilization received little attention when it was introduced, it has become one of the most popular fault tolerance approaches. On the other hand, graph algorithms form the basis of many network protocols. They are used in routing, clustering, multicasting and many other tasks. The objective of this paper is to survey the self-stabilizing algorithms for dominating and independent set problems, colorings, and matchings. These graph theoretic problems are well studied in the context of self-stabilization and a large number of algorithms have been proposed for them.     

A distance measure for large graphs based on prime graphs

Graphs are universal modeling tools. They are used to represent objects and their relationships in almost all domains: they are used to represent DNA, images, videos, social networks, XML documents, etc. When objects are represented by graphs, the problem of their comparison is a problem of comparing graphs. Comparing objects is a key task in our daily life. It is the core of a search engine, the backbone of a mining tool, etc. Nowadays, comparing objects faces the challenge of the large amount of data that this task must deal with. Moreover, when graphs are used to model these objects, it is known that graph comparison is very complex and computationally hard especially for large graphs. So, research on simplifying graph comparison gainedan interest and several solutions are proposed. In this paper, we explore and evaluate a new solution for the comparison of large graphs. Our approach relies on a compact encoding of graphs called prime graphs. Prime graphs are smaller and simpler than the original ones but they retain the structure and properties of the encoded graphs. We propose to approximate the similarity between two graphs by comparing the corresponding prime graphs. Simulations results show that this approach is effective for large graphs.     

Listing all maximal cliques in large graphs on vertex-centric model

The Journal of Supercomputing - Maximal Clique Enumeration (MCE), which consists to enumerate all maximal complete subgraphs in a given graph, is a fundamental problem in graph theory, and it is...