Abstract: Much of the data in real applications can be represented as graphs where sets of vertices are joined by edges representing relationships. These are known as complex networks and much research and solutions have been proposed to such data. For some problems, nodes may even have values in networks. In the vast majority of the social network analysis solutions, the network structure is assumed to be exact and deterministically known. However, like with probabilistic databases, some applications present further complexities to information networks when the existence of some relationships is uncertain and known only with some probability, or when the values of some node attributes, or even the presence of a node is uncertain. We call these Probabilistic Complex Networks. These are gaining only few studies take the uncertainty into consideration. In this will present Probabilistic Complex Networks and the myriad still open problems they raise. We will present examples of early solutions for entity ranking, link prediction and community mining for networks with edge existential uncertainty.