Local measures for probabilistic networks

Modeling and analysis of imperfection in network data is essential in many applications such as protein–protein interaction networks, ad-hoc networks and social influence networks. In the study of imperfect network data, three issues have to be considered: first the type of imperfection, second the aspects of networks such as existence of nodes/edges or attributes of nodes/edges in which imperfection occurs and third the theory that has been used to represent imperfection. This thesis, first, reviews the different types of imperfection and consolidates the meaning of the terms used in literature. Second, it discusses network aspects and theories through which imperfect network data is represented and analyzed. Amongst all, the most applied model is uncertainty about existence of edges which is represented using probability theory, called probabilistic networks. Third, this thesis surveys queries and algorithms which have been applied over probabilistic networks. Fourth and the main focus of this dissertation is to look deeply at nodes' local properties in probabilistic networks. In our first contribution we have shown that two nodes with the same expected degree can have different properties. In this work we have highlighted the role of other summary information of degree distribution such as variance and skewness in addition to the expected value. In our second contribution, we have introduced two possible definitions of probabilistic ego networks and we have studied the concepts of degree, ego betweenness and ego closeness. One of the main applications of the proposed local properties could be in the sparsification process, in which a network's edges and the probability of the edges are altered, but nodes' local properties are preserved