Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
Motif-driven Dense Subgraph Discovery in Directed and Labeled Networks
复制标题
DOI：
10.1145/3442381.3450055
复制
发表时间：
2021-03
期刊：
影响因子：
--
通讯作者：
Ahmet Erdem Sarıyüce
中科院分区：
文献类型：
--
作者：
Ahmet Erdem Sarıyüce
网络中的密集区域是有趣和不寻常信息的指示器。然而，大多数现有的方法只考虑简单的，无向的，未加权的网络。然而，现实世界中的复杂网络通常具有丰富的信息：边是不对称的，节点/边具有分类和数值属性。根据这些丰富的信息在这样的网络中寻找稠密子图是一个具有许多应用的重要问题。此外，大多数现有算法忽略了高阶关系（即，在节点之间。模体被证明是有帮助的密集子图发现，但它们在异构网络中的广泛频谱使得它具有挑战性，有效地利用它们。在这项工作中，我们提出了夸克分解框架来定位密集的子图，丰富的一个给定的模体。我们专注于网络的有向边缘和分类属性的节点/边缘。对于一个给定的主题，我们的框架建立子图，称为夸克，在不同的质量和层次关系。我们的框架是通用的，高效的，可扩展的。我们讨论了我们的框架的局限性和实际的实例，以及在有向网络中需要考虑的角色混淆问题。我们给出了一个广泛的评估我们的框架，有向，有符号的，和节点标记的网络。我们考虑各种图案和评估夸克分解使用几个现实世界的网络。结果表明，夸克分解的性能优于国家的最先进的技术。我们的框架也是实用的和可扩展的网络与高达101 M的边缘。
Dense regions in networks are an indicator of interesting and unusual information. However, most existing methods only consider simple, undirected, unweighted networks. Complex networks in the real-world often have rich information though: edges are asymmetrical and nodes/edges have categorical and numerical attributes. Finding dense subgraphs in such networks in accordance with this rich information is an important problem with many applications. Furthermore, most existing algorithms ignore the higher-order relationships (i.e., motifs) among the nodes. Motifs are shown to be helpful for dense subgraph discovery but their wide spectrum in heterogeneous networks makes it challenging to utilize them effectively. In this work, we propose quark decomposition framework to locate dense subgraphs that are rich with a given motif. We focus on networks with directed edges and categorical attributes on nodes/edges. For a given motif, our framework builds subgraphs, called quarks, in varying quality and with hierarchical relations. Our framework is versatile, efficient, and extendible. We discuss the limitations and practical instantiations of our framework as well as the role confusion problem that needs to be considered in directed networks. We give an extensive evaluation of our framework in directed, signed-directed, and node-labeled networks. We consider various motifs and evaluate the quark decomposition using several real-world networks. Results show that quark decomposition performs better than the state-of-the-art techniques. Our framework is also practical and scalable to networks with up to 101M edges.