Discovery of Energy Network Topology from Uncertain Flow Measurements
The objective we focus on here consists in discovering the topology of an energy distribution network modeled by a flow digraph from which we only know the set of arcs without identification of their extremities. We also have as inputs a set of temporal s
- PDF / 548,067 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 21 Downloads / 194 Views
DAVID - Lab, Universit´e de Versailles - St Quentin, 55 Avenue des ´etats unis, 78000 Versailles, France [email protected] 2 DCbrain, 23 Avenue d’italie, 75013 Paris, France {ehounou willy,arnaud}@dcbrain.com http://www.dcbrain.com
Abstract. The objective we focus on here consists in discovering the topology of an energy distribution network modeled by a flow digraph from which we only know the set of arcs without identification of their extremities. We also have as inputs a set of temporal series of flow measures on these arcs and the correlation matrix of the arcs, with possible errors. From these inputs, we consider the graph which incidence matrix is the correlation one. If the correlation matrix contains no errors, this graph is the line graph of the network to be discovered. Thus, given this graph, we then propose here algorithms determining the graph with the same vertex set being a line graph and maximizing the set of similar edges with the initial correlation graph. We then evaluate the performances of this approach by simulation on 50 networks, randomly generated.
Keywords: Flow network
1
· Line graph · Topology discovery
Introduction
The aim of our work is to predict a probable topology of the network, considered as a DAG, knowing only the links (without knowing their extremities) and matching to the flow measures on them. Indeed, the contribution of this paper consists in algorithms to discover the topology of a flow network from a binary adjacency matrix called matE obtained by the correlation of the flow measures. Let’s remember that 1 means two measures are correlated and 0 means two measures are not correlated. The method used to correlate measures is Symbolic Aggregate approXimation (SAX) [2]. These correlations, if they are correct, induce the line graph [3] of the underlying undirected graph of the network under consideration. In fact, a line graph L(G) of an undirected graph G is a graph such that each vertex of L(G) represents an edge of G and two vertices of L(G) are adjacents iff their corresponding edges share a common endpoint in G. Unfortunately, measure errors often appear and the topology deduced from the c Springer International Publishing AG 2017 J. Rothe (Ed.): ADT 2017, LNAI 10576, pp. 355–360, 2017. DOI: 10.1007/978-3-319-67504-6 27
356
W.J. Ehounou et al.
correlations is not that of the desired line graph. The objective is to correct this graph in order to obtain a line graph as close as possible to that of the DAG. Various works have been devoted to the discovery of a graph from its line graph [1,3,4]. In particular, initial works [4] show that a graph is a line graph iff it admits a decomposition of its set of edges in cliques such that each vertex is covered by one or two cliques. Line graphs can also be characterized by a set of nine forbidden induced subgraphs [3]. A concept of root graph was introduced by Whitney [5] and he proved that if two line graphs are isomorphic and connected, then their root graphs are isomorphic except for the triangle graph. Algorithms, we
Data Loading...
