Fast approximation of centrality Export

@inproceedings{citeulike:2837010, abstract = {Social studies researchers 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 + \∈) factor in near-linear time.}, address = {Philadelphia, PA, USA}, author = {Eppstein, David and Wang, Joseph}, booktitle = {SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms}, citeulike-article-id = {2837010}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=365449}, isbn = {0-89871-490-7}, keywords = {algorithm, approximate, approximation-algorithm, betweenness, centrality, yrbcn}, location = {Washington, D.C., United States}, pages = {228--229}, posted-at = {2008-05-27 10:54:17}, priority = {2}, publisher = {Society for Industrial and Applied Mathematics}, title = {Fast approximation of centrality}, url = {http://portal.acm.org/citation.cfm?id=365449}, year = {2001} }

TY - CONF ID - citeulike:2837010 L3 - citeulike-article-id:2837010 N2 - Social studies researchers 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 + ∈) factor in near-linear time. CY - Washington, D.C., United States SN - 0-89871-490-7 AD - Philadelphia, PA, USA EP - 229 TI - Fast approximation of centrality PB - Society for Industrial and Applied Mathematics T2 - SODA '01: Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms SP - 228 KW - algorithm KW - approximate KW - approximation-algorithm KW - betweenness KW - centrality KW - yrbcn AU - Eppstein, David AU - Wang, Joseph PY - 2001/// UR - http://portal.acm.org/citation.cfm?id=365449 ER -