复杂社会网络的介数性质近似计算方法研究

随着计算机和互联网的迅猛发展，面向互联网的社会网络挖掘和分析成为一个新的课题。从互联网挖掘的社会网络往往规模巨大，这对网络分析算法的性能提出了更高的要求 。介数值作为图的重要结构性质，广泛应用于基于图的聚类、分类算法，如何降低其计算的复杂性是急需解决的问题。目前，常用的方法是利用对最短路径长度的近似来降低低网络分析算法的复杂性，但已有的近似方法没有考虑现实大规模网络的复杂网络特性，对最短路径长度的近似方 近似计算方法，其基本思想是结合复杂网络的结构特性，利用通过网络中枢节点的路径来近似最短路径，以近似的最短路径求得介数的近似值。这为图的结构性质的近似估算算提供了一种新颖的思路。通过与传统的介数计算方法和近的分析得到了若干有益的结论，为进一步的研究工作奠定了基础。

Research on the Approximation Algorithms for the Betweenness Property Computation on Complex Social Networks

With the rapid growth of Internet 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.Betweenness centrality,as an important 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 between the pairs of nodes,but these typical approximation algorithms do not take the complex network property into account;furthermore,the distance estimation formulas can not be directly used to estimate betweenness centrality.In this paper,an efficient approximation algorithm to calculate betweenness properties is proposed.This algorithm adopts the internal structure characteristics of complex social networks,and gives existent "possible" short paths to estimate the real shortest paths between nodes.Experimental results demonstrate that our algorithm can largely reduce the computational complexity and meanwhile remains a high approximation efficiency.Some useful conclusions are obtained through the analysis of the experimental results,which lays a solid foundation for further research.