Eppstein, David; Wang, Joseph Fast approximation of centrality. (English) Zbl 1090.68117 J. Graph Algorithms Appl. 8, No. 1, 39-45 (2004). Summary: Social scientists use graphs to model group activities in social networks. An important property in this context is the centrality of a vertex: the inverse of the average distance to each other vertex. We describe a randomized approximation algorithm for centrality in weighted graphs. For graphs exhibiting the small world phenomenon, our method estimates the centrality of all vertices with high probability within a \((1+\varepsilon)\) factor in \(\widetilde O(m)\) time. Cited in 12 Documents MSC: 68W25 Approximation algorithms 68W20 Randomized algorithms 05C80 Random graphs (graph-theoretic aspects) 05C85 Graph algorithms (graph-theoretic aspects) 68R10 Graph theory (including graph drawing) in computer science 91D30 Social networks; opinion dynamics PDFBibTeX XMLCite \textit{D. Eppstein} and \textit{J. Wang}, J. Graph Algorithms Appl. 8, No. 1, 39--45 (2004; Zbl 1090.68117) Full Text: DOI EuDML