基于社区分析的网络分割

NETWORK PARTITION ON COMMUNITY ANALYSIS BASIS

在并行计算中,网络分割的质量会极大地影响并行计算的效率,然而在网络分割时并没有一个统一的质量评价指标,因此网络分割评价指标的定义以及最佳网络分割方法的构造,成为大规模网络中并行计算的一个核心问题。根据对影响并行计算效率的各种因素的分析,给出了一个网络分割评价指数的定义,并利用并行最短路径的计算验证了该评价指数的定义的正确性;并且基于社区分析,给出了一个全新的网络分割方法,理论分析表明:该网络分割方法是最优的。

In parallel computing the quality of network partition may greatly affect the efficiency of parallel computing, yet there is no unanimous evaluation index defined for the quality of network partition, therefore the definition of partition evaluation index and the construction of the best partition algorithm are the core issues of parallel computing in large-scale network. This paper,based upon the analysis of the factors that affect the efficiency of parallel computing, gives a definition to network partition evaluation index, and the validity of the definition of the index was verified by parallel shortest path computing. Based upon community anaysis a brand new partition algorithm was constructed. Theoretical proof shows that this network partition algorithm is the best.