Dense and well-connected subgraph detection in dual networks
Dense and well-connected subgraph detection in dual networks
复制标题
DOI：
10.1137/1.9781611977172.41
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Tianyi Chen;F. Bonchi;David García-Soriano;Atsushi Miyauchi;Charalampos E. Tsourakakis
中科院分区：
文献类型：
--
作者：
Tianyi Chen;F. Bonchi;David García-Soriano;Atsushi Miyauchi;Charalampos E. Tsourakakis
稠密子图发现是图挖掘中的一个基本问题，有着广泛的应用。尽管从计算神经科学到社交网络分析的大量应用都将对偶图（即同一组节点上的一对图）作为输入，但密集子图发现方法专注于单个图输入，很少有显着的例外。在这项工作中，我们专注于以下问题：给定一对图$G，H$在同一组节点$V$，我们如何找到一个子集的节点$S \subseteq V$，导致一个良好连接的子图在$G$和一个稠密的子图在$H$？我们的公式推广了以前的研究对偶图\cite{Wu+15，WuZLFJZ 16，Cui 2018}，通过启用{\em控制}的连通性约束$G$。我们提出了一个新的数学公式的基础上$k$-边连接，并证明了它是可解的多项式时间。我们比较我们的方法，以国家的最先进的竞争对手，我们发现经验，范围的连接约束，使从业者获得有见地的信息，否则无法访问。最后，我们表明，我们提出的挖掘工具可用于更好地了解用户如何在Twitter上互动，以及有和没有自闭症谱系障碍（ASD）的人脑网络的连接方面。
Dense subgraph discovery is a fundamental problem in graph mining with a wide range of applications \cite{gionis2015dense}. Despite a large number of applications ranging from computational neuroscience to social network analysis, that take as input a {\em dual} graph, namely a pair of graphs on the same set of nodes, dense subgraph discovery methods focus on a single graph input with few notable exceptions \cite{semertzidis2019finding,charikar2018finding,reinthal2016finding,jethava2015finding}. In this work, we focus the following problem: given a pair of graphs $G,H$ on the same set of nodes $V$, how do we find a subset of nodes $S \subseteq V$ that induces a well-connected subgraph in $G$ and a dense subgraph in $H$? Our formulation generalizes previous research on dual graphs \cite{Wu+15,WuZLFJZ16,Cui2018}, by enabling the {\em control} of the connectivity constraint on $G$. We propose a novel mathematical formulation based on $k$-edge connectivity, and prove that it is solvable exactly in polynomial time. We compare our method to state-of-the-art competitors; we find empirically that ranging the connectivity constraint enables the practitioner to obtain insightful information that is otherwise inaccessible. Finally, we show that our proposed mining tool can be used to better understand how users interact on Twitter, and connectivity aspects of human brain networks with and without Autism Spectrum Disorder (ASD).