Reconstruction of Networks from Their Betweenness Centrality
In this paper we study the reconstruction of a network topology from the values of its betweenness centrality, a measure of the influence of each of its nodes in the dissemination of information over the network. We consider a simple metaheuristic, simula
- PDF / 432,730 Bytes
- 7 Pages / 430 x 660 pts Page_size
- 93 Downloads / 197 Views
bstract. In this paper we study the reconstruction of a network topology from the values of its betweenness centrality, a measure of the influence of each of its nodes in the dissemination of information over the network. We consider a simple metaheuristic, simulated annealing, as the combinatorial optimization method to generate the network from the values of the betweenness centrality. We compare the performance of this technique when reconstructing different categories of networks –random, regular, small-world, scale-free and clustered–. We show that the method allows an exact reconstruction of small networks and leads to good topological approximations in the case of networks with larger orders. The method can be used to generate a quasi-optimal topology for a communication network from a list with the values of the maximum allowable traffic for each node.
1
Introduction
In recent years there has been a growing interest in the study of complex networks, related to transportation and communication systems (WWW, Internet, power grid, etc.), see [1,2]. Many of these networks are large with a number of nodes very often in the thousands. To store the topological details of the network requires knowing the list of adjacencies and, although usually the networks are sparse, this means the use of a large amount of memory. In contrast, many invariants of the network (degree sequence, eccentricity, spectrum, betweenness, etc.) contain important information with significantly less memory use. Therefore it would be of interest to reconstruct, even partially, a network from one (or more) of these invariants. Another related problem is the construction of a new network from a list of desired values of some relevant parameter associated to its nodes. One useful case would be the generation a topology for a quasi-optimal communication network from the values of the maximum allowable traffic for each node. In [3], Ipsen and Mikhailov use simulated annealing with an elaborated cost function based on the spectral density to perform such
Research supported by the Ministerio de Educaci´ on y Ciencia, Spain, and the European Regional Development Fund under project TEC2005-03575 and by the Catalan Research Council under project 2005SGR00256.
M. Giacobini et al. (Eds.): EvoWorkshops 2008, LNCS 4974, pp. 31–37, 2008. c Springer-Verlag Berlin Heidelberg 2008
32
F. Comellas and J. Paz-S´ anchez
a reconstruction from the values of the Laplacian spectrum. Here we propose a reconstruction of a network topology from the values of its (vertex) betweenness centrality, a measure of the influence of each of its nodes in the dissemination of information over the network. The use of a simple cost function, together with the information provided implicitly by the knowledge of the betweenness centrality, drives the simulated annealing optimization method towards a good network reconstruction. The method is probabilistic, i.e. it contain a random component, and as a consequence we can not guarantee that the algorithm will find an optimal reconstruct
Data Loading...
