Abstract: Super-peer P2P network takes advantage of the heterogeneity of capabilities across peers to solve the problem of bandwidth barrier. However, its constructing protocols are inefficient and its topology is fragile. An efficient and robust super-peer P2P network ERSN is presented. The ERSN utilizes peer sampling protocol based on random walks to estimate the network requirements for constructing an efficient super-peer network and establishes emergence links between leaf peers to get a robust network. Experimental results show that compared with Gnutella 0.6 network, the number of peers which process the locating request reduces by 76% at most and the hit rate for locating file increases by 36.4% at most with many super-peers and leaf peers leaving network simultaneously.