1、图划分
Min-cut
图G=(V,E)，V为节点集合，E为边集，寻找一个划分，使得划分的各个分量之间的连边权重之和最小。
Min Cut的问题
-
平凡解
所有节点划分到同一个分量中
解决办法：指定K
-
不均衡解
划分的各个分量，大小差异大
解决办法：限制分量大小
Min Cut的扩展：Ratio-cut， Normalized-cut
图划分求解算法
-
局部方法：KL算法
目标：寻找图的最优两路划分
第一步：构造初始划分C=C1+C2
第二步：从C1中选择一个节点a，从C2中选择一个节点b，交换a和b可以使cutC减小，则交换
重复第二步直至cutC不再减小
-
全局方法：谱划分
谱聚类的基本思想便是利用样本数据之间的相似矩阵（拉普拉斯矩阵）进行特征分解（ 通过Laplacian Eigenmap 的降维方式降维），然后将得到的特征向量进行 K-means聚类。
2、社区发现
识别出网络中“内部连接紧密、与外部连接稀疏”的节点组。
和图划分的区别
-
图划分
按照任务需求对网络进行划分
划分的分量数通常已知
各个分量彼此不重叠
-
社区发现
寻找网络固有的结构规则
社区个数通常未知
社区可以重叠、嵌套
GN算法：基于边介数的算法 详细
步骤1：计算每条边的介数
步骤2：删除介数最大的边
模块度
回答的问题：什么样的网络划分是一个好划分？
直观认识：内部连边多、外部连边少
模块度的性质：
取值范围：-1和1之间值越大，划分质量越好
可加性：社区上的定义和节点上的定义一致
社区发现问题变成了模块度优化问题
给定一个网络，寻找该模块度最大的划分
这是一个NP-hard问题，可使用多中优化算法
- 模块度优化算法示例-局部优化
初始化：每个节点属于一个社区
步骤1，对于每个节点，判定加入其邻居节点所属的社区是否可以增加模块度，如果能够增加，加入使模块度增加最大的社区，直到所有节点所属的社区都不再变动为止
步骤2，将每个社区视为一个节点， 构造新网络
重复上述步骤至模块度不再增加
InfoMap
两级哈夫曼编码
3、图建模
非负矩阵分解
随机块模型
