Abstract: With the rapid development of data centers,supercomputing,cloud computing and other technology areas,interconnected networks as one of the foundations of these technologies,are expanding in size.However,as the scale of the network increases,it is inevitable that servers in the network will fail.Once the interconnected network is paralyzed by failures,the normal work and life of human beings will be seriously affected.Therefore,how to minimize the negative impact of faulty units on the entire network topology is a very meaningful topic.Usually,the largest connected component in the remaining network is called the functional subsystem,which quantifies the communication capability and efficiency between processors in the faulty network.This study of quantitative reliability helps us to better understand and manage the stability of interconnected networks.Starting from a star graph-based interconnection network,this paper determines that a small component H in S_n－F satisfies |V(H)|≤4 when the set of fault nodes |F|≤5n－15,and when |F|≤6n－19,the small components H in S_n－F satisfy |V(H)|≤5.In addition,it focuses on the remaining components of a star network S_n(n≥6)when faulty vertices up to 6n－19 are removed from the network.Finally,an approximation algorithm for solving the minimum number of neighbours of small components in a faulty network is proposed,and by simulation experiments,the star network possesses good robustness and fault tolerance.These results are significant for understanding and designing highly reliable interconnection networks.

Key words: Star graph, Interconnection network, Component Reliability, Robustness