Unifying community detection using higher-order structures in directed networks

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

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.