A figure from the presentation.
Citation:
Pfeffer, Jürgen & Carley, Kathleen M. (2012). Using k-centralities to approximate centrality measures in large networks. Paper presented at the XXXII International Sunbelt Social Network Conference, Redondo Beach, CA, March 12-18, 2012.
Abstract:
Some of the most popular centrality measures (e.g., betweenness centrality, closeness centrality) are based on the calculation of shortest paths. This characteristic limits the applicability of these measures for large networks with millions of actors. Another limitation for centrality calculations comes to the force in dynamic networks. For instance, if we have to recalculate our measure every minute to monitor transformations in changing networks, the measure must not delay the analysis process. In this paper we use the idea of bounded-distance shortest paths calculations (Borgatti and Everett, 2006) to create a framework of a k-measure approach for closeness and betweenness based centralities. We claim criteria fork-centralities and discuss aspects of normalization and implementation. We present the results of performance and validity studies using random, stylized, and real-world networks. We show that k-centrality measures are good approximations for the corresponding centrality measures by achieving a tremendous gain of calculation time. Even more, the calculation complexity of k-centralities is almost linear. This allows researchers to calculate centrality measures based on shortest paths for networks with millions of nodes or with high frequency in dynamically changing networks. Finally, we discuss drawbacks of using k-centrality measures as approximation for the corresponding centrality measures and approaches to identify possible divergent results.
Figure:
A figure from the presentation.