Algorithm for large and Dynamic Networks

Programme INRIA "Equipes Associées" 2013-2015

Team project INRIA : COATI Foreign Partner: Universidad Adolfo Ibáñez, Santiago
Centre de recherche INRIA : INRIA Sophia Antipolis
Thème INRIA : Com B
Country: Chile
French coordinator
Chilean coordinator
Name, surname Nicolas Nisse Karol Suchan
Title Chargé de recherche Inria (Research officer) Assistant professor
team-project COATI, common team
INRIA Sophia Antipolis - I3S (UMR 6070 of the CNRS and the University of Nice-Sophia Antipolis)
Adolfo Ibáñez University
Facultad de Ingeniería y Ciencias
Santiago, Chile.
Address Projet COATI, commun Inria, I3S(CNRS/UNSA)
INRIA Sophia-Antipolis
2004, route des Lucioles -- B.P. 93
06902 Sophia-Antipolis Cedex
Universidad Adolfo Ibáñez
Av. Diagonal Las Torres 2640, Oficina 215-B
Peñalolén 7941169, Santiago
Phone +33 4 97 15 53 28 +56 2 331-1533
email name dot surname arobase inria dot fr name dot surname arobase uai dot cl

Proposal and Common Publications

Publications of the Project
Related Links
Scientific programme and objectives

Context: Current evolution of telecommunication networks leads to new algorithmic challenges. Indeed, both the size of networks as well as the amount of traffic in such networks grow drastically. In this context, numerous problems become challenging to solve even if there exist algorithms that are suitable for smaller networks (in general n-node graphs, algorithms of running time O(n^4) are not scalable to networks of size n=10^4; at n=10^5 even O(n^3) is impractical). Therefore, solutions proposed so far do not scale up and new alternatives must be provided. On the one hand, recent results have proposed to design algorithms that take advantage of special structural properties often found in large-scale networks to achieve better performances. Indeed, it is well known that many telecommunication, social, and biological networks share structural properties such as logarithmic diameter, power-law degree distribution and high clustering coefficient. These properties can be exploited for algorithmic purposes (e.g., for routing). On the other hand, centralized solutions proposed so far do not allow to efficiently face the dynamicity of these networks (variations of both topology and state of connections). Moreover, another important aspect of some of the new networks is that they are not defined in a global way (but, e.g., social networks are defined through local interactions). Hence, it is interesting to propose distributed or even localized solutions, i.e., algorithms based on information that can be retrieved locally and in a distributed way. Many recent works study the tradeoffs between the power of communication and the kind of structural properties that can be computed.

Objectives: The main goal of this Associate Team is to study the structure of networks (modeled by graphs) to design both efficient distributed algorithms and reliable network topologies suitable to applications. We are interested both in large-scale (Facebook, Internet, etc.) and in smaller networks (e.g., WDM) that handle heavy traffic. More precisely, we aim at designing new techniques of distributed and localized computing to test structural properties of networks and to compute structures (e.g., decompositions) to be used in applications. Concerning the applications, we will first focus on routing and subgraph packing problems. There are two main objectives: To verify the practical efficiency of our results, the designed algorithms will be implemented and compared to existing ones. For this purpose, a particular effort will be put to design and implement algorithms to generate graphs that satisfy properties of interest, in order to use them to test the algorithms. The originality of the proposal is to combine powerful tools of graphs theory (e.g., FPT complexity) and of combinatorial optimization (Mixed Integer Programming) with distributed computing. One challenge here is to balance between the degree of locality of desired algorithms and the relevance of properties that may be computed.

Last decade have shown promising advances in exploiting the structure of the underlying graph to solve hard problems efficiently. We propose to study structural properties of graphs with two main guidelines: to focus on specific graph classes and to keep in mind the algorithmic applications of the considered properties. We expect to find structures that could be computed easily (by greedy or localized algorithms) and that would allow to design efficient algorithms for important problems like routing or graph packing. For this purpose, we want to first extend the classical centralized approaches to have a better understanding of graph structures: Most of the graph characteristics used to improve the performances of algorithms are centralized and global structures. We aim at deriving simpler structures and graph characterizations that could be locally computable. In particular, we want to focus on information localized at vertices (or close neighborhoods) that suffices to compute structural properties that support efficient algorithms for applications, therefore: