Structure in Network
在Course里面Jure是把Structural Roles 和Community Structure分成了两个Part讲解，由于自己是写笔记所以就简单的把两个放在同一片文章之中吧。
本文主要讲述的是怎么去寻找到网络图之中的某些的特定的结构信息，毕竟在上文之中我们的讲述的特征都是一些Global的宏观特征，但是在网络之中我们很多时候也会去关注一些Local的特征。那么如何捕获呢？
SubGraph ,Motifs and Graphlets
子图(SubGraph)可以看成是在建造网络的Blocks，如果把网络看成是一个乐高的话，子图就是一个个的小积木以组成整个的模型。
那么Motif呢？原文说的是Recurring, significant patterns of interconnections,也就是在网络的图结构之中重复出现的高频Pattern,可以看成是卷积神经网络之中的卷积核。
那么是怎么样的Pattern呢？定义为Small Induced Subgraph，Induced subgraph如果大家没有学过图论还是有一些有一些迷茫的，所以我给大家讲一下吧，假设原图定义为$G = \{V,E\}$,其中的$V$代表是节点，而$E$代表是Edges，那么其导出子图的$V’$是$V$的子集，对于$V’$之中的所有两两之间的节点如果在原图之中有Edge那么在导出子图之中也一定有Edge。有点抽象，就是说导出子图的节点可以是在原图之中的抽取的子集，但是如果一旦从原图之中抽取了，那么在原图之中的关系都要在导出子图之中涵盖。
有了Pattern之后我们就可以去对比原图了，那么什么叫做是Significant呢？显著是一个相对的概念而不是一个绝对的概念，那么是相对于什么而言的呢？在很多的实际任务之中我们会将Random Guess做为Baseline所以在这里我们就将Random Graph作为Baseline。那人可以随机的猜就行了，可是随机的图又要怎么样的形成呢？有两种方式分别是Configuration Model还有Switching Model，这两种模型是两种不一样的生成的方式，对于Configuration Model我们生成模型的方式是通过确定每一个节点的Degree，然后将这些节点连接起来。
之所以要确定每一个节点的Degree是因为我们只是想更改模型的连接的方式而不是对于整个模型进行重构，上面的流程也可以看出来，首先是确定四个节点的Degree分别是3,4,2,1，然后进行随机的配对环节，也就是第二步，再根据图二之中的连接的关系就可以得到最后的生成的Graph了。
当然还有一种方式叫做Switching，听名字就知道这个玩意是通过交换得到随机的图的，那么怎么交换呢？随机选择两个Edges，假设分别是$A\to B$和$C\to D$，然后将他们的入点相互Switch，就得到了$A\to D$和$C\to B$
运行足够多的次数之后，现在的模型就会与原来的模型大相径庭了。
然后得到了Random的Graph之后接下来就是在这两个图之中寻找Motifs，假设有$i$个Motif，那么在原图之中的Motifs的数量记作$N_{i}^{real}$,在随机图之中的数量记作$N_{i}^{rand}$，通过归一化计算出$Z$Score
$$Z_{i} = (N_{i}^{real} – N_{i}^{rand})/std(N_{i}^{real})$$
如果Z越高说明在网络之中存在这样的现象越Significant。
上图就是一个实例，可以发现在不同的数据集之中各个节点所存在的Pattern是不同的，而这些特定的Pattern则是网络所组成的深层次的原因，
那么Motifs是在整个图之中寻找某一些Pattern，但是如果想要去在更细的水平上提取信息就需要其他的特征了，比如说我们接下来要讨论的Graphlet Degree Vector，这个的概念与Degree非常的相似，Degree是包含了该节点的Edges的数量，而Graphlet Degree Vector是包含了该节点的Graphlets的数量。
那么Graphlet是什么呢？大家在高中的时候如果学过化学的话，应该接触过一个概念叫做同分异构体，在这里有更加General/Fancy的名字称为Automorphism Orbit.
而一个“同分异构体”就是一个Graphlets，所以我们可以对于每一个节点得出一个长度为$n$的向量，而向量的维度取决于有多少种Graphlets，而向量的对应的维度的值则取决于对于第$i$个Graphlet，在该节点上出现了多少次。有些抽象，我们用一个例子说明
我们如今考虑的节点是$v$，现在有4种不同的Graphlets，所以GDV的维度是4，那么对于每一个维度，我们分别去Test在该节点上是否可以找到对应的类似的结构，举例如果是$v$是$d$的话，有两种可能性，这两种可能性分别画在图中了，而为什么$c$是0呢？因为这里的Graphlets依旧是要求是Induced Graph，而不是差不多的就行了。所以我们就可以对于每一个节点得到如上的向量。
而具体怎么去找Motifs以及GDV的求解有非常多的算法可以高效的进行处理，自己暂时就不在这里讲解了。
Structural Roles In Networks
那么我们之前的上文都是讲如何发现图之中的特征，大家也知道，当搞定完特征的下一步就是去利用这些特征，接下来就是讲解如何更好的利用这些特征，大家都知道在网络之中存在着不同的角色，比如在生态网络之中，有些动物在食物链的顶端，有些动物在底端；在公司的网络之中，有些组织的控股结构错综复杂，有的却非常直接。那么寻找到这些在网络之中的不同的角色对于我们理解系统而言是至关重要的。
什么是角色呢？也即是在网络之中所承担的相似的功能的那些节点。或者说，他们处理和接触他们周围的节点的方式是相似的
比如上图之中就是这样，其中的$u$和$v$在网络之中所承担的功能就是类似的，所以我们可以认为他们所承担的角色是相同的。 通过寻找Role的算法我们可以得到一个这个的图
上图是Co-Author的网络，什么叫做是Co-Author呢？大家都知道在写书的时候，写一本书是非常困难的事情(写Blog也好难)，那么这时候就会大家聚起来，分别写书的不同部分以简化工作。而上图之中如果两个人之间一起写过书，他们就形成一条边。可以发现，网络之中的红色的点就是那些Stars，大家都愿意和他们一起写书，在现实生活之中一般指的就是那些大牛学者，大家都希望蹭蹭他们，而那些蓝色的圆形的，可以看成是在一个SubTopic下面，这些人做了一个比较偏门的领域，使得他们自己之间形成了一个Cliques而并不和外界连接。对于那些绿色的，就是那些摸鱼选手，比如在下这种摸鱼选手应该就会被分到绿色之中。
怎么发现这些Role呢？我们之前不是有发掘出来了不同的特征吗，Local和Global的信息都有，那么我们就使用这些信息进行聚类，比如简单的K-Means就可以了，在上图使用的Rolex算法则是使用Negative Matrix Factorization进行处理。
在Rolex之中还利用了其他的信息，在论文之中称为是Recursive Feature,这里的Recursive是什么意思呢？也就是对于原来的信息进行处理之后再利用他们去生成新的信息。比如说得到了一个节点的周围的点的Degree，然后取均值作为整个Egonet(即节点的周围的点)的一个特征。具体的算法细节也不介绍了，点到为止。具体可以看RolX: structural role extraction & mining in large graphs
其实这种任务我觉得特别适合DBSCAN来做，毕竟人家就是基于密度来做聚类这种事情。不过不知道有没有人做过这方面的研究就是了。
Community Structure In Networks
在上面我们讲了Role Detection的问题，接下来的问题可以看成是Community Detection的问题，什么叫做是Community呢？他和Role的区别是什么呢？
如果说Role Detection的算法关注于发掘每一个个体在网络之中的地位，而Community专注于发掘你是属于哪个群体？比如说在前者的算法之中，其会将Boris和Trump分类进一类，因为他们都是承担了国家的领导人的职责，但是在后者之中，可能会将Trump和希拉里分成一类，因为他们都是美国人。
但是如何达到这样的目的呢？Role的概念非常的直接，根据在网络之中的连接的特征就可以达到分类的目的。但是Community并不同，我们需要找到一些其他的特征来对于Community进行处理。
那么在社会学之中，有一个很有意思的工作 ，Mark Granovetter在上个世纪六十年代发现了一个现象，人们寻找工作的时候往往不是通过自己身边的朋友，而是通过那些自己并不熟悉的人找到工作的，这时候Mark就陷入迷思了，为什么大家在找工作这么重要的事情上面不是依赖自己的朋友而是去寻找那些不熟悉的人呢？很明显，自己的朋友与自己是处于一个Strong的联系，而那些不熟悉的人是处于Weak的联系之中。后来他经过了研究得出了下面的结论
- 网络结构紧密的地方代表着社交联系紧密，那些长距离的跨越的边代表着社会联系弱。
- 长距离跨越的边使得我们可以从不同的地方获取信息，从而拿到工作。网络结构紧密的边是Redundancy的，因为信息的传播并不需要同时认识这么多人。
换成人话就是，你确实和你的朋友关系非常好，但是在找工作这件事情上面，因为你和你朋友都是差不多的圈子，那么他很有可能无法为你在找工作这件事情上面提供什么帮助。相反，通过其他的并不熟悉的人可以跨越圈子，从而得到更多的信息。
在后来2007年Onnela的一个研究之中也对于上述的论述观点进行了 实证的验证。证明了在连接紧密的网络区域之中会有更加频繁的网络联络。其中使用了一个概念叫做是Edge Overlap，也就是对于两个点之间的连接的紧密的程度进行度量。
$$O_{ij}=\frac{|(N(i)\cap N(j))/\{i,j\}|}{|(N(i)\cup N(j))/\{i,j\}|}$$
这里就使用$/$代表不包括原数据对了。
上述图片就是计算这个$O$的几个例子，可以发现$O$越高说明两个Part之间的联系就会越多，宅一点的说法就是左右两边之间的“节”(結び)就越多。
那么通过研究发现，如果$O_{ij}$越大，那么这两个节点之间的打电话的时间也就越长，而如果把网络之间的Edge按照$O$的值从小到大的删去的话
网络则会比按照从大到小大删去方法所瓦解的更快。
所以说，网络之中是有Community这种性质的，而衡量的标准自然就是是否连接的如设想之中的那么紧密，但是上述的$O$只能针对于Edges而言，而无法处理Group层面的信息。所以我们需要一个新的指标，而对于网络层面的话，这个指标就是Modularity，记作是$Q$，其应该要服从这样的性质
$$Q\propto\sum_{s\in S}[(\text{# of edges within Group} s)-(\text{Expected # of edges with group }s)]$$
也就是当在Group之内出现的Edges比期望所出现的Edges多的时候，我们就认为其连接的更紧密，而越多说明连接越紧密。这里的Expeced说的好听其实就是Random的结果。而Random的方法大家也非常熟悉，就是之前提过的Configuration Model，假设最后随机生成的模型之中总共有$m$条边，那么Modularity被定义为
\begin{aligned}Q(G,S)&=\frac1{2m}\sum_{s\in S}\sum_{i\in s}\sum_{j\in s}(A_{ij}-\frac{k_ik_j}{2m}) \\
&=\frac1{2m}\sum\limits_{ij}[A_{ij}-\frac{k_ik_j}{2m}]\delta(c_i,c_j)\end{aligned}
其中的$\delta(c_i,c_j)$是示性函数，如果$c_{i},c_{j}$同属于一个社区，那么就是1，反之是0，而其中的$A_{ij}$代表的是边的权重。我们看看他能不能够满足上面的所需求的性质。
当在Group之中的连接更紧密的时候，$A_{ij}$的值就会倾向于更大，那么Modularity也就更大。所以可以符合我们的函数的构造的条件。至于为什么不是其他的，这个就是数学家考虑的事情了，俺们还是只是会用就行。
有了度量标准自然就要拿一个算法来处理，而Louvain算法就是这样的一个算法。算法分两步，然后不停的迭代，感觉这个算法和决策树的算法非常的类似
- 对于已经识别出来的Community之内的节点进行交换，如果交换之后可以使得Modularity增加，那么对于交换进行保留，否则不执行
- 在上述收敛之中，将所有属于一个社区的节点汇聚成为一个Super Node，然后建造一个新的网络
- 再去第一步
那么初始化怎么初始化呢？初始化就是大家都是一个人是一个单独的社区,然后把$i$给丢到$j$里面去，计算$\Delta$,选择最大的那个，作为第一步。
但是这个算法虽然快，也实用，但是它只能够给每一个节点分配一个Community，但是在现实生活之中，一个人肯定不仅仅是属于一个Community，所以就需要对于其进行改进，而改进的方法叫做是BigCLAM算法。
其可以达成这样的效果，也就是为一个节点分配多个Community，看起来的确有点像GMM的感觉。而如果从Adjacency的角度上看，其更像是下面的这种形式
也就是在两个网络之间会有更多的连接。那么怎么生成呢？很直观也很简单的思路，就是和捏橡皮泥一样，只不过我们这里的橡皮泥叫做(Community Affiliation Graph Model , AGM)，通过对于AGM进行变化，捏成所需要的$G$。那么我们的橡皮泥的参数有什么呢？当然要有节点的数量$V$，还要有Community的数量$C$，还有节点属于的Community$M$，每一个Community都有它的专属的概率记作$p_c$，这个专属概率是用来判断Community内的节点是否相互连接，当这个越大的时候，整个Community就连接的越紧密。那么两个节点相互连接的概率就是$p(u,v) =1-\prod_{c\in M_{u}\cap M_{v}}(1-p_{c})$。
现在我们所要做的就是通过给定的网络结构获得其AGM模型，也就是给定了图$G$寻找模型$F$，即
$$P(G|F)=\prod\limits_{(\mu,\nu)\in G}P(\mu,\nu)\prod\limits_{(\mu,\nu)\notin G}(1-P(\mu,\nu))$$
换一种记号的话，使用向量$F_{\mu}$表示这个节点属于各个Community的概率，那么$u$和$v$所连接的概率就可以写成是
$$P(\mu,\nu)=1-\exp(-F_{\mu}F_{\nu}^T)$$
那么整个的目标的概率则是
$$l(F)=\sum\limits_{(\mu,\nu)\in E}\log(1-\exp(-F_{\mu}F_{\nu}^T))-\sum\limits_{(\mu,\nu)\notin E}F_{\mu}F_{\nu}^T$$
有了目标，我们就可以优化了，所以接下来就是选择一个优化算法对于上述大目标进行优化。对于$F_{\mu}$求梯度
$$\nabla l(F_{\mu})=\sum\limits_{\nu\in\mathcal{N}(\mu)}F_{\nu}\frac{\exp(-F_{\mu}F_{\nu}^T)}{1-\exp(-F_{\mu}F_{\nu}^T)}-\sum\limits_{\nu\notin\mathcal{N}(\mu)}F_{\nu}$$
然后使用梯度下降法就行了。
Spectral Clustering
除了上面的那种算法，我们也可以使用谱聚类的方法来做，所谓的谱就是通过矩阵分解SVD找特征值，这个特征值就是谱。和把大象放进冰箱里一样，我们这个算法也仅仅是需要三步就行了
- 第一步：预处理，构建一个关于图的表示的矩阵
- 第二步：分解矩阵，使用SVD把矩阵的谱找出来
- 第三步：聚类，根据上面的谱，把他们分进不同的类
相信在上一个BlogBasic Knowledge to Graph之中大家对于图的划分(Graph Partitioning)也有了一定的了解，所谓的划分就是将图分进两边之中，这个就像是LDA分类了，Linear Discriminate Analysis 不是那个Topic Model LDA,LDA的目标也是很简单，使得组内方差小，组间方差大。而在图的划分之中，我们也希望Community内的连接丰富而Community之间的连接系数。因此我们希望我们可以最大化Partitioning之内的连接而最小Partitioning之间的连接。
那么现在假设有一个特别的连通图(connected)$G$，其中的所有的节点的度都是$d$，那么我们称这个图是一个$d-Regular$的图。将其Adjacent Matrix记作是$A$而$x$则可以看成是每一个节点的Label的值
回顾一下线代，特征值指的是
$$A\cdot x = \lambda \cdot x$$
的$\lambda$，如果$x = (1,1,\cdots,1)$的时候$A\cdot x = (d,d,\cdots,d) = d \cdot x$(由于每一个度都是$d$所以等式成立，这个还是蛮简单的可以自己手推一下就理解了。)，那么$\lambda = d$.可以利用反证法证明$d$是最大的特征值，但是在这里我依旧不再赘述。
那么上述是一个连通图的情况，如果不是连通图呢？假设有两个图，而每一个部分都是$d-regular$的，可以得到下面的等式
\begin{cases}
x’=(1,…,1,0,…,0)^T, Ax’=(d,…,d,0,…,0)^T \\
x”=(0,…,0,1,…,1)^T, Ax”=(0,…,0,d,…,d)^T
\end{cases}
同样可以得到特征值为$d$，不过此时其对应了两个特征向量。
那么如果做一些改变，把两个图给用线段连接起来，但是连接的并不多，只是零星的，对于整个图的特征也不会有太大的改变。
这时候$\lambda_{n}$所对应的特征向量$x_{n}$已经知道了就是$(1,1,\cdots ,1)$，那么第二大的特征值$\lambda_{n-1}$的对应的特征向量是什么呢？我们虽然不大清楚，但是有一个性质是可以确认的，也就是他的各个维度的分量加起来就是0，那么就说明其中的元素是有正有负的，如果将正的元素归类为左边，负的元素归类为右边，也就一定程度上达成了将他们分开的目的。
可是除了Adjacent矩阵还有什么矩阵呢？还有一个特别牛逼的矩阵叫拉普拉斯矩阵Laplacian Matrix这个矩阵在自己之前的那篇论文笔记之中也出现过，性质非常的棒。其表达的形式是$L = D – A$，其中的$A$就是邻接矩阵而$D$则是度矩阵。
而对于对称矩阵$M$有一个蛮好的性质就是其第二大的特征值
$$\lambda_2=\min\limits_{x:x^Tw_1=0}\frac{x^TMx}{x^Tx}$$
可以通过上面的这个公式计算。由于$A$是对称矩阵，而$D$是对角矩阵，所以$L$是一个对称矩阵，把拉普拉斯矩阵带进去
\begin{aligned}
x^TLx&=\sum\limits_{i,j=1}^nL_{ij}x_ix_j=\sum\limits_{i,j=1}^n(D_{ij}-A_{ij})x_ix_j \\
&=\sum_iD_{ii}x_i^2-\sum_{(i,j)\in E}2x_ix_j \\
&=\sum_{(i,j)\in E}(x_i^2+x_j^2-2x_ix_j) \\
&=\sum_{(i,j)\in E}(x_i-x_j)^2
\end{aligned}
可以发现，这里的$\lambda_{2}$是特征向量之中的各个元素的“距离”的最小值，而这里的元素是什么？是其所属的标签的Label，也就是可以使得组内的连接尽量的小。而这里的得到的$x$称为是Fielder Vector，表示是进行分类进Field的向量。而如果是多分类的问题的话，就利用多次二分类叠加就完事了。
而上面的谱聚类的方式是基于Edge的，相信大家都觉得Motif这个概念非常的好，那么我们能不能把谱聚类的方式和Motifs结合一下呢？聪明的数学家总是可以给我们静息，确实是有一种方法叫做Motif-Based Spectral Clustering的，基于特定的结构进行划分。
为什么会使用Motif呢，在网络之中的节点之间的结合的形式不一定是通过两两链接所实现的，可能是通过某些奇怪的Pattern所实现的，而这种算法则为解决更加复杂的问题也提供了可能。
同样也是用拉普拉斯矩阵来做，不过这里的概念有一些不同，比如说Adjacent矩阵改成了该节点在几个Motif之中，以上图的节点2为例子，其在123，125，267这三个节点之中都表现出了Motif，所以其值是3.那么据此我们就可以构造出矩阵$W^{M}$
然后得到Degree Matrix，不过这里的Degree和之前的Degree的还是有一定的区别
$$D^{(M)} = \sum_{j} W_{ij}^{(M)}$$
然后$L = D – W$，再重复上述的谱聚类即可。还是蛮好理解的。
Comments
好了我们现在基本上掌握了如何去处理网络的一些应用的问题了，包括如何给网络之中的Role分类，如何把网络之中的Node分进不同的Community之中。其实我感觉在社会科学之中，把这些东西摸熟悉了基本上已经可以做很多开创新的工作了。不过自己写完其实也不敢说摸熟悉了，这里只是一个大概的介绍，对于自己也只是一个大概的提纲帮助自己了解这个学科。
Comments
Leave a Comment