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).

翻译：浓密的子图发现是图解开采中的一个基本问题, 其应用范围很广 。 尽管从计算神经科学到社会网络分析等大量应用范围很广, 从计算神经科学到社会网络分析, 这些应用包含一个 {em 双重} 图, 即同一一组节点上的一对图表, 密集的子图发现方法集中在单一的图形输入上, 鲜有例外 \ cite{semertsidis2019study, charikar2018study, charikar2018study, reinthal2016调查, Jethava2015Switter互动} 。 在这项工作中, 我们集中关注以下问题: 在计算计算神经神经神经科学到社会网络分析的一对一对一对一 美元, 如何找到连接网络的精确度限制, 从而让我们的数学工具 得到新的理解。