Inverse All Shortest Path Problem

Although resource management schemes and algorithms for networks are well established, we present two novel ideas, based on graph theory, that solve inverse all shortest path problem. Given a symmetric and non-negative demand matrix, the inverse all shortest path problem (IASPP) asks to find a weighted adjacency matrix of a graph such that...

Influence of assortativity and degree-preserving rewiring on the spectra of networks

Newman’s measure for (dis)assortativity, the linear degree correlation coefficient ?D, is reformulated in terms of the total number Nk of walks in the graph with k hops. This reformulation allows us to derive a new formula from which a degree-preserving rewiring algorithm is deduced, that, in each rewiring step, either increases or decreases ?D...

Influence of assortativity and degree-preserving rewiring on the spectra of networks

Weight of the Shortest Path to the First Encountered Peer in a Peer Group of Size m

We model the weight (e.g. delay, distance or cost) from an arbitrary node to the nearest (in weight) peer in a peer-to-peer (P2P) network. The exact probability generating function and an asymptotic analysis is presented for a random graph with i.i.d. exponential link weights. The asymptotic distribution function is a Fermi-Dirac distribution...