Hidden features and information diffusion in large social networks

In social networks, connections are made based on a degree of communality between the users. Typically, links are more likely if users share common features or belong to the same community. Network formation can be modelled by assuming the nodes to be embedded in a feature space, and links to be formed through a stochastic process which depends on the distance between the nodes in the underlying space. The aim of the proposed research is to develop models and algorithms that will allow for the extraction of the latent feature space from the link structure of large networks. I will use theoretical tools to study the relationship between spatial features of the nodes and the link structure, using the infinite limit to understand the behaviour as the network gets large. I will also further develop and analyze a spatial model for growing networks, built on the principle of preferential attachment, which leads to graphs that exhibit commonly observed features such as a power law degree distribution, high clustering, and the presence of long links that lead to the small world property.

The first objective of this research is to develop methods to test whether a given graph is likely the result of a spatially informed link formation process, and what are the characteristics of the underlying space. Once an appropriate spatial model for a given class of networks has been established, the developed theory will lead to improved methods for common link mining tasks, such as community extraction and quantification of node similarity. This can have important applications in the analysis of on-line social networks towards targeted marketing, or identification of fraudulent or criminal elements. These methods may also be of use in the analysis of biological networks, such as protein interaction networks or food webs.

A second aim of the proposed work is to study the effect of the network and its underlying spatial structure on the diffusion of information and the evolution of behavioural strategies. Of particular interest are models based on game theory. On a network, nodes adopt a game strategy, and play a strategic game with their neighbours. Each node receives a pay-off that depends on the strategy of its neighbours. Nodes then are given a chance to change their strategy to that of a neighbour with a higher pay-off. This leads to a spread of successful strategies through the network. My interest is in studying how the network structure affects such dynamic processes. Moreover, using spatial network models, I will focus on the question to what extend the underlying space informs these processes.

In short, the goal of the proposed research is to study stochastic spatial models to gain a nuanced understanding of the hidden deep information that is expressed by the link structure of a large complex network, and of the dynamic processes that propagate along its links.