问题与概念域：
{
重叠社区，非重叠社区，nested
nodes 属于多个 communities
如何生成 graph(network)？ 即有了nodes的set，如何定义edge？
有graph如何生成能够generate这个network的 model？
}
Community-Affiliation Graph: AGM
{
- community c
- probability p ( each community has a single p)
- memberships m
- nodes v
=>how to generate network？
- 对每个在community A中的nodes对，我们将两者以probability Pa 连接。(只要nodes对有相同的community那么两者就会以一定概率连接)
- 计算edge probability
}
BIGCLAM：
{
memberships have strength，越大则代表越活跃，0则非member
community membership strength matrix F：
行为nodes，列为communities只有一个共同community，计算同一个community中nodes对连接的概率：1-exp(-F(nodea)*F(nodeb))；share多个communities，计算则从反面考虑1-(1-p1)(1-p2)...(即计算至少有一个community将nodes对连接的概率)
给定一个network G(V,E) 如何找到F，使得network的极大似然最大(极大似然的计算公式：有边的概率和无边的概率连×)？即 l(F) = log P(G|F),给定F条件下G的极大似然函数求对数形式。1.计算gradient 2.梯度下降，对每一行计算l对该行F的梯度，以学习步长更新该行F，迭代 3.如果该行F<0，则令其为0
但是计算每行F的偏导是linear time，非常慢。
对属于node u的邻节点，和不属于u的邻节点的F都出现在公式中，每次计算偏导都需要对所有node n个 进行遍历。改进：将所有node的F的和 cache，那么非邻节点部分的计算则转化为和减去邻节点，这样只需要遍历u的邻节点的F 即可计算偏导再进行迭代，加速明显。
数据：BIGCLAM 5min处理300k节点的nets，其他需要10days，能够处理100M条边的连接。
}
Detecting cluster：
{
Goal: given network, find densely linked clusters(output: set of nodes in same cluster)
应用场景：
query - to - adveritser （许多广告都属于类似的几个query）
actor - to -movie （subset of actors belong to a subset of movies）
social circles，circles of trust （找到set of my family ，set of my classmates等等network的子集）how to define a good cluster？
最大化cluster内部的连接数量
最小化cluster之间的链接数量
即为 关于edges的cut函数cut：(对于有权无权图来说都可用，无权则设所有权都为1) 是set of edges with only one node in the cluster cut(S) = 所有一个节点属于S另一个指向另一cluster的edge的weight和
=>最小cut？最优cut？引入Conductance--Graph Partitioning Criteria：
- 给定set A ，Conductance = cut(A) / min(vol(A) , 2m-vol(A))，其中
vol(A) = di的和 (i是A的node，di : degree of node i)，m是graph的edges总数。
注意这里的degree会对edges重复计算，因为是基于nodes的degree。 - min意味着，选择的cluster A的所有degree之和应当小于m/2，即总edges一半。否则如果A过大，那对这个比直接过影响太大。即相对于group自身的density来说group和其余network部分的连接。
这个比值越低，意味着cut越好。
- 为什么使用这个criteria？
实践证明能够产生更多balanced partitions
但是计算最优cut是np问题。
}
Spectral Graph Partitioning：
{
从邻接矩阵来看，cluster会是什么样子？一块数字比较大，一块几乎是0。数字较大表明nodes之间关联强，属于同一个cluster。行列皆为nodes。
spectrum是邻接矩阵特征值的集合。那么和graph有什么关系？(考虑最简单的情况，graph有两个component，每个component中每个node的degree都为d)
intuition：如果一个特征值有两个特征向量，则这两个子图分离；如果两个特征值相近，则两个字图之间有连接但非常弱。邻接矩阵重要性质：对称，特征值为实数且正交
Degree matrix：D= [dii] dii是node i的degree
Laplacian matrix： L = D - A。
性质：L *x =0 ；每行每列和为0 ；特征值为0对一个对称矩阵M第二小的特征值公式：math证明略。化简后问题转为找到最小化 (xi - xj)^2之和的 x ，i、j为一个cluster中的node。
将partition(A,B)表达为一个向量，即属于A时，y为+1，属于B为-1。将 最小化 (xi - xj)^2之和 转为找x使得 (yi-yj)^2之和 最小。yi只能在-1，+1中取值。=>不能准确解决，将y松弛。恰好即为第二小的特征值。
Rayleigh Theorem
总结：最优化cut的问题，即时最小化第二小特征值的问题，即时寻找参数 x的问题，而x又是第二小特征值的特征向量。x被称作Fiedler vector最后，根据L计算出的第二小特征值及特征向量进行分组，如何cluster？即如何选择splitting point的问题。排序，split at 0，分成正负两类。
有降维的意思。x就能够涵盖cluster的信息即graph中所有nodes的信息，比L小得多。
多个cluster 如何？
k-way spectral clustering:
- 迭代bi-partitioning
- 使用多个特征向量，构成一个矩阵，使用一种聚类方式(kmeans等)进行对这个特征向量构成的矩阵聚类(每个node被特征向量中对应的值表示 i：（x1i, x2i ,x3i...）x1,x2...为特征向量)（实践效果很好）
}
Trawling：
{
找到graph中的小的community？
定义task：
given：left 有 s个nodes，每个links all nodes on the right (fully connected)；right 有 t个nodes。identify all the 完全二部子图(complete bipartite subgraphs)frequent itemsets：
找到所有subsets T of at least f times bought together by users。这个问题和完全二部子图的关联？=> frequent itemsets = complete bipartite subgraphs可以把一个graph转成itemsets，graph中出边指向的node即为set中的items，起始点即可视为为user的basket。完全二部子图是整个graph的一部分，可用频繁物品集表示。
}
