1.Bipartite graph。

答：

bipartite graph的例子如下图，红色节点和绿色节点之间互相没有link。

2.Folded graph(projected bipartite graph)。

答：Folded graph是定义在bipartite graph之上的，如下图，中间的是一个bipartite graph，左边和右边分别是投影到U上和V上的folded graph。以左图为例，节点1和节点2有连接，是因为在bipartite graph中，节点1和节点2共同连接了节点A。

3.self-edges and multigraph。

答：

4.connected graph(undirected)。

答：

可以通过邻接矩阵判断是不是连通图。

5.connectivity of directed graphs。

答：分为强连接和弱连接。

6.degree distribution。

答：degree distribution指的是节点的度分布。

7.paths in a graph。

答：一个path中的边可以多次经过。

8.distance in a graph。

答：distance指的是一个节点到另一个节点所需要经过的边数。如果不可达，一般设为无穷或0。在有向图中，需要沿着箭头的方向。在带权图中，distance指节点A到节点B的最小边权和。

9.图的直径。

答：图的直径指最大的两个节点间的最短距离。有的时候直径(diameter)不一定是一个好的度量(可能有那种很扁但很长的图)。一般会使用average path length，如下。

10.clustering coefficient。

答：clustering coefficient一般定义在无向图上，反应了节点的neighbors之间的连接情况。clustering coefficient ∈ [0,1]。其实就是节点的neighbors之间的连接数 / neighbors之间的最大连接数。对于度为0或1的节点，clustering coefficient没有定义，或者定义为0。

11.connected component(连通区域)。

答：

12.真实网络的degree distribution。

答：

上图似乎没有什么明确的规律性，我们用log作为坐标重新绘图。

可以看到，这服从一个长尾分布。

12.简单生成一个图(Erdos-Renyi random graph)。

答：

Gnp图的一些性质。
Gnp的degree distribution是一个二项分布。下图中括号上下n-1和k的意思是，从n-1个点中选择k个点(其实就是组合数)。

这个二项分布的均值和方差。同时，下图中对两个参数做了比值，可以看到，当n很大时，比值趋向于0，也就是每个节点的度都接近为k。

Gnp的clustering coefficient的性质。
E[ei] = p * ki * (ki - 1) / 2的理解。ki * (ki - 1) / 2是所有可能出现的边的总数，每条边以p的概率出现，因此ei的期望(均值)为p * ki * (ki - 1) / 2。
求E[Ci]的时候有p = k_bar / (n-1)，这一步来自于前面k_bar = p * (n-1)。
如果我们固定k_bar，即创建一个图并且固定平均的度数k，那么节点越多，Ci越小。

expansion。其中S指的是节点集V的一个子集。

下图中c是一个常数。

下图比较了MSN(一个现实场景中的网络)和Gnp(随机生成的网络)的各个指标。Gnp给了我们一个参考。

如何创造一个high clustering with low diameter的图。左图P = 0，右图P = 1。P是节点A去掉与B的连接，rewire到另一个节点的概率。只需要较少的rewire就可以collapse diameter。

13.network significance profile。

答：通过各种各样的子图来反应网络的组成情况。

定义motif。

induced graph必须完全match，不能有多出来的边(如红色图)。

occurence指的是，指定的motif在图中出现的部分。

总结一下上面所做的事情：
1)定义一个motif，也就是一个子图。
2)寻找该子图在real graph中出现的次数。
3)比较该子图在random graph中出现的次数。

具体的数值表达如下，std表示标准差。

现在问题转为如何构建一个random graph，之前提到过使用Erdos-Renyi random graph，但是这里我们希望构建的random graph每个节点的度能由我们指定。也就是希望G_real和G_random能有一样的度序列。

如下图所示，使用的是configuration model。看最下面的三个小图，左边是目标，希望生成的图中A的度为3，C的度为2等等。然后构造中间那个图，如果A的度为3，就在A的小方框里画三个点，画出所有点后，进行一些连接，要求所有的点刚好被连接一次。最后构建最终图，如果在第二个图中，A和B有连接，那么最终图中就连接A和B。(第二个图中的连接是随意的，不需要按顺序，因为我们希望得到一个随机图) (如果是有向图，那么中间那个图，A需要有两个小方框，A-in和A-out)
可以发现这么做有一个问题，第二个图中A和B连接了两次，那么就导致了最终的图中A和B的度都少了1，但是当节点数量很大，图很大时，我们认为这是一种可以接受的噪声，也就是说我们认为这种方式生成了一个近似的图。

如果希望能构建一个准确的图，可以使用switching。从图G_real开始，挑选两条边，做一个rewire，重复多次，就能得到一个random graph。

到目前为止，解释了本问题最上面的那个图是怎样计算得来的。
总结如下，上面的所有工作是为了给graph提供一个表述方式，衡量不同的graph。

14.Graphlets。

答：graphlets指的是连通的非同构子图。比如节点数量为4时，有6个graphlets。

Graphlet Degree Vector指的是各种子图出现的次数(必须包含v，并且必须是完全符合子图，子图包含的节点之间不能有多余的边，即下图中的b不包含c，这是induced graph定义决定的)。见下图中的例子。也就是说，GDV是node level的。

比较两个节点的GDV向量，可以反映出两个节点的local similarity。

什么是orbit？看下图就知道了。

graphlet和motif的区别？motif考虑的是整个图中的结构信息，graphlet是一个local的概念，考虑的是一个节点周围的结构信息。

如何找graphlet和motif？需要注意的是，这个问题是指数级的复杂度，这也是为什么graphlet和motif一般包含的节点比较少，通常最多8个。

ESU算法(exact subgraph enumeration，用于产生k size的subgraph)。

下图给出了ESU算法的一个例子。

完成枚举后，count不同的类型有几个。

如何判断两个图是不是同构的？如下图，如果两个图中的节点可以完美的mapping，那么就是同构的。

两个节点是structure equivalence指的是这两个节点对于剩下节点的连接情况是一样的。
如何发现structure equivalence的节点？RoIX算法，流程如下。

下面对第二步做一个具体的解释(recursive feature extraction)。
feature包括了local，egonet和recursive三部分。

recursive的计算方式如下，简单的说就是用已有的特征产生新特征，当特征数量很多时，使用一些剪枝，去掉一些相关度很高的特征。当然，也可以再这部分采用node representation vector或者同时结合node representation vector和recursive。

在role extraction部分，再提取的特征上使用聚类算法。

下面是使用RoIX的一个例子。