Graph Entropy from Closed Walk and Cycle Functionals
This paper presents an informational functional that can be used to characterise the entropy of a graph or network structure, using closed random walks and cycles. The work commences from Dehmer’s information functional, that characterises networks at the
- PDF / 1,765,133 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 116 Downloads / 211 Views
2
Department of Computer Science, IM—Sciences, Peshawar, Pakistan [email protected] Department of Computer Science, University of York, York YO10 5GH, UK {edwin.hancock,richard.wilson}@york.ac.uk
Abstract. This paper presents an informational functional that can be used to characterise the entropy of a graph or network structure, using closed random walks and cycles. The work commences from Dehmer’s information functional, that characterises networks at the vertex level, and extends this to structures which capture the correlation of vertices, using walk and cycle structures. The resulting entropies are applied to synthetic networks and to network time series. Here they prove effective in discriminating between different types of network structure, and detecting changes in the structure of networks with time.
Keywords: Graph entropy
1
· Random walks · Ihara coefficients
Introduction
The problem of determining the complexity of network structures is an elusive one, which has challenged graph-theorists for over five decades. Broadly speaking the are two approaches to the problem. According to randomness complexity, the aim is to probabilistically characterise the degree of disorganisation of a network, and Shannon entropy provides one convenient way of doing this. One of the earliest attempts at computing network entropy was proposed by K¨ orner [3]. This involves computing the entropy of a vertex packing polytope, and is linked to the chromatic number of the graph. Another simple approach is to use Shannon entropy to compute the homogeneity of the vertex degree distribution. Statistical complexity, on the other hand aims to characterise network complexity beyond randomness. One of the shortcomings of randomness complexity is that it does not capture vertex correlations. To overcome this problem, statistical complexity allows more global structure to be probed. For instance, by using the logical or thermodynamic depth of a network, the details of inhomogeneous degree structure can be problem. One powerful techniques here is to use a variant of the Kologomorov-Chaitin [4,5] complexity to measure how many operations are need to transform a graph into a canonical form (see [9] for a review of network complexity). c Springer International Publishing AG 2016 A. Robles-Kelly et al. (Eds.): S+SSPR 2016, LNCS 10029, pp. 174–184, 2016. DOI: 10.1007/978-3-319-49055-7 16
Graph Entropy from Closed Walk and Cycle Functionals
175
So although entropy based methods provide powerful tools to characterise the properties of a complex network, one of the challenges is to define the entropy in a manner that can capture the correlations or long-range interactions between vertices. One way to do this is to adopt path or cycle-based methods or to use other substructures that allow networks to be decomposed into non-local primitives [7,8]. In this way some of the strengths of both the randomness and statistical approaches to complexity can be combined. One approach that takes an important step in this direction is thermody
Data Loading...
