The recently developed bag-of-paths framework consists in setting a Gibbs-Boltzmann distribution on all feasible paths of a graph. This probability distribution favors short paths over long ones, with a free parameter (the temperature @math ) controlling the entropic level of the distribution. This formalism enables the computation of new distances or dissimilarities, interpolating between the shortest-path and the resistance distance, which have been shown to perform well in clustering and classification tasks. In this work, the bag-of-paths formalism is extended by adding two independent equality constraints fixing starting and ending nodes distributions of paths. When the temperature is low, this formalism is shown to be equivalent to a relaxation of the optimal transport problem on a network where paths carry a flow between two discrete distributions on nodes. The randomization is achieved by considering free energy minimization instead of traditional cost minimization. Algorithms computing the optimal free energy solution are developed for two types of paths: hitting (or absorbing) paths and non-hitting, regular paths, and require the inversion of an @math matrix with @math being the number of nodes. Interestingly, for regular paths, the resulting optimal policy interpolates between the deterministic optimal transport policy ( @math ) and the solution to the corresponding electrical circuit ( @math ). Two distance measures between nodes and a dissimilarity between groups of nodes, both integrating weights on nodes, are derived from this framework.
The main motivation for using such models can be understood as follows @cite_0 . Most of the traditional network measures are essentially based on two different paradigms about movement or communication occurring in the network: optimal communication based on shortest paths, and random communication based on a random walk on the graph. For instance, shortest path distance, as well as the standard betweenness centrality @cite_37 are defined from shortest paths, while resistance distance and random walk centrality @cite_36 @cite_6 are based on random walks (which have a strong analogy with electrical flow on the network @cite_75 ).
@cite_37 @cite_36 @cite_6 @cite_0 @cite_75
1971937094 2096646197 2154897810 2963414985 2167064216
A family of new measures of point and graph centrality based on early intuitions of Bavelas (1948) is introduced. These measures define centrality in terms of the degree to which a point falls on the shortest path between others and there fore has a potential for control of communication. They may be used to index centrality in any large or small network of symmetrical relations, whether connected or unconnected. We consider variations of two well-known centrality measures, betweenness and closeness, with a different model of information spread. Rather than along shortest paths only, it is assumed that information spreads efficiently like an electrical current. We prove that the current-flow variant of closeness centrality is identical with another known measure, information centrality, and give improved algorithms for computing both measures exactly. Since running times and space requirements are prohibitive for large networks, we also present a randomized approximation scheme for current-flow betweenness. Betweenness is a measure of the centrality of a node in a network, and is normally calculated as the fraction of shortest paths between node pairs that pass through the node of interest. Betweenness is, in some sense, a measure of the influence a node has over the spread of information through the network. By counting only shortest paths, however, the conventional definition implicitly assumes that information spreads only along those shortest paths. Here, we propose a betweenness measure that relaxes this assumption, including contributions from essentially all paths between nodes, not just the shortest, although it still gives more weight to short paths. The measure is based on random walks, counting how often a node is traversed by a random walk between two other nodes. We show how our measure can be calculated using matrix methods, and give some examples of its application to particular networks. Abstract This work compares several node (and network) criticality measures quantifying to which extend each node is critical with respect to the communication flow between nodes of the network, and introduces a new measure based on the Bag-of-Paths (BoP) framework. Network disconnection simulation experiments show that the new BoP measure outperforms all the other tested measures on a sample of Erdős-Renyi and Albert-Barabasi graphs. Furthermore, a faster (but still O ( n 3 )), approximate, BoP criticality relying on the Sherman–Morrison rank-one update of a matrix is introduced for tackling larger networks. This approximate measure shows similar performances as the original, exact, one. Probability theory, like much of mathematics, is indebted to physics as a source of problems and intuition for solving these problems. Unfortunately, the level of abstraction of current mathematics often makes it difficult for anyone but an expert to appreciate this fact. In this work we will look at the interplay of physics and mathematics in terms of an example where the mathematics involved is at the college level. The example is the relation between elementary electric network theory and random walks. Central to the work will be Polya’s beautiful theorem that a random walker on an infinite street network in d-dimensional space is bound to return to the starting point when d = 2, but has a positive probability of escaping to infinity without returning to the starting point when d ≥ 3. Our goal will be to interpret this theorem as a statement about electric networks, and then to prove the theorem using techniques from classical electrical theory. The techniques referred to go back to Lord Rayleigh, who introduced them in connection with an investigation of musical instruments. The analog of Polya’s theorem in this connection is that wind instruments are possible in our three-dimensional world, but are not possible in Flatland (Abbott [1]). The connection between random walks and electric networks has been recognized for some time (see Kakutani [12], Kemeny, Snell, and