Unifying community detection using higher-order structures in directed networks

在有向网络中使用高阶结构统一社区检测

• 批准号: 2598017
• 金额: --
• 依托单位: University of Strathclyde
• 依托单位国家: 英国
• 项目类别: Studentship
• 财政年份: 2021
• 资助国家: 英国
• 起止时间: 2021 至 无数据
• 项目状态: 未结题
• 来源: https://gtr.ukri.org/projects?ref=studentship-2598017
• 关键词: Unifying; community; detection; using; higher

Community detection is an essential tool in the analysis of complex networks for grouping together similar nodes. This has proven useful in applications as diverse as understanding cell functions; finding groups of genes related to colon cancer in gene co-occurrences networks; uncovering groups of users spreading terrorist propaganda on Twitter; and understanding connections between politicians. In the case of undirected networks, a simple and widely accepted definition of a community or a partition is that nodes within a community are densely connected but only loosely connected to the nodes outside. Finding such communities/partitions has been an area of abundant research, and an increasing number of algorithms to uncover community structures have been proposed. Each makes its own interpretation of the meaning of "densely'" and/or "loosely" connected, and the best way to reveal such a structure.Detection of partitions/communities when the network is directed is a much more sparsely populated field, with no such consensus about what a community should look like. In part this is because the very nature of a community is strongly application dependent. There are situations where nodes can be expected to belong to the same community but may not be connected at all. The potential of effective community detection in directed networks is great and already it has been used to highlight a lack of racial mixture within relationships of some high school students; derive recommender systems on websites; and to explore the pattern of knowledge transfer between technology fields.A framework has been proposed based on higher-order representations of networks in terms of graphlets, and they offer an attractive route to community detection. In larger part this is because these higher-order representations of networks produce undirected graphs, called Motif Adjacency Matrices (MAM). With a judicious choice of graphlets, the MAM should exhibit community structures that fit the classic definition stated for undirected networks. One can aim to employ the community detection methods designed for such a situation. These MAMs have proven meaningful in applications such as food webs, to accurately uncover the ecological classes; in transcriptional regulation networks to uncover functionalities of groups of operons; in transportation networks to highlight hub airports in North America; and in neuronal networks, to explain the control of nictation. However efficient algorithms to build these MAM and exploit them, as well as effective validation tools, are still thin on the ground.Purpose of this project is to investigate more deeply how one can exploit graphlets to produce higher-order representations of networks, with a focus on unifying the application dependent problem of community detection within directed networks.1. Building higher-order representations. Some efficient methods have been proposed for 3-node graphlets, and certain kinds of 4-node graphlets. These graphlets do not cover the range of communities of interest. Project aims to extend existing work to build MAMs for other graphlets by adapting existing methods and/or proposing new ones, and providing efficient implementations to be made publicly available. Since some key graphlets may occur with very high frequency in a network, MAMs have the potential to be dense, which is a barrier to developing methods to deal with large-scale networks. We propose to develop methods that can work with only partially filled MAMs.2. Automating graphlet choice. The choice of the right graphlet to use to get a MAM which is consistent with a particular application can be far from straightforward. The possibility of automating this choice will be investigated, for instance by using sweep profile-like procedures or by applying consensus algorithms on multiple MAMs.3. Determining effective community detection algorithms/definitions.

社区检测是分析复杂网络中相似节点的重要工具。事实证明，这在理解细胞功能、在基因共现网络中发现与结肠癌相关的基因组、发现在Twitter上传播恐怖主义宣传的用户群以及理解政治家之间的联系等各种应用中都很有用。在无向网络的情况下，社区或分区的一个简单且广泛接受的定义是社区内的节点密集连接，但仅松散连接到外部节点。发现这样的社区/分区已经是一个丰富的研究领域，并且已经提出了越来越多的算法来发现社区结构。每一个都对“密集”和/或“松散”连接的含义做出了自己的解释，以及揭示这种结构的最佳方式。当网络是定向的时，分区/社区的检测是一个更稀疏的领域，对于社区应该是什么样子没有这样的共识。部分原因是社区的本质是强烈依赖于应用程序的。在某些情况下，可以预期节点属于同一社区，但可能根本没有连接。在有向网络中有效的社区检测的潜力是巨大的，它已经被用来突出一些高中学生的关系中缺乏种族混合;在网站上导出推荐系统;并探索技术领域之间的知识转移模式。提出了一个基于网络的高阶表示的框架，它们提供了一个吸引人的社区检测途径。在很大程度上，这是因为网络的这些高阶表示产生了无向图，称为Motif邻接矩阵（MAM）。通过明智地选择小图，MAM应该展示出符合无向网络经典定义的社区结构。可以旨在采用针对这种情况设计的社区检测方法。这些MAMs已被证明是有意义的应用程序，如食物网，以准确地揭示生态类;在转录调控网络，以揭示功能组的操纵子;在交通网络，以突出枢纽机场在北美;和在神经元网络，以解释控制眨眼。然而，有效的算法来构建这些MAM和利用它们，以及有效的验证工具，仍然很薄。这个项目的目的是更深入地研究如何利用graphlets来产生网络的高阶表示，重点是统一有向网络中社区检测的应用相关问题。构建更高阶的表示。已经提出了一些有效的方法，3节点的graphlets，和某些类型的4节点graphlets。这些graphlets并不涵盖感兴趣的社区的范围。该项目旨在扩展现有的工作，通过调整现有的方法和/或提出新的方法，为其他graphlet构建MAM，并提供公开可用的高效实现。由于一些关键的小图可能在网络中以非常高的频率出现，因此MAM有可能是密集的，这是开发处理大规模网络的方法的障碍。我们建议开发的方法，可以与只有部分填充MAMs。自动化Graphlet选择。选择正确的graphlet来获得与特定应用程序一致的MAM可能远非简单。自动化这种选择的可能性将被调查，例如通过使用扫描配置文件一样的程序或通过在多个MAMs上应用共识算法。确定有效的社区检测算法/定义。