A Stochastic Approach to Finding Densest Temporal Subgraphs in Dynamic Graphs
A Stochastic Approach to Finding Densest Temporal Subgraphs in Dynamic Graphs
复制标题
寻找动态图中最密集时间子图的随机方法
DOI：
10.1109/tkde.2020.3025463
复制
发表时间：
2020
影响因子：
8.9
通讯作者：
Wu, Yinghui
中科院分区：
文献类型：
--
作者：
Liu, Xuanming;Ge, Tingjian;Wu, Yinghui
在大型动态图中寻找稠密持久子图是一个重要的研究不足的问题，它考虑了子图模式的持续时间。我们提出了一个框架，称为期望最大化与效用函数（EMU），一种新的随机方法，nontrivially扩展了传统的EM方法。EMU具有优化任何用户定义的实用程序功能的灵活性。我们验证我们的EMU方法，它收敛到最优证明，它是一个规范的一般Minorization-Maximization（MM）框架的收敛保证。我们设计EMU算法的持久的子图问题，以及通过改变效用函数的几个变种。使用真实世界的数据，我们评估我们的技术的有效性和效率，并将它们与两个先前的方法进行比较稠密子图检测。
One important problem that is insufficiently studied is finding densestlasting-subgraphs in large dynamic graphs, which considers the time duration of the subgraph pattern. We propose a framework called Expectation-Maximization with Utility functions (EMU), a novel stochastic approach that nontrivially extends the conventional EM approach. EMU has the flexibility of optimizing any user-defined utility functions. We validate our EMU approach by showing that it converges to the optimum—by proving that it is a specification of the general Minorization-Maximization (MM) framework with convergence guarantees. We devise EMU algorithms for the densest lasting subgraph problem, as well as several variants by varying the utility function. Using real-world data, we evaluate the effectiveness and efficiency of our techniques, and compare them with two prior approaches on dense subgraph detection.