In social network analysis, graphs are used to model relationships between actors or participants in a social setting. Each node or vertex in the graph represents a participant or actor. Each link or edge represents a connection or relationship between two participants. A variety of graph algorithms have been developed to analyze the structure of social networks and to assess the roles or importance of the individual players. Since the September 11 bombing of the World Trade Center, social network analysis has emerged as a potential vehicle for modeling and analyzing the structure of terrorist networks [10, 15].

There are a variety of measures to assess the “importance” or centrality of each actor in a social network [16]. The most popular of these centrality measures require the computation or enumeration of shortest paths between all pairs of nodes in the graph. Such computations can be time consuming in large graphs. Moreover, they may become problematic even in more moderately-sized networks when changing data or “what-if” scenario analysis warrant frequent recomputation.