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.