CS224W: Machine Learning with Graphs
课件:http://web.stanford.edu/class/cs224w/
视频:https://www.bilibili.com/video/av837826756/
Introduction; Structure of Graphs
介绍图的基本概念,如有向图,无向图,二部图,邻接矩阵,强连接,弱连接等
Properties of Networks and Random Graph Models
介绍图的一些特性,如度的分布,直径,聚类系数,最大连通集等.
通过随机图指出社交网络聚类系数偏高,也即人群呈现社区属性,相反六度理论这些是很平凡的结论.
通过Kronecker点积生成随机的符合社交网络特性的图,类似于分形.
Motifs and Structural Roles in Networks
介绍subgraph,比如三个点的连通图就只有两种,这种特征可以用来定义点的周边结构特性.
引出了点的结构相似性,它和点的社区属性是互补的.
介绍一种识别结构结构相似性的经典方法
Community Structure in Networks
介绍点的社区属性
介绍了如何根据图判定社区的算法,注意社区可以使无交集的,也可以是多重交集包含得到.
Spectral Clustering
从直观上介绍谱聚类,是谋求最小的电导率.
为什么是laplace矩阵,因为全1向量是特征向量,他提供了一个很好地先验要求:所有点加起来为0.
考虑将点集划分为两类,自然的定义类别是-1,+1,要保证这两类数目差不多,因此就会需要这个先验.
如果图不连通,有几部分就会有几个相同的全零特征值.
如果图连通,找到的最小非0特征值(第二小特征值)对应的特征向量自然而然的就将点标记为两类.
对应的,第三小特征值也可以使用,最小特征值为全正,第二小是负正,第三小可能是负正负正,etc...
总之其余的特征值能更好的区分之前的未区分的相邻的类别.
因此常见的做法(之前是层次区分)是取m个特征值做kmeans即可,的确很符合直观.