# introduce #
近年来，互联网数据量呈指数级爆发式增长，促进了大数据的发展，如何高效的处理数据成为关键。海量数据中有很大一部分的数据由不同个体间的交互产生，这种互相关联的数据天然适合组织为图数据结构。图（graph）数据由节点（vertice）和边（edge）组成，将个体信息存储为节点，个体之间的联系存储为边，可以借助该结构所代表网络的拓扑和度量等研究数据之间关联性。图计算（Graph Computing）将数据结构组织为图进行分析计算，社交网络、网页链接关系等等是图计算的典型运用场景，如社交网络中将“用户”存储为节点，用户间“关注”存储为边，运用图计算可实现“节点间最短路径”、“最大社区”等等功能。

图计算中的一种重要的处理方法方法是从子图的角度处理数据，该方法的核心是子图计数问题，即计算子图的频率。包括主题查找、频繁子图挖掘（FSM）和团挖掘。子图计数算法执行时间很长，已有文章证明在一个图数据集中查询一个子图（即子图同构）是NP完全问题[引用]，要对特定子图进行精确计数比子图同构更加复杂。数千万边的图数据集中三角子图数量能达到数亿。对于非常大的图数据集来说，确定准确计数的最先进算法仍然需要数小时甚至数天。

随着社会产生的数据量不断增加（例如，在Twitter和Facebook等大型社交网络图中[引用]），精确统计所有可能的子图是不可行的。与此同时，研究者发现在许多应用中并不需要非常精确的结果，比如在计算统计汇总信息的应用中，返回数量级接近的结果即可。所以为了解决难以精确计数子图的问题，研究转向了近似计数这些子图的频率，在失去准确性但获得时间之间进行权衡。

在精确计数方面，Arabesque[55]，是一个分布式图计算系统，提出了解决精确计数的方案。然而，Arabesque响应时间依然很长。例如，Arabesque在一个由20台机器组成的集群上，用10个多小时来计算一个图中大小为3的图案，每个机器的内存为256GB，边数不到10亿条。对于近似计数方面，ASAP提出了一种基于边缘采样的近似方法进行计算，在Arabesque基础上将性能提高了两个数量级，而产生不到5%误差。但是ASAP系统在采样过程中仍然存在昂贵的边缘搜索操作，而且对于一定规模的数据图，为了达到保证一定程度的精度，ASAP需要使用大量估计器，这也带来了带来了很大的开销。这些不足说明了现有的一些研究，在性能，精度，计算复杂性几个方面上很难兼顾。

实际上，真实世界的图数据集大多数呈现幂律分布特征（如社交网络数据集等），幂律分布是某个关键变量的分布函数为幂函数的一种分布。表现形式为变量x的概率密度函数：f(x)~x^(-k)。在图数据中通常节点数-度数呈幂律分布：{vertices} = C*{degree}^{-k}。通过考察图数据的幂律特征我们发现，不同度数的点对pattern的贡献是不同的：少量高度数点比大量低度数点对pattern计数的贡献大的多。但目前的这些方法，并没有考虑图数据本身的幂律分布特性，均匀处理所有节点，使得部分计算浪费在低度数节点上。

有一部分研究探寻特定子图计数与图数据集幂律特征之间的关系，在Gao.P等人[引用]的研究从幂律指数为2~3之间的图数据提取度序列，并根据度序列采样生成了一个简单图，称为均匀随机图（uniform random graphs）。并且数学上证明了均匀随机图中度序列和特定子图（三角）数量之间的联系。

于是，我们的文章实现一个基于幂律分析的近似子图计数方法：将幂律分析引入近似计数中的分析方法，对幂律特征与特定子图数量关系进行数学分析，与Gao.P等人[引用]不同，我们使用真实的图数据集的特定子图数量进行分析，而不是随机生成的均匀随机图，并且不限制幂律指数的选取范围。通过度序列和特定子图之间关系曲线对子图总体数量进行近似计算。我们分析"子图的累加计数"与"数序列"之间幂律特性，使用曲线拟合分析法可以通过部分数据点拟合出子图累加曲线，从而分析子图总体计数。因为是部分数据点，不用枚举所有子图数量，大大减少了枚举的计算量。另外我们还将常用的采样估计的近似方法引入曲线分析，即少量的数据点也通过采样估计法获取，不再精确枚举。进一步节约时间。并且本文实现了基于该方法的原型系统，通过大量实验发现我们提高了XX精度，XX时间。

文中剩余部分的组织结构如下，第二章介绍了子图计数的精确计算和近似计算两个方面的相关工作。第三章描述了我们的方法的设计思路。第四章说明了原型系统的实现。第五章的实验对比了我们的方法与先进工作的性能。

# related work #

子图计数的精确算法大致分为：(a)经典方法：需要查询的子图为k-size，首先枚举所有具有k顶点的连通子图，然后使用图同构工具（如nauty[引用]）对发现的每个子图进行分类，来发现特定子图。如Milo等人[引用]提出了MFinder是一种递归回溯算法，适用于网络的每个边缘。给定的边最初存储在集合S上，该集合使用不在S中但与S中至少一条边共享一个端点的边进行递归增长。当| S |=k时，该算法通过保留已找到的子图的哈希表来检查是否首次找到了由S诱导的子图。(b)单子图搜索：只列举一个感兴趣的特定子图来实现的而不是列举所有k-size子图之后再进行分类。Grochow和Kellis[引用]的基本方法是应用于每个顶点的回溯算法。它试图通过基于邻域数构建所有可能的赋值，来构建从输入图到目标子图（它试图计数的子图）的部分映射。(c)封装方法：使用子图的公共拓扑特征或提取子图特征以避免同构的重复计算，如里贝罗和席尔瓦[引用]设计一种图的前缀树，树每个节点代表一个不同的图，其中父节点的图与其子节点的图共享公共子结构，并展示了基于该前缀树的子图计数算法。

精确计数难以满足越来越大的图数据集对子图计数的需求，研究者采用了多种方法来进行近似计数：(a)采样方案：主要思想是对图数据进行概率抽样，在采样样本上执行精确算法，再依据概率估计真实数据集的结果[引用]，很多研究者提出了很多采样方法如：

Bloom过滤器[引用]设置m bits初始化为0，使用独立的哈希函数z，一条边插入bloom过滤器，使用z函数随机从m bits中选择z bits设置为1。扫描边时，先检查已经出现过，方法是哈希之后获得相关的z bits，如果这z bits中有一位为0，则该边未出现过，则执行插入边。有可能因为其他边导致该边被丢弃，实际上它并未重复。Bloom过滤器在插入边数量越多，丢弃的概率越大，会导致误差较大。

FURL算法[引用]提出基于库和哈希的采样技术，设置一个k大小的库，扫描边时通过哈希计算哈希值，每次跟踪 k 个具有最小哈希值的不同边。FURL的缺陷除了采样边之外，还需要大量内存来存储辅助信息。

Triest[引用]的采样法设置k个bucket。对图流中的不同边随机分配不同的rank，每个bucket只维护一条边是哈希到bucket中rank最小的边。寻找特定图模式，依靠组成模式的相关边的rank值，使用Hyperloglog方法估计真实模式数量。Triest相较于FURL时间复杂度更低，但需要更多的参数设置和更多的计算步骤。

ASAP[引用]使用一种邻域采样的算法，先均匀采样一条边，然后不断从该边的邻域进行采样添加到嵌入中，直到判定出是否完成的查询的子图，最后通过贝叶斯概率估计真实模式数量。

我们注意到，这些采样算法Bloom过滤器、FURL、Triest等对所有的边均等采样，没有利用图数据边与边本身的关联性，采用存储额外信息的方式加速采样计算过程，APAP依据从边邻域中采样提高了构成子图的概率，但也没有考虑图本身的幂律特性，其第一条边的选择依然是均匀的。导致计算消耗较长或误差较大。

(b)分析方案：通过数学分析的方法计算子图数，如ORCA[引用]是基于矩阵乘法的实用分析方法进行计数。

【总结】

# design #
## 定义 ##
度序列(degree sequence)：度序列是一个序列包含n个不重复度正整数d=(d1,d1,···,dn),它表示一个图数据集中所有出现的不重复的度数。

度数-顶点曲线(degree-vertex curve)：以度序列为横轴，以每个度数对应顶点数为纵轴。如果曲线呈幂律分布，则称对应的图数据集为幂律图。

度数-子图曲线(degree-subgraph curve)：每个度数对应若干顶点，每个顶点如果包含在感兴趣的特定子图中，则将子图计数加1。以度数序列为横轴、子图计数为纵轴。

度数-子图累加曲线(degree-subgraph accumulation curve)：以度数序列为横轴、小于等于当前度数的子图累加数为纵轴，曲线可视为“度数-子图曲线”的积分曲线。

## 度数-模式分析 ##
在图的幂律规律通常指度序列和顶点之间分布满足幂律关系，我们分析高度数顶点占据了大量邻接边，因此少量的高度数相较于大量的低度数顶点应该有更高的概率存在于子图当中，因此我们猜测度序列和子图数量之间分布关系也满足长尾分布特性，但满足长尾分布的特征曲线有多种，如（）等等，我们使用多种曲线分布对多个数据集进行了拟合实验，发现在大多数图数据集中度数-子图曲线关系也满足幂律分布，也有部分数据集的度数-子图数不符合幂律，但这部分数据集本身的度数-顶点分布就不满足幂律特性。度数-子图累加曲线的纵轴是小于等于当前度数的子图数累加和，在度数-子图曲线满足幂律分布的基础上，度数-子图累加曲线可以视为幂律积分曲线。

设度序列为d，度序列上的子图数分布为Tr(d)，若Tr(d)满足幂律分布，有：

Tr(d) = C0*d^-α + C1 (C0 > 0, C1 > 0)(1)

度序列上的子图累加数分布为SumTr(d)，有：

SumTr(d) ≈ ∫(1 d)Tr(x)dx = (C0/(-α+1))x^(-α+1) + C1 + C2 简化后记作 Ax^-β + B (A < 0, B > 0, β > 0) (3)

式中可以看出SumTr(d)也是幂函数，可以通过部分数据点拟合得到其对应曲线就是度数-子图累加曲线。

## 拟合过程 ##
我们的方法基于上述定理，提取图数据集的度序列，然后使用精确计算或者采样估计的方法获取部分度数对应待计数的特定子图数量，然后将度数做叠加操作，度数-子图累加曲线得出近似子图计数。由于图的幂律特征是每个图数据集的属性，不同数据集都包含不同的幂律参数：幂指数等。想要利用幂律特征，必须要对每个数据集进行预处理分析，获取相关属性。对于不符合幂律特征的数据集，不适用与本文曲线拟合方法，因此需要在预处理分析中进行甄别，预处理阶段根据数据集属性绘制度数-顶点曲线，**（计算幂律相关度）**，判断是否符合幂律特征，相差过大则不进行幂律曲线拟合。

**选取哪些采样点，采样的的数据获取，拟合过程**，
想要进行度数-子图累加曲线拟合，首先需要获取度序列对应的子图计数：我们采用拟合方法，并不需要枚举所有度序列的子图计数来得出完整的曲线，因此只需要部分度数序列的对应的子图数就能进行曲线拟合。由于我们直接进行度数-子图累加曲线拟合而不是度数-子图曲线，我们真正用于拟合的数据是子图累加数，所以选择部分度序列应该完整度序列的从序列头开始的连续子序列，否则无法从子图数累加计算数子图累加数。

对于部分度序列的选择，一个重要的挑战就是如何选择部分度序列的长度，如果度序列太短，数据量不够将造成曲线拟合不准确，如果度序列太长会导致计算该部分度序列对于子图数的时间过长。

**（这里应该有一个选取前5%、10%、25%等等度序列的采样点拟合效果的图，来说明选择25%或其他什么差不多足够拟合）？？？**

**（通过实验，25%以上再多效果提升不大，因此我们确定选取25%的度序列）**
（关键点，误差估计，忽略掉的子图数）

接着按照**（25%）**度数进行图划分，根据度序列，依次将每个度数的对应顶点以及该顶点关联边划分到部分图数据集，在该部分数据集上进行子图计数，

采用子图搜索算法和采样估计方法（方法的选择也是一个问题）

我们在部分数据集中执行单子图搜索算法，因为我们每次在部分数据集中查询都针对特定的子图，所以不需要列举所有相同尺寸的子图，也不需要寻找公共结构。**（使用[引用]搜索算法）**

而另一种获取部分数据集的子图数的方法是采样估计方法，它在部分数据集中再进行采样，采样后统计子图数，并根据采样概率估算部分数据集中的子图数。我们使用的采样法的邻域采样法[引用]，其基本思想是对一条边进行采样，然后逐步添加更多边，直到这些边形成或无法形成子图。邻域采样与普通随机采样相比，增加了每次试验找到给定子图实例的概率，因此需要更少的估计才能达到相同的精度。

我们对图进行了按照度数划分的估计，得到了子图个数关于部分度序列的分布情况，记作Tr(d)，其中d是度序列中的每个度数，d∈Dpartial。我们利用这部分估计数据进行曲线拟合，对总体子图个数进行估计。
**累加曲线的拟合。**幂律图中高度数的点分布稀疏，并且连接了大部分的边，因此为了降低此因素带来的拟合误差，我们采用拟合Tr(d)的拟合累加曲线来估计。即拟合

Sum(d)=Σ(1<=i<=d)Tr(i) (1)

考虑到Tr满足幂律分布，即

Tr(d) = C0*d^-α + C1 (2)

由欧拉-麦克劳林公式，忽略低阶项，我们有

Sum(d) ≈ ∫(1 d)Tr(x)dx = Ax^-α + B (A > 0, B > 0, α > 0) (3)

即三角形关于度数分布的曲线为幂函数，我们利用此性质可以对幂律图上的三角形数量进行估计。
**数据的插值处理。** 由于对于高度数 d，幂律图可能不存在度数为 d 的点，故我们对点列Sum(d)进行线性插值，以符合累加曲线的单调增性质。【引用，细化一下周边参考点的数量，及原因】

# Implement #
【架构图】
我们的系统基于Apache Spark。系统使用了Spark的图形处理库GraphX来处理图数据集。在Spark基础上，我们实现了图数据集加载模块，图数据集预处理模块，拟合计数模块等模块，并向外提供图数据集加载接口。整个系统使用scala编写。

图数据集加载接口，用户向系统指定数据集文件路径，由系统加载路径文件。

图数据加载模块使用图形处理库GraphX的load功能从文件中加载图数据，模块将自动对图数据集进行划分，存储到Spark中。

图数据预处理模块首先要对图数据集进行去重复边和规范化处理，重复边是指两条边的源顶点和目标顶点相同，规范化是指如果边的src_id > dst_id则交换src_id和dst_id，规范化可以保证不出现无向图的两个顶点循环。接着对图数据集进行分析，获取数据集基本属性如顶点数、边数等等，提取数据集度序列。

拟合计数模块根据用户指定的特定子图结构，查询部分度序列的子图数量，根据数据拟合子图累加曲线，并估计计算总体子图数量。

# Evaluation #
【实验环境】、【数据集介绍】我们使用许多真实世界的图数据集来评估我们的系统，我们将其与精确计算的Arabesque和近似计算的ASAP进行比较。

**数据集选取。**我们选取了多个真实图数据集，包括：
（XXX 大小····）

**查询子图。** 3-motif等

**与精确结果和ASAP对比。**在不同数据集上查询多种子图，我们的系统采用精确估计和采样估计两种数据获取方法分别与Arabesque、ASAP对比

**不同拟合参数选择近似计数对比* *

# introduce #
近年来，互联网数据量呈指数级爆发式增长，促进了大数据的发展，如何高效的处理数据成为关键。海量数据中有很大一部分的数据由不同个体间的交互产生，这种互相关联的数据天然适合组织为图数据结构。图（graph）数据由节点（vertice）和边（edge）组成，将个体信息存储为节点，个体之间的联系存储为边，可以借助该结构所代表网络的拓扑和度量等研究数据之间关联性。图计算（Graph Computing）将数据结构组织为图进行分析计算，社交网络、网页链接关系等等是图计算的典型运用场景，如社交网络中将“用户”存储为节点，用户间“关注”存储为边，运用图计算可实现“节点间最短路径”、“最大社区”等等功能。

图计算中的一种重要的处理方法方法是从子图的角度处理数据，该方法的核心是子图计数问题，即计算子图的频率。包括主题查找、频繁子图挖掘（FSM）和团挖掘。子图计数算法执行时间很长，已有文章证明在一个图数据集中查询一个子图（即子图同构）是NP完全问题[引用]，要对特定子图进行精确计数比子图同构更加复杂。数千万边的图数据集中三角子图数量能达到数亿。对于非常大的图数据集来说，确定准确计数的最先进算法仍然需要数小时甚至数天。

随着社会产生的数据量不断增加（例如，在Twitter和Facebook等大型社交网络图中[引用]），精确统计所有可能的子图是不可行的。与此同时，研究者发现在许多应用中并不需要非常精确的结果，比如在计算统计汇总信息的应用中，返回数量级接近的结果即可。所以为了解决难以精确计数子图的问题，研究转向了近似计数这些子图的频率，在失去准确性但获得时间之间进行权衡。

在精确计数方面，Arabesque[55]，是一个分布式图计算系统，提出了解决精确计数的方案。然而，Arabesque响应时间依然很长。例如，Arabesque在一个由20台机器组成的集群上，用10个多小时来计算一个图中大小为3的图案，每个机器的内存为256GB，边数不到10亿条。对于近似计数方面，ASAP提出了一种基于边缘采样的近似方法进行计算，在Arabesque基础上将性能提高了两个数量级，而产生不到5%误差。但是ASAP系统在采样过程中仍然存在昂贵的边缘搜索操作，而且对于一定规模的数据图，为了达到保证一定程度的精度，ASAP需要使用大量估计器，这也带来了带来了很大的开销。这些不足说明了现有的一些研究，在性能，精度，计算复杂性几个方面上很难兼顾。

实际上，真实世界的图数据集大多数呈现幂律分布特征（如社交网络数据集等），幂律分布是某个关键变量的分布函数为幂函数的一种分布。表现形式为变量x的概率密度函数：f(x)~x^(-k)。在图数据中通常节点数-度数呈幂律分布：{vertices} = C*{degree}^{-k}。通过考察图数据的幂律特征我们发现，不同度数的点对pattern的贡献是不同的：少量高度数点比大量低度数点对pattern计数的贡献大的多。但目前的这些方法，并没有考虑图数据本身的幂律分布特性，均匀处理所有节点，使得部分计算浪费在低度数节点上。

有一部分研究探寻特定子图计数与图数据集幂律特征之间的关系，在Gao.P等人[引用]的研究从幂律指数为2~3之间的图数据提取度序列，并根据度序列采样生成了一个简单图，称为均匀随机图（uniform random graphs）。并且数学上证明了均匀随机图中度序列和特定子图（三角）数量之间的联系。

于是，我们的文章实现一个基于幂律分析的近似子图计数方法：将幂律分析引入近似计数中的分析方法，对幂律特征与特定子图数量关系进行数学分析，与Gao.P等人[引用]不同，我们使用真实的图数据集的特定子图数量进行分析，而不是随机生成的均匀随机图，并且不限制幂律指数的选取范围。通过度序列和特定子图之间关系曲线对子图总体数量进行近似计算。我们分析"子图的累加计数"与"数序列"之间幂律特性，使用曲线拟合分析法可以通过部分数据点拟合出子图累加曲线，从而分析子图总体计数。因为是部分数据点，不用枚举所有子图数量，大大减少了枚举的计算量。另外我们还将常用的采样估计的近似方法引入曲线分析，即少量的数据点也通过采样估计法获取，不再精确枚举。进一步节约时间。并且本文实现了基于该方法的原型系统，通过大量实验发现我们提高了XX精度，XX时间。

文中剩余部分的组织结构如下，第二章介绍了子图计数的精确计算和近似计算两个方面的相关工作。第三章描述了我们的方法的设计思路。第四章说明了原型系统的实现。第五章的实验对比了我们的方法与先进工作的性能。

# related work #

子图计数的精确算法大致分为：(a)经典方法：需要查询的子图为k-size，首先枚举所有具有k顶点的连通子图，然后使用图同构工具（如nauty[引用]）对发现的每个子图进行分类，来发现特定子图。如Milo等人[引用]提出了MFinder是一种递归回溯算法，适用于网络的每个边缘。给定的边最初存储在集合S上，该集合使用不在S中但与S中至少一条边共享一个端点的边进行递归增长。当| S |=k时，该算法通过保留已找到的子图的哈希表来检查是否首次找到了由S诱导的子图。(b)单子图搜索：只列举一个感兴趣的特定子图来实现的而不是列举所有k-size子图之后再进行分类。Grochow和Kellis[引用]的基本方法是应用于每个顶点的回溯算法。它试图通过基于邻域数构建所有可能的赋值，来构建从输入图到目标子图（它试图计数的子图）的部分映射。(c)封装方法：使用子图的公共拓扑特征或提取子图特征以避免同构的重复计算，如里贝罗和席尔瓦[引用]设计一种图的前缀树，树每个节点代表一个不同的图，其中父节点的图与其子节点的图共享公共子结构，并展示了基于该前缀树的子图计数算法。

精确计数难以满足越来越大的图数据集对子图计数的需求，研究者采用了多种方法来进行近似计数：(a)采样方案：主要思想是对图数据进行概率抽样，在采样样本上执行精确算法，再依据概率估计真实数据集的结果[引用]，很多研究者提出了很多采样方法如：

Bloom过滤器[引用]设置m bits初始化为0，使用独立的哈希函数z，一条边插入bloom过滤器，使用z函数随机从m bits中选择z bits设置为1。扫描边时，先检查已经出现过，方法是哈希之后获得相关的z bits，如果这z bits中有一位为0，则该边未出现过，则执行插入边。有可能因为其他边导致该边被丢弃，实际上它并未重复。Bloom过滤器在插入边数量越多，丢弃的概率越大，会导致误差较大。

FURL算法[引用]提出基于库和哈希的采样技术，设置一个k大小的库，扫描边时通过哈希计算哈希值，每次跟踪 k 个具有最小哈希值的不同边。FURL的缺陷除了采样边之外，还需要大量内存来存储辅助信息。

Triest[引用]的采样法设置k个bucket。对图流中的不同边随机分配不同的rank，每个bucket只维护一条边是哈希到bucket中rank最小的边。寻找特定图模式，依靠组成模式的相关边的rank值，使用Hyperloglog方法估计真实模式数量。Triest相较于FURL时间复杂度更低，但需要更多的参数设置和更多的计算步骤。

ASAP[引用]使用一种邻域采样的算法，先均匀采样一条边，然后不断从该边的邻域进行采样添加到嵌入中，直到判定出是否完成的查询的子图，最后通过贝叶斯概率估计真实模式数量。

我们注意到，这些采样算法Bloom过滤器、FURL、Triest等对所有的边均等采样，没有利用图数据边与边本身的关联性，采用存储额外信息的方式加速采样计算过程，APAP依据从边邻域中采样提高了构成子图的概率，但也没有考虑图本身的幂律特性，其第一条边的选择依然是均匀的。导致计算消耗较长或误差较大。

(b)分析方案：通过数学分析的方法计算子图数，如ORCA[引用]是基于矩阵乘法的实用分析方法进行计数。

【总结】

# design #
## 定义 ##
度序列(degree sequence)：度序列是一个序列包含n个不重复度正整数d=(d1,d1,···,dn),它表示一个图数据集中所有出现的不重复的度数。

度数-顶点曲线(degree-vertex curve)：以度序列为横轴，以每个度数对应顶点数为纵轴。如果曲线呈幂律分布，则称对应的图数据集为幂律图。

度数-子图曲线(degree-subgraph curve)：每个度数对应若干顶点，每个顶点如果包含在感兴趣的特定子图中，则将子图计数加1。以度数序列为横轴、子图计数为纵轴。

度数-子图累加曲线(degree-subgraph accumulation curve)：以度数序列为横轴、小于等于当前度数的子图累加数为纵轴，曲线可视为“度数-子图曲线”的积分曲线。

## 度数-模式分析 ##
在图的幂律规律通常指度序列和顶点之间分布满足幂律关系，我们分析高度数顶点占据了大量邻接边，因此少量的高度数相较于大量的低度数顶点应该有更高的概率存在于子图当中，因此我们猜测度序列和子图数量之间分布关系也满足长尾分布特性，但满足长尾分布的特征曲线有多种，如（）等等，我们使用多种曲线分布对多个数据集进行了拟合实验，发现在大多数图数据集中度数-子图曲线关系也满足幂律分布，也有部分数据集的度数-子图数不符合幂律，但这部分数据集本身的度数-顶点分布就不满足幂律特性。度数-子图累加曲线的纵轴是小于等于当前度数的子图数累加和，在度数-子图曲线满足幂律分布的基础上，度数-子图累加曲线可以视为幂律积分曲线。

设度序列为d，度序列上的子图数分布为Tr(d)，若Tr(d)满足幂律分布，有：

Tr(d) = C0*d^-α + C1 (C0 > 0, C1 > 0)(1)

度序列上的子图累加数分布为SumTr(d)，有：

SumTr(d) ≈ ∫(1 d)Tr(x)dx = (C0/(-α+1))x^(-α+1) + C1 + C2 简化后记作 Ax^-β + B (A < 0, B > 0, β > 0) (3)

式中可以看出SumTr(d)也是幂函数，可以通过部分数据点拟合得到其对应曲线就是度数-子图累加曲线。

## 拟合过程 ##
我们的方法基于上述定理，提取图数据集的度序列，然后使用精确计算或者采样估计的方法获取部分度数对应待计数的特定子图数量，然后将度数做叠加操作，度数-子图累加曲线得出近似子图计数。由于图的幂律特征是每个图数据集的属性，不同数据集都包含不同的幂律参数：幂指数等。想要利用幂律特征，必须要对每个数据集进行预处理分析，获取相关属性。对于不符合幂律特征的数据集，不适用与本文曲线拟合方法，因此需要在预处理分析中进行甄别，预处理阶段根据数据集属性绘制度数-顶点曲线，**（计算幂律相关度）**，判断是否符合幂律特征，相差过大则不进行幂律曲线拟合。

**选取哪些采样点，采样的的数据获取，拟合过程**，
想要进行度数-子图累加曲线拟合，首先需要获取度序列对应的子图计数：我们采用拟合方法，并不需要枚举所有度序列的子图计数来得出完整的曲线，因此只需要部分度数序列的对应的子图数就能进行曲线拟合。由于我们直接进行度数-子图累加曲线拟合而不是度数-子图曲线，我们真正用于拟合的数据是子图累加数，所以选择部分度序列应该完整度序列的从序列头开始的连续子序列，否则无法从子图数累加计算数子图累加数。

对于部分度序列的选择，一个重要的挑战就是如何选择部分度序列的长度，如果度序列太短，数据量不够将造成曲线拟合不准确，如果度序列太长会导致计算该部分度序列对于子图数的时间过长。

**（这里应该有一个选取前5%、10%、25%等等度序列的采样点拟合效果的图，来说明选择25%或其他什么差不多足够拟合）？？？**

**（通过实验，25%以上再多效果提升不大，因此我们确定选取25%的度序列）**
（关键点，误差估计，忽略掉的子图数）

接着按照**（25%）**度数进行图划分，根据度序列，依次将每个度数的对应顶点以及该顶点关联边划分到部分图数据集，在该部分数据集上进行子图计数，

采用子图搜索算法和采样估计方法（方法的选择也是一个问题）

我们在部分数据集中执行单子图搜索算法，因为我们每次在部分数据集中查询都针对特定的子图，所以不需要列举所有相同尺寸的子图，也不需要寻找公共结构。**（使用[引用]搜索算法）**

而另一种获取部分数据集的子图数的方法是采样估计方法，它在部分数据集中再进行采样，采样后统计子图数，并根据采样概率估算部分数据集中的子图数。我们使用的采样法的邻域采样法[引用]，其基本思想是对一条边进行采样，然后逐步添加更多边，直到这些边形成或无法形成子图。邻域采样与普通随机采样相比，增加了每次试验找到给定子图实例的概率，因此需要更少的估计才能达到相同的精度。

我们对图进行了按照度数划分的估计，得到了子图个数关于部分度序列的分布情况，记作Tr(d)，其中d是度序列中的每个度数，d∈Dpartial。我们利用这部分估计数据进行曲线拟合，对总体子图个数进行估计。
**累加曲线的拟合。**幂律图中高度数的点分布稀疏，并且连接了大部分的边，因此为了降低此因素带来的拟合误差，我们采用拟合Tr(d)的拟合累加曲线来估计。即拟合

Sum(d)=Σ(1<=i<=d)Tr(i) (1)

考虑到Tr满足幂律分布，即

Tr(d) = C0*d^-α + C1 (2)

由欧拉-麦克劳林公式，忽略低阶项，我们有

Sum(d) ≈ ∫(1 d)Tr(x)dx = Ax^-α + B (A > 0, B > 0, α > 0) (3)

即三角形关于度数分布的曲线为幂函数，我们利用此性质可以对幂律图上的三角形数量进行估计。
**数据的插值处理。** 由于对于高度数 d，幂律图可能不存在度数为 d 的点，故我们对点列Sum(d)进行线性插值，以符合累加曲线的单调增性质。【引用，细化一下周边参考点的数量，及原因】

# Implement #
【架构图】
我们的系统基于Apache Spark。系统使用了Spark的图形处理库GraphX来处理图数据集。在Spark基础上，我们实现了图数据集加载模块，图数据集预处理模块，拟合计数模块等模块，并向外提供图数据集加载接口。整个系统使用scala编写。

图数据集加载接口，用户向系统指定数据集文件路径，由系统加载路径文件。

图数据加载模块使用图形处理库GraphX的load功能从文件中加载图数据，模块将自动对图数据集进行划分，存储到Spark中。

图数据预处理模块首先要对图数据集进行去重复边和规范化处理，重复边是指两条边的源顶点和目标顶点相同，规范化是指如果边的src_id > dst_id则交换src_id和dst_id，规范化可以保证不出现无向图的两个顶点循环。接着对图数据集进行分析，获取数据集基本属性如顶点数、边数等等，提取数据集度序列。

拟合计数模块根据用户指定的特定子图结构，查询部分度序列的子图数量，根据数据拟合子图累加曲线，并估计计算总体子图数量。

# Evaluation #
【实验环境】、【数据集介绍】我们使用许多真实世界的图数据集来评估我们的系统，我们将其与精确计算的Arabesque和近似计算的ASAP进行比较。

**数据集选取。**我们选取了多个真实图数据集，包括：
（XXX 大小····）

**查询子图。** 3-motif等

**与精确结果和ASAP对比。**在不同数据集上查询多种子图，我们的系统采用精确估计和采样估计两种数据获取方法分别与Arabesque、ASAP对比

**不同拟合参数选择近似计数对比* *