论文标题
楔形拾取模型：基于三合会闭合的动态图模型
The Wedge Picking Model: A dynamic graph model based on triadic closure
论文作者
论文摘要
社交网络已成为人类生活中不可分割的一部分，并以有效的方式处理它们是网络研究的重中之重。这些网络具有高度的动态性，并且正在不断增长。受三元闭合概念的启发，我们提出了一种概率机制来模拟这些动态图的演变。尽管三合会的封闭在社交网络中无处不在及其在场有助于形成社区，但概率模型封装了它，尚未对其进行充分研究。 我们理论上分析了我们的模型，并展示了如何绑定图表的某些特征的增长率，例如顶点程度。利用我们的理论结果，我们开发了一个调度子例程，以分批处理图表的修改。然后，我们的调度子例程用于加快最先进的算法，并在其近似保证中可以忽略不计。我们通过将其应用于最密集的子图和三通子图发现问题来证明我们的方法的适用性。
Social networks have become an inseparable part of human life and processing them in an efficient manner is a top priority in the study of networks. These networks are highly dynamic and they are growing incessantly. Inspired by the concept of triadic closure, we propose a probabilistic mechanism to model the evolution of these dynamic graphs. Although triadic closure is ubiquitous in social networks and its presence helps forming communities, probabilistic models encapsulating it have not been studied adequately. We theoretically analyze our model and show how to bound the growth rate of some characteristics of the graph, such as degree of vertices. Leveraging our theoretical results, we develop a scheduling subroutine to process modifications of the graph in batches. Our scheduling subroutine is then used to speed up the state-of-the-art algorithms with negligible loss in their approximation guarantees. We demonstrate the applicability of our method by applying it to the densest subgraph and tri-densest subgraph discovery problem.
