UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Sampling and inference in social networks Nettasinghe, Don Buddhika Wijayantha


This thesis explores three practically important problems related to social networks and proposes solutions utilizing tools from statistical signal processing and applied mathematics. In the first problem, we consider the maximum likelihood estimation of the degree distribution of a network from a sampled network. We are interested in the variance of the estimates for two widely used degree distribution models of large scale networks: (1) exponential model (2) power-law model. We find that the variance of the estimate is approximately an order of magnitude smaller for exponential model when compared to the power-law model. The intuition behind this interesting property is conjectured to follow from the second order stochastic dominance of the probability distributions. In the second problem, we consider a social network where each node has a vector of parameters (interests) associated with it. Only the partial graph and parameters of a subset of nodes are known. Our aim is to identify the parameters associated with each node. Assuming the Homophily behaviour of the social network, we propose a Cayley-Menger Determinant based optimization approach combined with a previously proposed spectral clustering method to solve the interest identification problem. In the third problem, we study interest influencing in social networks where the aim is to find the minimum set of missing edges in order to maximize the influential power over the interests of the individuals in the network. This problem is formulated as a classic problem in structural rigidity theory using the characteristic Contagion behaviour of social networks. We propose a solution approach using the Laman's theorem which characterizes minimally rigid graphs in the two dimensional space.

Item Citations and Data


Attribution-NonCommercial-NoDerivatives 4.0 International