問題與概念域：
{
重疊社區(qū)怖糊，非重疊社區(qū)，nested
nodes 屬于多個(gè) communities
如何生成 graph(network)伍伤？ 即有了nodes的set，如何定義edge扰魂？
有g(shù)raph如何生成能夠generate這個(gè)network的 model？
}
Community-Affiliation Graph: AGM
{
- community c
- probability p ( each community has a single p)
- memberships m
- nodes v
=>how to generate network姐直？
- 對(duì)每個(gè)在community A中的nodes對(duì)付翁，我們將兩者以probability Pa 連接。(只要nodes對(duì)有相同的community那么兩者就會(huì)以一定概率連接)
- 計(jì)算edge probability
}
BIGCLAM：
{
memberships have strength砰识，越大則代表越活躍佣渴，0則非member
community membership strength matrix F：
行為nodes辫狼，列為communities只有一個(gè)共同community辛润，計(jì)算同一個(gè)community中nodes對(duì)連接的概率：1-exp(-F(nodea)*F(nodeb))砂竖；share多個(gè)communities，計(jì)算則從反面考慮1-(1-p1)(1-p2)...(即計(jì)算至少有一個(gè)community將nodes對(duì)連接的概率)
給定一個(gè)network G(V,E) 如何找到F乎澄，使得network的極大似然最大(極大似然的計(jì)算公式：有邊的概率和無邊的概率連×)？即 l(F) = log P(G|F),給定F條件下G的極大似然函數(shù)求對(duì)數(shù)形式置济。1.計(jì)算gradient 2.梯度下降锋八，對(duì)每一行計(jì)算l對(duì)該行F的梯度护盈，以學(xué)習(xí)步長(zhǎng)更新該行F，迭代 3.如果該行F<0紊服，則令其為0
但是計(jì)算每行F的偏導(dǎo)是linear time脏款，非常慢。
對(duì)屬于node u的鄰節(jié)點(diǎn)撤师，和不屬于u的鄰節(jié)點(diǎn)的F都出現(xiàn)在公式中，每次計(jì)算偏導(dǎo)都需要對(duì)所有node n個(gè) 進(jìn)行遍歷剃盾。改進(jìn)：將所有node的F的和 cache痒谴，那么非鄰節(jié)點(diǎn)部分的計(jì)算則轉(zhuǎn)化為和減去鄰節(jié)點(diǎn)衰伯，這樣只需要遍歷u的鄰節(jié)點(diǎn)的F 即可計(jì)算偏導(dǎo)再進(jìn)行迭代积蔚，加速明顯。
數(shù)據(jù)：BIGCLAM 5min處理300k節(jié)點(diǎn)的nets怎顾，其他需要10days漱贱，能夠處理100M條邊的連接槐雾。
}
Detecting cluster：
{
Goal: given network, find densely linked clusters(output: set of nodes in same cluster)
應(yīng)用場(chǎng)景：
query - to - adveritser （許多廣告都屬于類似的幾個(gè)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內(nèi)部的連接數(shù)量
最小化cluster之間的鏈接數(shù)量
即為 關(guān)于edges的cut函數(shù)cut：(對(duì)于有權(quán)無權(quán)圖來說都可用逐抑，無權(quán)則設(shè)所有權(quán)都為1) 是set of edges with only one node in the cluster cut(S) = 所有一個(gè)節(jié)點(diǎn)屬于S另一個(gè)指向另一cluster的edge的weight和
=>最小cut？最優(yōu)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總數(shù)泞莉。
注意這里的degree會(huì)對(duì)edges重復(fù)計(jì)算，因?yàn)槭腔趎odes的degree鲫趁。 - min意味著利虫，選擇的cluster A的所有degree之和應(yīng)當(dāng)小于m/2，即總edges一半糠惫。否則如果A過大，那對(duì)這個(gè)比直接過影響太大硼讽。即相對(duì)于group自身的density來說group和其余network部分的連接。
這個(gè)比值越低壤躲，意味著cut越好。
- 為什么使用這個(gè)criteria您炉？
實(shí)踐證明能夠產(chǎn)生更多balanced partitions
但是計(jì)算最優(yōu)cut是np問題。
}
Spectral Graph Partitioning：
{
從鄰接矩陣來看棉胀，cluster會(huì)是什么樣子冀膝？一塊數(shù)字比較大，一塊幾乎是0窝剖。數(shù)字較大表明nodes之間關(guān)聯(lián)強(qiáng)，屬于同一個(gè)cluster赐纱。行列皆為nodes。
spectrum是鄰接矩陣特征值的集合诚隙。那么和graph有什么關(guān)系？(考慮最簡(jiǎn)單的情況久又，graph有兩個(gè)component巫延，每個(gè)component中每個(gè)node的degree都為d)
intuition：如果一個(gè)特征值有兩個(gè)特征向量炉峰，則這兩個(gè)子圖分離脉执；如果兩個(gè)特征值相近，則兩個(gè)字圖之間有連接但非常弱适瓦。鄰接矩陣重要性質(zhì)：對(duì)稱，特征值為實(shí)數(shù)且正交
Degree matrix：D= [dii] dii是node i的degree
Laplacian matrix： L = D - A否彩。
性質(zhì)：L *x =0 ；每行每列和為0 列荔；特征值為0對(duì)一個(gè)對(duì)稱矩陣M第二小的特征值公式：math證明略贴浙∈鸹校化簡(jiǎn)后問題轉(zhuǎn)為找到最小化 (xi - xj)^2之和的 x ，i盯质、j為一個(gè)cluster中的node。
將partition(A,B)表達(dá)為一個(gè)向量囱修，即屬于A時(shí)王悍，y為+1，屬于B為-1鲜漩。將 最小化 (xi - xj)^2之和 轉(zhuǎn)為找x使得 (yi-yj)^2之和 最小孕似。yi只能在-1，+1中取值鳞青。=>不能準(zhǔn)確解決臂拓，將y松弛习寸。恰好即為第二小的特征值。
Rayleigh Theorem
總結(jié)：最優(yōu)化cut的問題霞溪，即時(shí)最小化第二小特征值的問題鸯匹，即時(shí)尋找參數(shù) x的問題殴蓬，而x又是第二小特征值的特征向量痘绎。x被稱作Fiedler vector最后孤页，根據(jù)L計(jì)算出的第二小特征值及特征向量進(jìn)行分組行施，如何cluster悲龟？即如何選擇splitting point的問題须教。排序乐疆，split at 0挤土，分成正負(fù)兩類仰美。
有降維的意思咖杂。x就能夠涵蓋cluster的信息即graph中所有nodes的信息诉字，比L小得多壤圃。
多個(gè)cluster 如何琅轧？
k-way spectral clustering:
- 迭代bi-partitioning
- 使用多個(gè)特征向量，構(gòu)成一個(gè)矩陣鹰晨，使用一種聚類方式(kmeans等)進(jìn)行對(duì)這個(gè)特征向量構(gòu)成的矩陣聚類(每個(gè)node被特征向量中對(duì)應(yīng)的值表示 i：（x1i, x2i ,x3i...）x1,x2...為特征向量)（實(shí)踐效果很好）
}
Trawling：
{
找到graph中的小的community墨叛？
定義task：
given：left 有 s個(gè)nodes漠趁，每個(gè)links all nodes on the right (fully connected)闺兢；right 有 t個(gè)nodes绞幌。identify all the 完全二部子圖(complete bipartite subgraphs)frequent itemsets：
找到所有subsets T of at least f times bought together by users。這個(gè)問題和完全二部子圖的關(guān)聯(lián)士复？=> frequent itemsets = complete bipartite subgraphs可以把一個(gè)graph轉(zhuǎn)成itemsets，graph中出邊指向的node即為set中的items菠镇，起始點(diǎn)即可視為為user的basket利耍。完全二部子圖是整個(gè)graph的一部分盔粹，可用頻繁物品集表示出嘹。
}
