Fast Approximation of Centrality

Details Fast Approximation of Centrality Fast Approximation of Centrality

2000-09-13

arxiv.org/abs/cs/0009005v1

J. Graph Algorithms & Applications 8(1):27-38, 2004

Computer Science

Data Structures and Algorithms

2 pages. To appear in 12th ACM/SIAM Symp. Discrete Algorithms (SODA 2001)

Scientific paper

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+epsilon) factor in near-linear time.

Affiliated with

Also associated with

No associations

Rating

Fast Approximation of Centrality does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fast Approximation of Centrality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast Approximation of Centrality will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-630438