Alain Y Kibangou

Christian Commault

Observability in Connected Strongly Regular Graphs and Distance Regular Graphs

Keywords: Observability, Association scheme, Distance regular graphs, Strongly regular graphs, Consensus networks, Nullity of graphs, Bipartite graph

This paper concerns the study of observability in consensus networks modeled with strongly regular graphs or distance regular graphs. We first give a Kalman-like simple algebraic criterion for observability in distance regular graphs. This criterion consists in evaluating the rank of a matrix built with the components of the Bose-Mesner algebra associated with the considered graph. Then, we define some bipartite graphs that capture the observability properties of the graph to be studied. In particular, we show that necessary and sufficient observability conditions are given by the nullity of the so-called local bipartite observability graph (resp. local unfolded bipartite observability graph) for strongly regular graphs (resp. distance regular graphs). When the nullity cannot be derived directly from the structure of these bipartite graphs, the rank of the associated bi-adjacency matrix allows evaluating observability. Eventually, as a by-product of the main results we show that non-observability can be stated just by comparing the valency of the graph to be studied with a bound computed from the number of vertices of the graph and its diameter. Similarly nonobservability can also be stated by evaluating the size of the maximum matching in the above mentioned bipartite graphs.

I. INTRODUCTION

A system is observable if its internal state can be fully reconstructed from its outputs. In complex systems, interconnections between several entities occur so that an emergent behaviour can be observed. For instance, in large scale factory or multi-brand retailing, the overall system is constituted with small entities that are networked. The networking of these small entities allows the monitoring of the production of the overall system through an average consensus method for instance (see [START_REF] Garin | A survey on distributed estimation and control applications using linear consensus algorithms[END_REF] and references therein). From any entity (node of the network) it is then possible to assess the production of the overall system. If in the meanwhile, we are also interested with knowing the specific production of each entity then the networked system should be observable. However, in a context of economical war, one can promote to have a nonobservable system in order to limit spying of each entity. More generally, observability plays an important role in distributed estimation and intrusion detection problems [START_REF] Sundaram | Distributed function calculation via linear iterative strategies in the presence of malicious agents[END_REF], [START_REF] Pasqualetti | Consensus computation in unreliable networks: A system theoretic approach[END_REF]. Indeed, in estimating the network state, one can decide if the functioning of the network is normal or not and decide an action to preserve the system functionalities. In consensus networks, *Alain Y. Kibangou is with Univ. Grenoble Alpes, CNRS, Inria, Gipsa-Lab, F-38000 Grenoble, France (Phone: +33 4 76 82 64 51, e-mail: alain.kibangou@ujf-grenoble.fr). Christian Commault is with Univ. Grenoble Alpes, CNRS,Gipsa-Lab, F-38000 Grenoble, France (Phone: +33 4 76 82 64 16, e-mail: christian.commault@gipsa-lab.grenoble-inp.fr) observability properties can serve for designing finite-time average consensus protocols such that in [START_REF] Sundaram | Distributed function calculation and consensus using linear iterative strategies[END_REF]. Studying the observability properties of a given network can also help for characterizing the resilience of the network to external attacks.

In this paper, we are interested in the observability issue in a network running a consensus algorithm. Different notions of network observability can be considered. A network is said to be:

• node-observable from a given node if that node is able to reconstruct the entire network state from its own measurements. This issue has been studied for instance in [START_REF] O'cleary | Observability and coarse graining of consensus dynamics through the external equitable partition[END_REF] and [START_REF] Parlangeli | On the reachability and observability of path and cycle graphs[END_REF] where it has been stated that a network with a state matrix having at least one non-simple eigenvalue is not node-observable. • nodes set-observable from a given set of nodes if the entire network state can be reconstructed from the measurements of these nodes. This issue has been considered in the pioneering work [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF] and also in [START_REF] Parlangeli | On the reachability and observability of path and cycle graphs[END_REF]. • neighborhood observable from a given node if that node can reconstruct the entire network state from its own measurements and those of its neighbors. This issue was studied in [START_REF] Kibangou | Algebraic characterization of observability in distance-regular consensus networks[END_REF].

• globally observable if it is neighborhood observable from any node.

The main contribution in [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF] was to carry out a graphtheoretic characterization of observability. Precisely a necessary condition for nodes set-observability based on the notion of equitable partition over graphs was stated. This notion is also the cornerstone of several results concerning the dual problem of controllability [START_REF] Rahmani | Controllability of multi-agent systems from a graph-theoretic perspective[END_REF], [START_REF] Zhang | Controllability of diffusivelycoupled multi-agent systems with general and distance regular coupling topologies[END_REF]. Recently, for the node-observability problem over consensus networks, a full relationship between the minimal size of the external equitable partition and the dimension of the observable subspace has been investigated in [START_REF] O'cleary | Observability and coarse graining of consensus dynamics through the external equitable partition[END_REF]. In general, studying necessary and sufficient conditions of observability for arbitrary graphs is a tough task. Therefore, in the recent years, studies have been generally restricted to some particular families of graphs. For instance, observability has been studied in [START_REF] Parlangeli | On the reachability and observability of path and cycle graphs[END_REF] for paths and circular graphs where the study was carried out based on rules on number theory. The case of simple grids and torus were considered by the same authors in [START_REF] Notarstefano | Reachability and observability of simple grid and torus graphs[END_REF] and [START_REF]Observability and reachability of grid graphs via reduction and symmetries[END_REF]. To summarize, two methodological approaches have been considered for a graph-theoretic characterization of observability: equitable partitions and number theory. The first approach gives rise to necessary conditions for general graphs, whereas the second allows getting necessary and sufficient conditions for specific graphs (paths, cycles, simple grids). In this paper, we introduce a new methodological approach that is well adapted for a larger family of graphs: distance regular graphs, which include cycles and strongly regular graphs. The regularity properties of these graphs can particularly be useful for improving network robustness as it is the case for cryptographic systems [START_REF] Zhou | Securing wireless sensor networks: a survey[END_REF], [START_REF] Kibangou | Step-size sequence design for finite-time average consensus in secure wireless sensor networks[END_REF]. Moreover, universality of strongly regular graphs have been stated in [START_REF] Fon-Der-Flaass | New prolific constructions of strongly regular graphs[END_REF] where it is established that any graph on N vertices is an induced subgraph of a strongly regular graph on at most 4N 2 vertices.

It is noteworthy to mention that, for distance regular graphs, the dual problem of controllability in multi-agent systems has been recently studied in [START_REF] Zhang | Controllability of diffusivelycoupled multi-agent systems with general and distance regular coupling topologies[END_REF]. The analysis methodology was based on the notion of graph equitable partitions. It was shown that a networked system modelled with a distance regular graph cannot be controlled from a single leader. At least N -D leaders are necessary, N and D standing respectively for the number of nodes and the diameter of the graph. In this paper, our approach is different. It is based on the Bose-Mesner algebra [START_REF] Bose | On linear associative algebras corresponding to association schemes of partially balanced designs[END_REF] and on the notion of nullity of graphs. In several cases, it gives simpler ways for assessing observability and we provide necessary and sufficient conditions in contrast to equitable partitions based analysis that only provides necessary conditions. Since distance regular graphs and strongly regular graphs have multiple eigenvalues, according to [START_REF] Parlangeli | On the reachability and observability of path and cycle graphs[END_REF], they are not node-observable. Therefore, our study concerns neighborhood observability and global-observability. We first extend the preliminary results on the algebraic characterization reported in [START_REF] Kibangou | Algebraic characterization of observability in distance-regular consensus networks[END_REF] and then introduce new results related to a graph characterization of observability, which does not require the computation of a matrix rank. Precisely, we show how building a bipartite graph that captures the observability properties of the graph. We derive a couple of necessary and sufficient conditions based on the nullity of such a graph.

The paper is organized as follows: in Section II, we state the problem and define the class of graphs under study. In Section III, we study the observability conditions by following an algebraic point of view. In Section IV, a graph characterization of observability conditions is proposed for strongly regular graphs first and then for more general distance regular graphs. Finally, the obtained results are illustrated for some particular families of graphs in Section V before concluding the paper.

Notations: The N × N matrices I N and J N denote respectively the identity matrix and the all ones matrix. e n stands for the nth vector of the canonical basis of ℜ N . For matrices A and B and the integer N, K (A, B T , N) stands for the matrix

A T BA T • • • B N-1 A T T .

II. PROBLEM FORMULATION

Agents in distributed multi-agent networks are required to operate in concert with each other in order to achieve system level objectives, while having access to short range communications, local sensing capabilities, and limited computational resources [START_REF] Mesbahi | Graph Theoretic Methods in Multiagent Networks[END_REF]. Graphs provide powerful abstractions of interactions in such networks. Throughout this paper, we will consider connected regular graphs. A graph

X (V ; E ) consists of a vertex set V = {v 1 , v 2 , • • • , v N }, of cardinality |V | = N,
and an edge set E ⊂ V × V , where an edge is an unordered pair of distinct vertices of X . For two vertices v n and v m of X (V ; E ), if (v n , v m ) ∈ E then v n and v m are said to be adjacent or neighbors. In the sequel, we will denote by N n the neighborhood of v n , i.e. the set of vertices of X that are adjacent to vertex v n , whereas N n will stand for the set of vertices non-adjacent to v n . Therefore, N n N n {v n } = V . The adjacency matrix A, with entries A nm defined as A nm = 1 if (v n , v m ) ∈ E and 0 elsewhere, captures the interaction between the vertices of a graph. X (V ; E ) is said to be regular of degree (or valency) K, when every vertex is precisely adjacent to K vertices, and connected if for each pair of distinct vertices there exists a path containing them; a path being a sequence of distinct vertices such that consecutive vertices in the sequence are adjacent. The number of edges involved is usually called the length of the path. For two vertices v n and v m , the length of the shortest path between them defines the distance dist(v n , v m ). The diameter, D, of a graph is then the maximum distance between any two vertices in V .

A. Problem Statement

Let us consider a network with N agents whose interactions are modeled with a connected regular graph X (V ; E ) of valency K and adjacency matrix A. The dynamics of the network are given by

x(k + 1) = Wx(k), W = γ 1 I N + γ 2 A, 0 < γ 2 < 1 K , (1)
where γ 1 and γ 2 are nonzero real scalars such that γ 1 +Kγ 2 = 1, while x(k) ∈ ℜ N contains the local values and defines the state of the network. By selecting the parameters γ 1 and γ 2 such that the spectral radius ρ(γ

1 I N + γ 2 A -1 N J N ) < 1, equation (1)
defines an average consensus protocol, which constitutes the cornerstone of several distributed estimation algorithms [START_REF] Garin | A survey on distributed estimation and control applications using linear consensus algorithms[END_REF].

Through short range communications, each node can directly observe the value of its neighbors. Therefore, the observation vector at vertex v n is given by

y n (k) = C n x(k), (2)
where

C T n = e n e m 1 • • • e m K ∈ ℜ N×(K+1) , with m i ∈ {m ∈ N|(v n , v m ) ∈ E } , i = 1, 2, • • • , K.
In this paper, the fundamental question to be studied is as follows: given consecutive measurements y n (k), k ≥ 0, is it possible to reconstruct the initial state x(0) of the entire network ? In other words, is the pair (W, C n ) observable ?

It is well known that observability of the pair (W, C n ) is guaranteed if and only if the so-called Kalman matrix O W,C n = K (C n , W, N) ∈ ℜ N(K+1)×N is full column rank. It is worth noting that observability of a given pair, i.e. neighborhoodobservability does not imply global-observability. As noticed in [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF], checking the rank condition of the Kalman matrix becomes infeasible when the number N of agents becomes very large. In what follows, we will devise alternative ways for studying observability for networks modeled as distance regular graphs and strongly regular graphs.

B. Strongly regular and distance regular graphs

Before defining strongly regular graphs and distance regular graphs, let us first recall the notion of association scheme with

D classes, that is a set A = {A 0 , • • • , A D } of N × N binary ( 0 -1) matrices such that [18]: 1) A 0 = I N , 2) D ∑ i=0 A i = J N , 3) A T i ∈ A for each i, 4) A i A j = A j A i ∈ span{A }
The algebra generated by the matrices A i , i = 0, • • • , D, is called Bose-Mesner algebra [START_REF] Bose | On linear associative algebras corresponding to association schemes of partially balanced designs[END_REF]. We can note from the second item that the matrices A i are linearly independent. In addition, from the fourth item, we can also note that this algebra is closed under multiplication.

Definition 1: A connected graph X (V ; E ) is said to be strongly regular if there are integers K, a, and c such that:

1) X (V ; E ) is regular with valency K.

2) Any two adjacent vertices v n and v m have exactly a common neighbors, i.e.

|N n N m | = a if (v n , v m ) ∈ E . 3) Any two distinct non-adjacent vertices v n and v m have exactly c common neighbors, i.e. |N n N m | = c if (v n , v m ) / ∈ E .
A strongly regular graph with N vertices, degree K, and parameters a and c is denoted by SRG(N,K,a,c). It has been shown that {I N , A, J N -I N -A}, with A the adjacency matrix of a strongly regular graph, forms an association scheme with two classes. Conversely, any association scheme with two classes arises from a strongly regular graph [START_REF] Brouwer | Distance-regular graphs[END_REF]. Definition 2: Consider a connected graph X (V ; E ) with diameter D. Define graphs X i , i = 0, • • • , D, with adjacency matrices A i , where two vertices are adjacent in X i if and only if their distance equals i. If {A 0 , A 1 , • • • , A D } defines an association scheme then X (V ; E ) is said to be distance regular.

Defining by

N (i)
n the neighborhood of v n in X i , for any two vertices v n and v m such that dist(v n , v m ) = i, distance regular graphs are characterized by the parameters

c i = N m N (i-1) n , i = 1, • • • , D, a i = N m N (i) n , i = 1, • • • , D, b i = N m N (i+1) n , i = 0, • • • , D -1.
We can interpret these parameters as follows: given two vertices v n and v m such that d(v n , v m ) = i, among the neighbors of v m there are c i at distance i -1 from v n , a i at distance i, and b i at distance i + 1. It follows that:

a i + b i + c i = K, a 0 = c 0 = b D = 0, c 1 = 1, c i k i = b i-1 k i-1 ,
where k i stands for the valency of the ith-distance graph

X i . One can note that: b 0 ≥ b 1 ≥ • • • ≥ b D-1 ≥ 0 and 0 < c 1 ≤ c 2 ≤ • • • ≤ c D .
The intersection array associated with a distance regular graph with diameter D is then defined as

{b 0 , b 1 , • • • , b D-1 ; c 1 , c 2 , • • • , c D }.
Example 1: A cycle with N vertices is a distance regular graph with valency 2. Its intersection array is given by {2, 1,

• • • , 1; 1, 1, • • • , 1, 1} if N is odd and {2, 1, • • • , 1; 1, 1, • • • , 1, 2} if N is even.
Example 2: A connected strongly regular graph SRG(N,K,a,c) is a distance-regular graph with diameter 2. Its intersection array is given by {K, Ka -1; 1, c}.

The Bose-Mesner algebra being closed under multiplication, one important property, in the case of distance regular graphs, is as follows [START_REF] Brouwer | Distance-regular graphs[END_REF]:

AA i = b i-1 A i-1 + a i A i + c i+1 A i+1 . (3)

III. ALGEBRAIC CHARACTERIZATION OF OBSERVABILITY

IN DISTANCE REGULAR GRAPHS.

In this section, for an arbitrary vertex v n , our aim is to devise algebraic conditions for neighborhood-observability, i.e. observability of the pair (W, C n ), by using simpler matrices than the Kalman observability matrix. In order to carry out our study, we will rewrite O W,C n according to the matrices A i defining the Bose-Mesner algebra. For this purpose, we first state the following lemma:

Lemma 1: [START_REF] Kibangou | Algebraic characterization of observability in distance-regular consensus networks[END_REF] The powers A p of the adjacency matrix of a distance regular graph can be expanded in the Bose-Mesner algebra as follows:

A p = p ∑ j=0 β p, j A j , (4)
where the coefficients β p, j depend uniquely on the intersection parameters and β p,p > 0.

From this lemma, we can show that rather studying observability through the Kalman matrix, we can instead study a simpler matrix depending on matrices of the Bose-Mesner algebra.

Lemma 2: Consider a network with N nodes modeled with a distance regular graph X (V ; E ) of diameter D and valency K whose association scheme is given by A = {A 0 , • • • , A D }. Assume that the dynamics of the network are modeled with equations ( 1) and ( 2) where C n stands for the observation matrix associated with vertex v n ∈ V .

The pair (W, C n ) is observable if and only if the matrix Ôn

= A 0 C T n A 1 C T n • • • A D C T n T ∈ ℜ (D+1)(K+1)×N is full column rank. Proof: See Appendix A.
The matrix Ôn is simpler than the Kalman matrix. Indeed, it is smaller and it does not resort to powers of the network matrix. The matrices C n A l , l = 0, 1, • • • , D, involved in Ôn have also some nice properties. For instance the following result demonstrated in [START_REF] Kibangou | Algebraic characterization of observability in distance-regular consensus networks[END_REF] will be particularly useful in the sequel.

Lemma 3: Let v n be a vertex of a graph X (V ; E ) characterized by the association scheme

A = {A 0 , A 1 , • • • , A D }
and let C n be the observation matrix associated with v n . The first row w T 1,l of the matrix C n A l can be written as a linear combination of rows of

C n A j , j = 0, 1, • • • , l -1.
Now, equivalently to the Kalman matrix, we define a Bose-Mesner observability matrix that completely characterizes observability in distance regular graphs.

Theorem 1: Consider a network with N nodes modeled with a distance regular graph X (V ; E ) of diameter D and valency K whose association scheme is given by

A = {A 0 , • • • , A D }.
Assume that the dynamics of the network are modeled with equations ( 1) and ( 2) where C n stands for the observation matrix associated with vertex v n ∈ V . The pair (W, C n ) is observable if and only if:

1) the Bose-Mesner observability matrix Ōn

= A 0 C T n • • • A D-1 C T n T ∈ ℜ D(K+1)×N is full column rank.

2) the truncated Bose-Mesner observability matrix Õn

= A 0 CT n • • • A D-1 CT n T ∈ ℜ DK×N has rank equal to N -1, where CT n = e m 1 • • • e m K ∈ ℜ N×K , with m i ∈ {m ∈ N|(v n , v m ) ∈ E } , i = 1, 2, • • • , K. Proof: See Appendix B.
The Bose-Mesner observability matrix and its truncated version are much simpler than the Kalman matrix since in general the diameter D is much lower than N.

Eventually, we can deduce the following necessary observability condition:

Corollary 1: Consider a network with N nodes modeled with a distance regular graph X (V ; E ) of diameter D and valency K whose association scheme is given by

A = {A 0 , • • • , A D }.
Assume that the dynamics of the network are modeled with equations ( 1) and ( 2) where C n stands for the observation matrix associated with vertex v n ∈ V . The pair

(W, C n ) is observable only if DK ≥ N -1.
From the corollary above, non-observability can be stated by considering only the number of vertices of the graph, its diameter, and its valency. We can therefore easily conclude on non-observability in some families of graphs without carrying out complex studies. O 2 is a triangle while O 3 is the Petersen graph (see Fig. 4). These graphs have been proposed as a network topology in parallel computing [START_REF] Ghafoor | A study of odd graphs as fault-tolerant interconnection networks[END_REF]. We can note that for n ≥ 3 the necessary condition is not fulfilled. With the simple tool provided herein we can state on non-observability of graphs that can have a very high number of vertices without any computation of matrix rank nor investigation of existence of equitable partitions as in [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF].

In what follows, we exploit some properties of the truncated Bose-Mesner observability matrix to devise a graph based characterization of observability.

IV. GRAPH BASED CHARACTERIZATION OF OBSERVABILITY IN STRONGLY REGULAR GRAPHS AND DISTANCE REGULAR GRAPHS

Before analyzing observability from structural properties of some given induced graphs to be defined, we first recall the notion of matching that will be useful in the sequel of our study.

Definition 3: For a graph X (V ; E )

• A matching is a collection of mutually non-adjacent edges of X . • A maximum matching is a matching with the maximum possible number of edges. Induced graphs that will be used for characterizing observability are bipartite. We will, in particular, be interested by the notion of nullity of graphs.

A. Nullity of bipartite graphs

The nullity η(X ) of a graph X (V ; E ), with N = |V |, is defined as the algebraic multiplicity of the number zero in the graph spectrum, i.e. in the spectrum of the corresponding adjacency matrix. It is linked to the rank of the adjacency matrix as: η(X ) = Nrank(A). In addition to the evident relation of this notion with spectral graph theory, it is noteworthy to mention its importance in the research field named Chemical Graph Theory [START_REF] Gutman | Mathematical concepts in organic chemistry[END_REF], [START_REF] Dias | Molecular Orbital calculations using chemical graph theory[END_REF]. In the sequel we will make use of theorems characterizing the nullity of bipartite graphs introduced by Chemical Graph theorists. We first recall that Definition 4: A graph X (V ; E ) with N vertices is said to be bipartite if the vertex set can be partitioned in two parts V 1 and V 2 such that every edge has one end in V 1 and one in V 2 . In such a case, the graph will be denoted as

X (V 1 , V 2 ; E ).
For a bipartite graph X (V 1 , V 2 ; E ), the adjacency matrix is structured as:

A = 0 B B T 0 . the matrix B, with dimensions |V 1 | × |V 2 |
, called the biadjacency matrix, captures the relationship between vertices of the two disjoint subsets defining the bipartite graph. Theorem 2: [START_REF] Longuet | Resonance structures and MO in insaturated hydrocarbons[END_REF] For a bipartite graph X (V 1 , V 2 ; E ) with N vertices and bi-adjacency matrix B, η(X ) = N -2rank(B).

For computing the nullity of a graph, we can also draw conclusions from the structure of the graph. In general, finding connections between the structure of a graph and its nullity is a tough task. For bipartite graphs we have the following result:

Theorem 3: [START_REF] Cvetković | Graph theory and molecular orbitals II[END_REF] If a bipartite graph X (V 1 , V 2 ; E ) with N ≥ 1 vertices does not contain any cycle of length 4s (s = 1, 2, • • • ), then η(X ) = N -2m, where m is the size of a maximum matching in X . One can note that a particular case of this theorem concerns trees that are by definition acyclic. Moreover, the two previous theorems yield the following obvious corollary:

Corollary 2: If a bipartite graph X (V 1 , V 2 ; E ) with N ≥ 1 vertices does not contain any cycle of length 4s (s = 1, 2, • • • ), then the rank of its bi-adjacency matrix B is the size of the maximum matching in X . Determining whether a bipartite graph contains a cycle whose length is a multiple of 4 is a question that has been answered by providing some sufficient conditions. Following the formalism of signed graphs, an answer has been provided in [START_REF] Conforti | Balanced cycles and holes in bipartite graphs[END_REF] and more generally some algorithms have been proposed for instance in [START_REF] Halford | An algorithm for counting short cycles in bipartite graphs[END_REF].

B. Graph-based characterization of observability in strongly regular graphs

Keeping in mind that strongly regular graphs admit an association scheme with D = 2 classes, then applying Theorem 1 to strongly regular graphs yields that observability of the pair (W, C n ) is guaranteed if and only if the truncated Bose-

Mesner observability matrix Õn

= Cn A 0 Cn A 1 ∈ ℜ 2K×N has rank N -1.
Let us define a permutation matrix Π Π Π that allows partitioning Õn in two sub-matrices of dimensions 2K × K and 2K × (N -K) respectively:

Õn Π Π Π = Õn,1 Õn,2 = I K 0 Bn,1 Bn,2
.

We can easily note that the intersection of the column space of these two sub-matrices is restricted to zero. Therefore rank( Õn ) = rank( Õn Π Π Π) = rank( Õn,1 ) + rank( Õn,2 ) [START_REF] Lopez-Valcarce | On blind equalization of rank deficient nonlinear channels[END_REF]. As a consequence, we get:

rank( Õn ) = K + rank( Õn,2 ) = K + rank( Bn,2 ). (5)
From the above equation, we can conclude that the rank property of Õn is completely characterized by the rank of Bn,2 . This matrix can be studied following a graph theory point of view. For this purpose, we first state the following definition: Definition 5: Consider a strongly regular graph X (V ; E ). The local bipartite observability graph L n (N n , N n ; E), E ⊂ E , associated with vertex v n ∈ V is defined as the bipartite graph where u ∈ N n and v ∈ N n are adjacent if and only if they are adjacent in X (V ; E ). Its bi-adjacency matrix B n is equal to Bn,2 . The local bipartite observability graph associated with vertex v n can be built by first dividing the vertices in V \v n in two sets: the neighbors of v n and the non-adjacent vertices. Then take off the edges between vertices of the same set along with vertex v n . The obtained graph is bipartite.

Example 4: Figure 1 depicts a 5-Payley graph, that is also a cycle graph with 5 vertices, and the local bipartite observability graph associate with a given vertex. Now, in the following theorem, we state that observability of the pair (W, C n ) depends only on the local bipartite observability graph.

v 1 v 2 v 3 v 4 v 5 v 2 v 3 v 4 v 5 N 1 N1
Theorem 4: Consider a network with N nodes modeled with a connected strongly regular graph X (V ; E ) of valency K and adjacency matrix A. Assume that the dynamics of the network are modeled with equations (1) and (2) where C n stands for the observation matrix associated with vertex v n ∈ V . Let L n (N n , N n ; E), with bi-adjacency matrix B n , be the local bipartite observability graph associated with v n . The following statements are equivalent:

• the pair (W, C n ) is observable;

• the bi-adjacency matrix B n of its associated local bipartite observability graph L n (N n , N n ; E) has rank N -K -1;

• the local bipartite observability graph L n (N n , N n ; E) has nullity η(L n ) = 2K -N + 1. Proof: From Theorem 1, we know that (W, C n ) is observable iff rank( Õn ) = N -1. Using (5), it is equivalent to have rank(B n ) = N -K -1 since B n is the bi-adjacency matrix of L n . Applying Theorem 2, we know that the nullity of this bipartite graph is given by η(L n (N n , N n ; E)) = N -1 -2rank(B n ). Knowing that observability means that rank(B n ) = N -K -1, we conclude that the nullity of the local bipartite observability graph must be equal to 2K -N + 1.

Inferring the nullity of a graph from its structure is not an easy task in general. However, we can deduce conditions that can be particularly useful in practice. For instance, taking into account the link between the rank of the bi-adjacency matrix and the notion of maximum matching of a bipartite graph for a given family of graphs, we can state the following condition:

Theorem 5: Consider a network with N nodes modeled with a connected strongly regular graph X (V ; E ) of valency K and adjacency matrix A. Assume that the dynamics of the network are modeled with equations ( 1) and ( 2) where C n stands for the observation matrix associated with vertex v n ∈ V . Assuming that L n (N n , N n ; E), the local bipartite observability graph associated with v n , does not contain any cycle of length 4s (s = 1, 2, • • • ). The pair (W, C n ) is observable if and only if the size of a maximum matching in L n equals N -K -1. Proof: As said before, observability is ensured if and only if the rank of the bi-adjacency matrix of the local bipartite observability graph L n (N n , N n ; E) equals N -K -1. When L n (N n , N n ; E) does not contain any cycle of length 4s (s = 1, 2, • • • ), from Corollary 2, we know that the rank of the bi-adjacency matrix is equal to the size of a maximum matching in L n . We can therefore deduce that observability of the pair (W, C n ) is equivalent to ensure that the size of a maximum matching of L n (N n , N n ; E) equals N -K -1.

C. Graph-based characterization of observability in distance regular graphs

In this section, we extend the results from strongly regular graphs to distance regular graphs. First, we can note that the notion of local bipartite graph introduced for strongly regular graphs only takes adjacency relation into account. When considering more general distance regular graphs, the notion of distance is to be seriously considered. Each class d of the association scheme associated with a distance regular graph introduces a different modality for the analysis of the graph. For this purpose, we resort to the concept of multilayer graphs that can be used for representing interactions with different modalities. A multi-layer graph is defined as a graph G (V ; E ) with M individual layers each layer being a graph G (i) (V ; E (i) ). Such representations have been used for modeling social networks or citation networks for instance [START_REF] Eagle | Reality mining: Sensing complex social systems[END_REF], [START_REF] Eagle | Multi-dimensional edge inference[END_REF].

Definition 6: Let X (V ; E ) and X i (V ; E i ) be a distance regular graph, with valency K and diameter D, and its ithdistance graph, respectively. The local observability multilayer graph associated with a vertex v n is defined as a multilayer graph M n (N n , N n ; E), E ⊂ E constituted with (D -1) layers, each layer M (i) n being defined as a bipartite graph where u ∈ N n and v ∈ N n are adjacent if they are adjacent in X i . Figure 2 depicts a distance regular graph, here a cycle with 6 vertices, and the two layers defining the local observability multilayer graph associated with vertex v 1 .

v 2 v 1 v 3 v 4 v 5 v 6 v 2 v 3 v 4 v 5 v 6 N 1 N1 M (1) 1 v 2 v 3 v 4 v 5 v 6 N 1 N1 M (2) 1
B n = B T n,1 B T n,2 • • • B T n,D-1
T as biadjacency matrix.

The local unfolded bipartite observability graph associated with vertex v 1 of the graph depicted in Fig. 2 is given in Fig. 3. For D = 2, corresponding to a strongly regular graph, M n (N n , N n ; E) has a single layer. Therefore the local unfolded bipartite observability graph is the so-called local bipartite observability graph defined in the previous subsection. Then, we can easily extend the previous results to the more general case of distance regular graphs, i.e. for an arbitrary value of D. Theorem 6: Consider a network with N nodes modeled with a connected distance regular graph X (V ; E ) of valency K, diameter D, and association scheme

A = {A 0 , A 1 , • • • , A D }.
Assume that the dynamics of the network are modeled with equations ( 1) and ( 2) where C n stands for the observation matrix associated with vertex v n ∈ V . Let Y n , with biadjacency matrix

B n = B T n,1 B T n,2 • • • B T n,D-1
T , be the local unfolded bipartite observability graph associated with v n .

The following statements are equivalent:

• the pair (W, C n ) is observable;

• the bi-adjacency matrix B n of the local unfolded bipartite observability graph Y n associated with v n has rank N -K -1; • the local unfolded bipartite observability graph Y n associated with v n has nullity η(Y n ) = DK -N + 1.

Proof: From Theorem 1, we know that the pair (W, C n ) is observable iff the corresponding truncated Bose-Mesner observability matrix Õn has rank N -K -1. As we did for SRGs we can also partition Õn Π Π Π in two parts Õn,1 and Õn,2 where rank( Õn,1 ) = K and Õn,2

= 0 T B T n,1 • • • B T n,2 T .
We can show that rank( Õn ) = K + rank( Õn,2 ) where the matrix B n having B n,i , i = 1, • • • , D -1, as sub-matrices can be viewed as the bi-adjacency matrix of the unfolded bipartite observability graph Y n . This graph has (D -2)K + N -1 vertices. Then, applying Theorem 2, we know that the nullity of this graph is given by

(D -2)K + N -1 -2rank(B n ). Since observability means that rank( Õn,2 ) = rank(B n ) = N -K -1,
we conclude that the nullity of the local unfolded bipartite observability graph must be equal to DK -N + 1. Now, we can state the following observability conditions that can be proven by following guidelines similar to those considered for strongly regular graphs: Theorem 7: Consider a network with N nodes modeled with a connected distance regular graph X (V ; E ) of valency K, diameter D, and association scheme

A = {A 0 , A 1 , • • • , A D }.
Assume that the dynamics of the network are modeled with equations ( 1) and ( 2) where C n stands for the observation matrix associated with vertex v n ∈ V . Assuming that Y n , the local unfolded bipartite observability graph associated with vertex v n , does not contain any cycle of length 4s (s = 1, 2, • • • ). The pair (W, C n ) is observable if and only if the size of a maximum matching in Y n equals N -K -1.

Eventually, we can deduce the following necessary condition:

Corollary 3: Consider a network with N nodes modeled with a connected distance regular graph X (V ; E ) of valency K and diameter D. Assume that the dynamics of the network are modeled with equations ( 1) and ( 2) where C n stands for the observation matrix associated with vertex v n ∈ V . Let Y n be the local unfolded bipartite observability graph associated with v n . The pair

(W, C n ) is observable only if the size of a maximum matching in Y n equals N -K -1.
From corollaries 1 and 3, we have two ways for concluding on non-observability in a given connected distance regular graph. The first condition is a simple comparison of the valency of the graph with the lower bound given by N-1 D whereas the second condition goes further by exploring the adjacency relation through the analysis of the local bipartite observability graph. For instance, let us consider the well known Petersen and Clebsch graphs that are strongly regular graphs (distance regular with D = 2) with parameters SRG(10,3,0,1) and SRG(16,5,0,2) respectively.

Using Corollary 1, we can directly conclude that these graphs are not observable. Indeed their respective valencies are lower than the required lower bound. In figures 4 and 5 (right) are depicted the local observability bipartite graphs associated with a given vertex of the Petersen graph and the Clebsch graph respectively. According to Corollary 3, the size of a maximum matching should be 6 for the Petersen graph and 10 for the Clebsch graph. We can note from figures 4 and 5 that the size m of a maximum matching in L 1 is equal to 3 for the Petersen graph and m = 5 for the Clebsch graph. The obvious conclusion concerns again non-observability of these graphs.

The necessary condition for observability, as stated in [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF], requires the enumeration of all equitable partitions of the graph under study and those of the associated augmented graph. It is well known that graph partitioning is NP-hard [START_REF] Karypis | A parallel algorithm for multilevel graph partitioning and sparse matrix ordering[END_REF]. Provided the graph is known to be distance-regular, the conditions stated herein only require the knowledge of some graph parameters (number of vertices, valency, and diameter), on one hand, and the computation of the size of the maximum matching of a bipartite graph on the other hand. The later can be computed with a complexity of order of the number of edges of the bipartite graph. In addition, checking that an arbitrary graph is distance-regular can be carried out by checking that for every vertex, the distance partition is regular with the same quotient matrix [START_REF] Van Dam | Spectral characterizations of some distance regular graphs[END_REF]. Therefore, from a computation point of view, the conditions proposed herein are less complex than that in [START_REF] Ji | Observability and estimation in distributed sensor networks[END_REF].

V. OBSERVABILITY OF DISTANCE-TRANSITIVE GRAPHS

In the previous sections we have studied neighborhoodobservability, i.e. observability for a given pair (W, C n ). As explained in the problem formulation section, a graph will be said to be globally-observable if all the pairs are observable. We can state that a graph is not globally-observable if at least one pair is not observable. In this section, the fundamental question is: can we conclude on global-observability of the graph from the study of a single pair? The answer is yes for a family of graphs exhibiting some desirable symmetries.

Definition 8: [START_REF] Godsil | Algebraic graph theory[END_REF] Given a graph X (V ; E ), an automorphism of X is a bijective function ϕ :

V → V such that v n is adjacent to v m if and only if ϕ(v n ) is adjacent to ϕ(v m ).
The set of all automorphisms is the automorphism group of X , denoted by Aut(X ).

Definition 9:

[31] X (V ; E ) is said to be distance-transitive if, for vertices v n , v j , v k , v l ∈ V , with dist(v n , v j ) = dist(v k , v l ), there exists some ϕ ∈ Aut(X ) satisfying ϕ(v n ) = v k and ϕ(v j ) = v l .
A distance-transitive graph is symmetric and also distance regular. Given two vertices v n and v m it exists a permutation matrix such that

Π Π Π such that Π Π Π -1 AΠ Π Π and C m Π Π Π -1 = C n , meaning that O W,C m = O W,C n Π Π Π. Thus, rank(O W,C m ) = rank(O W,C n )
for two distinct vertices v n and v m . Therefore we can state the following corollary:

Corollary 4: Consider a network with N nodes modeled with a connected distance-transitive graph X (V ; E ). The network is globally-observable if the pair (W, C n ) is observable for any arbitrary vertex v n .

A. Application to some families of graphs

In this sub-section, we consider application of the main results of this paper to some families of graphs that are distancetransitive. As said before, in such a case, the conclusions drawn do not depend on the selected vertex. Therefore, we can conclude if the underlying graph is globally-observable or not.

1) Rook's graph [START_REF] Godsil | Algebraic graph theory[END_REF]: An n × n Rook's graph is a SRG with parameters (n 2 , 2n -2, n -2, 2), n ≥ 2. It represents the moves of a rook on an n × n chessboard. Its vertices may be given coordinates (x 1 , x 2 ), where 1 ≤ x i ≤ n, i = 1, 2. Two vertices are adjacent if and only if they have one common coordinate. From Corollary 5, we can deduce that an n × n Rook's graph is observable only for the values of n giving rise to non positive values for the polynomial f (n) = n 2 -4n + 3. Only two values of n fulfill this condition: n = 2 and n = 3. Their corresponding local bipartite observability graphs are depicted in Fig. 6. For n = 2 the local observability bipartite graph has no cycle and the size of the maximum matching is equal to 1. Applying Theorem 5, we can conclude that the graph is observable. However, for n = 3, the local observability bipartite graph admits cycles of length 8. Unfortunately, we are outside the framework of Theorem 5. Studying the bi-adjacency matrix of this graph:

B =     1 1 0 0 1 0 1 0 0 1 0 1 0 0 1 1     ,
we can note that this matrix is rank deficient (rank(B) = 3). Since observability is ensured if and only if the bi-adjacency matrix of the local observability matrix is full column rank, we can deduce that for n > 2 the Rook's graph is not observable. Note that observability occurs only for n = 2 that is a cycle graph with 4 vertices.

2) Payley graph [START_REF] Godsil | Algebraic graph theory[END_REF]: The Payley graph is a graph whose vertex set is a finite field with q elements. Two vertices are adjacent when their difference is a square in the field. This is an undirected graph when q is congruent to 1 (mod 4). It is a SRG(q, q-1 2 , q-5 4 , q-1 4 ). We can note that for any value of q, the minimal number of adjacent nodes is fulfilled. Let us study the Payley graph (13,6,2,3). Its associated local bipartite observability graph is depicted in Fig. 7. We can note the existence of a cycle of length 4. The analysis of the structure of the graph cannot confirm the observability of the graph. However, by studying its bi-adjacency matrix, we can note that B is full column rank. Hence, the Payley graph with 13 vertices is observable. Generalizing this result to an arbitrary value of q congruent to 1 (mod 4) is still an open question. Indeed, for q = 5 a Payley graph is observable. Its local bipartite observability graph is depicted in Fig. 1(b). However, for q = 9, the payley graph is not observable. Indeed, we get the graph depicted in Fig. 8 with the corresponding bi-adjacency matrix: 3) Hamming graph: Let S be a set of q elements and d a positive integer. The Hamming graph H(d,q) has for vertex set the set of ordered d-tuples of elements of S , or sequences of length d from S . Two vertices are adjacent if they differ in precisely one coordinate. Therefore the number of vertices is q d . The Hamming graph is distance regular with degree d(q -1). We can note that H(1,q), H(2,q), and H(d,1) correspond to a complete graph, a Rook's graph, and a single vertex respectively. According to the sufficient condition derived in the previous section, we know that observability is ensured only if d(q -1) ≥ q d -1 d ; meaning that the bi-variate function f (d, q) = q dd 2 (q -1) -1 should be non positive. By discarding the complete graph and the single vertex case, the only values for which f (d, q) is non positive are (d = 2, q = 2), (d = 2, q = 3), (d = 3, q = 2), and (d = 4, q = 2). Since the cases H(2,2) and H(2,3) have been studied in the subsection devoted to the Rook's graph, here we concentrate our study on H(2,3) and H(4,2). The corresponding local observability bipartite graphs are depicted in figure 9. For H(3,2), we can note that the bipartite graph has a cycle of length 6. The size of the maximum matching equals 4. Then applying Theorem 7, we can conclude that H(3,2) is observable. Unlike H(3,2), the local observability bipartite graph associated with H(4,2) has a cycle of length 8. By computing the rank of its bi-adjacency matrix we get rank(B) = 9 instead of 11 as required by the observability condition. In conclusion, the Hamming graph fulfilling the observability condition are: H(2,2) and H(3,2). J(n,1) and J(n,n-1) correspond to a complete graph. Since the valency of a non complete graph is strictly lower than the number of vertices of the graph, we have k(nk) ≤ n k -1. As a consequence, in order to also fulfill the observability necessary condition, we should have the following inequality:

B =         1 0 1 0 0 1 0 0 0 1 1 1 0 0 1 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 1 1 0 1 0 0        
B =     1 1 0 0 0 1 1 0 0 0 1 1 1 0 0 1     .
n k -1 ≤ ε n,k k(n -k) ≤ ε n,k n k -1 ,
with ε n,k = min{k, n -k}. Such inequality is verified only for k = 1 or k = n -1. Therefore, except the case of complete graph J(n,1) and J(n,n-1), Johnson graphs are not observable.

5) Cycle graph:

A cycle graph with N vertices is distance regular with valency 2 and diameter D = N/2 if N is even and D = (N -1)/2 if N is odd. It has been shown in [START_REF] Parlangeli | On the reachability and observability of path and cycle graphs[END_REF] that these graphs are observable. The proof was based on number theory. Herein, we show how getting the same conclusion from properties of the local unfolded bipartite graph Y n . Indeed, we can note that the degree of each vertex in the local unfolded bipartite observability graph will be 1 or 2. Moreover, for a given vertex v n , two vertices in N n can share at most 1 neighbor in N n . We can deduce that the local unfolded bipartite observability graph Y n associated with a cycle graph is a forest, that is by definition acyclic. We can therefore apply the necessary and sufficient condition of Theorem 7. Since a cycle has valency 2, the size of a maximum matching should be equal to N-3. We can note that each layer of the local unfolded bipartite observability graph Y n induces a maximum matching of size 2 except the layer associated with distance D -1 that gives a maximum matching of size 2 if N is odd and 1 if N is even. Therefore the size of a maximum matching in Y n equal 2(D -2) + 1 if N is even and 2(D -2) + 2 if N is odd. As a consequence the size of a maximum matching in Y n is exactly equal to N -3, which confirms observability of cycles. One can note that the proof of this statement as carried out herein is simpler than that in [START_REF] Parlangeli | On the reachability and observability of path and cycle graphs[END_REF].

VI. CONCLUSION

In this paper, we have studied the observability issue in a consensus network described with a connected undirected graph and a topology constrained to be strongly regular or distance regular. These families of graphs admit an association scheme. We have first derived a new algebraic condition for observability based on the Bose-Mesner algebra. Then we have shown that observability can be studied by considering the nullity of some bipartite graphs introduced in this paper. Such a nullity can be deduced from the structure of the bipartite graph. When conclusion cannot be drawn from the structure of the graph, the bi-adjacency matrix of the so-called local bipartite observability graph must be full column rank for guaranteeing observability. A new necessary condition has been stated: observability is ensured in such graphs only if DK ≥ N -1 where D is the number of classes of the association scheme, or the diameter of the graph, N the number of vertices, and K the valency of the graph, i.e. the cardinality of the neighborhood. Similarly, non-observability can also be stated when the size of the maximum matching of the local bipartite observability graph is not equal to N -K -1. The main message of this paper can be summarized as follows: observability condition does not necessarily require the computation of the rank of the observability matrix. Analyzing the structure of well defined graphs such as the local bipartite observability graph can be sufficient as shown herein. When such a characterization is not possible, instead of computing the rank of the Kalman observability matrix, the analysis can be carried out from the rank of a much simpler matrix called here Bose-Mesner observability matrix.

Example 3 :

 3 Odd graphs O n are distance-regular graphs of degree n, diameter n -1, and number of vertices 2n -1 n -1 .

Fig. 1 .

 1 Fig. 1. (a) A strongly regular graph SRG(5,2,0,1) with the associated local bipartite observability graph corresponding to vertex v 1 (b).

Fig. 2 .Definition 7 :

 27 Fig. 2. A distance regular graph (left) and the two layers (middle and right) of the associated local observability multilayer graph or the vertex v 1 . Definition 7: Let B n,i , i = 1, • • • , D -1, be the bi-adjacency matrices of the layers M (i) n of a local observability multilayer graph M n (N n , N n ; E), then the local unfolded bipartite observability graph Y n is defined as the bipartite graph admitting the matrix B n = B T n,1 B T n,2 • • • B T

Fig. 3 .

 3 Fig. 3. Local unfolded bipartite observability graph associated with a cycle with 6 vertices.

Fig. 4 .

 4 Fig. 4. Petersen graph (left) and the Local bipartite observability graph associated with vertex v 1 (right).

Fig. 5 .

 5 Fig. 5. Clebsch graph (left) and the local bipartite observability graph associated with vertex v 1 (right).

Fig. 6 .

 6 Fig. 6. Local observability bipartite graphs for n × n Rook's graph for n = 2 (left) and n = 3 (right).

Fig. 7 .

 7 Fig. 7. Bi-adjacency matrix and local observability bipartite graph associated with a Payley graph with 13 vertices.

Fig. 8 .

 8 Fig. 8. Bi-adjacency matrix and local observability bipartite graph associated with a Payley graph with 9 vertices.

Fig. 9 .

 9 Fig. 9. Local unfolded observability bipartite graph associated with H(3,2) (left) and H(4,2) (right) 4) Johnson graph [18]: Let Ω be a fixed set of size n. The Johnson graph J(n,k) is the graph whose vertices are the subsets of Ω with size k and where two subsets are adjacent

APPENDIX

A-Proof of Lemma 2

First, we expand powers W p of the consensus matrix in the Bose-Mesner algebra. Since W = γ 1 I + γ 2 A, we get:

α p, j A j , with α p, j = p j γ p-j 1 γ j 2 .

γ 1 and γ 2 being nonzero, the coefficients α p, j are nonzero. By denoting Φ Φ Φ the N × N nonsingular triangular matrix of entries α p, j , we can note that K (I N , W, N) = (Φ Φ Φ ⊗ I N ) K (I N , A, N), where ⊗ stands for the Kronecker matrix product. Now, using Lemma 1, we get: ) and using properties of the Kronecker product, we get O W,C n = (Γ Γ Γ ⊗ I K+1 ) Ôn . Φ Φ Φ being a nonsingular matrix, we can also conclude that Γ Γ Γ is full column rank:

Hence, the pair (W, C n ) is observable iff Ôn is full column rank.

B-Proof of Theorem 1

From properties of the association scheme we know that

where

× N all ones matrix. We can conclude that a row of C n A D can be written as a linear combination of the all ones row vector 1 T and those of matrices

More precisely if w T j,l denotes the j-th row of the matrix C n A l , then we have w T

As a consequence the K last rows of C n A D do not increase the rank of Ôn . Thus

),which concludes the proof of the first condition. From Lemma 3, we also know that first rows w T 1,l of C n A l are linearly dependent from rows of