Section: New Results

Networked systems and Graph analysis

Observability in consensus networks

Participants : A. Kibangou [Contact person] , C. Commault [Gipsa-Lab] .

Studying the observability problem of a system consists in answering the question: is it possible, for a given node, to reconstruct the entire network state just from its own measurements and those of its neighbors ?

Studying observability for arbitrary graphs is particularly a tough task. Therefore, studies are generally restricted to some families of graphs. For instance, recently, observability has been studied in [70] for paths and circular graphs where the study was carried out based on rules on number theory. Herein, we have considered families of graphs admitting an association scheme [62] such that strongly regular graphs and distance regular graphs. The regularity properties of these kinds of graphs can particularly be useful for robustifying the network as for cryptographic systems [79] . Based on the so-called Bose-Mesner algebra [60] , we have stated observability conditions on consensus networks modeled with graphs modeled with strongly regular graphs and distance regular graphs. For this purpose, we have introduced the notion of local observability bipartite graph that allows characterizing the observability in consensus networks. We have shown that the observability condition is given by the nullity of the so-called local bipartite observability graph. When the nullity of the graph cannot be derived directly from the structure of the local bipartite observability graph, the rank of the associated bi-adjacency matrix allows evaluating the observability; the bi-adjacency matrix of the so-called local bipartite observability graph must be full column rank for guaranteeing observability. From this general necessary and sufficient condition, we have deduced sufficient conditions for strongly regular graphs and distance regular graphs. In particular, we have shown that observability is ensured in such graphs only if $DK\ge N-1$ where $D$ is the number of classes of the association scheme, $N$ the number of nodes, and $K$ the valency of the graph, i.e. the cardinality of the neighborhood.

Distributed graph discovery

Participants : A. Kibangou [Contact person] , F. Garin [Contact person] , C. Commault [Gipsa-Lab] , D. Tran, D. Varagnolo [KTH] , K.H. Johansson [KTH] .

We have studied the problem of estimating the eigenvalues of the Laplacian matrix associated with a graph modeling the interconnections between the nodes of a given network. Two approaches have been developed. For the first one [38] , based on properties of the observability matrix, we have shown that Laplacian eigenvalues can be recovered by solving a local eigenvalue decomposition on an appropriately constructed matrix of observed data. Unlike FFT based methods recently proposed in the literature (see [65] , [73] ), in our proposed method we are also able to estimate the multiplicities of the eigenvalues. However, this method is only applicable to networks having nodes with sufficient storage and computation capabilities. That's why we have proposed a second method requiring much less computation and storage capabilities in [76] . Based on a recent result showing that the average consensus matrix can be factored in $D$ Laplacian based consensus matrices, where $D$ stands for the number of nonzero distinct Laplacian eigenvalues [40] , we have shown how carrying out such a factorization in a fully distributed way. The proposed solution results on a distributed solution of a constrained consensus problem.

The availability of information on the communication topology of a wireless sensor network is essential for the design of the estimation algorithms. In the context of distributed self-organized sensor networks, there is no central unit with the knowledge of the network, and the agents must run some distributed network-discovery algorithms. This is particularly difficult in the case when the agents do not have or do not want to disclose their identifiers (IDs), either for technological reasons (in time-varying self-organized networks, assigning unique identifiers to agents is a challenge) or for privacy concerns. In a recent work [78] the authors proposed an algorithm which allows each agent to find an estimate of the number of agents in the network, in an anonymous way. Such an algorithm is based on the generation of pseudo-random numbers, on some consensus algorithms (for distributed computation either of average or of maximum), and on statistical inference. In our work [37] , we show how the same algorithm, with some minor modifications, can provide more information: approximations of each node's eccentricity, of the graph diameter and of the graph radius. We study the quality of such approximations, providing tight bounds on the error.