• KSII Transactions on Internet and Information Systems
    Monthly Online Journal (eISSN: 1976-7277)

An Estimated Closeness Centrality Ranking Algorithm and Its Performance Analysis in Large-Scale Workflow-supported Social Networks


Abstract

This paper implements an estimated ranking algorithm of closeness centrality measures in large-scale workflow-supported social networks. The traditional ranking algorithms for large-scale networks have suffered from the time complexity problem. The larger the network size is, the bigger dramatically the computation time becomes. To solve the problem on calculating ranks of closeness centrality measures in a large-scale workflow-supported social network, this paper takes an estimation-driven ranking approach, in which the ranking algorithm calculates the estimated closeness centrality measures by applying the approximation method, and then pick out a candidate set of top k actors based on their ranks of the estimated closeness centrality measures. Ultimately, the exact ranking result of the candidate set is obtained by the pure closeness centrality algorithm [1] computing the exact closeness centrality measures. The ranking algorithm of the estimation-driven ranking approach especially developed for workflow-supported social networks is named as RankCCWSSN (Rank Closeness Centrality Workflow-supported Social Network) algorithm. Based upon the algorithm, we conduct the performance evaluations, and compare the outcomes with the results from the pure algorithm. Additionally we extend the algorithm so as to be applied into weighted workflow-supported social networks that are represented by weighted matrices. After all, we confirmed that the time efficiency of the estimation-driven approach with our ranking algorithm is much higher (about 50% improvement) than the traditional approach.


Statistics

Show / Hide Statistics

Statistics (Cumulative Counts from December 1st, 2015)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article

[IEEE Style]
Jawon Kim, Hyun Ahn, Minjae Park, Sangguen Kim and Kwanghoon Pio Kim, "An Estimated Closeness Centrality Ranking Algorithm and Its Performance Analysis in Large-Scale Workflow-supported Social Networks," KSII Transactions on Internet and Information Systems, vol. 10, no. 3, pp. 1454-1466, 2016. DOI: 10.3837/tiis.2016.03.031

[ACM Style]
Kim, J., Ahn, H., Park, M., Kim, S., and Kim, K. P. 2016. An Estimated Closeness Centrality Ranking Algorithm and Its Performance Analysis in Large-Scale Workflow-supported Social Networks. KSII Transactions on Internet and Information Systems, 10, 3, (2016), 1454-1466. DOI: 10.3837/tiis.2016.03.031