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.