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.
Besides the works mentioned above, other new families of distances have recently been developed integrating information on both the proximity (shortest-path distance) and amount of connectivity between nodes (captured, e.g., by the resistance distance) @cite_41 @cite_23 @cite_49 @cite_25 @cite_62 @cite_47 @cite_20 @cite_61 @cite_8 @cite_19 . Many of these measures indeed interpolate (up to a constant scaling factor) between the shortest path distance (or length) and the resistance distance, therefore alleviating the previously mentioned lost-in-space effect.
@cite_61 @cite_62 @cite_8 @cite_41 @cite_19 @cite_49 @cite_23 @cite_47 @cite_25 @cite_20
1979104937 2951597259 2410761564 2166319632 2096633276 1614319616 2030435519 1590313574 2497633600 2065777790
Link prediction in complex networks has attracted increasing attention from both physical and computer science communities. The algorithms can be used to extract missing information, identify spurious interactions, evaluate network evolving mechanisms, and so on. This article summaries recent progress about link prediction algorithms, emphasizing on the contributions from physical perspectives and approaches, such as the random-walk-based methods and the maximum likelihood methods. We also introduce three typical applications: reconstruction of networks, evaluation of network evolving mechanism and classification of partially labeled networks. Finally, we introduce some applications and outline future challenges of link prediction algorithms. Large unweighted directed graphs are commonly used to capture relations between entities. A fundamental problem in the analysis of such networks is to properly define the similarity or dissimilarity between any two vertices. Despite the significance of this problem, statistical characterization of the proposed metrics has been limited. We introduce and develop a class of techniques for analyzing random walks on graphs using stochastic calculus. Using these techniques we generalize results on the degeneracy of hitting times and analyze a metric based on the Laplace transformed hitting time (LTHT). The metric serves as a natural, provably well-behaved alternative to the expected hitting time. We establish a general correspondence between hitting times of the Brownian motion and analogous hitting times on the graph. We show that the LTHT is consistent with respect to the underlying metric of a geometric graph, preserves clustering tendency, and remains robust against random addition of non-geometric edges. Tests on simulated and real-world data show that the LTHT matches theoretical predictions and outperforms alternatives. Appearing in Proceedings of the 19th International Conference on Artificial Intelligence and Statistics (AISTATS) 2016, Cadiz, Spain. JMLR: W&CP volume 51. A new class of distances for graph vertices is proposed. This class contains parametric families of distances which reduce to the shortest-path, weighted shortest-path, and the resistance distances at the limiting values of the family parameters. The main property of the class is that all distances it comprises are graph-geodetic: d(i,j)+d(j,k)=d(i,k) if and only if every path from i to k passes through j. The construction of the class is based on the matrix forest theorem and the transition inequality. We study the family of p-resistances on graphs for p ≥ 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p =1 the p-resistance coincides with the shortest path distance, for p = 2 it coincides with the standard resistance distance, and for p → ∞ it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase transition takes place. There exist two critical thresholds p* and p** such that if p p**, it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p* = 1 + 1 (d − 1) and p** = 1 + 1 (d − 2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p* and p** is an artifact of our proofs). We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1 p* + 1 q =1. In data analysis, there is a strong demand for graph metrics that differ from the classical shortest path and resistance distances. Recently, several new classes of graph metrics have been proposed. This paper presents some of them featuring the cutpoint additive distances. These include the path distances, the reliability distance, the walk distances, and the logarithmic forest distances among others. We discuss a number of connections between these and other distances. The walk distances in graphs are defined as the result of appropriate transformations of the @?"k"="0^ (tA)^k proximity measures, where A is the weighted adjacency matrix of a graph and t is a sufficiently small positive parameter. The walk distances are graph-geodetic; moreover, they converge to the shortest path distance and to the so-called long walk distance as the parameter t approaches its limiting values. We also show that the logarithmic forest distances which are known to generalize the resistance distance and the shortest path distance are a specific subclass of walk distances. On the other hand, the long walk distance is equal to the resistance distance in a transformed graph. We study the problem of predicting the labelling of a graph. The graph is given and a trial sequence of (vertex,label) pairs is then incrementally revealed to the learner. On each trial a vertex is queried and the learner predicts a boolean label. The true label is then returned. The learner’s goal is to minimise mistaken predictions. We propose minimum p-seminorm interpolation to solve this problem. To this end we give a p-seminorm on the space of graph labellings. Thus on every trial we predict using the labelling which minimises the p-seminorm and is also consistent with the revealed (vertex, label) pairs. When p = 2 this is the harmonic energy minimisation procedure of [22], also called (Laplacian) interpolated regularisation in [1]. In the limit as p → 1 this is equivalent to predicting with a label-consistent mincut. We give mistake bounds relative to a label-consistent mincut and a resistive cover of the graph. We say an edge is cut with respect to a labelling if the connected vertices have disagreeing labels. We find that minimising the p-seminorm with p = 1 + where → 0 as the graph diameter D → ∞ gives a bound of O(Φ logD) versus a bound of O(ΦD) when p = 2 where Φ is the number of cut edges. Network data are produced automatically by everyday interactions - social networks, power grids, and links between data sets are a few examples. Such data capture social and economic behavior in a form that can be analyzed using powerful computational tools. This book is a guide to both basic and advanced techniques and algorithms for extracting useful information from network data. The content is organized around 'tasks', grouping the algorithms needed to gather specific types of information and thus answer specific types of questions. Examples include similarity between nodes in a network, prestige or centrality of individual nodes, and dense regions or communities in a network. Algorithms are derived in detail and summarized in pseudo-code. The book is intended primarily for computer scientists, engineers, statisticians and physicists, but it is also accessible to network scientists based in the social sciences. Matlab Octave code illustrating some of the algorithms will be available at: http: www.cambridge.org 9781107125773. As a crucial operation, routing plays an important role in various communication networks. In the context of data and sensor networks, routing strategies such as shortest-path, multi-path and potential-based (“all-path”) routing have been developed. Existing results in the literature show that the shortest path and all-path routing can be obtained from @math and @math flow optimization, respectively. Based on this connection between routing and flow optimization in a network, in this paper we develop a unifying theoretical framework by considering flow optimization with mixed (weighted) @math -norms. We obtain a surprising result: as we vary the trade-off parameter @math , the routing graphs induced by the optimal flow solutions span from shortest-path to multi-path to all-path routing—this entire sequence of routing graphs is referred to as the routing continuum. We also develop an efficient iterative algorithm for computing the entire routing continuum. Several generalizations are also considered, with applications to traffic engineering, wireless sensor networks, and network robustness analysis.