A network reduction method inducing scale-free degree distribution

Nicolas Martin (1) , Paolo Frasca (1) , Carlos Canudas de Wit (1)

1 NECS - Networked Controlled Systems

This paper deals with the problem of graph reduction towards a scale-free graph while preserving a consistency with the initial graph. This problem is formulated as a minimization problem and to this end we define a metric to measure the scale-freeness of a graph and another metric to measure the similarity between two graphs with different dimensions, based on spectral centrality. We also want to ensure that if the initial network is a flow network, the reduced network preserves this property. We explore the optimization problem and, based on the gained insights, we derive an algorithm allowing to find an approximate solution. Finally, the effectiveness of the algorithm is shown through a simulation on a Manhattan-like network.

Domaines: Algorithme et structure de données [cs.DS]; Réseaux sociaux et d'information [cs.SI]; Réseaux et télécommunications [cs.NI]

Nicolas Martin, Paolo Frasca, Carlos Canudas de Wit. A network reduction method inducing scale-free degree distribution. ECC 2018 - 16th European Control Conference, Jun 2018, Limassol, Cyprus. pp.2236-2241. ⟨hal-01632482v3⟩