| Many of today's applications can benefit from the discovery of the most central entities in real-world networks.;A person planning to open a store will, for instance, want to choose the location that is closest, on average, to a large number of potential customers.;Viral marketers strive to discover a small group of people who can quickly and effectively convince a large population to adopt a product.;Other applications that benefit from the discovery of highly central entities include sociopolitical science, national security and power grid management.;This dissertation presents our new technique that efficiently finds the k most central entities.;This technique shares intermediate results between centrality computations instead of independently calculating the centrality of every entity.;Since the cost of each centrality computation may vary substantially depending on the choice of the previous computation, the technique schedules centrality computations in a manner that minimizes the estimated completion time.;Our technique updates, with negligible overhead, an upper bound on the centrality of every entity.;Using this information, our technique proactively skips entities that cannot belong to the final result.;Furthermore, a parallel implementation of our technique for effectively utilizing multicore environments is presented.;Evaluation results for actual networks are also presented which demonstrate the various benefits of our technique. |
