Betweenness centrality is an important index widely used in different domains such as social networks, traffic networks and the world wide web. However, even for mid-size networks that have only a few hundreds thousands vertices, it is computationally expensive to compute exact betweenness scores. Therefore in recent years, several approximate algorithms have been developed. In this paper, first given a network @math and a vertex @math , we propose a Metropolis-Hastings MCMC algorithm that samples from the space @math and estimates betweenness score of @math . The stationary distribution of our MCMC sampler is the optimal sampling proposed for betweenness centrality estimation. We show that our MCMC sampler provides an @math -approximation, where the number of required samples depends on the position of @math in @math and in many cases, it is a constant. Then, given a network @math and a set @math , we present a Metropolis-Hastings MCMC sampler that samples from the joint space @math and @math and estimates relative betweenness scores of the vertices in @math . We show that for any pair @math , the ratio of the expected values of the estimated relative betweenness scores of @math and @math respect to each other is equal to the ratio of their betweenness scores. We also show that our joint-space MCMC sampler provides an @math -approximation of the relative betweenness score of @math respect to @math , where the number of required samples depends on the position of @math in @math and in many cases, it is a constant.
Riondato and Kornaropoulos @cite_26 presented shortest path samplers for estimating betweenness centrality of all vertices or the @math vertices that have the highest betweenness scores in a graph. They determined the number of samples needed to approximate the betweenness with the desired accuracy and confidence by means of the VC-dimension theory @cite_23 . Recently, Riondato and Upfal @cite_26 introduced algorithms for estimating betweenness scores of all vertices in a graph. They also discussed a variant of the algorithm that finds the top- @math vertices. They used Rademacher average @cite_16 to determine the number of required samples. Finally, Borassi and Natale @cite_2 presented the KADABRA algorithm, which uses balanced bidirectional BFS (bb-BFS) to sample shortest paths. In bb-BFS, a BFS is performed from each of the two endpoints @math and @math , in such a way that they are likely to explore about the same number of edges.
@cite_26 @cite_2 @cite_23 @cite_16
1029409534 2344526012 2029538739 607505555
Betweenness centrality is a fundamental measure in social network analysis, expressing the importance or influence of individual vertices (or edges) in a network in terms of the fraction of shortest paths that pass through them. Since exact computation in large networks is prohibitively expensive, we present two efficient randomized algorithms for betweenness estimation. The algorithms are based on random sampling of shortest paths and offer probabilistic guarantees on the quality of the approximation. The first algorithm estimates the betweenness of all vertices (or edges): all approximate values are within an additive factor @math ??(0,1) from the real values, with probability at least @math 1-?. The second algorithm focuses on the top-K vertices (or edges) with highest betweenness and estimate their betweenness value to within a multiplicative factor @math ?, with probability at least @math 1-?. This is the first algorithm that can compute such approximation for the top-K vertices (or edges). By proving upper and lower bounds to the VC-dimension of a range set associated with the problem at hand, we can bound the sample size needed to achieve the desired approximations. We obtain sample sizes that are independent from the number of vertices in the network and only depend on a characteristic quantity that we call the vertex-diameter, that is the maximum number of vertices in a shortest path. In some cases, the sample size is completely independent from any quantitative property of the graph. An extensive experimental evaluation on real and artificial networks shows that our algorithms are significantly faster and much more scalable as the number of vertices grows than other algorithms with similar approximation guarantees. We present KADABRA, a new algorithm to approximate betweenness centrality in directed and undirected graphs, which significantly outperforms all previous approaches on real-world complex networks. The efficiency of the new algorithm relies on two new theoretical contributions, of independent interest. The first contribution focuses on sampling shortest paths, a subroutine used by most algorithms that approximate betweenness centrality. We show that, on realistic random graph models, we can perform this task in time @math with high probability, obtaining a significant speedup with respect to the @math worst-case performance. We experimentally show that this new technique achieves similar speedups on real-world complex networks, as well. The second contribution is a new rigorous application of the adaptive sampling technique. This approach decreases the total number of shortest paths that need to be sampled to compute all betweenness centralities with a given absolute error, and it also handles more general problems, such as computing the @math most central nodes. Furthermore, our analysis is general, and it might be extended to other settings. This chapter reproduces the English translation by B. Seckler of the paper by Vapnik and Chervonenkis in which they gave proofs for the innovative results they had obtained in a draft form in July 1966 and announced in 1968 in their note in Soviet Mathematics Doklady. The paper was first published in Russian as Вапник В. Н. and Червоненкис А. Я. О равномерноЙ сходимости частот появления событиЙ к их вероятностям. Теория вероятностеЙ и ее применения 16(2), 264–279 (1971). Machine learning is one of the fastest growing areas of computer science, with far-reaching applications. The aim of this textbook is to introduce machine learning, and the algorithmic paradigms it offers, in a principled way. The book provides an extensive theoretical account of the fundamental ideas underlying machine learning and the mathematical derivations that transform these principles into practical algorithms. Following a presentation of the basics of the field, the book covers a wide array of central topics that have not been addressed by previous textbooks. These include a discussion of the computational complexity of learning and the concepts of convexity and stability; important algorithmic paradigms including stochastic gradient descent, neural networks, and structured output learning; and emerging theoretical concepts such as the PAC-Bayes approach and compression-based bounds. Designed for an advanced undergraduate or beginning graduate course, the text makes the fundamentals and algorithms of machine learning accessible to students and non-expert readers in statistics, computer science, mathematics, and engineering.