From random walks to distances on unweighted graphs
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.
Abstract: Large unweighted directed graphs are commonly used to capture relations be- tween 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 met- rics has been limited.What particular problem do the authors have in mind? The same argument is true for weighted, undirected graphs but they seem to be excluded. If one would know what problem the authors are talking about this would become clear. In the paper I could not find any connection to some 'real world' problem but only a mathematical consideration of the problem.How about betweenness centrality, as used to identify bottleneck genes in gene networks. http://journals.plos.org/ploscompbiol/article?id=10.1371/journal.pcbi.0030059 Is that a problem the author has in mind? Can one compare both methods? Compare with any other method?Without a clear connection to a real world problem I consider the paper out of scope for NIPS. However, I think the paper could make a nice contribution for a mathematics conference/journal.The paper concludes without a summary/discussion.