×

Fast approximation of centrality. (English) Zbl 1090.68117

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.

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
Full Text: DOI EuDML