Network vulnerability analysis is one of the irreplaceable foundations of network security. Host- centric methods of vulnerability analysis can generate an attack graph in polynomial time, whereas the inherent link uncertainty has not been of a concern. An uncertain-graph based method for network vulnerability analysis is proposed in this paper, which uses link uncertainties to describe link states accurately. In this way, finding an optimal exploit chain becomes feasible. An algorithm for generating an uncertain attack graph (UAG) is proposed, whose running time is O(n⁴). Next, a heuristic algorithm to that can generate the optimal exploit chain, on the basis of UAG, is proposed, which runs in O(n³) time. Experimental results show that this method can generate UAG in an acceptable amount time and find a vulnerability exploit chain with a maximum attack benefit.