Finding Densest Lasting Subgraphs in Dynamic Graphs: A Stochastic Approach
Finding Densest Lasting Subgraphs in Dynamic Graphs: A Stochastic Approach
复制标题
DOI：
10.1109/icde.2019.00075
复制
发表时间：
2019-04
期刊：
影响因子：
--
通讯作者：
Xuanming Liu;Tingjian Ge;Yinghui Wu
中科院分区：
文献类型：
--
作者：
Xuanming Liu;Tingjian Ge;Yinghui Wu
在大型动态图中寻找离散持续子图是一个重要的研究不足的问题，它考虑了子图模式的持续时间。我们提出了一个框架，称为期望最大化与效用函数（EMU），一种新的随机方法，nontrivially扩展了传统的EM方法。EMU具有优化任何用户定义的实用程序功能的灵活性。我们验证我们的EMU方法，它收敛到最优证明，它是一个规范的一般Minorization-Maximization（MM）框架的收敛保证。然后，我们设计EMU算法的持久子图问题。使用真实世界的图数据，我们实验验证了我们的技术的有效性和效率，并与两个以前的方法进行比较稠密子图检测。
One important problem that is insufficiently studied is finding densest lasting-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 then devise EMU algorithms for the densest lasting subgraph problem. Using real-world graph data, we experimentally verify the effectiveness and efficiency of our techniques, and compare with two prior approaches on dense subgraph detection.