论文标题
采样小连接子图的有效和近乎最佳的算法
Efficient and near-optimal algorithms for sampling small connected subgraphs
论文作者
论文摘要
我们研究以下问题：鉴于整数$ k \ ge 3 $和简单的图$ g $，样品a connected诱导的$ k $ node子图的$ g $均匀地均匀地均匀。这是一个基本的图形挖掘原始的，在社交网络分析，生物信息学等方面的应用。令人惊讶的是，没有有效的算法以均匀的采样而闻名。唯一有效的可用算法产生的样本仅大致均匀，运行时间不清或次优。在这项工作中，我们提供了：（i）一个近乎最佳的混合时间，用于众所周知的随机步行技术，（ii）真正均匀的Graphlet采样的第一个有效算法，以及（iii）第一个用于$ε$ - 均匀均匀的尺寸的sublinear-time算法。
We study the following problem: given an integer $k \ge 3$ and a simple graph $G$, sample a connected induced $k$-node subgraph of $G$ uniformly at random. This is a fundamental graph mining primitive with applications in social network analysis, bioinformatics, and more. Surprisingly, no efficient algorithm is known for uniform sampling; the only somewhat efficient algorithms available yield samples that are only approximately uniform, with running times that are unclear or suboptimal. In this work we provide: (i) a near-optimal mixing time bound for a well-known random walk technique, (ii) the first efficient algorithm for truly uniform graphlet sampling, and (iii) the first sublinear-time algorithm for $ε$-uniform graphlet sampling.
