Magnetic Laplacian for Directed Networks

点击翻译按钮获取中文摘要

Numerous complex systems in nature and society can be modelled as networks where interacting agents are connected by edges. Examples include protein-protein interaction networks in biology, food-webs in ecology, and friendship networks in social sciences. Network science is a rapidly growing field that studies the network representations of these complex systems. Many of those networks are directed, and the edge directions encode essential information of the roles of the nodes. For example, in food-webs, edges direct from preys to predators; the input-output network in economics describes the chain of supply and purchase between industrial sectors. However, most traditional network algorithms do not consider edge directions. The main objective of this project is to understand and visualize the structure of large-scale complex directed networks. A key question is how to assign physical positions to the nodes, in two dimensions or higher, in order to give insights about the underlying connectivity patterns. In particular, this could help unveil any hierarchical structure. We will tackle this problem with a novel spectral clustering method using the Magnetic Laplacian, which extends traditional methods by incorporating directional information. An important first step is to investigate the properties of the Magnetic Laplacian and understand its connection with random graph models. We will also investigate the choice of parameters and aim to develop an algorithm that automatically adapts these to the given network. Algorithmic developments will be tested and refined via computational experiments on artificial networks and also on real, public domain, data arising from online social interaction and from supermarket transactions.