In Mobile Ad Hoc Networks (MANET), network partitioning can cause sudden and severe disruptions to ongoing data accesses, and consequently data availability is decreased. A new distributed clustering algorithm is presented in this paper for dynamically organizing mobile nodes into clusters in which the probability of path availability can be bounded. Based on this clustering algorithm, a data replication algorithm is proposed to improve data availability. Theoretic analysis indicates that the algorithm has a proper complexity. Simulation results show that the clusters created by the clustering algorithm have desirable properties and the data availability is improved effectively by the clustering-based data replication algorithm.