关键词: 复杂网络 介数值 最短路径 计算复杂度 近似算法

Abstract:

With the rapid growth of Intemet users, social network mining and analyzing based on the Internet has become a hot research topic. The social networks
           mined from the Internet usually have large scales which need an efficient algorithm to calculate the statistics. Betweermess centrality, as an importan    t network statistic property, has been used in many graph cluster/classification algorithms, and how to decrease its computational complexity has become an emergent problem. The recent algorithms on network statistics calculating usually use the approximation methods to estimate the graph distance betwe  en the pairs of nodes, but these typical approximation algorithms do not take the complex network property into aceount; furthermore, the distance estim ation formulas can not be directly used to estimate betweenness cen- trality. In this paper, an efficient approximation algorithm to calculate betweenne  ss properties is proposed. This algorithm adopts the internal structure characteristics of complex social networks, and gives existent ＂possible＂ shor   rt paths to estimate the real shortest paths between nodes. Experimental results demonstrate that our algorithm can largely reduce the computational com plexity and meanwhile remains a high approximation efficiency. Some useful conclusions are obtained through the analysis of the experimental results, wh ich lays a solid foundation for further research.

Key words: complex networks, betweenness centrality, shortest paths, computational complexity, approximation algorit
         , hm